0
$\begingroup$

Given a grammar as follows:

$\left<stmt\right> \rightarrow \left<id\right> = \left<expr\right>$

$\left<const\right> \rightarrow A | B$

$\left<expr\right> \rightarrow \left<term\right> \times \left<expr\right> | \left<term\right>$

$\left<term\right> \rightarrow \left<factor\right> + \left<term\right> | \left<factor\right>$

$\left<factor\right> \rightarrow (\left<expr\right>) | \left<id\right>$

I think this grammar is right associative because it expands on the right. Where I am confused is it can be expanded using other non-terminals on the left. For example,

$\left<expr\right> \rightarrow \left<term\right> \times \left<expr\right> | \left<term\right>$

Could be expanded via $\left<term\right>$ on the left, I think. Does this make the associativity ambiguous? Assuming it could be ambiguous, how would I fix this to make the grammar completely right associative?

$\endgroup$
2
$\begingroup$

$\left<expr\right> \to \left<term\right>×\left<expr\right> | \left<term\right>$

could certainly expand $\left<term\right>$. But the operator in that expansion (if there is one) is certainly not $×$; it would have to be $+$. So associativity doesn't apply, since associativity is only about expressions involving two of the same operator.

So yes, in both operator productions in that grammar, the operator is right-associative.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.