Syntax von Reni. Teil 2: Prioritäten

Ich hatte ja schon mal angedeutet, dass ich nicht so der große Anhänger von LEX und YACC bin. Das sind kranke Tools im Unix-Stil, die schon den 70ern veraltet waren.
Eine Bekannte hat mich kürzlich gefragt, ob ich so Bücher kenne wie "Compilers: Principles, Techniques, and Tools" (das so genannte Drachenbuch). Meine Meinung: Man kann nur hoffen, dass Compilerbauer dieses Buch höchstens als Schrankfußersatz verwenden.
Was hab ich damit für Probleme:
a) Es wird mit Kanonen auf Spatzen geschossen. (LEX)
b) Die Theorie der formalen Sprachen, die da immer zugrunde gelegt wird, ist für Compilerbau ungeeignet. Wozu brauche ich eine Fabrik die Autos herstellen kann, die für Fahrer mit einer variablen Anzahl von Gliedmaßen bestimmt sind?
c) Ich brauche nicht etwas, was mir zu einem Text sagt "Gehört zur Sprache L" oder "Gehört nicht zur Sprache L". Was bringt das? Was ich brauche, ist erstmal ein Syntaxbaum und dann etwas, mit dem ich denselben durchwandere, um den Code zu "stricken".
Klar geht das mit den o. g. Tools, aber es ist reingefummelt, viel zu kompliziert und viel zu eingeschränkt.

Deshalb geht Reni anders vor: Reni hat einen Prioritätsparser, der den Syntaxbaum erstellt und einen kontextabhängigen Visitor, der durch den Baum marschiert und dabei den Code erzeugt.
Der kontextabhängige Visitor wird später vorgestellt. Hier geht es zunächst um den Prioritätsparser.

Jeder kennt die Regel "Punktrechnung geht vor Strichrechnung". Nichts anderes ist das Prinzip des Prioritätsparsers (Eine entscheidende Kleinigkeit kommt noch dazu, doch davon gleich.).
Der Ausdruck 2 + 3 * 4 ergibt 14, weil erst 3*4 gerechnet werden muss und dann das Ergebnis zu 2 addiert wird. Das Beispiel ist sehr einfach, hier die Darstellung als Syntaxbaum:

Die Prioritäten sind hier ganz einfach, oder? Höchste Priorität haben die einzelnen Zahlen, dann kommen die Punktrechnungen ("*" für Multiplikation und "/" für Division) und zum Schluß kommen die Strichrechnungen ("+" für Addition und "-" für Subtraktion).

P(Zahl) > P("*", "/") > P("+", "-")

Was ist aber jetzt mit einem Ausdruck wie 2 + 3 + 4? Sieht simpel und unproblematisch aus. Aber das gilt nur für einen menschlichen Betrachter. Der arme Compiler hat nämlich jetzt keine Ahnung, ob er erst 2 + 3 rechnen muss

oder erst 3 + 4

(Er kann auch nicht erkennen, dass das in diesem Beispiel egal ist.). Wir müssen ihm irgendwie mitteilen, dass - sagen wir - erst 2 + 3 gerechnet werden soll. Dass nennt man Links-Assoziativität. Es gibt auch Rechts-Assoziativität und es gibt auch noch kompliziertere Dinge. Die obige Formel sagt aus, das es sich bei der Priorität um eine sogenannte Ordnungsrelation handelt. Tatsächlich werden Prioritäten manchmal als Zahlen angegeben. Aber schon ein Blick auf die Rechts- bzw. Linksassoziativität läßt die Schwächen dieses Konzepts erkennen: Je nachdem hat der betroffene Operator eine höhere (Linksassoziativität) oder niedrigere (Rechtsassoziativität) Priorität als er selber(!). Man könnte das noch hintricksen, indem man die Assoziativität als zusätzliche Eigenschaft dazu nimmt. Aber wenn dann noch andere Operatormuster ins Spiel kommen, wie zum Beispiel Klammerkonstrukte oder dreistellige Operatoren, wie then-else, muß man ins Grübeln kommen.
Was wäre, wenn man die Priorität nicht als Ordnungsrelation ansetzt, sondern einfach nur als Relation - mit einer schnöden Tabelle? Hier mal ein Beispiel für eine solche Tabelle (Erklärt wird sie im nächsten Eintrag):

	(bot)	(	(any)	*	/	+	-	)
(	<-	<-	<-	<-	<-	<-	<-	^^
(any)	<-	<-	^^	<-	<-	<-	<-	^^
*	<-	<-	^^	^^	^^	<-	<-	^^
/	<-	<-	^^	^^	^^	<-	<-	^^
+	<-	<-	^^	^^	^^	^^	^^	^^
-	<-	<-	^^	^^	^^	^^	^^	^^
)	<-	=	^^	^^	^^	^^	^^	^^
(eot)	=	^^	^^	^^	^^	^^	^^	^^