C++ parsen
-
So, ich melde mich mal wieder :). Ich hab mich die letzten Monate mit der Materie auseinandergesetzt (Dragonbook), mich mit verschiedenen Parsertechniken (hauptsächlich rekursiv absteigend und LALR) beschäftigt. In nächster Zeit (nach meiner FIAE Abschlussprüfung anfang Mai) werde ich wohl mal einen C-Parser angehen. Wie im Verlauf des Threads schon kenntlich gemacht wurde, geht es mir nicht nur rein ums parsen, sondern um einen Parser, der eher wie eine Code-Completion arbeitet. Änderungen im Source-Code direkt nachdem diese durchgeführten wurden entsprechend parsen und den AST aktualisieren. Nun zu meiner eigentlichen Frage. Gibt es bereits Techniken, wie man so einen, ich sag mal "Live-Parser" implementieren kann?
Viele Grüße
-
Hat niemand eine Idee?
-
Ich denke die wenigsten haben schon einmal einen Live-Parser geschrieben.
Was hindert dich daran, einen schon bestehenden anzuschauen? Mal angefangen mit man: ctags (oder vllt. Geany), dann weiter zu KDevelop oder anderen IDEs.Genau darum gibt es Open Source.
-
Das richtige Stichwort heißt Incremental Compiler.
Für weitere Infos dann einfach google bemühen (ggf. Google Scholar).
-
Ich rate dir noch kleiner anzufangen. Ich bin selber momentan dran eine kleine Skriptsprache zu basteln un das is wirklich nicht in 1 oder 2 wochen gemacht.
Ich empfehl dir ein Zwischencode zu erstellen und dann zu parsen, am besten einen im hex style oder nach deiner wahl. Das kann das parsen um einiges schneller machen.
-
life schrieb:
Das richtige Stichwort heißt Incremental Compiler.
Für weitere Infos dann einfach google bemühen (ggf. Google Scholar).
Exakt nach dem Stichwort hab ich gesucht. Vielen Dank!
@gamebuntu: Danke für den Rat. Jedoch bin ich von meinem wuchtigen Ziel eines C++-Parsers zu einen C-Parser abgestiegen ^^. Grammatikalisch ist C relativ leicht zu parsen. Bei der semantischen Analyse wird mir wohl noch das eine oder andere Problem übern Weg laufen, aber da führt bei allen Skript- oder Programmiersprachen kein Weg dran vorbei.
An dieser Stelle nochmal ein großes Danke an alle hier :).
Viele Grüße
-
Guten Morgen,
ich hab mich nun mal etwas mit der inkrementellen Übersetzung beschäftigt. Des Weiteren hab ich schonmal ein Gropkonzept aufgesetzt, wie sowas umsetzbar wäre. Jedoch habe ich bei der ganzen Sache noch ein Problem, welches ich nicht zu lösen weiss. Ich übersetze jeweils den Teil im Source-Code neu, der aktualisiert wurde, und alles was damit zusammenhängt. Bspw. Es wird im Bereich einer Funktion oder eines Block-Statements etwas geändert, so muss die Funktion in der dieser Block existiert ebenfalls neu validiert werden. Im Falle der Funktion müssen alle aufrufenden bzw. referenzierenden Stellen validiert werden. Wenn ich nun am Anfang einmal initial den kompletten Source-Code übersetze (parsen + semantische Überprüfung) habe ich nun erstmal einen Abstract-Syntax-Tree (AST). Wenn ich nun an einer beliebigen Funktion oder sonstigen Elementen im Source-Code etwas ändere, brauch ich dazu den Verweis auf die Stelle im AST. Jedoch weiss ich nicht wie ich das ordentlich abgebildet bekomme. Theoretisch könnte ich bei der lexikalschen Analyse für jedes Token die Stelle im Source (Row, Column) speichern. Jedoch wird es ziemlich unflexibel wenn ich mitten im Code etwas ändere und sich somit der komplette nachfolgende Code verschiebt, oder einfach nur weitere Newlines zwischen Funktionen einfüge.
Kennt jemand für dieses Probleme eine bewährte bzw. praktikable Lösung?
Viele Grüße
-
skNiNe schrieb:
Wenn ich nun an einer beliebigen Funktion oder sonstigen Elementen im Source-Code etwas ändere, brauch ich dazu den Verweis auf die Stelle im AST. Jedoch weiss ich nicht wie ich das ordentlich abgebildet bekomme. Theoretisch könnte ich bei der lexikalschen Analyse für jedes Token die Stelle im Source (Row, Column) speichern.
Wieso Row/Column? Auf den ersten Wurf würde ich eine Symboltabelle erstellen, in denen zu den Symbolen Verweise auf die AST-Knoten liegen, in denen das Symbol definiert/deklariert oder verwendet wird.
Wenn jetzt irgendwo ein Symbol neu verwendet wird bzw. die Verwendung geändert wird, kannst du über die Tabelle die vorhandenen Deklarationen finden und prüfen, ob die Verwendung passt.
Wenn die Deklaration eines Symbols verändert, gelöscht oder hinzugefügt wird, findest du über die Tabelle die Knoten, in denen sie verwendet wird und kannst die Knoten neu evaluieren.
-
Nabend,
grundsätzlich eine gute Idee. Jedoch muss ich beachten, dass in der Symboltabelle in der Regel ja erstmal nur Identifier gespeichert werden (bspw. für Objekte oder Funktionen). Grundsätzlich kann ein Identifier an verschiedenen Stellen bzw. Scopes auftreten bzw. deklariert werden. Wenn ich nun an bestimmter Stelle den Code ändere, muss ich ja an dieser Stelle schon wissen, welches Element in der Symboltabelle gemeint ist um erstmal meinen Verweis auf den AST-Knoten zu bekommen. Des Weiteren könnte ich ja bspw. einfach eine Klammer irgendwo hinzufügen oder entfernen. Für so eine Änderung gibt es in der Symboltabelle kein Element, somit wüsste ich auch nicht, an welcher Stelle neu evaluiert werden müsste.
Btw: Bezüglich inkrementeller Übersetzung lassen sich nur schwer detailierte Informationen beschaffen. Beim "normalen" parsen hätte ich solche Probleme nicht. Theoretisch könnte ich direkt erstmal mit dem Parser usw. beginnen, jedoch möchte ich im vornherein einige Einzelheiten planen, um später eine saubere Implementierung zu haben.
Ich bin für jede Hilfe dankbar :).
Viele Grüße
-
Nabend,
ich habe nun eine Lösung für das Problem gefunden.
http://wiki.eclipse.org/CDT/designs/Overview_of_Parsing
Eclipse macht es wohl so, dass sie tatsächlich ein Mapping zwischen Code und AST-Nodes haben.
Daraufhin folgt nun leider das nächste kleine Problem. C und C++ wird bei der Übersetzung in Translation Phases aufgeteilt. Hier finden schon vor dem parsen usw. Aktionen statt. Bspw. wird mit #include eingebundener Code mit rein gezogen, Makros aufgelöst usw. ... Das heisst, dass der zu parsende Code nicht gleich dem ist, den der Benutzer in seinem Editor sieht. Demzufolge müsste ich den zu parsenden Code irgendwo zwischenspeichern. Leider fällt mir hierzu keine ordentliche Lösung ein. Einerseits könnte ich den Code in eine temporäre Datei schreiben, wodurch aber die Performance sehr leidet. Andererseits könnte ich den Code direkt in den Arbeitsspeicher laden, was bei großen Dateien (vorallem wenn verschieden Header-Dateien eingebunden werden) zu übertrieben großen Overhead führt.
Falls jemand hierfür eine Lösung hat ... ich hab immer ein offenes Ohr :).
PS: Ich merk schon, der Thread hier ist mittlerweile schon fast mein eigener Blog :D.
Viele Grüße
EDIT:
Die Lösung von Eclipse findet man im Kapitel "Scanning and Preprocessing" im letzten Absatz.