Krautkanal.com

Veröffentlicht am 2017-01-14 13:02:16 in /prog/

/prog/ 9781: Parser

thomasgeisen Avatar
thomasgeisen:#9781

Hallo Bernds, Bernd benötigt einen Parser, will aber aufgrund von Abhängigkeitsvermeidung keinen Generator einsetzen.

Was ist denn heutzutage so der beste Parser, den man recht einfach per Hand schreiben kann?
Immer noch rekursiv absteigend? Hab gehört, man trennt heute den Tokenizer nicht mehr raus, Bernd, sondern tut so, als wären die Buchstaben Token?

intertarik Avatar
intertarik:#9782

>Was ist denn heutzutage so der beste Parser, den man recht einfach per Hand schreiben kann?
Um eine sinnvolle Antwort auf diese Fragen zu geben,
braucht man mehr Information zur Grammatik die implementiert wird.

>Abhängigkeitsvermeidung
Wenn es sich um was komplexeres handelt ist es besser einen CC zu verwenden, egal ob es eine Abhängigkeit bringt oder nicht.
In einen solchen Fall tauscht man die Abhängigkeit durch eine ungetestete Ansammlung von Programmcode.
Bernd lief mal diese Route und ratet davon ab.

>Hab gehört, man trennt heute den Tokenizer nicht mehr raus, Bernd, sondern tut so, als wären die Buchstaben Token?
Das wäre mir neu. Wie würden dann die einzelnen Lexeme innerhalb von Produktionsregeln zustande kommen?

ah_lice Avatar
ah_lice:#9783

>>9782
>Um eine sinnvolle Antwort auf diese Fragen zu geben, braucht man mehr Information zur Grammatik die implementiert wird.

Vermutlich etwas BASIC- oder PASCAL- ähnliches mit hoffentlichen keinem Kontext, Garantie würde Bernd dafür aber nicht geben.

Wegen Generatoren: Bernd hat da vor ein paar Jahren mal kurzrecherchiert und das Ergebnis war in etwa:

- GCC/Clang/viele weitere benutzen heutzutage handgeschriebene Parser
- yacc/bison lex/flex sind Krebs aus einer Vielzahl von Gründen
- Ragel verkommerzialisiert sich nachträglich und droppt Backends
- ANTLR wäre wohl die beste Wahl, aber leider eine Bibliothek und/oder Javakrebs
- viele weitere Memes wie Bibliotheken, grässlicher erzeugter Code und Parser Combinatoren

>Das wäre mir neu. Wie würden dann die einzelnen Lexeme innerhalb von Produktionsregeln zustande kommen?
Irgendein anderer Bernd hat dies im Zusammenhang mit PEG-Parsing mal fallen gelassen. Es sei wohl einfacher, wenn man z.B. verschachtelte Syntaxhervorhebungen haben möchte, z.B. JS in HTML. Völlig ungeachtet, dass verschachtelte Syntaxhervorhebung Krebs ist, was aber eine andere Geschichte ist.

jpotts18 Avatar
jpotts18:#9788

>>9783
Warum ist flex Krebs? Habe damit einen Scanner gebaut, der ziemlich abgeht.

syntetyc Avatar
syntetyc:#9789

>>9788
So vage in Erinnerung hab ich noch:
- kein richtiger Unicode-Support (war ja zu erwarten)
- Zeilennummer muss man reinfrickeln
- generierter Kram sehr hässlich und die Verbindung von Lex/Flex zu Yacc/Bison geschieht über irgendwelche globalen Variablen

i3tef Avatar
i3tef:#9802

>>9789
Kann bestätigen, gerade wegen den globalen Variablen ist es absoluter Krebs, speziell falls mehrere Scanner und Parser im selben Projekt sind.
Prefixe lösen es zwar, aber es ist unsauber in meinen Augen.
Das Reinfrickeln von Zeilennummern (und Spaltennummern) hatte ich noch nie zu 100% korrekt gelöst.

Hatte auch noch keinen flex oder bison Code in der Wildniss gesehen, welcher ordentlich gekapselt ist.

leandrovaranda Avatar
leandrovaranda:#9803

>>9788
>>9789
>>9802
Nachdem also hinreichend geklärt wäre, warum Bernd keine Generatoren/Fremdbibliotheken benutzen möchte:
Rekursiv absteigend oder doch etwas anderes?

iqbalperkasa Avatar
iqbalperkasa:#9804

Marpa ist der beste Parsingalgorithmus seit Jahrzehnten, Implementierung mit demselben Namen liegt in C vor.

https://jeffreykegler.github.io/Marpa-web-site/

* Marpa gibt vernünftige Fehlermeldungen aus, wenn Nonterminals nicht erreichbar oder reifizierbar sind, wenn die Grammatik Zyklen enthält oder nicht null-nicht-ambiguierbar ist. (LALR versagt hier.)
* Marpa geht sinnvoll mit Mehrdeutigkeit um und liefert alle möglichen Parsebäume. (PEG versagt hier.)
* Marpa schert sich nicht um First Set Clash oder Shift-Reduce Conflict; alle kontext-freien Grammatiken werden akzeptiert und in höchstens O(n**3) geparst. (yacc versagt hier.)
* Marpa parst alle LR-regulären Grammatiken in linearer Zeit. Wenn deine Grammatik mittels Recursive Descent geparst werden kann, dann trifft das zu. Marpa enthält ein Informatikabhandlung mit Beweisen der Korrektheit und Komplexitätsaussagen.
* Marpa weiß jederzeit, wo genau der Parsevorgang fehlschlug und aus welchem Grund, an welchen Regeln schon gearbeitet wurde und wie weit in jeder hinein, und liefert konkrete und korrekte Fehlermeldungen. Falls der Lexer ein ungültiges Token übergibt, kann Marpa Aussagen treffen, welches akzeptable Token an dieser Stelle sind. Marpa kann den Lexer auch darüber informieren, und so ein passendes Token einfach aus der Luft greifen oder die Regeln zur Laufzeit anpassen, um den Parsevorgang fortzusetzen, als ob der Fehler nicht aufgetreten wäre.

andyisonline Avatar
andyisonline:#9805

>>9804
Beeindruckend Bernd, leider jedoch mit zu vielen Abhängigkeiten und zu kombliziert zu installieren und zu benutzen, wenn man bedenkt, dass Bernd sein Problem auch mit einem rekursiv absteigenden Parser erschlagen kann. Wirklich, dass schwerste wird vermutlich das Auflösen der Operratorrangfolge sein.

alagoon Avatar
alagoon:#9813

>>9781
Bernd verwendet immer gerne Parser-combinator, damit lässt sich der Parser selbst gleich durch dessen syntaktische Struktur definieren.

RussellBishop Avatar
RussellBishop:#9814

>>9804
Kann Marpa auch als syntax annotator (zB. mit highlighting tags) funktionieren? Das fande ich immer so ein cooles feature von Trifecta, dass der Parsbaum sich quasi beim Parsen wieder in einen annotierten quellcode zusammenklappen lässt

exevil Avatar
exevil:#9818

>>9813
Wäre vermutlich eine Alternative zu rekursiv absteigenden Parsern, aber hier muss Bernd mal schauen, wie einfach es ist, dies selbst zu implementieren...

>>9814
Das sollte man mit jedem Parser umsetzen können, oder?

joshclark17 Avatar
joshclark17:#9819

>>9814
Ja, das habe ich mal programmiert und ging auch ganz leicht, aber das ist nicht out-of-the-box Bestandteil von Marpa.

Neuste Fäden in diesem Brett: