Bewährte Verfahren zum Schreiben eines Parsers für Programmiersprachen

Question

Gibt es bewährte Verfahren, die ich beim Schreiben eines Parsers beachten sollte?

Answer 1

Ein paar Ratschläge:

• Kennen Sie Ihre Grammatik - schreiben Sie sie in einer geeigneten Form auf
• Wählen Sie das richtige Werkzeug. Machen Sie es von C++ aus mit Spirit2x, oder wählen Sie externe Parser-Tools wie antlr, yacc oder was immer Ihnen zusagt
• Brauchen Sie einen Parser? Vielleicht reicht regexp aus? Oder vielleicht ein Perl-Skript hacken, um den Trick zu tun? Das Schreiben von komplexen Parsern kostet Zeit.

Answer 2

Verwenden Sie reguläre Ausdrücke nicht übermäßig - sie haben zwar ihre Berechtigung, aber sie sind einfach nicht in der Lage, eine echte Analyse durchzuführen. Man kann sie zwar einsetzen, aber irgendwann stößt man an eine Wand oder hat ein unwartbares Chaos. Es ist besser, einen Parser-Generator zu finden, der mit einer größeren Sprachmenge umgehen kann. Wenn Sie sich wirklich nicht mit Werkzeugen beschäftigen wollen, können Sie sich rekursive Descent-Parser ansehen - das ist ein wirklich einfaches Muster, um einen kleinen Parser von Hand zu schreiben. Sie sind nicht so flexibel oder leistungsfähig wie die großen Parsergeneratoren, aber sie haben eine viel kürzere Lernkurve.

Wenn Sie keine sehr strengen Leistungsanforderungen haben, sollten Sie versuchen, Ihre Schichten getrennt zu halten - der Lexer liest einzelne Token ein, der Parser ordnet diese in einem Baum an, und dann prüft die semantische Analyse alles und verknüpft Referenzen, und dann gibt es eine letzte Phase, um auszugeben, was immer produziert wird. Wenn Sie die verschiedenen Teile der Logik getrennt halten, ist es später einfacher, die Dinge zu pflegen.

Answer 3

Lesen Sie den größten Teil der Drachenbuch Erstens.

Parser sind nicht kompliziert, wenn man weiß, wie sie zu bauen sind, aber sie sind NICHT die Art von Dingen, die man, wenn man genug Zeit investiert, irgendwann erreichen kann. Es ist viel besser, auf der vorhandenen Wissensbasis aufzubauen. (Andernfalls müssen Sie damit rechnen, dass Sie es ein paar Dutzend Mal schreiben und wieder wegwerfen).

Answer 4

Jepp. Versuchen Sie, es zu erzeugen, nicht zu schreiben. Erwägen Sie die Verwendung von yacc, ANTLR, Flex/Bison, Coco/R, GOLD Parser Generator, etc. Greifen Sie nur dann auf das manuelle Schreiben eines Parsers zurück, wenn keiner der vorhandenen Parsergeneratoren Ihren Anforderungen entspricht.

Answer 5

• Wählen Sie die richtige Art von Parser, manchmal reicht ein Recursive Descendant aus, manchmal sollten Sie einen LR-Parser verwenden (es gibt auch viele Arten von LR-Parsern).
• Wenn Sie eine komplexe Grammatik haben, erstellen Sie einen abstrakten Syntaxbaum.
• Versuchen Sie genau zu bestimmen, was in den Lexer eingeht, was Teil der Syntax ist und was eine Frage der Semantik ist.
• Versuchen Sie, den Parser so wenig wie möglich an die Implementierung des Lexers zu koppeln.
• Bieten Sie dem Benutzer eine gute Schnittstelle, damit er unabhängig von der Implementierung des Parsers ist.