Discussion Session 3¶
Ambiguity X Left Recursion X Associativity¶
Grammar with ambiguity:
term ::=term
+term
term ::=term
-term
term ::=NUM
After doing left-recursion elimination mechanically:
term ::=NUM
term2
term2 ::= +term
term2
term2 ::= -term
term2
term2 ::= // Empty
Left-recursion elimination won’t be able to remove ambiguity. The grammar still has ambiguity, but we can use recursive descent parsing technique now. Ambiguity is ressolved by the parsing process. (Semantics of the language is now influenced by the parsing process.)
Grammar without ambiguity but with left recursion (left associativity):
term ::=term
+NUM
term ::=term
-NUM
term ::=NUM
After doing left-recursion elimination mechanically:
term ::=NUM
term2
term2 ::= +NUM
term2
term2 ::= -NUM
term2
term2 ::= // Empty
A smarter way to express such grammar (right associativity):
term ::=NUM
+term
term ::=NUM
-term
term ::=NUM
Operator Precedence and Associativity¶
start ::=term2
// lowest precedence term2 ::=term2
Opr2aterm1
// left associative term2 ::=term2
Opr2bterm1
// left associative term2 ::=term1
// next precedence term1 ::=term
Opr1term1
// right associative term1 ::=term
// next precedence term ::=factor
+term
// right associative term ::=factor
// next precedence factor ::=factor
*base
// left associative factor ::=base
// next precedence base ::= -base
base ::= log (term2
) base ::= (term2
) base ::= Variable base ::= Number
- Operator Precedence: The lower in the grammar, the higher the precedence.
- Operator Associativity:
Tie breaker for precedence
Left recursion in the grammar means
- left associativity of the operator
- left branch in the tree
Right recursion in the grammar means
- Right associativity of the operator
- Right branch in the tree
Limitation of our implementation of Recursive Descendent Parser¶
program ::= printexpression
;program
program ::= // Empty expression ::=formula
expression ::=term
formula ::=prop
formula ::=prop
andformula
formula ::=prop
orformula
prop ::= true prop ::= false prop ::=VAR
term ::=factor
+factor
term ::=factor
-factor
term ::=factor
factor ::=NUM
factor ::=VAR
Question
Does this grammar have ambiguity?
Assume we do not care. Let parsing process dissolve the ambiguity for concrete
syntax like print x
.
Question
Can our recursive descendent parser handle the concrete syntax print true and false
?
Ordering of rules matters.
Question
Can our recursive descendent parser handle the concrete syntax print x + 1
?
Any remedy?
program ::= printformula
;program
program ::= printterm
;program
program ::= // Empty
program ::= printexpression
program
program ::= // Empty expression ::=formula
; expression ::=term
;
Question
What is perfect backtracking?
a1 ::= b1 b2 b3 b1 ::= c1 b1 ::= c2
Search all possible sequences of choices: record the state at each choice and backtrack if necessary.