Wie kann ich ternäre Operatoren in einen Präzedenzkletteralgorithmus integrieren?

Ich folgte der Erklärung im Abschnitt „Vorrangklettern“ weiter diese Webseite einen arithmetischen Evaluator zu implementieren, der den Präzedenzkletteralgorithmus mit verschiedenen unären Präfix- und binären Infix-Operatoren verwendet. Ich möchte auch ternäre Operatoren einbeziehen (nämlich den ternären Bedingungsoperator ?:).

Der auf der Webseite angegebene Algorithmus verwendet die folgende Grammatik:

E --> Exp(0) 
Exp(p) --> P {B Exp(q)} 
P --> U Exp(q) | "(" E ")" | v
B --> "+" | "-"  | "*" |"https://stackoverflow.com/" | "^" | "||" | "&&" | "="
U --> "-"

Wie kann ich ternäre Operatoren in diese Grammatik einbauen?

Genauer gesagt verwende ich C/C++/Java ?: als Beispiel.

Es scheint, dass in diesen Sprachen die ?: -Operator erlaubt jeden gültigen Ausdruck zwischen ? und :einschließlich Ausdrücken, die mit gebildet werden ?: selbst und solche, die mit Operatoren gebildet werden, deren Vorrang niedriger ist als der Vorrang von ?:z.B = und , (Beispiele: a ? b = c : d, a ? b , c : d, a ? b ? c : d : e).

Dies legt nahe, dass Sie behandeln sollten ? und : genau so wie ( und ) beim Analysieren von Ausdrücken. Wenn Sie geparst haben ? expr :, es ist insgesamt ein binärer Operator. Also parsen Sie ( expr ) und ? expr : auf die gleiche Weise, aber ersteres ist ein Ausdruck, während letzteres ein binärer Operator ist (mit einem darin eingebetteten Ausdruck).

Nun das ? expr : ist ein binärer Operator (a ?-expr-: b ist nicht anders als a * b in Bezug auf “Binärheit”), sollten Sie in der Lage sein, es so ziemlich wie jeden anderen binären Operator zu unterstützen, den Sie bereits unterstützen.

Ich persönlich würde mir nicht die Mühe machen zu splitten ?: in eigene binäre Operatoren umwandeln. Am Ende ist es immer noch ein ternärer Operator und muss mit 3 Operanden verknüpft und bei der Ausdrucksauswertung als Ganzes betrachtet werden. Wenn Sie dem Ansatz in dem Artikel folgen, den Sie in der Frage erwähnt haben, und einen AST erstellen, dann los, ?: hat einen linken untergeordneten Knoten, einen rechten untergeordneten Knoten (wie jeder andere binäre Operator) und zusätzlich einen mittleren untergeordneten Knoten.

Der Vorrang von ?-expr-: insgesamt sollte er niedrig sein. In C/C++ (und in Java?) ist es jedoch nicht die niedrigste. Es liegt an Ihnen, zu entscheiden, was Sie wollen.

Bisher haben wir die Assoziativität von nicht behandelt ?:. In C/C++ und Java, ?-expr-: ist wie der Zuweisungsoperator rechtsassoziativ =. Auch hier liegt es an Ihnen, es linksassoziativ zu machen oder rechtsassoziativ zu halten.

Und das:

E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "https://stackoverflow.com/" | "^"
U --> "-"

sollte sowas werden:

E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "https://stackoverflow.com/" | "^" | "?" E ":"
U --> "-"

Ich bin auf diese Frage gestoßen, als ich nach Informationen zum Umwandeln von ternären Operatoren in umgekehrte polnische Notationen (RPN) gesucht habe, obwohl ich keine solide Implementierung für die Implementierung von habe ?: Operator mit Precedence Climbing, ich denke, ich kann vielleicht einen Hinweis auf die Transformation geben ?: Bediener zu RPN mit zwei Stapeln … was dem Rangierbahnhof-Algorithmus auf der von Ihnen angegebenen Webseite ähnelt.

(Bearbeiten) Ich muss darauf hinweisen, dass das, was ich hier mache, nicht sehr effizient ist (beide Zweige des ternären Operators müssen ausgewertet werden), aber um zu demonstrieren, wie einfach es ist, einen neuen Operator (?:) in einem bestehenden Framework (dem RPN-Transformationscode) (durch Deklaration ? und : mit zwei niedrigsten Vorrangstufen).

Ich möchte mit einigen Beispielen beginnen, wie Ausdrücke mit ?: werden basierend auf meinem Parser in RPN umgewandelt … Ich füge hinzu zwei Operatoren statt nur einem, dem ? und :aber ich glaube nicht, dass es seitdem einen großen Unterschied macht : und ? immer zusammengefügt (Es ist nur praktischer, dass die RPN und der ursprüngliche Ausdruck die gleiche Anzahl von Token haben). In den Beispielen können Sie sehen, wie es funktioniert.

