[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
Misc:
[2001S]
[2002F]
[SamR]
Back to Ambiguous Grammars. On to Predictive Parsing (1).
Held: Friday, 20 February 2004
Summary: Today we consider the traditional grammar for expressions and mechanisms for making that grammar unambiguous.
Related Pages:
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 CLOSE
a+b*2
is an expression? First, we observe that the
lexer converts this to ID PLUS ID TIMES 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 CLOSE | NUM | ID
-+num
is meaningless, as is ---num
).
Back to Ambiguous Grammars. On to Predictive Parsing (1).
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
Misc:
[2001S]
[2002F]
[SamR]
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 Wed May 5 11:47:02 2004.
The source to the document was last modified on Tue Jan 20 23:06:45 2004.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2004S/Outlines/outline.14.html
.
You may wish to
validate this document's HTML
;
;
Check with Bobby