CFG arithmetic precedence/ambiguity

448 Views Asked by At

Been a while since I've worked w/ CFG. Anyways, I have a particular grammar that goes through all the operations properly, but at the end (I excluded other standard mathematic operations).

S ::= S+T | S-T | T

T ::= nonterminal | ID | -S | (S)

per everything I have.. I know that -S should be -T. But additionally.. what does that do to the precedence. Is it ambiguous? Mathematically I can it obviously won't be correct.. but that shouldn't make a difference on the issue of ambiguity.

If it was a -T would that have equal precedence as the (S)?

really trying to comprehend how this occurs with it looping back to the Start state.

1

There are 1 best solutions below

0
On BEST ANSWER

If you change -S to -T, the ambiguity is solved. Before the change, here is an example for an ambiguous sentence: -a-b. Is it -(a-b), or (-a)-b?

With the change, however, there is no more ambiguity.

As for precedence, in your specific example, there doesn't have to be a rule between -T and (S), since it is always the inner one that has precedence, which is exactly the behavior you would expect.