[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
Misc:
[2001S]
[2002F]
[SamR]
Back to Predictive Parsing (1). On to Predictive Parsing (3).
Held: Wednesday, 25 February 2004
Summary: Today we continue our exploration of predictive parsing by looking at steps for automating the construction of predictive parsers.
Related Pages:
Notes:
Overview:
First
table.Nullable
table.Follow
table.b
when matching
an S
in
S ::= X b S ::= c X ::= x X | epsilon
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
for each nonterminal N, First(N) = emptySet(); repeat for each production N ::= RHS First(N) = union(First(N), first(RHS)) end for until no changes are made
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
foreach nonterminal N, Nullable(N) = false repeat for each production N := RHS if nullable(RHS) { Nullable[N] = true; } end for until no changes are made
Back to Predictive Parsing (1). On to Predictive Parsing (3).
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
Misc:
[2001S]
[2002F]
[SamR]
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:03 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.16.html
.
You may wish to
validate this document's HTML
;
;
Check with Bobby