# Class 17: Predictive Parsing (3)

Back to Predictive Parsing (2). On to Predictive Parsing (4).

Held: Friday, 27 February 2004

Summary: Today we continue our exploration of predictive parsing by looking at the construction of the primary tables and functions.

Related Pages:

Overview:

• Building the tables and functions
• Using the tables

## Predictive Parsing Tables, Revisited

• Predictive parsing is aided by three tables (and corresponding functions) known as First (and first), Follow, and Nullable (and nullable).
• The tables and functions are mutually 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
• There is no follow function as it is neither interesting nor useful.
• 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

## Building the First table and first function

• How do we define the first function?
• We know that if a sequence begins with a token, then it can only derive strings that begin with that token.
• But what if the sequence begins with a nonterminal?
• Then the sequence can derive strings that begin with any token that begins strings that the nonterminal can derive.
• What what if the nonterminal can derive the empty string?
• Then we need to look further in the original sequence.
• Putting it all together
```TokenSet first(SymbolList string) {
Symbol s1 = string.car();
if (isToken(s1)) {
return new TokenSet(s1);
}
else {
tmp = First[s1];
if (Nullable[s1]) {
return new Union(tmp,
first(string.cdr()));
} // if s1 is nullable
} // if s1 is a nonterminal
} // first
```
• Note that this relies on the First table and the Nullable table.
• How do we build the First table? Using the first function.
```  for each nonterminal N, First(N) = emptySet();
repeat
for each production N ::= RHS
First(N) = union(First(N), first(RHS))
end for
```
• How do we know this terminates?

## Building the Nullable table and the nullable function

• The nullable function is relatively easy to define
```boolean nullable(SymbolList string) {
// The empty string can derive the empty string
if (String.isEpsilon()) {
return true;
}
Symbol s1 = string.car()
// If we begin with a token, we're not nullable
if (isToken(s1)) {
return false;
}
// Otherwise, we begin with a nonterminal.  That nonterminal must
// be nullable, as must the rest of the sequence.
else {
return Nullable[s1] &&
nullable(string.cdr());
}
} // nullable
```
• And, once again, we can define the Nullable table in terms of the nullable function.
```  foreach nonterminal N, Nullable(N) = false
repeat
for each production N := RHS
if nullable(RHS) {
Nullable[N] = true;
}
end for
```
• Why are we sure this loop terminates?

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

Back to Predictive Parsing (2). On to Predictive Parsing (4).

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.17.html`.

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

Samuel A. Rebelsky, rebelsky@grinnell.edu