Back to Predictive Parsing, Continued. On to Shift-Reduce Parsing.
Held Wednesday, February 21, 2001
Summary
Today we consider how to build and use predictive parsing tables.
Notes
Overview
First
table and first
function
Nullable
table and nullable
function
Follow
table
TokenSet first(s1 ... sn) { if (isToken(s1)) { return new TokenSet(s1); } else { tmp = First(s1); if (Nullable(s1)) { return TokenSet.union(tmp, first(s2 ... sn)) } // 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(s1 ... sn) { // The empty string can derive the empty string if (n == 0) { return true; } // 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(s2..sn); } } // 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
Follow
table is a little
bit more subtle.
Follow
table? We know that M can be followed by anything that can begin
a string derivable from beta.
for each nonterminal, N Follow(N) = {}; for each production P for each form of P, N ::= alpha M beta Follow(M) = Follow(M) union first(beta) end for end for repeat for each production P for each form of P, N :: = alpha M beta if nullable(beta) Follow(M) = Follow(M) union Follow(N) end if end for end for until no changes are made end for
Monday, 22 January 2001
Wednesday, 21 February 2001
Back to Predictive Parsing, Continued. On to Shift-Reduce Parsing.
[Current]
[Discussions]
[Glance]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Primary
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Quizzes]
[Readings]
[Reference]
Sets
[Blackboard]
[98F]
Links
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:54 2001.
This page may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2001S/outline.14.html
.
You may validate
this page's HTML.
The source was last modified Wed Feb 21 10:45:08 2001.