Class 13: 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