Parsing - Introduction to Compiler Construction in a Java World - page 64

E ::= E + T
E ::= T
T ::= T * F
T ::= F
F ::= ( E )
F ::= id

(3.9)

We may surmise that the symbols (here E, T, and F) that are defined by at least one
production rule are non-terminals. Conventionally, the first defined non-terminal (that is,
E here) is our start symbol. Those symbols that are not defined (here + , * , ( , ) , and id )
are terminals.
The start symbol is important to us because it is from this symbol, using the production
rules, that can generate strings in a language. For example, because we designate E to be
the start symbol in the grammar above, we can record a sequence of applications of the
production rules, starting from E to the sentence id+id*id as follows:

E ) E + T
) T + T
) F + T
) id + T
) id + T * F
) id + F * F
) id+id* F
) id+id*id

We call this a derivation. When a string of symbols derives another string of symbols
in one step, that is, by a single application of a production rule, we say that first string
directly derives the second string. For example,

E directly derives E + T
E + T directly derives T + T
T + T directly derives F + T
and so on :::

When one string can be rewritten as another string, using zero or more production rules
from the grammar, we say the first string derives the second string. For this derives relation,
we usually use the symbol ). For example,

E ) E (in zero steps)
E ) id+ F * F
T + T ) id+id*id

We say the language L(G) that is described by a grammar G consists of all the strings
(sentences) comprised of only terminal symbols that can be derived from the start symbol.
A little more formally, we can express the language L(G) for a grammar G with start symbol
S and terminals T as

L(G) = fw j S ) w

and w 2 T*g.

(3.10)

For example, in our grammar above,

) id+id*id

E

) id

E

) (id+id)*id

E