Converting given ambiguous arithmetic expression grammar to unambiguous LL(1)

2
votes

In this term, I have course on Compilers and we are currently studying syntax - different grammars and types of parsers. I came across a problem which I can't exactly figure out, or at least I can't make sure I'm doing it correctly. I already did 2 attempts and counterexamples were found. I am given this ambiguous grammar for arithmetic expressions: E → E+E | E-E | E*E | E/E | E^E | -E | (E)| id | num , where ^ stands for power.

I figured out what the priorities should be. Highest priority are parenthesis, followed by power, followed by unary minus, followed by multiplication and division, and then there is addition and substraction. I am asked to convert this into equivalent LL(1) grammar. So I wrote this:

  • E → E+A | E-A | A
  • A → A*B | A/B | B
  • B → -C | C
  • C → D^C | D
  • D → (E) | id | num

What seems to be the problem with this is not equivalent grammar to the first one, although it's non-ambiguous. For example: Given grammar can recognize input: --5 while my grammar can't. How can I make sure I'm covering all cases? How should I modify my grammar to be equivalent with the given one? Thanks in advance.

Edit: Also, I would of course do elimination of left recursion and left factoring to make this LL(1), but first I need to figure out this main part I asked above.

1
parsinggrammarcontext-free-grammarformal-languages
Can you recheck what you wrote? I am trying to follow the logic but there is no C on the right side anywhere except right from C itself. I guess you wanted to write something else - Luka Bulatovic
updated: nopaste.linux-dev.org/?1021470 - Marco A.
Thank you! I will try testing this grammar on some corner cases but it looks okay at first sight, also I can notice the fix around that minus. - Luka Bulatovic

1 Answers

2
votes

Here's one that should work for your case

E = E+A | E-A | A
A = A*C | A/C | C
C = C^B | B
B = -B | D
D = (E) | id | num

As a sidenote: pay also attention to the requirements of your task since some applications might assign higher priority to the unary minus operator with respect to the power binary operator.