LL Parser - Constructing An LL(1) Parsing Table

Constructing An LL(1) Parsing Table

In order to fill the parsing table, we have to establish what grammar rule the parser should choose if it sees a nonterminal A on the top of its stack and a symbol a on its input stream. It is easy to see that such a rule should be of the form A → w and that the language corresponding to w should have at least one string starting with a. For this purpose we define the First-set of w, written here as Fi(w), as the set of terminals that can be found at the start of some string in w, plus ε if the empty string also belongs to w. Given a grammar with the rules A₁ → w₁, ..., A_n → w_n, we can compute the Fi(w_i) and Fi(A_i) for every rule as follows:

1. initialize every Fi(w_i) and Fi(A_i) with the empty set
2. add Fi(w_i) to Fi(A_i) for every rule A_i → w_i, where Fi is defined as follows:
   • Fi(a w' ) = { a } for every terminal a
   • Fi(A w' ) = Fi(A) for every nonterminal A with ε not in Fi(A)
   • Fi(A w' ) = Fi(A) \ { ε } ∪ Fi(w' ) for every nonterminal A with ε in Fi(A)
   • Fi(ε) = { ε }
3. add Fi(w_i) to Fi(A_i) for every rule A_i → w_i
4. do steps 2 and 3 until all Fi sets stay the same.

Unfortunately, the First-sets are not sufficient to compute the parsing table. This is because a right-hand side w of a rule might ultimately be rewritten to the empty string. So the parser should also use the rule A → w if ε is in Fi(w) and it sees on the input stream a symbol that could follow A. Therefore we also need the Follow-set of A, written as Fo(A) here, which is defined as the set of terminals a such that there is a string of symbols αAaβ that can be derived from the start symbol.

Computing the Follow-sets for the nonterminals in a grammar can be done as follows:

1. initialize every Fo(A_i) with the empty set
2. if there is a rule of the form A_j → wA_iw', then
   • if the terminal a is in Fi(w' ), then add a to Fo(A_i)
   • if ε is in Fi(w' ), then add Fo(A_j) to Fo(A_i)
3. repeat step 2 until all Fo sets stay the same.

Now we can define exactly which rules will be contained where in the parsing table. If T denotes the entry in the table for nonterminal A and terminal a, then

T contains the rule A → w if and only if

a is in Fi(w) or

ε is in Fi(w) and a is in Fo(A).

If the table contains at most one rule in every one of its cells, then the parser will always know which rule it has to use and can therefore parse strings without backtracking. It is in precisely this case that the grammar is called an LL(1) grammar.