Primary:
[Skip To Body]
[Front Door]
[Current]
[Glance]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Sets:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Miscellaneous:
[2001S]
[98F]
[SamR]
[Glimmer Labs]
Back to Even More Predictive Parsing. On to Shift-Reduce Parsing.
Held Wednesday, October 2, 2002
Summary
Today we conclude our discussion of predictive parsing.
Notes
If you move it, it will collapse.)
anbn or ancn
S -> B S -> C B -> a B b B -> epsilon C -> a C c C -> epsilon
Overview
improvedexpression grammar
Exp ::= Term AddStuff AddStuff ::= addop Term AddStuff AddStuff ::= epsilon Term ::= Factor MulStuff MulStuff ::= mulop Factor MulStuff MulStuff ::= epsilon Factor ::= number Factor ::= id Factor ::= open-paren Exp close-paren
Nonterminal | First | Follow | Nullable |
---|---|---|---|
Exp | number, id, open-paren | end-of-string, close-paren | false |
AddStuff | addop | end-of-string, close-paren | true |
Term | number, id, open-paren | end-of-string, close-paren, addop | false |
MulStuff | mulop | end-of-string, close-paren, addop | true |
Factor | number, id, open-paren | end-of-string, close-paren, addop, mulop | false |
stack.push(end-of-string) stack.push(Exp) while (input.peek() != end-of-string) { if stack.top() is a token if stack.top == input.peek() then stack.pop(); input.consume(); else crash and burn end if // stack.top == peek() else // stack.top is a nonterminal N := stack.top; t := input.peek(); switch (N,t) // Exp ::= Term AddStuff case (Exp,number): case (Exp,id): case (Exp,open-paren): stack.push(AddStuff) stack.push(Term) break; // AddStuff ::= addop Term AddStuff case (AddStuff, addop): stack.push(AddStuff); stack.push(Term); stack.push(addop); break; // AddStuff ::= epsilon case (AddStuff,end-of-string): case (AddStuff,close-paren): break; // Term ::= Factor MulStuff case (Term,number): case (Term,id): case (Term,open-paren): stack.push(MulStuff); stack.push(Factor); break; // MulStuff ::= mulop Factor MulStuff case (MulStuff,mulop): stack.push(MulStuff); stack.push(Factor); stack.push(mulop); break; // MulStuff ::= epsilon case (MulStuff,end-of-string): case (MulStuff,conse-paren): case (MulStuff,addop): break; // Factor ::= number case (Factor,number): stack.push(number); break; // Factor ::= id case (Factor,id): stack.push(id); break; // Factor ::= open-paren Exp close-paren case (Factor,open-paren): stack.push(close-paren); stack.push(Exp); stack.push(open-paren); break; default: crash-and-burn end switch end if // stack.top is a nonterminal end while if (stack.top != end-of-string) then crash-and-burn end if
Thursday, 29 August 2002 [Samuel A. Rebelsky]
Wednesday, 2 October 2002 [Samuel A. Rebelsky]
Back to Even More Predictive Parsing. On to Shift-Reduce Parsing.
Primary:
[Skip To Body]
[Front Door]
[Current]
[Glance]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Sets:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Miscellaneous:
[2001S]
[98F]
[SamR]
[Glimmer Labs]
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 Fri Dec 6 10:38:11 2002.
The source to the document was last modified on Wed Oct 2 10:35:12 2002.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2002F/Outlines/outline.15.html
.
You may wish to
validate this document's HTML
;
;
Check with Bobby