# 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 precedenceterm2::=`term2`

Opr2a`term1`

// left associativeterm2::=`term2`

Opr2b`term1`

// left associativeterm2::=`term1`

// next precedenceterm1::=`term`

Opr1`term1`

// right associativeterm1::=`term`

// next precedenceterm::=`factor`

+`term`

// right associativeterm::=`factor`

// next precedencefactor::=`factor`

*`base`

// left associativefactor::=`base`

// next precedencebase::= -`base`

base::= log (`term2`

)base::= (`term2`

)base::= Variablebase::= 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::= print`expression`

;`program`

program::= // Emptyexpression::=`formula`

expression::=`term`

formula::=`prop`

formula::=`prop`

and`formula`

formula::=`prop`

or`formula`

prop::= trueprop::= falseprop::=`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::= print`formula`

;`program`

program::= print`term`

;`program`

program::= // Empty

program::= print`expression`

`program`

program::= // Emptyexpression::=`formula`

;expression::=`term`

;

Question

What is perfect backtracking?

a1::= b1 b2 b3b1::= c1b1::= c2

Search all possible sequences of choices: record the state at each choice and backtrack if necessary.