Context-free grammar

Consider a conditional statement
If S1 and S2 are statements and E is an expression, then
                                             “if E then S1 else S2”
We know that, regular expression can specify the lexical structure of tokens. Using some syntactic variable, stmt, we can specify grammar production
                                       Stmt _if expr then stmt else stmt
A context-free grammar consists of terminals, nonterminals, start symbol and set of productions.

1. Terminals are the basic symbols from which strings are formed. The term "token name" is a synonym for "terminal" and frequently we will use the word "token" for terminal when it is clear that we are talking about just the token name. We assume that the terminals are the first components of the tokens output by the lexical analyzer. The terminals are the keywords if and else and the symbols "(" and " ) ."
2. Nonterminals are syntactic variables that denote sets of strings. stmt and expr are nonterminals. The sets of strings denoted by nonterminals help define the language generated by the grammar. Nonterminals impose a hierarchical structure on the language that is key to syntax analysis and translation.
3. In a grammar, one nonterminal is distinguished as the start symbol, and the set of strings it denotes is the language generated by the grammar. Conventionally, the productions for the start symbol are listed first.
4. The productions of a grammar specify the manner in which the terminals and nonterminals can be combined to form strings. Each production consists of:
(a) A nonterminal called the head or left side of the production; this production defines some of the strings denoted by the head.
(b) The symbol : = has been used in place of ->

(c) A body or right side consisting of zero or more terminals and nonterminals. The components of the body describe one way in which strings of the nonterminal at the head can be constructed.

Consider the grammar for simple arithmetic expressions as follows:




0 comments