Ich implementiere einen Pretty-Drucker für einen JavaScript-AST und ich wollte fragen, ob jemand einen "richtigen" Algorithmus kennt, um Ausdrücke mit minimalen Klammern automatisch zu klammern basierend auf der Operator-Priorität und Assoziativität . Ich habe auf Google kein nützliches Material gefunden.
Offensichtlich ist, dass ein Operator, dessen Elternteil eine höhere Priorität hat, in Klammern gesetzt werden sollte, z. B .:
%Vor%Es gibt jedoch auch einige Operatoren, die nicht assoziativ sind. In diesem Fall werden noch Klammern benötigt, z. B .:
%Vor%Ich frage mich, was für diesen letzteren Fall die beste Regel wäre. Ob es ausreichend ist zu sagen, dass der rhs-Unterausdruck für Division und Subtraktion in Klammern gesetzt werden sollte, wenn er weniger als oder gleiche Priorität hat.
Ich stolperte über Ihre Frage auf der Suche nach der Antwort selbst. Während ich keinen kanonischen Algorithmus gefunden habe, habe ich festgestellt, dass, wie Sie sagen, Operatorenpräzedenz allein nicht ausreicht, um Ausdrücke minimal einzuklammern. Ich habe versucht, einen hübschen JavaScript-Drucker in Haskell zu schreiben, obwohl ich es mühsam fand, einen robusten Parser zu schreiben, also änderte ich die konkrete Syntax: Ссылка
Zusätzlich zur Priorität müssen Sie die Operator-Assoziativität berücksichtigen. Binäre Operationen wie / und - werden als links assoziativ analysiert. Die Zuordnung = , Exponentiation ^ und Gleichheit == sind jedoch rechts assoziativ. Dies bedeutet, dass der Ausdruck Div (Div a b) c ohne Klammern in a / b / c geschrieben werden kann, aber Exp (Exp a b) c muss als (a ^ b) ^ c geklammert werden.
Ihre Intuition ist korrekt: Wenn der Ausdruck des linken Operanden für linksassoziative Operatoren weniger fest bindet als sein Elternelement, sollte er in Klammern gesetzt werden. Wenn der Ausdruck des rechten Operanden so fest oder weniger fest bindet als sein Elternelement, sollte er in Klammern gesetzt werden. So würde Div (Div a b) (Div c d) keine Klammern um den linken Teilausdruck benötigen, aber der rechte Teilausdruck würde: a / b / (c / d) .
Als nächstes müssen unäre Operatoren, insbesondere Operatoren, die entweder binär oder unär sein können, wie Negation und Subtraktion - , Zwang und Addition + usw. von Fall zu Fall behandelt werden. Zum Beispiel sollte Sub a (Neg b) als a - (-b) ausgegeben werden, obwohl die unäre Negation stärker bindet als die Subtraktion. Ich schätze, das hängt von deinem Parser ab, a - -b ist vielleicht nicht mehrdeutig, nur hässlich.
Ich bin nicht sicher, wie unäre Operatoren, die sowohl Präfix als auch Postfix sein können, funktionieren sollten. In Ausdrücken wie ++ (a ++) und (++ a) ++ muss einer der Operatoren dichter als der andere binden, oder ++ a ++ wäre mehrdeutig. Aber ich vermute, auch wenn Klammern in einem davon nicht benötigt werden, sollten Sie aus Gründen der Lesbarkeit trotzdem Klammern hinzufügen.
Es hängt von den Regeln für die spezifische Grammatik ab. Ich denke, Sie haben es richtig für Operatoren mit unterschiedlicher Priorität und Recht für Subtraktion und Division.
Die Potenzierung wird jedoch oft anders behandelt, indem der Operand der rechten Hand zuerst ausgewertet wird. Du brauchst also
%Vor%wenn c das richtige Kind der Wurzel ist.
Welcher Weg der Klammerung geht, wird durch das bestimmt, was die Grammatikregeln definieren. Wenn Ihre Grammatik die Form von
hat %Vor%Wenn op1 und op2 nicht assoziativ sind, dann wollen Sie den rechten Teilbaum von op1 in Klammern setzen, wenn der Teilbaum root auch op1 ist, und Sie wollen den linken Teilbaum von op2 in Klammern setzen, wenn der linke Teilbaum root op2 hat.
Es gibt einen generischen Ansatz für hübsche Ausdrücke mit minimalen Klammern. Beginnen Sie mit der Definition einer eindeutigen Grammatik für Ihre Ausdruckssprache, die Vorrang- und Assoziativitätsregeln codiert. Angenommen, ich habe eine Sprache mit drei binären Operatoren (*, +, @) und einem unären Operator (~), dann könnte meine Grammatik wie
aussehen %Vor%Parse-Bäume für die Grammatik enthalten alle notwendigen (und unnötigen) Klammern, und es ist unmöglich, einen Syntaxbaum zu konstruieren, dessen Abflachung zu einem mehrdeutigen Ausdruck führt. Zum Beispiel gibt es keinen Syntaxbaum für die Zeichenfolge
%Vor%weil '@' nicht assoziativ ist und immer Klammern benötigt. Auf der anderen Seite die Zeichenfolge
%Vor%hat Syntaxbaum
%Vor%Das Problem wird somit auf das Problem reduziert, einen abstrakten Syntaxbaum in einen Syntaxbaum zu zwingen. Die minimale Anzahl von Klammern wird erhalten, indem vermieden wird, einen AST-Knoten wann immer möglich zu einem atomaren Ausdruck zu zwingen. Dies ist auf systematische Weise einfach zu tun:
Pflegen Sie ein Paar bestehend aus einem Zeiger auf den aktuellen Knoten im AST und der aktuellen Produktion, die expandiert wird. Initialisiere das Paar mit dem Wurzel-AST-Knoten und der "E" -Produktion. In jedem Fall für die möglichen Formen des AST-Knotens erweitern Sie die Grammatik so viel wie nötig, um den AST-Knoten zu kodieren. Dies wird eine nicht erweiterte Grammatikproduktion für jeden AST-Teilbaum hinterlassen. Wenden Sie die Methode rekursiv auf jedes Paar (Teilbaum, Produktion) an.
Beispiel: Wenn der AST (* (+ 1 2) 3) ist, gehen Sie wie folgt vor:
Der Algorithmus kann natürlich viel weniger explizit implementiert werden, aber die Methode kann verwendet werden, um eine Implementierung zu führen, ohne verrückt zu werden:).
Tags und Links javascript pretty-print compiler-construction abstract-syntax-tree parentheses