spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Ich habe vor einigen Jahren mal YAPPS fuer Python benutzt, es generiert Python Code fuer einen Parser aus einer Grammatik Definition die sehr aehnlich zu EBNF aussieht.

Du koenntest nen simplen Parser damit generieren und dir anschauen wie der Code aussieht. Wenn ich mich recht erinnere ist der generierte Code sehr einfach zu verstehen.
http://theory.stanford.edu/~amitp/yapps/…nual/node1.html

PS: Es sieht so aus, als sei ANTLR auch ein Parser Generator. Du kannst dir auch anschauen wie der generierte code von denen aussieht.

Boost::Spirit ist auch recht nützlich.

Das ist nicht trivial und eine ganze Ecke schwieriger als einen Zustands-Automaten zu einem regulären Ausdruck zu implementieren. Aber folgendes Skript scheint einen guten Überblick über die Theorie zu geben:

http://amor.cms.hu-berlin.de/~kunert/papers/lr-analyse/

Willst du einfach nur einen Parser zu einer Sprache haben, ohne notwendigerweise die Implementierungsdetails zu verstehen, sind die angesprochenen Generatoren aber sicherlich eine gute Anlaufstelle.

Zitat von »Roflo«

Boost:pirit ist auch recht nützlich.

Uii... hast du Spirit schonmal benutzt? Ich habe vor ein paar jahren mal damit gearbeitet um eine CSS-ähnliche Sprache zu parsen und ja es hat zum Schluss funktioniert... aber ich würde is niemandem empfehlen (es sei denn es ist eine sehr einfache Grammatik). Die Zeit zum Kompilieren einer Datei die spirit benutzt ist mindestens 10 mal so hoch wie die einer normalen datei. Und wenn du einen Fehler machst bekommst du 1000 Zeilen Fehlermeldung (für einen fehler... und der eigentliche Grund ist darin irgendwo versteckt... nicht am anfang und auch nicht am Ende). Rückblickend war es der mein größter Fehler den ich je beim proggen gemacht habe boost::spirit zu verwenden. Hier eine Codedatei aus besagtem Projekt

PS: ihr dürft mich nicht falsch verstehen... boost::spirit ist das coolsten meta-template projekte überhaupt und ich finde die Idee und die Umsetzung super.... nur für große Grammatiken ist es einfach nicht geeignet

Dein Beispiel ist ja gar nicht so schlecht. Lieber erst mal einfach anfangen. Ich würde dir vorschlagen sogar erst mal auf einfache BNF zurück zu greifen. Fürs parsing gibt es verschiedene Ansätze. Möchtest du das ganze von Hand schreiben würde sich ein Top Down Parser anbieten. Das kannst du relativ einfach realisieren wenn du pro Regel eine Funktion bastelst. Du hast ja irgendeine Startregel. Das ist deine Startfunktion. Diese prüft im Prinzip das erste Zeichen (besser als Zeichen wären an sich Tokens, dafür würde man normalerweise einen Lexer schreiben um das ganze einzuteilen). Je nach Token leitet diese Funktion dann passend weiter an weitere Funktionen. Die Funktionen lesen dann an sich Terminale ein. Ein Terminal ist im Prinzip ein Zeichen/Token welches direkt verarbeitet wird und keine extra Regel ist. Je nachdem rufst du weitere Regeln auf was wieder einfachen Funktionsaufrufen entspricht. Guck dir doch vielleicht mal LL1 Grammatiken an. Damit kann man eigentlich relativ gut starten. Für den Anfang bietet es sich an einen Parser für Terme oder vergleichbares zu schreiben. Kannst ja mal einen Taschenrechner schreiben welcher von dir eingetippte Ausdrücke auswertet. Das ganze kann man dann natürlich mit allerlei Funktionen erweitern.
Hier wirklich ausführlich auf den Stoff einzugehen sprengt ein wenig den Rahmen. Kannst mich aber gern mal anschreiben wenn du ein wenig Hilfe benötigst.
Was die Einrückung von Python angeht. Im Prinzip wird der Code zuerst in Token unterteilt. Dabei könnte ein Tab bzw mehrere Leerzeichen als einzelnes Token angesehen werden. Diese könnten dann vom Parser als Codeebene ausgewertet werden. Im vergleich nutzen andere Sprachen Klammern wie du weißt. Das ist für den Anfang auf jeden Fall simpler, das mit den Tabs oder Leerzeichen geht an sich aber auch. Das theoretische Modell hinter Parsern sind Kellerautomaten. Guck dir die vielleicht einfach mal an. Eine simple Aufgabe für einen solchen Automaten wäre zum Beispiel das zählen von Klammern, bzw die Verifizierung ob ein Ausdruck vernünftig geklammert ist. Du kannst dir ja mal überlegen wie man das ganze jetzt für Python umsetzen könnte.
Wichtig ist alt wirklich erst mal klein anzufangen. Nimm dir eine einfache Art von Grammatiken und versuche erst mal damit zu arbeiten. Und dann langsam Schritt für Schritt weiter arbeiten.