Beispiel 1: 1 + ((0+1) ? 2 : 3 + 8) + 4

UPN: 1 0 1 + 2 3 8 + : ? + 4 +

Lassen Sie uns nun die RPN auswerten.

1 – Schieben Sie die ersten Elemente in den Stapel und wir stoßen auf den ersten binären Operator:

1 0 1 und Betreiber +fügen wir die oberen 2 Elemente hinzu und verwandeln den Stapel in 1 1

2 – Dann drücken Sie drei weitere Elemente und wir stoßen auf den zweiten binären Operator:

1 1 2 3 8 + ——> 1 1 2 11

3 – Jetzt haben wir : und ?. Dies sagt uns eigentlich, dass wir entweder die auswählen sollen Folgezweig (das zweitoberste Element oben auf dem Stapel, 2) oder der alternative Filiale (das oberste Element auf dem Stapel, 11), basierend auf Prädikat (das drittoberste Element auf dem Stapel, 1). Da das Prädikat 1 (wahr) ist, wählen wir 2 und verwerfen 11. Der Parser entfernt die 3 Elemente (Prädikat/Folge/Alternative) und schiebt das ausgewählte zurück (in diesem Fall den Folgezweig), sodass der Stapel wird

1 2

4 – Verbrauchen Sie die restlichen Elemente:

1 2 + ——> 3

3 4 + ——> 7

Beispiel 2: 1 + ((0+0+0?0:0) ? 2 : (3 + 8)) + 4

UPN: 1 0 0 + 0 + 0 0 : ? 2 3 8 + : ? + 4 +

Auswertung:

Anfang:

1 0 0 + 0 + 0 0 : ? 2 3 8 + : ? + 4 +

Nach dem Addieren von 0 zu 0:

1 0 0 + 0 0 : ? 2 3 8 + : ? + 4 +

Nach dem Addieren von 0 zu 0:

1 0 0 0 : ? 2 3 8 + : ? + 4 +

Nach dem ersten :? wählt 0:

1 0 2 3 8 + : ? + 4 +

Nach dem Addieren von 3 und 8:

1 0 2 11 : ? + 4 +

Nach dem ?: wählt 11:

1 11 + 4 +

Nach dem Addieren von 1 und 11:

12 4 +

Endlich:

16

Dies kann darauf hindeuten, dass es möglich ist, einen Ausdruck mit zu transformieren ?: in umgekehrter polnischer Notation. Da auf der Webseite steht, dass RPN und AST äquivalent sind, da sie ineinander und voneinander transformiert werden könnten, sollte der ternäre Operator in ähnlicher Weise mit Precedence Climbing implementiert werden können.

Eine Sache, die getan werden muss, scheint die „Priorität“ (oder der Vorrang) des zu sein ?: Operator. Und ich bin tatsächlich darauf gestoßen, als ich die RPN-Transformation versuchte. Ich habe Fragezeichen und Doppelpunkten den niedrigsten Vorrang gegeben:

Wie Sie im obigen Beispiel sehen können, wann immer wir kurz vor der Ausführung stehen ?:das Vorrangzweig und die alternative Filiale und die Prädikat sollten bereits ausgewertet worden sein, was zu einer einzigen Zahl führt. Dies ist durch Vorrang gewährleistet.

Es folgt die Prioritätstabelle (Vorrang).

! ~ > * / % > + - > & > ^ > | > && > || > ? > :

Das ? und : haben die geringste Priorität, d.h. in Ausdrücken wie 1?2+3:4+5, ? und : nimmt niemals die Operanden um sich herum auf.

? vorangeht : damit : davor erscheinen ? im RPN. Nach meinem Verständnis ist dies nur eine Designentscheidung, weil : und ? nicht einmal unbedingt in 2 Operatoren aufteilen müssen.

Hoffe das hilft..

Bezug: http://en.cppreference.com/w/cpp/language/operator_precedence

Definieren Sie den Doppelpunkt so, dass er eine niedrigere Priorität als das Fragezeichen hat. Mit anderen Worten, ein ? b : c würde als (a ? b) : c geparst. Dadurch kann der Parser einen (if/then/empty-else) abstrakten Syntaxknoten konstruieren, der dann vom Operator „:“ bearbeitet wird, um die gewünschte Else-Komponente bereitzustellen.

Die Vorrangbeziehungen bewahren auch die Zusammensetzbarkeit des Operators. B. ein ? b:c? d : e wird als (a ? b) : (c ? d) : e analysiert, wie man es erwarten würde.

Hoffe das hilft.