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: