Back to Ambiguous Grammars. On to Predictive Parsing.
Held Wednesday, February 14, 2001
Summary
Today we consider the traditional grammar for expressions and mechanisms for making that grammar unambiguous.
Notes:
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.
[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:51 2001.
This page may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2001S/outline.11.html
.
You may validate
this page's HTML.
The source was last modified Mon Jan 22 10:39:10 2001.