Entwicklung eines einfachen Parsers

Question

In meinem Beruf arbeite ich an der Entwicklung eines Pascal-ähnlichen Compilers. Ich habe die ganze Zeit an Optimierungen und Codegenerierung gearbeitet.

Ich würde auch gerne lernen, einen einfachen Parser für dieselbe Sprache zu erstellen. Ich bin mir aber nicht sicher, wie ich das anstellen soll. Flex und Bison scheinen die erste Wahl zu sein. Aber ist es nicht möglich, einen Parser mit C++ oder C# zu schreiben? C ist mir ein bisschen unheimlich.

Yacc++ unterstützt C#, aber es ist eine lizenzierte Version. Ich bin auf der Suche nach jeder Hilfe, die ich in dieser Hinsicht finden kann. Vorschläge würden sehr geschätzt werden.

Answer 1

Sie können Flex und Bison tatsächlich mit C++ verwenden. Unter diese Anleitung können Sie zum Beispiel sehen, dass Abschnitt 5 diesem Thema gewidmet ist. Googeln Sie einfach danach, und ich bin sicher, Sie werden viele Beispiele finden.

Answer 2

Wenn Sie Lex und Yacc verwenden, schreiben Sie eigentlich kaum etwas in C. Lex ist eine eigene Sprache, ebenso wie Yacc. Sie schreiben also den lexikalischen Analysator in Lex und den Parser in Yacc . Für Pascal, Lex und Yacc sind die Eingaben jedoch bereits verfügbar .

Der resultierende Parser und Lexer haben C-Schnittstellen, das ist richtig. Die meisten Sprachen, einschließlich C++, haben jedoch einfache Möglichkeiten, C-Schnittstellen aufzurufen (oder zu verpacken).

Ich bin kein Experte auf diesem Gebiet, aber ich bin mir sicher, dass all das oben Gesagte auch für ANTLR gilt.

Wenn Sie es in "reinem C++" machen wollen (was auch immer das bedeutet), sollten Sie die Verwendung von boost Geist . Ich sehe nicht wirklich den Sinn in theoretischer Reinheit, wenn es eine Tonne mehr Arbeit verursacht, obwohl.

Eigene Lexer und Parser von Hand zu schreiben, macht eigentlich ganz schön Spaß. Ein Lexer ist eine der wenigen Situationen, in denen man die Verwendung von sowohl siehe s und den Präprozessor. Allerdings würde ich es nicht für eine vollwertige Sprache wie Pascal empfehlen, wenn es sich vermeiden lässt. Das würde eine Menge Arbeit bedeuten. Ich spreche von Mannjahren.

Answer 3

Ich habe einen XSLT-Parser mit Flex und Bison geschrieben. In letzter Zeit mache ich allerdings ein Projekt mit ANTLR:

Ist die Syntax der JFig-Sprache effizient und klar (und besser als die XML-DSL von Spring-Framework)?

Die Arbeit mit ANTLR hat mir viel besser gefallen als die mit Flex und Bison. ANTLR bietet in mancher Hinsicht eine höhere Abstraktionsebene. Die lexikalischen Definitionen und die Parsergrammatik können alle in einer Datei gespeichert werden. (ANTLR generiert die Token-Datei.)

Einer der wichtigsten Punkte ist die Möglichkeit, Baumgrammatiken zu definieren. Im Grunde genommen parsen Sie die Eingabesprache mit einer Grammatik und haben Aktionen, die in einen optimalen AST-Baum umgeschrieben werden (die als verknüpfte Datenstrukturen im Speicher verbleiben). Dieser Baum kann dann an einen anderen Parser weitergegeben werden, der in einer separaten Baumparserdatei definiert ist. Der Baumparser ist der Ort, an dem Sie die eigentliche Arbeit der gewünschten Aktionen durchführen.

Dies ist ein guter Ansatz, da man die AST-Form beibehalten und sie bei Bedarf immer wieder neu verarbeiten kann - indem man bestimmte Teilbaumknoten herausschält, um sie auf der Grundlage der letzten Aktionen zu verarbeiten usw. Stellen Sie sich so etwas wie einen Sprachinterpreter vor. Anstatt in eine for-Schleife zu gehen und die Sprache immer wieder von Grund auf zu verarbeiten, kann man einfach die AST-Darstellung durcharbeiten.

In meinem Fall habe ich eine Bean Factory für IoC Dependency Injection entwickelt. Meine Bean-Factory behält den AST eines Bean-Deskriptors zur Laufzeit bei. Wenn sie eine neue Bean-Instanz erstellen (oder abrufen) muss, übergebe ich einfach den AST-Teilbaum des Bean-Deskriptors an meinen Baumparser - das Ergebnis ist die gewünschte Bean-Instanz (es gibt viele Faktoren, die bestimmen, wie die angeforderte Bean instanziiert wird, einschließlich der Erstellung anderer Beans, auf die verwiesen wird, und/oder der Anwendung anderer spezieller Verhaltensweisen über Meta-Attribute).

Schließlich zielt meine aktuelle Bean Factory auf Java ab, aber ich möchte ActionScript3 und C# .NET ansprechen. ANTLR bietet dafür Unterstützung.

Wie bereits erwähnt, hat Terrence Parr ein Buch über die Verwendung von ANTLR geschrieben. Es richtet sich an berufstätige Programmierer, die etwas Praktisches mit ANTLR machen müssen (im Gegensatz zu einer akademischen Behandlung des Themas).

Answer 4

Wenn Sie C# wollen, wie in diesem Pregunta versuchen Sie Gardens Point GPPG und GPLEX.