Using LR parser we can even parse certain ambigous grammars

There is an automaton for every grammar, but it may have shift/reduce conflicts

For ambigous grammars, even LR(1) automaton will generate conflicts

Example: grammar like

E ::= E MINUS E | E TIMES E | E POWER E | ID

Yacc approach: use priorities to resolve conflicts

• each token has a priority number
• each token has left or right associativity
  • nonassoc
  • left
  • right

Example:

nonassoc EQ
left PLUS
left TIMES
right EXP

This will:

• forbid expression x = y = z
• interpret x * y * z as (x * y) * z
• interpret x ^ y ^ z as x ^ (y ^ z)
• interpret x + y * z as x + (y * z)

Example: draw LR(0) items for the grammar

E ::= E MINUS E | ID

and consider parsing

ID - ID - ID

Priorities:

• token priority given by declaration order (later binds higher)
• grammar rule priority is priority of last terminal ocurring on RHS

Resolving shift/reduce conflicts:

• if token to shift has higher priority than rule to reduce, then shift
• if equal priority then:
  • report error if non-assoc
  • reduce if left
  • shift if right

What if even this approach fails?

• approximate: use more general grammar
• later check that tree makes sense