Class 18: Predictive Parsing (4)

Held: Monday, 1 March 2004

Summary: Today we conclude our primary discussion of predictive parsing.

Related Pages:

• EBoard.

Overview:

• The Follow table.
• The Parse table.
• Problems with predictive parsing: Left factoring; Eliminating left recursion.
• Problems with predictive parsing, revisited.

• The Follow table is our final table for the predictive parser.
• For every nonterminal, n, Follow[n] is the set of terminals that can follow n in a derived string.
• Optimally: In a string derived from the start symbol.
• Practically: In a string derived from some symbol.
• The Follow table is used to tell us when we can apply a rule in which the rhs is nullable.
• Why do we care?
• Sometimes it helps us catch errors earlier. (That is, you shouldn't nullify something when you know it will eventually lead to a dead end.)
• More often, it helps us catch problems in the grammar. (Example in class.)

Building the Follow Table

• The easy part: Whenever a terminal, T, follows a nonterminal, n, in a right-hand side, add T to Follow[n].
• The moderate part: Whenever a nonterminal, m, follows a nonterminal, n, in a right-hand side, add First[m] to Follow[n].
• The hard part: What do you do when a nonterminal, m, follows a nonterminal, n and m is nullable?

Building the Predictive Parsing Table

• Recall that the predictive parsing table tells you, for every nonterminal/terminal pair, what rule to apply next.

  for each production, pi of the form n ::= rhs
    for each terminal, T, in first(rhs)
      set Parse[n,T] to pi
    if nullable(rhs)
      for each terminal, T, in Follow[n]
        set Parse[n,T] to pi
  If you ever set an already-set position
     report an error
  

Some Grammars that Cause Problems

• As you may have noted in your own work (or your analysis of the code above), some grammars seem to be unamenable to predictive parsing.
• In particular, grammars in which two RHS's can begin with the same token cannot be predictively parsed.
• It also turns out that left recursive grammars (grammars in which a nonterminal can derive a sequence that starts with that nonterminal) also cannot be predictively parsed.
• The first problem can usually be solved by left factoring the grammar:
• Identify the common initial sequence.
• Rewrite the grammar so that there is only one rule for the nonterminal that uses that common initial sequence which is then followed by a new nonterminal.
• That new nonterminal then represents all possible remainders.
• The second problem can be fixed by making the grammar right recursive.

Predictive Problems, Revisited

• Many grammars are not amenable to predictive parsing.
• Some are for languages not amenable to predictive parsing.
• Some must be mangled to permit predictive parsing.
• Neither situation is useful.
• With careful programming, we can handle use grammars to generate unmangled parse trees.
• With more lookahead, we can often do better (at keeping the original grammar and at accepting a greater range of languages).
• However, it is also instructive to look for other techniques, which we will start to do after a slight detour.