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:


Top-down and Bottom-up parsing


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. ...

Get Compilers: Principles and Practice now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.