Compilers: Principles and Practice

4.1 Top-down and Bottom-up Parsing

Parsing of a given sentence can be done in one of the two ways shown in Fig. 4.1:

 

 

Fig. 4.1 Top-down and Bottom-up parsing

 

Top-down: Starting with the start symbol of the grammar, we apply various productions to ultimately obtain the required sentence.

Bottom-up: Starting with a handle in the given sentence, we construct a forest of trees by applying the reductions (i.e. productions in reverse) which will ultimately merge into one parse tree.

Consider a grammar:

G = <{I,D,L}, {a−z, 0−9}, I, P>, with productions
P = { I –> L | IL | ID
      L –> a | b | … | z
      D –> 0 | 1 | … | 9
    }

and a sentence x2 to be parsed. ...