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)	=	^^	^^	^^	^^	^^	^^	^^

Syntax von Reni. Teil 1: Die Zerschnippelung in Tokens

Heute werde ich mal einige Grundlagen der Programmiersprache Reni vorstellen.
Was man braucht, um zu programmieren, ist ein Text, den man "Das Programm" nennt. Der Text muss bestimmten Regeln gehorchen, sonst meckert der Compiler. Oder aber er meckert nicht, aber wenn das Programm dann laufen soll, tut es nicht das, was es soll oder stürzt gar ab.
Die erste Sorte von Regeln nennt man, grob gesprochen, Syntaxregeln. Die zweite Sorte betrifft die sogenannte Semantik. Da komme ich später dazu.
Die simpelste, grundlegendste Regel: Ein Programm besteht aus eine Folge von Zeichen, die durch bestimmte Regeln in Tokens, das sind so etwas wie Worte, zergliedert werden. Das ist eigentlich keine grosse Sache, aber es ist gut, das wenigstens einmal hin zu schreiben.
Um diese Regeln zu erklären, müssen wir zunächst über Zeichentypen sprechen. Das sind:

• Leerzeichen, Tabulator, Zeilenumbruch heissen Whitespaces
• Alle Klammern, Komma, Semikolon und Ausrufezeichen heissen Syntaxzeichen
• Buchstaben, Zahlen und der Unterstrich heissen alphanumerische Zeichen
• Einfaches und doppeltes Hochkomma sind Stringbegrenzer (kommen wir noch dazu)
• Das Doppelkreuz, auch Hashzeichen oder auch Gartenzaun ist das Kommentarzeichen (kommen wir auch noch dazu)
• Alle anderen Zeichen (Hier mal eine Auswahl der wichtigsten: ^°§$%&/=?\+*@~<.->|) heissen Symbolzeichen

Jetzt können wir die Tokenbildungsregeln angeben:

• Whitespaces trennen Token, sind aber selbst keine Token.
• Syntaxzeichen trennen Token und sind auch selbst Token
• Alphanumerische Zeichen bilden Token, wenn sie eine ununterbrochene Folge bilden
• Auch Symbolzeichen bilden Token, wenn sie eine ununterbrochene Folge bilden
• Ein Wechsel von alphanumerischen Zeichen zu Symbolzeichen oder umgekehrt trennt Token

Da kommt noch mehr, aber erstmal will ich diese Regeln durch ein paar Beispiele verdeutlichen:

Hello world123   123
dump_print
Die Token sind hier: "Hello", "world123", "123" und "dump_print". 


