Konvertieren von gegeben mehrdeutigen arithmetischen Ausdruck Grammatik zu eindeutig LL (1)

Question

In diesem Begriff habe ich natürlich auf Compiler und wir studieren derzeit Syntax - verschiedene Grammatiken und Arten von Parsern. Ich bin auf ein Problem gestoßen, das ich nicht genau herausfinden kann, oder zumindest kann ich nicht sicherstellen, dass ich es richtig mache. Ich habe bereits 2 Versuche gemacht und Gegenbeispiele gefunden. Ich bin diese mehrdeutige Grammatik für arithmetische Ausdrücke gegeben: E → E + E | E-E | E * E | E/E | E^E | -E | (E) | ID | num, wobei^für Leistung steht.

Ich habe herausgefunden, was die Prioritäten sein sollten. Höchste Priorität haben Klammern, gefolgt von Potenz, gefolgt von einem Minus, gefolgt von Multiplikation und Division. Dann gibt es Addition und Subtraktion. Ich werde gebeten, dies in Äquivalent LL (1) Grammatik zu konvertieren. Also schrieb ich folgendes:

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

Was ist das Problem mit diesem zu sein scheint, ist nicht äquivalente Grammatik zum ersten, obwohl es nicht eindeutig. Zum Beispiel: Gegebene Grammatik kann Eingabe erkennen: --5 während meine Grammatik nicht kann. Wie kann ich sicherstellen, dass ich alle Fälle abdecke? Wie soll ich meine Grammatik ändern, um mit der gegebenen zu äquivalent zu sein? Danke im Voraus.

Edit: Auch würde ich natürlich Beseitigung der linken Rekursion und links factoring machen, um diese LL (1), aber zuerst muss ich herausfinden, diesen Hauptteil habe ich oben gefragt.

Answer 1

Hier ist eine, die

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

Als Nebenbemerkung für Ihren Fall funktionieren sollte: ihre Aufmerksamkeit auch auf die Anforderungen Ihrer Aufgabe, da some applications könnten höhere Priorität unären Minusoperator zuweisen in Bezug auf die Leistung Binäroperators .