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 Opr2a term1  // left associative
term2  ::=  term2 Opr2b term1  // left associative
term2  ::=  term1               // next precedence
term1  ::=  term Opr1 term1   // 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
  1. Operator Precedence: The lower in the grammar, the higher the precedence.
  2. 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    ::=                   // Empty
expression ::=  formula
expression ::=  term

formula ::=  prop
formula ::=  prop and formula
formula ::=  prop or formula
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 ::=  print formula ; program
program ::=  print term ; program
program ::=                   // Empty

program    ::=  print expression 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.