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

so, L(G) includes each of
id+id*id
id
(id+id)*id
and infinitely more finite sentences.
We are interested in languages, those strings of terminals that can be derived from a
grammar's start symbol. There are two kinds of derivation that will be important to us when
we go about parsing these languages: left-most derivations and right-most derivations.
A left-most derivation is a derivation in which at each step, the next string is derived by
applying a production rule for rewriting the left-most non-terminal. For example, we have
already seen a left-most derivation of id+id*id :
E ) E + T
) T + T
) F + T
) id + T
) id + T * F
) id + F * F
) id+id* F
) id+id*id
Here we have underlined the left-most non-terminal in each string of symbols in the deriva-
tion to show that it is indeed a left-most derivation.
A right-most derivation is a derivation in which at each step, the next string is derived
by applying a production rule for rewriting the right-most non-terminal. For example, the
right-most derivation of id+id*id would go as follows:
E ) E + T
) E + T * F
) E + T *id
) E + F *id
) E +id*id
) T +id*id
) F +id*id
) id+id*id
We use the term sentential form to refer to any string of (terminal and non-terminal)
symbols that can be derived from the start symbol. So, for example in the previous deriva-
tion,
E
E + T
E + T * F
E + T *id
E + F *id
E +id*id
T +id*id
F +id*id
id+id*id