Class 18: Predictive Parsing (4)

Back to Predictive Parsing (3). On to A Sample Parser.

Held: Monday, 1 March 2004

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

Related Pages:

Overview:

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

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

Back to Predictive Parsing (3). On to A Sample Parser.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Wed May 5 11:47:04 2004.
The source to the document was last modified on Tue Jan 20 23:06:45 2004.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2004S/Outlines/outline.18.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu