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 Ambiguous Grammars. On to Predictive Parsing.
Held Monday, September 23, 2002
Summary
Today we consider the traditional grammar for expressions and mechanisms for making that grammar unambiguous.
Notes:
strings of a's and b's with equal numbers of a's and b's.)
Overview
Exp ::= NUMBER
Exp ::= ID
Exp ::= UnOp Exp
UnOp ::= PLUS UnOp ::= MINUS
Exp := Exp BinOp Exp
BinOp ::= PLUS | MINUS | TIMES | DIVIDE
Exp ::= OPEN Exp OPEN
a+b*2
is an expression? First, we observe that the
lexer converts this to identifier + identifier * number
Exp => // Exp ::= Exp BinOp Exp Exp BinOp Exp => // Exp ::= ID ID BinOp Exp => // BinOp ::= PLUS ID PLUS Exp => // Exp ::= Exp BinOp Exp ID PLUS Exp BinOp Exp => // Exp ::= NUMBER ID PLUS Exp BinOp NUMBER => // Exp ::= ID ID PLUS ID BinOp NUMBER => // Binop ::= TIMES ID PLUS ID TIMES NUMBER
Exp
rather than the
first in Exp BinOp Exp
.
Exp / | \ / | \ Exp BinOp Exp------ / | | | \ / | | \ \ ID PLUS Exp BinOp Exp / | | / | | ID TIMES NUMBER
NUMBER PLUS NUMBER TIMES NUMBER
Exp / | \ / | \ Exp + Exp | / | \ | / | \ NUM Exp * Exp | | | | NUM NUM
Exp / | \ / | \ Exp * Exp / | \ | / | \ | Exp + Exp NUM | | | | NUM NUM
NUM MINUS NUM MINUS NUM
might be parsed with
two different trees.
Term
.
Term
? Something that may include
multiplication but does not include no unparenthesized addition.
AddExp
Term
.
Term
.
Factor
.
Term
s.
Term ::= Term MulOp Term
Term
s? Those that don't include
multiplication. We've already called those Factor
s.
Term ::= Factor
Factor ::= OPEN Exp CLOSE Factor ::= NUM Factor ::= ID
Term
, we can separate them into those that do and
those that don't.
Exp ::= Exp AddOp Exp Exp ::= Term
Term
.
Exp ::= Exp AddOp Term
Term ::= Term MulOp Factor
Exp ::= Exp AddOp Term | Term Term ::= Term MulOp Factor | Factor Factor ::= OPEN Exp OPEN | NUM | ID
-+num
is meaningless, as is ---num
).
Back to Ambiguous Grammars. On to Predictive 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:06 2002.
The source to the document was last modified on Wed Sep 4 10:08:34 2002.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2002F/Outlines/outline.11.html
.
You may wish to validate this document's HTML ; ; Check with Bobby
Glimmer Labs: The Grinnell Laboratory for Interactive Multimedia Experimentation & Research