# Class 13: Predictive Parsing, Continued

Back to Predictive Parsing. On to Predictive Parsing, Continued.

Held Monday, February 19, 2001

Summary

Today we continue our exploration of predictive parsing by looking at steps for automating the construction of predictive parsers..

Notes

• The college has released a draft mission statement. I strongly encourage you to read it and comment on it.
• This Thursday, Pete Broadwell, Elizabeth Hulse, Chris Kern, and Erin Nichols are speaking on their summer research which we informally refer to as "Ha ha, I can modify your Web page". I hope you'll attend.
• Don't forget to turn in your writeup of lab 3.
• Quiz! (As promised.)

Overview

• Helpful tables: First, Follow, and Nullable
• Build the `First` table.

## Analyzing the Grammar

• As you can tell, we need to make a number of decisions when we convert a grammar into a predictive parser.
• Given multiple right-hand sides that start with a nonterminal, which one do you choose?
• If a nonterminal derives epsilon, how do you decide to apply that derivation?
• What if a nonterminal derives a nonterminal that derives epsilon? Consider what to do when you see a `b` when matching an `S` in
```S :: = X b
X ::= x X
|  epsilon
```
• All of these analyses are aided by three tables (and corresponding functions) known as First (and first), Follow, and Nullable (and nullable).
• The tables and functions are recursively constructed. That is, the functions may be defined in terms of the tables and the tables may be defined in terms of the current versions of the functions.
• First maps nonterminals to sets of tokens that can begin strings derived from those nonterminals.
• first maps sequences of nonterminals and terminals to the symbols that can begin strings derived from those sequences
• Follow maps nonterminals to sets of tokens that can follow those nonterminals in sequences derivable in the grammar
• Nullable indicates which nonterminals can derive the empty string
• nullable operates on sequences of symbols (nonterminals and terminals), returning true only when the sequence can derive epsilon

## History

Monday, 22 January 2001

• Created as a blank outline.

Monday, 19 February 2001

Wednesday, 21 February 2001

• Removed uncovered material. (Moved to the next outline.)

Back to Predictive Parsing. On to Predictive Parsing, Continued.

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

This page was generated by Siteweaver on Mon Apr 30 10:51:53 2001.
This page may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2001S/outline.13.html`.