Search code examples
grammarbnfassociativityambiguous-grammar

BNF grammar associativity

I'm trying to understand how left and right associative grammars work and I need a little help. So I decided to come up an example and ask for some clarification. Basically, I want to create a grammar for two logical operations: and + implication. I want to make it so and is left associative and implication is right associative. This is what I got so far. Is this correct? I feel like it might be ambiguous. (I also kept in mind that and has higher precedence than implication)

<exp> := <and>
<and> := <impl> | <and> ^ <impl>
<impl> := <term> | <term> -> <impl>
<term> := (<exp>) | <bool>
<bool> := true | false
Solution

  • From my limited knowledge, it seems to me that you got the precedences inverted.

    At the grammar level, a left associative operator has the following format:

    exp = exp op other | other

    ...and a right associative operator would have the following format:

    exp = other op exp | other

    As you can see, it depends on your use of recursion: left associativity would use a left recursive rule while right associativity would use a right recursive one.

    As for precedence, the later a rule is in the grammar, the higher its precedence. In the grammar bellow, where opL represents a left-associative operator and opR represents a right associative one, exp0 has lower precedence than exp1, which has lower precendence than other:

    exp0 = exp0 opL exp1 | exp1
exp1 = other opR exp1 | other
other = ...

    As an example, if opL is "+" and opR is "**" and other is a letter, see how the parse tree for a few expressions would be built:

    • Left associativity:

      a + b + c -> (a + b) + c
exp0 -+-> exp0 +-> exp0 --> exp1 --> other --> a
      |        |
      |        +-> opL --> "+"
      |        |
      |        \-> exp1 --> other --> b
      |
      +-> opL --> "+"
      |
      \-> exp1 --> c

    • Right Associativity:

        a ** b ** c -> a ** (b ** c)
  exp0 --> exp1 +-> other --> a
                |
                +-> opR --> "**"
                |
                \-> exp1 +-> other --> b
                         |
                         +-> opR --> "**"
                         |
                         \-> exp1 --> other --> c

    • Precedence:

      a + b ** c -> a + (b ** c)
exp0 +-> exp0 +-> exp1 --> other --> a
     |
     +-> opL --> "+"
     | 
     \-> exp1 +-> other --> b
              |
              +-> opR --> "**"
              |
              \-> exp1 --> other --> c