Eindeutige Grammatik für die Potenzierung - kontextfreie Grammatik

E -> E+T | E-T | T
T -> T*F | T/F | F
F -> i | (E)

Wie kann ich diese Grammatik so ändern, dass eine Exponentiation möglich ist? ^ damit ich schreiben kann i+i^i*i? Da wir wissen, dass die Reihenfolge der Operationen höher ist ^ dann weiß ich nur, dass ich es richtig assoziativ machen muss.

Antworten:

8 für die Antwort № 1

In EBNF (Erweitertes Backus-Naur-Formular) könnte dies wie folgt aussehen:

expr -> term [ ("+" | "-") term ]*
term -> factor [ ("*" | "/") factor ]*
factor -> base [ "^" exponent ]*
base -> "(" expr ")" | identifier | number
exponent -> "(" expr ")" | identifier | number

(genommen von Hier)

In Ihre Notation übersetzt (kein Unterschied zwischen Zahlen und Bezeichnern)

E -> E+T | E-T | T
T -> T*F | T/F | F
F -> F^X | B
B -> i | (E)
X -> i | (E)

Man könnte "B" und "X" aus Gründen der Klarheit zusammenführen.

---

2 für die Antwort № 2

Symmetrisch wie unten.

E -> E + T | E - T | T
T -> T * F | T / F | X
X -> X ^ Y | Y
Y -> i | (E)

Erläuterung:
==========
Beachten Sie, dass diese Grammatik eindeutig ist. Um einen Ausdruck zu erzeugen, bestehen Operatoren ^, *, /, +, -Zuerst müssen wir mit dem Schreiben von Schritten beginnen, in denen der Operator mit niedrigerer Priorität so ist +, - kann vor dem höheren hinzugefügt werden, d. h *, /. Und dann ^ kann am Ende in den Zielausdruck eingefügt werden. Daher im abstrakten Syntaxbaum-Operator (Analysebaum) ^ erscheint unten (in Richtung Blätter). Auf diese Weise, wenn wir diesen Ausdruck nach Baum bewerten, ^ wird zuerst durchgeführt.

Hinweis: Entsprechend den Grammatikregeln in sentimentaler Form X -> O ^ Y Wir können nicht noch einmal hinzufügen +, -.., Aber wenn Sie irgendeine sentimentale Form haben E+T | E-T | T dann können wir wieder andere Operatoren hinzufügen. In dieser Form der Grammatik haben wir also die Kontrolle über den Fluss der Erzeugung eines beliebigen gültigen Ausdrucks (String), der zur Sprache der Grammatik gehört (so wird der Vorrang von Operatoren eindeutig gesteuert).

Zum Beispiel, um den Ausdruck zu erzeugen i + i ^ i * ikönnen wir nicht gehen E --> T --> X ---> X ^ Y denn einmal hast du X ^ Y Sie können nicht hinzufügen +, - (ohne Klammer (E)).

Die mögliche Wahl zum Erzeugen eines Ausdrucks i + i ^ i * i ist wie folgt:

E --> E - T --> E + T - T --> E + X - T --> E + X ^ Y - T --*--> i+i^i*i

`--*-->` means more than one step

Operator beachten ^ wird im letzten Schritt hinzugefügt (kann im Baum unten angezeigt werden, siehe unten im Diagramm):

Der Baum wird ungefähr so ​​aussehen:

                     E
/ | 
/  |  
E   -   T    <--  - evaluates 3rd
/ |      "
/  |      "
E   +   T   i    <--  + evaluates 2nd
"       |
"       |
i       X
/ | 
/  |  
X   ^   Y     <--  ^ evaluates first
"       "
"       "
i       i
NOTE:

in tree  "  means more than one steps
"
^ has higher precedence

because of Left to right associativity + evaluated before then -

Wenn Sie anfangen, diesen Baum auszuwerten, dann ^ wird zuerst ausgewertet.

Denken Sie daran, dass Operatoren mit hoher Priorität immer unten hinzugefügt werden. Daher sollte die Grammatik so sein, dass Operatoren später hinzugefügt werden können (in der Satzsynthese).

_{(Sie sollten warum in Ihrer Grammatik verstehen + und - kann direkt über generiert werden E und via T Du kannst hinzufügen *, /. Warum andere eindeutige Version E -> E*T | E/T | T, T -> T+F | T-F | X das ist nicht richtig! Dabei ist die durch diese Grammatik erzeugte Sprache und Ihre Grammatik gleichwertig. Der Grund dafür ist, dass Ihre Grammatik einen korrekten Baum aus Bewertungsgründen erstellt)}

Außerdem, wenn Sie einen Parser mit schreibenYACC-Tool. Sie können eine mehrdeutige Version dieser Grammatik mit einer geringeren Anzahl von Produktionsregeln verwenden und die Priorität der Operatoren außerhalb der Grammatikregeln angeben (was eine ungefähre Vorstellung davon gibt, welcher Operator zuerst ausgewertet werden sollte und wie ein Baum erstellt werden sollte). Und das ist vorzuziehen als diese eindeutige Form, da eine geringere Anzahl von Produktivitätsregeln einen kleineren Baum im Hochformat erstellt (daher benötigt ein effizienter Compiler weniger Zeit zum Parsen).

---

1 für die Antwort № 3

Beide Antworten sind falsch. In diesen Antworten assoziiert er nach links, wenn er sich tatsächlich nach rechts verbinden soll. Die korrekte modifizierte Grammatik sollte sein:

  E -> E+T | E-T | T
T -> T*X | T/X | X
X -> F^X | F //Note: it"s F^X not X^F
F -> i | (E)

Auf diese Weise funktioniert Ihre Grammatik wie erwartet mit einem Ausdruck wie:

a+b^c^d^e*f

Vielen Dank!

---