__PARSE TREES.__ Let
*G* = (*V*_{T}, *V*_{N}, *S*, *P*) be a context-free grammar.
A parse tree for *G* is a tree constructed as follows:

- its root is labelled by the start-symbol
*S*of*G*, - each internal node is labeled by a non-terminal,
- the leaves are labeled by terminals or , the empty-word symbol,
- if an internal node is labeled by a non-terminal
*A*and its children from left to right are labeled by grammar symbols*X*_{1},...,*X*_{n}then*A**X*_{1}^{ ... }*X*_{n}(16)

is a production of*G*. Moreover if*n*= 1 we can have*X*_{1}= .

Let *w* be a word of the language generated by *G*.
Clearly there exists at least one parse tree for *G*
whose yield is *w*.
Such a tree is called a parse tree for *w* w.r.t. *G*.

__LEFTMOST/RIGHTMOST DERIVATIONS.__ Let
*G* = (*V*_{T}, *V*_{N}, *S*, *P*) be a context-free grammar.
The derivation
(,,...,)
is __LEFTMOST__ if for each
(with
*i* = 1^{ ... }*n* - 1) the leftmost non-terminal
is rewritten.
Analogously we define rightmost derivations.

*However, to any parse tree we can associate a unique
leftmost (or a unique rightmost) derivation.
Top-down parsing attempts to find a leftmost
derivation for the input.
In bottom-up parsing, we construct a rightmost
derivation (in reverse order).
*

2004-12-02