CSC362 2011F, Class 16: Predictive Parsing (1)
Overview:
* Leftovers: Disambuating the Expression Grammar.
* Introduction to Parsing.
* Basics of Predictive Parsing.
* An Example: Language Membership.
* Some Problems with the Technique.
Admin:
* If you haven't done so already, you should read Aho et al. 4.4.
* EC for DK's talk next Thursday.
exp : _INT
| _ID
| _LPAREN exp _RPAREN
| exp binop exp
;
binop : _PLUS
| _MINUS
| _TIMES
| _DIVIDE
;
Problem: Two parse trees for 3-4*5
* One perspective: Since we're just doing language membership, it's
fine to have multiple proofs.
* Another perspective: The structure of the parse tree has meaning; we
will probably use it in code generation.
* In many cases, only one tree gives us the correct code
General issue: How do we rewrite an ambiguous grammar to an unambiguous
one?
* Can we do this automatically? No, not in the general case
* But we're smarter than computers, so we can probably do so
exp : exp binop exp
* This says that "any expression is okay in those two positions"
* In actuality, if we have exp _TIMES exp, there are restrictions
on what we'd accept for the left and right subexpressions
* What restrictions do you want to place on this two subexpressions
* Neither should have an unparenthesized lower-precedence operation
* Others? Consider
2 / 3 / 4
* (2/3)/ 4 = 2/12 = 1/6
* 2/ (3/4) = 8/3
2 - 3 - 4
* (2 - 3) - 4 = -1 - 4 = -5
* 2 - (3 - 4) = 2 - -1 = 3
* Tradition: Both subtraction and division are left-associative
(as are multiplication and addition, but that seems to make less
of a difference)
* This brings us back to restrictions
* The right subexpression cannot have unparenthesized multiplcation of
division
Three kinds of expressions in our world:
* exp: "anything goes"
* term: no unparenthesized addition (lhs of multiplication)
* All addition operations (plus/minus) are parenthesized
* factor: no unparenthesized addition or unparenthesized multiplication (rhs of multiplication)
* All addition and multiplication operations (plus/minus/times/divide) are parenthesized
exp : exp addop term
| term
;
term : term mulop factor
| factor
;
factor : _INT
| _ID
| _LPAREN exp _RPAREN
;
addop : _PLUS
| _MINUS
;
mulop : _TIMES
| _DIVIDE
;
Examples on board: You can only parse 3 - 4 * 5 and 3 - 4 - 5 in one
way each, and those are the "correct" parse
next question: Add exponentiation, which has higher precedence than
multiplication and is right associative
2 ^ 3 ^ 4 = 2 ^ (3 ^ 4)
waytop : exp relop exp
| exp
;
exp : exp addop term
| term
;
term : term mulop factor
| firm
;
firm : factor expop firm
| factor
factor : _INT
| _ID
| _LPAREN exp _RPAREN
;
addop : _PLUS
| _MINUS
;
mulop : _TIMES
| _DIVIDE
;
expop : _CARET