Writing a grammar

by 
<program> ::= <declaration_list> <statement_list>

<declaration_list> ::= <declaration> | <declaration> <declaration_list>

<declaration> ::= <type> <identifier>;

<type> ::= int | float | char

<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>

<letter> ::= a | b | ... | z | A | B | ... | Z

<digit> ::= 0 | 1 | 2 | ... | 9

<statement_list> ::= <statement> | <statement> <statement_list>

<statement> ::= <assignment_statement> | <expression>;

<assignment_statement> ::= <identifier> = <expression>;

<expression> ::= <term> | <term> + <expression> | <term> - <expression>

<term> ::= <factor> | <factor> * <term>

<factor> ::= <identifier> | <constant> | (<expression>)

<constant> ::= <digit> | <digit> <constant>

In this CFG:

  • <program> represents the entire program.
  • <declaration_list> represents a list of variable declarations.
  • <declaration> represents a single variable declaration.
  • <type> represents the data type (int, float, char).
  • <identifier> represents a variable name.
  • <letter> represents a letter in the alphabet (uppercase or lowercase).
  • <digit> represents a digit (0-9).
  • <statement_list> represents a list of statements.
  • <statement> represents a single statement, which can be either an assignment statement or an expression.
  • <assignment_statement> represents an assignment statement.
  • <expression> represents an arithmetic expression.
  • <term> represents a term in an expression.
  • <factor> represents a factor in an expression, which can be a variable, constant, or another expression.
  • <constant> represents a constant, which is a sequence of digits.

Let’s consider an example program that declares two variables, assigns values to them, and performs a simple arithmetic calculation:

int main;
float result;

main = 10;
result = (main + 5) * 2;

Now, let’s see how this program corresponds to the CFG:

  1. <program>:
    • <declaration_list>:
      • <declaration>: int main;
      • <declaration>: float result;
    • <statement_list>:
      • <statement>:
        • <assignment_statement>: main = 10;
      • <statement>:
        • <assignment_statement>: result = (main + 5) * 2;

This is a simple example to illustrate how the program structure can be represented using the CFG rules. The actual derivation would involve using these rules to derive the input program, step by step, until the terminal symbols are reached.

“Writing a grammar“

Leave a Comment