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
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