Auch Parser-Generatoren können gute Fehlermeldungen erzeugen.

Übersetzung eines 2010 von Go-Entwickler Russ Cox veröffentlichten Artikels.

• Es war der Mythos verbreitet, dass Parser-Generatoren wie yacc keine guten Syntaxfehlermeldungen erzeugen können.

• Dieses Problem wurde jedoch bereits 2003 von Clinton Jeffery gelöst und erfordert nicht, den Parser von Hand zu schreiben.

• Wenn man in der Tabelle den Inhalt findet, der zum (bison)-Zustand und zum Eingabe-Token passt, kann man bessere Fehlermeldungen als eine einfache Syntaxfehlermeldung verwenden.

[lifthrasiir]

(Im Folgenden habe ich Inhalte zusammengefasst, die ich auf dem koreanischen Rust-Discord-Server geschrieben habe.)

Das größte Problem dieses Artikels ist also die Frage, ob Go derzeit Parser-Generatoren verwendet. Nein. Der Hauptparser von Go ist nach wie vor von Hand geschrieben. Den genauen Grund kenne ich nicht, aber es ist gut möglich, dass andere Go-Entwickler nicht automatisch derselben Meinung waren, nur weil rsc es für in Ordnung hielt.

Jeffreys Idee lässt sich im Compiler-Kontext mit einem Peephole-Optimizer vergleichen. Bevor Maschinencode ausgegeben wird, hält dieser eine feste Anzahl der zuletzt erzeugten Maschinenbefehle vor — daher auch der Name, weil man durch ein Fenster dieser Größe, ein „peephole“, hineinschaut — und wenn ein bestimmtes Muster erscheint, ersetzt er die betreffenden Befehle direkt an Ort und Stelle durch schnellere Befehle. Ein Peephole-Optimizer ist ein praktisches Werkzeug, das sich zusammen mit anderen allgemeinen Optimierungspässen einsetzen lässt, aber allein mit einem Peephole-Optimizer kann man nicht jede Art von Optimierung durchführen, die ein Compiler benötigt. Genauso kann ein Ansatz, der Fehler aus den zuletzt gesehenen Tokens erzeugt, nicht alle Parsing-Fehler abdecken. Außerdem ist das ein eigenständiger Ansatz, der sich nicht speziell auf Parser-Generatoren beschränkt, sodass es nicht richtig ist zu behaupten, die Probleme von Parser-Generatoren würden verschwinden, nur weil es diesen Ansatz gibt.

Persönlich denke ich nicht, dass das Konzept des Parser-Generators an sich schlecht ist, sondern dass die Denkweise problematisch ist, zu der Parser-Generatoren einen „zwingen“. Wenn man einen Parser schreibt, muss man — egal ob generiert oder von Hand — zum Beispiel Left Recursion und Right Recursion berücksichtigen, und man kann eine „natürliche“ Grammatik nicht einfach unverändert in Code übertragen. Wenn man ihn von Hand schreibt, nimmt man das bewusst in Kauf; wenn man aber selbst mit einem Parser-Generator den Parser an eine Teilmenge der „Grammatik“ anpassen muss, die an bestimmte Parsing-Algorithmen wie LL/LR gebunden ist, dann werden die Vorteile des Generators stark geschmälert. (Algorithmen wie GLR verschaffen hier zwar etwas mehr Spielraum, haben aber ebenfalls Grenzen.) Dass die meisten produktionsreifen Sprachimplementierungen heute keine Parser-Generatoren verwenden oder gelegentlich Ansätze wie PEG einsetzen — also zwar Parser-Generatoren, aber solche, die die Vorteile allgemeiner Generatoren überhaupt nicht nutzen —, hat durchaus seine Gründe.

[dynalloc]

Ich kann nachvollziehen, dass man keinen Parsergenerator verwenden möchte, wenn man sich nicht in die von ihm eingeschränkte Grammatik zwängen lassen will. Aber deshalb zu behaupten, ein Parsergenerator zwinge den Nutzern eine bestimmte Grammatik auf, finde ich seltsam.

Parsergeneratoren sind entstanden, um bei der Erstellung von Parsing-Tabellen für LR-Grammatiken zu helfen, weil diese trotz der Vorteile des Parsens in linearer Zeit viel zu schwierig ist. Nichtdeterministische, kontextsensitive Grammatiken zu parsen oder rekursive Parser zu erzeugen, bei denen unklar ist, wann das Parsing überhaupt endet, dürfte kaum zum Interessengebiet von Forschern und Entwicklern von Parsergeneratoren gehören.

Deshalb denke ich, dass Parsergeneratoren keine Programme sind, die unkritisch an nicht intuitive LR- oder LALR-Grammatiken glauben und sie aufzwingen, sondern Werkzeuge, die ihre Aufgabe erfüllen, indem sie das sehr schwierige Problem des Parsens in linearer Zeit und der dafür nötigen Erstellung von Parsing-Tabellen lösen.

[lifthrasiir]

Fast alle Sprachen, die man in der Praxis sieht, haben eine LL(1)-Grammatik, sodass lineares Parsen auch ohne einen LR-Parser möglich ist. (Das bedeutet nicht, dass die für die jeweilige Sprache bevorzugte Grammatik LL(1) ist.) Daher ist die Aussage, man müsse für lineares Parsen einen LR-Parser verwenden und brauche einen Generator, weil das Erstellen der Parsing-Tabelle schwierig sei, eine Verdrehung von Ursache und Wirkung. Außerdem ist der Prozess des Erstellens einer Parsing-Tabelle an sich nicht wesentlich komplex (schwierig ist der Beweis des Algorithmus).