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 Parsing Expressions. On to Predictive Parsing, Continued.
Held Wednesday, September 25, 2002
Summary
Today we consider how to hand-code a parser based on a grammar. The traditional technique for doing such coding is called predictive parsing.
Notes:
Overview
palindromes of.a
's andb
's with ac
in the middle
S ::= a S a | b S b | c
boolean parseS(Lexer l) { Token t = l.nextToken(); if (t is an a) { if (!parseS(l) return false); Token u = l.nextToken(); return (u is an a); } else if (t is a b) { if (!parseS(l) return false); Token u = l.nextToken(); return (u is a b); } else { return t is a c; } } // parseS
S ::= epsilon
a
left a
,
we should apply S ::= a S a
right a
,
we should apply S ::= epsilon
S ::= A | B | c A ::= a S a B ::= b S b
Palindrome parseS(Lexer l) throws ParseException { Token t = l.nextToken(); if (t is an a) { Palindrome p = parseS(l); Token u = l.nextToken(); if (u is an a) { return new Palindrome(a,p,a); } else { throw new ParseException("Failed to find matching a; saw a " + u); } } else if (t is a b) { Palindrome p = parseS(l); Token u = l.nextToken(); if (u is an b) { return new Palindrome(b,p,b); } else { throw new ParseException("Failed to find matching b, saw a " + u); } } else if (t is a c) { return new SingletonPalindrome(c); } else { throw new ParseException("Found unexpected token: " + t); } } // parseS
b
when matching
an S
in
S :: = X b X ::= x X | epsilon
Thursday, 29 August 2002 [Samuel A. Rebelsky]
Wednesday, 25 September 2002 [Samuel A. Rebelsky]
Back to Parsing Expressions. On to Predictive Parsing, Continued.
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:07 2002.
The source to the document was last modified on Wed Sep 25 10:24:41 2002.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2002F/Outlines/outline.12.html
.
You may wish to
validate this document's HTML
;
;
Check with Bobby