Ein Blog

Beim Parsen von Operatorpräzedenzen gibt’s ja verschiedene Ansätze. Der erste und “einfache” Ansatz ist, die Präzedenzen in der Grammatik abzubilden. Die Implementierung mit einem rekursiven Abstieg ist dann trivial. Problematisch ist allerdings, dass der Syntaxbaum dann für einfache Sachen ziemlich tief wird. Für z. B. ein einfaches a = 5 hätte man auf der rechten Seite dann einen kompletten Unterbaum mit Nodes für jeden möglichen Operator, die dann aber quasi leer sind. Das ist sehr ineffizient.
Der nächste Schritt wäre ein Parser mit Dokus auf Operatorpräzedenz. Dort weist man jedem Operator eine Präzedenz in Form einer Zahl zu und löst es später ein einen vergleichsweise flachen Baum auf. Den Operatorpräzedenzparser kann man in den normalen rekursiven Abstieg integrieren und dann für binäre AUsdrücke verwenden. TypeScript macht das z. B. auch so.

Hier ist ein anderer Ansatz, Präzedenzen zu parsen: Better operator precedence