Top-down parsing

The construction of the parse tree relies on the following principles.

(1)

Create a tree reduced to the start-symbol of the grammar. The current token being scanned is called the lookahead symbol. Initially, the lookahead symbol is the leftmost token of the input string.

(2)

Repeat

(2.1)

If the leftmost leaf L of the current tree is labeled by a nonterminal A then

(2.1.1)

select an A-production A $\longmapsto$ $\alpha$ and

(2.1.2)

create a parse tree for A $\longmapsto$ $\alpha$ rooted at L.

(2.1.3)

Advance to the leftmost leaf in the tree.

(2.2)

Otherwise if the terminal at node L matches the lookahead symbol then

(2.2.1)

Advance to the next leftmost leaf in the tree.

(2.2.2)

Advance the lookahead symbol in the input string to the next token.

(2.3)

Otherwise

(2.3.1)

Back-track in the tree to the last nonterminal A for which several A-productions could be chosen.

(2.3.2)

Choose another A-production and peforms steps (2.1.2) and (2.1.3).

(2.3.3)

Adjust the lookahead symbol accordingly.

(3)

Until the input string is read completely or the back-tracking process fails.

Example 14   Consider the following grammar G (with terminals a, b, c, d and nonterminals S, A)

S	$\longmapsto$	cAd
A	$\longmapsto$	ab  | a

and the input string w = cad. Figures 6 and 7 show the building of a parse tree for w w.r.t. G.

Figure 6: Sketch of the top-down parsing of w = cad before conflict.

Figure 7: Sketch of the top-down parsing of w = cad: conflct, back-track and termination.

Remark 6   A left-recursive grammar can cause an infinite loop: when we try to expand the nonterminal A we may be led to expand A without having consumed any input. Fortunetely, any left-recursive grammar G can be replaced by a grammar without left-recursion and generating the same language as G.

However avoiding backtraking requires more advanced techniques to be described in the next section.