Ich lerne gerade über Parsing, aber ich bin ein wenig verwirrt, wie man einen AST erzeugt. Ich habe einen Parser geschrieben, der korrekt überprüft, ob ein Ausdruck einer Grammatik entspricht (er ist stumm, wenn der Ausdruck konform ist, und löst eine Ausnahme aus, wenn dies nicht der Fall ist). Wohin gehe ich von hier, um eine AST zu bauen? Ich habe viele Informationen über den Aufbau meines LL (1) -Parsers gefunden, aber sehr wenig darüber, wie ich den AST aufbauen kann.
Mein aktueller Code (geschrieben in sehr einfachem Ruby, einschließlich eines Lexers und eines Parsers) findet sich hier auf github: Ссылка
Kann mir jemand erklären, wie ich von dem, was ich gerade habe, zu einem AST gehe?
Wenn Sie mit Ruby nicht vertraut sind, aber C kennen, können Sie mir dann sagen, wie ich einen AST für den C-Code im rekursive Abstammung analysieren Wikipedia-Artikel.
Bitte beachten Sie, dass ich keinen Parser-Generator wie yacc oder antlr verwenden möchte, um die Arbeit für mich zu erledigen, ich möchte alles von Grund auf neu machen.
Danke!
Sie müssen jedes Symbol, das Sie zuordnen, mit einem Callback verknüpfen, der diesen kleinen Teil des Baums konstruiert. Nehmen wir zum Beispiel ein recht häufiges Konstrukt: verschachtelte Funktionsaufrufe.
%Vor%Ihre Terminal-Tokens sind hier wie folgt:
Und deine nichtterminalen Symbole sind etwas wie:
Offensichtlich ist die obige zweite Alternative für die Regel FUNCTION_CALL rekursiv.
Sie haben bereits einen Parser, der weiß, dass er ein gültiges Symbol gefunden hat. Das fehlende Bit ist das Anfügen eines Callbacks an die Regel, die ihre Komponenten als Eingaben erhält und einen Wert (normalerweise) zurückgibt, der diesen Knoten im AST darstellt.
Stellen Sie sich vor, die erste Alternative aus unserer obigen FUNCTION_CALL -Regel hätte einen Rückruf:
Das würde bedeuten, dass der AST aus dem Matching resultiert:
%Vor%wäre:
%Vor% Nun extrapoliere das auf die komplexere a(b()) . Da der Parser rekursiv ist, erkennt er zuerst das b() , dessen Callback das zurückgibt, was wir oben haben, aber mit "b" anstelle von "a".
Definieren wir nun den Callback, der der Regel zugeordnet ist, die der zweiten Alternative entspricht. Es ist sehr ähnlich, außer dass es sich auch mit dem Argument befasst, dass es übergeben wurde:
%Vor% Da der Parser b() bereits erkannt hat und dieser Teil des AST von Ihrem Callback zurückgegeben wurde, lautet der resultierende Baum nun:
Hoffentlich gibt dir das etwas zu denken. Übergeben Sie alle übereinstimmenden Token an eine Routine, die sehr kleine Teile Ihres AST erstellt.
OK, also hier bin ich wieder (und nein, diese Antwort hat nichts mit Scintilla per se zu tun; obwohl sie Teil eines Programmiersprachen- / Compilerdesign-Abenteuers von mir war).
Haben Sie daran gedacht, Lex / Yacc ? Das ist der Hauptgrund ihrer Existenz (= Parsing; Schreiben von Lexers und Parsern und somit die Art und Weise, AST s zu erstellen), und sie sind absolut C-freundlich.
Hier ist ein grobes Beispiel (aus meinem eigenen MathMachine Compiler).
mm_lexer.l (der Lexer)
%Vor%mm_parser.y (der Parser)
%Vor%Randbemerkung: Leider kann ich Ihnen bei Ruby-spezifischen Problemen nicht helfen (da ich nicht nur ein absoluter Neuling bin, sondern - aus einem unbekannten Grund - ich hasse es ); aber, auch in C, hoffe ich, dass dir das eine grobe Vorstellung gibt ...: -)
Tags und Links ruby parsing abstract-syntax-tree lexer ll