Wo kann ich die Grundlagen des Schreibens eines Lexers lernen?

79

Ich möchte lernen, wie man einen Lexer schreibt. Mein Universitätskurs hatte eine Aufgabe, bei der wir einen Parser (und einen Lexer dazu) schreiben mussten, aber dieser wurde uns ohne Anweisung oder Feedback (über die Marke hinaus) gegeben, so dass ich nicht wirklich viel daraus lernte.

Nachdem ich nach diesem Thema gesucht habe, kann ich nur ziemlich fortgeschrittene Artikel finden, die sich auf Bereiche konzentrieren, von denen ich glaube, dass sie ein paar Schritte vor meinem Standort liegen. Ich möchte eine Diskussion über die Grundlagen des Schreibens eines Lexers für eine sehr einfache Sprache, die ich als Grundlage für die Untersuchung der Tokenisierung komplexerer Sprachen verwenden kann.

Derzeit interessiere ich mich nicht wirklich für Best Practices oder Optimierungstechniken, sondern konzentriere mich lieber auf das Wesentliche. Was sind einige gute Ressourcen, um mich anzufangen?

Rupert Madden-Abbott
quelle

Antworten:

68

Grundsätzlich gibt es zwei Hauptansätze zum Schreiben eines Lexers:

  1. Erstellen eines handgeschriebenen In diesem Fall empfehle ich dieses kleine Tutorial .
  2. Verwenden einiger Lexer-Generator-Tools wie Lex . In diesem Fall empfehle ich, die Tutorials des jeweiligen Tools zu lesen.

Außerdem möchte ich das Kaleidoskop-Tutorial aus der LLVM- Dokumentation empfehlen . Es durchläuft die Implementierung einer einfachen Sprache und zeigt insbesondere, wie man einen kleinen Lexer schreibt. Es gibt eine C ++ - und eine Objective Caml-Version des Tutorials.

Das klassische Lehrbuch zu diesem Thema ist Compiler: Prinzipien, Techniken und Werkzeuge, auch bekannt als Drachenbuch. Dies fällt jedoch wahrscheinlich unter die Kategorie "ziemlich fortgeschrittene Zuschreibungen".

vitaut
quelle
4
Das Kaleidoskop-Tutorial war der Teil, der diese Frage für mich wirklich beantwortete.
Robert Byers
Weitere Informationen zum manuellen Schreiben eines LL (1) -Parsers finden Sie in dieser Antwort .
Jchook
10

Das Drachenbuch ist wahrscheinlich der endgültige Leitfaden zu diesem Thema, obwohl es etwas überwältigend sein kann. Sprachimplementierungsmuster und Programmiersprache Pragmatik sind ebenfalls großartige Ressourcen.

Brandon Moretz
quelle
5
+1 im Drachenbuch. Ich habe viel davon gelernt, als ich an der Universität war. Ja, da gibt es viel, aber wenn Sie wirklich an Compiler-Design und -Implementierung interessiert sind, ist dies eine großartige Ressource.
DarinH