Beste Methode zum Tokenisieren und Parsen von Programmiersprachen in meiner Anwendung

Question

Ich arbeite an einem Tool, das einige einfache Transformationen an Programmen durchführt (z. B. Extract-Methode). Zu diesem Zweck muss ich die ersten Schritte der Kompilierung durchführen (Tokenisierung, Parsing und möglicherweise Aufbau einer Symboltabelle). Ich werde mit C beginnen und dann hoffentlich erweitern, um mehrere Sprachen zu unterstützen.

Meine Frage ist, wie ich diese Schritte am besten durchführe:

1.) Erfindet das Rad nicht neu. Ich möchte natürlich keine Flex/Bison-Spezifikationen von Hand schreiben. Soll ich einfach bereits vorhandene Spezifikationen nehmen und von dort aus arbeiten? Ist Antlr hier der richtige Weg?

2.) Ist auf mehrere Sprachen erweiterbar. Natürlich wird das Lexing/Parsing für jeden anders sein, aber ich hätte gerne eine Lösung, die ich leicht auf andere Sprachen erweitern kann. Zumindest eine Reihe von Technologien, die das Ganze handhabbar machen würden.

Übrigens benutze ich C, um meine Anwendungen zu schreiben.

Wenn jemand eine Idee hat, wäre das großartig! Danke!

Answer 1

Die beste Methode für das Parsing ist zweifellos ANTLR . Es gibt zwei großartige Bücher des Autors zu diesem Thema, die man unbedingt haben muss. Die endgültige ANTLR-Referenz: Aufbau domänenspezifischer Sprachen y Muster für die Sprachimplementierung sind beide unschätzbare Ressourcen. ANTLR kann Verarbeitungscode in vielen verschiedenen Sprachen erzeugen.

Answer 2

Da Sie bereits geschriebene Grammatiken und reguläre Ausdrücke verwenden werden, ist die Wahl des Werkzeugs unbedeutend.

Sie können gehen mit flex / Bison und Sie werden viele bereits geschriebene Grammatiken finden. Ansonsten können Sie mit ANTLR die auf C, C++ und Java ohne Probleme funktionieren sollte und das Gleiche auch für sie tut.

Sie haben sich nicht dazu geäußert, welche Sprache Sie für diese Arbeit verwenden werden, daher ist es nicht so einfach, einen besseren Ansatz vorzuschlagen.

Denken Sie daran, dass jede Sprache ihre eigenen Merkmale hat, zum Beispiel sind Symboltabellen in Ruby anders aufgebaut als in C++. Das liegt daran, dass man strengere oder lockerere Deklarationen haben kann und so weiter. Sie sollten sich also gut überlegen, was Sie brauchen werden (und Sie können es auch in Ihrer Frage erklären, damit ich Ihnen besser helfen kann).

Zu Ihren beiden Phasen kann ich sagen, dass

• Die Tokenisierung ist recht einfach, erfordert nicht für jede Sprache eine andere Struktur und kann leicht erweitert werden, um eine Vielzahl von Programmiersprachen zu unterstützen.

• Das Parsing kann schwieriger sein. Sie müssen eine Abstrakter Syntaxbaum des Programms und können dann damit machen, was Sie wollen. Wenn Sie es im OOP-Stil tun möchten, müssen Sie eine Klasse für jeden Knotentyp verwenden, aber Knotentypen können sich zwischen den Sprachen ändern, weil sie strukturell unterschiedlich sind, so dass etwas Allgemeines und leicht erweiterbar auf andere Sprachen zu tun, ist ziemlich schwierig.

In diesem Punkt gewinnt ANTLR gegenüber Flex und Bison, weil es eine automatische Generierung von AST bietet (wenn ich mich recht erinnere).

Der Hauptunterschied zwischen diesen beiden Compilern ist die Tatsache, dass ANTLR eine LL(k) Parser (der von oben nach unten arbeitet), während Bison einen LALR(1) das ist bottom-up, aber wenn Sie bereits geschriebene Grammatiken verwenden, sollte das nicht so schwierig sein.

Ein persönlicher Rat: Ich habe viele Interpreter oder Compiler geschrieben, aber nie mit einer voll funktionsfähigen Sprache angefangen. C Die Syntax ist wirklich groß Vielleicht sollten Sie also mit einer Teilmenge beginnen, dann sehen, was Sie mit Token und AST machen können, und es später erweitern, um die volle Syntax zu unterstützen.

Answer 3

In welcher Sprache schreiben Sie Ihr Programm?

Ich würde mit antlr gehen (und eigentlich gehe ich für das Parsen von Java). Es unterstützt viele Sprachen und hat auch eine Menge von Beispielgrammatiken, die Sie kostenlos erhalten http://www.antlr.org/grammar/list . Leider müssen sie nicht perfekt sein (die Java-Grammatik hat keine AST-Regeln), aber sie bieten einen guten Anfang und ich nehme an, dass die Gemeinschaft für einen Parser-Generator recht groß ist.

Das Tolle an antlr ist neben den vielen Sprachzielen, dass LL(*) in Verbindung mit den von antlr unterstützten Prädikaten sehr mächtig und einfach zu verstehen ist und die generierten Parser es auch sind.

Mit "erweiterbar auf mehrere Sprachen" meinen Sie vermutlich mehrere Ausgangssprachen. Das ist nicht einfach, aber ich nehme an, dass man etwas Erfolg haben könnte, wenn man sie in ASTs übersetzt, die so viele gemeinsame Symbole wie möglich haben, und einen allgemeinen Tree Walker schreibt, der mit den Unterschieden in diesen Sprachen umgehen kann. Aber das könnte ziemlich schwierig sein.

Seien Sie jedoch gewarnt, dass die Online-Dokumentation nur dann gut ist, wenn Sie das offizielle antlr-Buch gelesen haben und LL(*) sowie semantische und syntaktische Prädikate verstehen.

Answer 4

Sie haben keine Sprache angegeben, also empfehle ich Ihnen dieses kleine Juwel, das ich neulich gefunden habe:

http://irony.codeplex.com/

Es ist super einfach zu bedienen und hat sogar Grammatiken für mehrere Sprachen (sogar für C#) vordefiniert. Es gibt auch pyparsing ( http://pyparsing.wikispaces.com/ ), wenn Sie Python als Ausgangssprache verwenden möchten.

Answer 5

Eine Tür, durch die man gehen kann, ist Eclipse. Es bietet Parsing, einschließlich fehlertolerantem Parsing, für eine Vielzahl von Sprachen. Eclipse hat eine interne Modularität, die es Ihnen ermöglicht, diese Funktionalität zu nutzen, ohne die IDE zu berühren.