[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
Samuel A. Rebelsky, rebelsky@grinnell.edu