(Hello[world123,123;dump_print

Die Token sind hier: Runde Klammer auf, "Hello", eckige Klammer auf, "world123", Komma, "123", Semikolon und wieder "dump_print". 

Hello<<world123*123=:=dump_print

Die Token sind hier: "Hello", "<<", "world123", "*", "123", "=:=" und schließlich wieder "dump_print". 

Was jetzt noch fehlt, sich Strings und Kommentare. 

Beide trennen Tokens und Strings sind selbst auch Tokens. 

Strings sind fast beliebige Zeichenfolgen, die durch jeweils einen Stringbegrenzer vorne und hinten  begrenzt werden. Nomen est omen! Der Stringbegrenzer muß vorne und hinten der gleiche sein. Also gibt es somit zwei Arten von Strings: die die mit einfachem Hochkomma begrenzt werden und die mit einem doppelten. Aber keine Panik, das macht keinen Unterschied. 

Naja, fast keinen.   

"Fast beliebige Zeichenfolgen" bedeutet, dass natürlich der jeweils benutzte Stringbegrenzer nicht so einfach vorkommen kann. Aber er kann vorkommen - dann muss man ihn aber doppelt schreiben. Auch ist es verboten, einen Zeilenumbruch mitten im String vorkommen zu lassen. Wenn man das mal braucht, muss man sich anders helfen. Aber das kommt später (viel später). 

Ok, jetzt wieder ein paar Beispiele:

"Hello world"dump_print

Die Token sind hier: der String "Hello world" und schließlich wieder unser gutes altes "dump_print". 

'Hello world'dump_print

Dasselbe. Ist hier egal ob einfache oder doppelte Hochkommas. 

"it's cool man"dump_print

Die Token sind hier: der String "it's cool man" und wieder "dump_print".

'it''s cool man'dump_print

Dasselbe. Jedoch mussten wir hier das Hochkomma verdoppeln, weil der Begrenzer schon das einfache Hochkomma ist. Aber Achtung: es zählt trotzdem nur als eines.

Wenn man mal ein kompliziertes, schwer lesbares oder schwer verständliches Programm vorfinden sollte, kann man das durch sogenanntes Refactoring in ein weniger kompliziertes, besser lesbares oder leichter verständliches Programm verwandeln.
Oder man verwendet Kommentare, um das Spaghettimonster irgendwie zu beschreiben.
Ich empfehle die erste Methode, aber die geht nicht immer. Deshalb gibts auch in Reni Kommentare.
Kommentare beginnen mit einem Kommentarzeichen (#). Es gibt gleich zwei Sorten von Kommentaren: Zeilenkommentare reichen bis zum Ende der Zeile. Blockkommentare reichen bis zum Kommentarende-Zeichen. Die Blockkommentare erkennt man daran, dass nach dem Kommentarzeichen eine öffnende Klammer steht und dann noch ein Kommentarbezeicher folgt. Der wird verwendet, um das Ende des Kommentars zu finden. Das ist am einfachsten mit Beispielen zu illustrieren:
"Hello world" #(* Das ist ein Kommentar *)#dump_print  

Der  Kommentarbezeicher ist hier der Stern. Man kann jedes Symbol hier verwenden aber auch Namen, also Folgen von Buchstaben. Beispiel:

"Hello world" #(ignorieren Das ist ein Kommentar ignorieren)#dump_print  

Der  Kommentarbezeicher ist hier das Wort "ignorieren". 

Wozu man das braucht? Na Ihr werdet schon sehen...

Zum Schluß noch ein Beispiel für Zeilenkommentare, der Vollständigkeit halber:

"Hello world" # Das ist der auszugebende String

dump_print # ... und damit wird er ausgegeben   

Für den Compiler sind Kommentare nichts anderes als Leerzeichen. Er verwendet sie, wenn nötig als Trenner zweier Tokens, aber ansonsten werden sie ignoriert.

Den Einstieg haben wir jetzt. Das war vielleicht etwas "urschleimig". Und nix mit richtig programmieren. Aber es musste mal gesagt werden. 

Denn...

Ich hatte da mal so ein traumatisches Erlebnis. Es war Ende der Neunziger. Die "Programmiersprache" hieß "Base SAS". Und die hat großzügig auf solche schnöden Beschreibungen verzichtet. Das Ende vom Lied war, dass man in etwas kniffligeren Fällen (und die kommen bei echten Anwendungen garantiert) nie so richtig wusste, wie die Syntax genau definiert war. Ich habe mir damals geschworen, so etwas nie niemals zu tun.

Am Strand

Blogleser wollen Podcasts! Das hab ich gelesen und finde das selbst auch. Deshalb hier der erste Reni-
Podcast.

Linkliste:
97 Things Every Programmer Should Know

Hallo Welt

Jede ordentliche Programmiersprache muß mit einen Hello-World-Programm beginnen. Ich will da auch nicht nachstehen. Hier ist es:

    "Hello world" dump_print


"Macht nicht viel her", wird jetzt so manche sagen. Aber das ist eigentlich mehr oder weniger immer so. Ein Hello-World-Programm dient der grundsätzlichen Klärung von Sachen: wie ist der allgemeine Rahmen des Programmtextes, wie findet die Kommunikation mit dem Benutzer des Programmes statt. Indem man dann versucht, dieses Programm zu Laufen zu bringen, werden eine weitere Grundsätze klar: wie man den Compiler oder Laufzeitumgebung besorgt und benutzt.
Also machen wir das mal:


Reni ist momentan eine experimentelle Programmiersprache. Deshalb gibt es nur eine eingeschränkte Infrastruktur. 


Level 1: Die niederschwelligste Variante ist eine Website, wo man oben das Programm eingibt und dann auf einen Kopf drückt. Ich habe mal eine solche Website erstellt. Meine "Mittel" als Webprogrammierer sind begrenzt, so dass diese Site definitiv ziemlich poplich daherkommt. Aber:
a) Sie tut es
b) Sie ist sie eine Mitmachprovokation
Hier ist also der Link

Level 2: Für die verschwindende Randgruppe der Windowsbenutzer gibt es noch eine weitere relativ einfache Möglichkeit. Man kann sich hier die Assemblies runterladen. Einfach irgendwohin auspacken und in einer Konsole "ReniExe <meinedatei>" eingeben. Dabei steht <meinedatei> für den Namen einer Textdatei, die das zu kompilierende Programm enthält. Möglicherweise muß man noch ".NET Framework 4" installieren. Außerdem möchte ich an dieser Stelle noch darauf hinweisen, dass alles was Ihr mit dieser Software tut, Ihr auf eigene Gefahr tut. Ich übernehme keinerlei Haftung für eventuelle Schäden.

Level 3: Das alles ist unter gpl3. Die Sourcen kann man auf github finden. Es wird VisualStudio und C# benötigt. Mitmachprovokation!

Level 3+: Vielleicht findet sich ja jemand, der das ganze mal unter Mono oder so ans Laufen kriegt. Das wäre für die Menschen, die sich mit Linux oder gar MacOS rumquälen müssen, hilfreich. Ich weiß nicht genau, aber möglicherweise eröffnet sich dann auch die Möglichkeit die Entwicklung mit etwas anderem als VisualStudio zu bestreiten (Nicht das ich das VisualStudio schlecht finde, aber eine größere Wahlfreiheit ist auf jeden Fall zu begrüßen). Da ich momentan keine großartigen Spezialfeatures benutze, sollte das nicht allzu schwer sein, aber schaun wir mal...

Hier mal noch ein etwas komplexeres Beispiel:


Viersich: 4;
EinsDazu: /\ arg + 1;
Konstrukt: /\
(
    Simpel: arg; 
    Pelsim: EinsDazu(arg); 
    Fun: /\ Simpel+ EinsDazu(arg)
);
lorum: Konstrukt(23);
ipsum: Konstrukt(8);
ipsum Pelsim := 15;
(Viersich, ipsum Simpel, ipsum Pelsim, ipsum Fun(7), lorum Simpel, lorum Fun(18)) dump_print

Man sieht hier Elementares zum Gebrauch von Variablen und Funktionen. Der Doppelpunkt definiert eine Variable mit Initialisierung. Das Zeichen "/\" soll ein Lambda symbolisieren. Es steht immer am Anfang der Funktionsdefinition und mit "arg" wird das Argument des Aufrufs bezeichnet. Wie man Strukturen definiert und dann auf die Elemente zugreift, kann man hier auch sehen (Funktion "Konstrukt", Variablen "lorum" und "ipsum"). Das Zeichen := ist die Wertänderung.

Update 14.9.2012: Lambda-Symbol ist jetzt ein Präfix.
Update 04.11.2012: Versionsnummer bei VisualStudio entfernt
Update 04.11.2012: Ein wenig mehr Erklärung beim komplexen Beispiel
Update 21.11.2012: Link zum Tester