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