LARA

Precedence in LR Parsing

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)

Using Priority and Associativity in LR Parsers

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