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 Shift-Reduce Parsing. On to Shift-Reduce Parsing, Concluded.
Held Monday, October 7, 2002
Summary
Today we consider how to build shift-reduce automata and the tables that represent them..
Notes
Overview
fills in the restwhenever we advance the mark. We'll call this
closure
closure(State S) repeat for each item, N ::= alpha . M beta in S for each production M ::= gamma add M ::= . gamma to S end for each production end for each item until no changes are made to S return S end closure
goto
goto(State S, Symbol s) newS = {} for each item N ::= alpha . s beta in S newS = newS union { N ::= alpha s . beta } end for return closure(newS) end goto
S0 = { S' ::= . S $ } S0 = closure(S0); while there are unmarked states pick an unmarked state, S mark S for each symbol, s, add state goto(S,s) with edge labelled s end while
Thursday, 29 August 2002 [Samuel A. Rebelsky]
Monday, 7 October 2002 [Samuel A. Rebelsky]
Back to Shift-Reduce Parsing. On to Shift-Reduce Parsing, Concluded.
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:14 2002.
The source to the document was last modified on Mon Oct 7 10:20:52 2002.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2002F/Outlines/outline.17.html
.
You may wish to
validate this document's HTML
;
;
Check with Bobby