Parsen Ausdrücke mit einer nicht definierten Anzahl von Argumenten

Question

Ich versuche, eine Zeichenfolge in einer selbstgemachten Sprache in eine Art von Baum zu analysieren, z.

# a * b1 b2 -> c * d1 d2 -> e # f1 f2 * g

sollten führen:

# a
  * b1 b2
    -> c
  * d1 d2
    -> e
# f1 f2
  * g

#, * und -> sind Symbole. a, b1, usw. sind Texte.

Seit dem Moment, wo ich weiß nur rpn Methode Ausdrücke zu bewerten, und meine aktuelle Lösung ist wie folgt. Wenn ich erlaube nur einen einzigen Text Token nach jedem Symbol I leicht Ausdruck zuerst in RPN-Notation (b = b1 b2; d = d1 d2; f = f1 f2) umwandeln kann und parst es von hier:

a b c -> * d e -> * # fg * #

Allerdings Text Token Zusammenführen und anderes, was kommt scheint problematisch zu sein. Meine Idee war, Marker-Token (M) zu erzeugen, so RPN wie folgt aussieht:

a M b2 b1 M c -> * M d2 d1 M e -> * # f2 f1 M g * #

, die auch parseable und scheint das Problem zu lösen.

Wie gesagt:

1. Hat jemand Erfahrung mit so etwas und kann sagen, es ist, oder es ist keine tragfähige Lösung für die Zukunft?
2. Gibt es bessere Methoden für Ausdrücke mit undefinierten arity von Operatoren Parsen?
3. Können Sie mich auf einige gute Ressourcen zeigen?

Hinweis. Ja, ich kenne dieses Beispiel sehr viel Lisp Präfixnotation ähnelt und vielleicht den Weg wäre zu gehen, um einige Klammern hinzuzufügen, aber ich habe keine Erfahrung hier. Allerdings muss der Quelltext keine künstlichen Klammern enthalten und auch ich bin nicht sicher, was über mögliche Infix Mixins wie # a * b zu tun -> [wenn value1 = Wert2] c. -> d

Vielen Dank für jede Hilfe.

EDIT: Es scheint, dass mit einer variablen Anzahl von Argumenten, was ich suche Quellen auf Postfixnotation sind

.

Answer 1

Ich konnte nicht vollständig verstehen Ihre Frage, aber es scheint, was Sie wollen, ist eine Grammatikdefinition und ein Parser-Generator. Ich schlage vor, Sie nehmen einen Blick auf ANTLR , sollte es ziemlich einfach sein, damit eine Grammatik zu definieren, entweder für Ihre Original-Syntax oder die RPN.

Edit: (. Nach Selbstkritik ausüben, und einige Mühe machen, die Frage Details zu verstehen) Eigentlich ist die Sprachgrammatik aus Ihrem Beispiel unklar. Allerdings scheint es mir, dass die Vorteile der Präfix / Postfix-Notation (dh, dass Sie weder Klammern noch ein Vorrang-aware-Parser müssen) von daher kommen, daß Sie kennen die Anzahl der Argumente jedes Mal, Sie stoßen einen Operator, damit Sie genau wissen, wie viele Elemente (für Präfixnotation) zu lesen oder aus dem Stapel Pop (für Postfixnotation). OTOH, ich glaube, dass mit Operatoren, die variable Anzahl von Argumenten haben Präfix / postfix Notationen nicht nur schwer zu analysieren, sondern geradezu mehrdeutig macht. Nehmen Sie den folgenden Ausdruck zum Beispiel:

# a * b c d

Welche der folgenden drei ist die kanonische Form?

1. (a * (b, c, d))

2. (a * (b, c), d)

3. (a * (b), c, d)

Ohne mehr über die Betreiber zu wissen, ist es unmöglich zu sagen. Natürlich könnte man eine Art von greedyness der Operatoren definieren, z.B. * Ist gieriger als #, so dass es verschlingt alle Argumente auf. Aber dies würde den Zweck einer Präfixnotation schlagen, weil Sie würde einfach nicht in der Lage sein, die zweite Variante aus der obigen drei aufzuschreiben; nicht ohne additinonal syntaktische Elemente.

Nun, da ich darüber nachdenke, ist es wahrscheinlich nicht durch die bloße Möglichkeit, dass keine der Programmiersprachen weiß ich Unterstützung Operatoren mit einer variablen Anzahl von Argumenten, nur Funktionen / Prozeduren .