[Alg] Parser generator, welke?

[beany]

Ik ben al een tijdje aan het rond kijken voor een goede parser generator(met daarbij uiteraard een lexer). Er is enorm veel te vinden, je kan bijna spreken van een overvloed. Toch kan ik niet helemaal een keuze maken, ik heb namelijk wat eisen:

- Het moet een C++ parser genereren, het liefst 1 waarbij het geen probleem is dat er meerdere parsers in een programma draaien(verschillende en/of dezelfde).

- De gegenereerde code moet portable zijn(win32 / Linux) of op beide platformen beschikbaar zijn die met dezelfde grammar overweg kunnen.

- GNU licentie / free

Nou leek flex + bison me wel wat(de ++ versie), alleen heb ik bij de win32 versie een raar gevoel: ik kan alleen maar oude builds vinden(paar jaar oud). Ik weet dus niet of die nog voldoen.

Ik gebruik als compiler de gnu c++ compiler(onder windows de mingw met als ide dev-C++)

Iemand ideeen? Suggesties? Interessante urls?

[.oisyn]

flex en bison werken prima onder win32, je zit alleen met een niet bestaande unistd.h (gewoon even aanmaken), en het feit dat ie de verouderde iostream.h gebruikt

maar persoonlijk vind ik de c++ variant van flex wel bagger hoor. En van bison is er niet eens een C++ variant, dat suckt ook wel

Ik heb laatst eens zitten zoeken naar parser generators, en eigenlijk de enige potentieel goede die ik heb gevonden is ANTCC, die ook C++ parsers kan genereren en automatisch een AST bouwt. Ik heb het toen echter niet gebruikt omdat het in java was geschreven, maar het schijnt wel een goede te zijn (ik denk dat mbravenboer of alarmnummer je hierover meer info kunnen geven )

oh, uiteindelijk heb ik gewoon flex++ en bison gebruikt

[ Voor 5% gewijzigd door .oisyn op 08-01-2003 23:26 ]

[Alarmnummer]

ANTLR is idd een scannerless parser (dus lexer en parser bij elkaar) en gebruikt een LL(k) grammatica. (LR grammatica`s zijn trouwens een stuk handiger omdat je lang niet zoveel last hebt van ambiguiteiten). Hij bouwt wel een AST op, maar die is niet echt handig. Ik had liever gezien dat hij nodes zou genereren op basis van de grammatica ipv 1 generieke node. Om al deze redenen gebruik ik nu een beter alternatief: SableCC (zie sig). Er zijn wel plannen om ook backends voor de parsergenerator voor andere talen te schrijven, maar op dit moment is alleen een java backend beschikbaar.

[ Voor 24% gewijzigd door Alarmnummer op 09-01-2003 09:28 ]

[mbravenboer]

Geen alternatief maar wel leuk om even mee te spelen:

Demo: http://www.cwi.nl/themes/sen1/sdf2-demo/index.html
Meer info: http://www.cwi.nl/htbin/sen1/twiki/bin/view/SEN1/SDF2
Nog meer info: http://www.program-transf...wiki/bin/view/Tools/SDFII

[beany]

conclusie: wat ik wil is er niet echt. Alleen flex++ en bison zou een optie kunnen zijn(al is de parser niet C++)

[Alarmnummer]

http://www.antlr.org/pccts133.html

[Zoijar]

Ik heb laatst LLgen (een LL(1) parser gen met statische en dynamische conflict resolvers en ondersteuning voor ebnf grammar notatie) gebruikt in combinatie met flex. Werkte best goed.

Ik vind LR parsers dus niets, met die recursieve gramaticas enzo... Het is wel zo dat je minder last hebt van conflicten in je gramatica, maar die kan je anders meestal heel makkelijk omschrijven. Top-down parsers hebben weer andere voordelen, bv bij L-attributed grammars.

[Alarmnummer]

Zoijar schreef op 09 januari 2003 @ 13:38:
Ik heb laatst LLgen (een LL(1) parser gen met statische en dynamische conflict resolvers en ondersteuning voor ebnf grammar notatie) gebruikt in combinatie met flex. Werkte best goed.

Ik vind LR parsers dus niets, met die recursieve gramaticas enzo...

Ik neem aan dat jij een LL grammatica als beter alternatief bedoelt? LL Grammtica`s zijn qua recursieviteit niets anders hoor (alleen links ipv rechts)

Het is wel zo dat je minder last hebt van conflicten in je gramatica, maar die kan je anders meestal heel makkelijk omschrijven.

In ANTLR kan je syntactische predicaten opstellen, maar zo wordt je taalsyntax echt slecht leesbaar. Een LR grammatica vind ik toch echt tig keer makkelijker werken omdat je maar nog een fractie van de tijd zit te klooien met ambiguiteiten.

Top-down parsers hebben weer andere voordelen, bv bij L-attributed grammars.

Ik zou niet weten wat het is

[ Voor 3% gewijzigd door Alarmnummer op 09-01-2003 14:24 ]

[beany]

Alarmnummer schreef op 09 January 2003 @ 13:09:
http://www.antlr.org/pccts133.html

hmmm, dit ziet er inderdaad wel interessant uit. Ben wel eens eerder op die page geweest, maar ik heb blijkbaar niet goed genoeg gelezen, want het voldoet inderdaad aan mijn eisen.

Heb het inmiddels volledig kunnen compilen(lib en voorbeelden) in mijn mingw compilertje.

Thankx!

[Verwijderd]

Beantwoord misschien niet helemaal je vragen maar heb je dit al gelezen?

[beany]

Verwijderd schreef op 10 januari 2003 @ 10:25:
Beantwoord misschien niet helemaal je vragen maar heb je dit al gelezen?

Ja, die had ik al gevonden Staat veel nuttige info in. Ben nu vol bezig met antlr/pccts

[.oisyn]

Oh, post even wat je bevindingen zijn als het zover is, vind ik ook wel interessant

[beany]

.oisyn schreef op 10 januari 2003 @ 18:08:
Oh, post even wat je bevindingen zijn als het zover is, vind ik ook wel interessant

Nou, een pre-bevinding dan:

Ik heb nog niks zelf geschreven, alleen maar veel gelezen, voorbeelden bekeken/gecompileerd/veranderd/etc

Tot dusver moet ik zeggen dat er erg goed over nagedacht is. Ik ben wat yast/lex gewend, en moet denk ik wel een beetje omschakelen. De .library die bij elk project nodig is compilde keurig onder mingw en C++ 7.0(moest wel een beetje rommelen met include directory's en bestanden die niet gevonden konden worden maar er wel waren).

Wat ook een beetje verwarrend was:

Een voorbeeld had 1 bestand: simple.g

Dus, ikke doe: antlr -CC simple.g

Pleur de gegenereerde code in een C++ project en compilen maar! Euhm, not... DLGLexer.h not found. ikke ->

Ik kon niet helemaal duidelijk vinden wat de bedoeling was, tot ik er per toeval achter kwam dat een voorbeeld gebruiken als volgt werkt:

antlr -CC simple.g
dlg -CC parser.dlg <- deze wordt dus gegenereerd door antlr

En dan de gegenereerde bestanden in een project flikkeren. DLGLexer.h/cpp is dan ook aanwezig. En niet vergeten de library aan je project toe te voegen, en de includes van pccts te gebruiken in je project.

Het aanroepen van een parser is heel netjes. Er is een class(wat je zelf aanmaakt in je .g file, maar afgeleid is van een antlr class) en je kan zelf bepalen wat de start rule is, door deze rule als een methode van het object aan te roepen. Antlr maakt dus van je rules ook methodes in je class. Erg gaaf!

De documentatie is wel redelijk, al had ik wel nog wat meer voorbeelden gewild, maar ik heb ook nog niet erg goed gezocht op internet. Op de pccts site was wel wat te vinden, maar allemaal java (no offense, maar het is gewoon mijn taal niet)

Al met al vind ik het er erg goed uit zien. Ik zag ook dat je C# code kan genereren met een versie van antlr. Ik moet op mijn werk nog wel eens werken met .net, dus dit komt wel goed uit. Verders is er support voor meerdere platformen.

Er zijn nog een hoop dingen waar ik wel wat van heb gezien, maar nog geen idee heb wat het allemaal kan(sorcerer bijvoorbeeld)

edit: het is maar goed dat ik kan programmeren, mijn geld verdienen als reviewer zou niet goed gaan denk ik Zodra ik wat verder ben met pccts zal ik mijn bevindingen posten!

[ Voor 5% gewijzigd door beany op 11-01-2003 00:34 ]

[Zoijar]

Alarmnummer schreef op 09 January 2003 @ 14:23:
[...]

Ik neem aan dat jij een LL grammatica als beter alternatief bedoelt? LL Grammtica`s zijn qua recursieviteit niets anders hoor (alleen links ipv rechts)

Ik drukte me enigszins verkeerd uit. Ik bedoelde eingelijk niet zo zeer LR of LL parsers, maar parser generators die geen EBNF notatie ondersteunen (* + en ?). En het klassieke voorbeeld hiervan zijn LR parsers met flink wat left-recursion.

Overigens is de term LL/LR gramatica niet juist. Elke gramatica die "LL(1) is", ofwel in geparseerd kan worden mbv het LL(1) algorithme, is automatisch ook LR(1). Het is namelijk zo dat elke gramatica die in tijd linear aan de grootte van de input discreet geparseerd kan worden, geparseerd kan worden met LR(1). Dit is niet het geval voor LL(1). LR(1) parsing is dus een stuk sterker dan LL(1), maar gebruikt erg veel geheugen. Daaruit afgeleid is LALR(1) dat vrijwel even sterk is maar een stuk minder geheugen gebruikt. De meeste moderne bottom-up parsers zijn LALR, en voor top-down heb je eigenlijk maar 1 alternatief, LL(1).

[...]

In ANTLR kan je syntactische predicaten opstellen, maar zo wordt je taalsyntax echt slecht leesbaar. Een LR grammatica vind ik toch echt tig keer makkelijker werken omdat je maar nog een fractie van de tijd zit te klooien met ambiguiteiten.

Ja klopt, het opstellen van de gramatica is makkelijker. Toch heb je nog steeds ambiguiteiten die je moet verhelpen (if ... if ... else ...). Verder hebben top-down parsers vaak betere error-recovery wat weer begrijpelijkere foutmeldingen geeft.

[...]

Ik zou niet weten wat het is

Dat is een atomatische vorm van semantische analyse. Je kan bv strong type-checking automatisch laten doen dmv van het schrijven van een attribute grammar. elke AST node heeft dan 2 sets attributen, degene die van de parent worden overgeerfd en degene die aan de kinderen worden doorgegeven. De child nodes kunnen de tweede set ook veranderen.
Je kan dan (recursief) dependencies opzetten tussen die attributen. Bv een operator+ die zijn type attribuut zet aan de hand van het type van de children. Resultaat is een ingewikkelde data-flow machine, waar veel makkelijker code voor te genereren is mbv een top-down parser. (moet anders maar is zoeken op multi- visit- en ordered- attribute grammar)

[mbravenboer]

Zoijar: Ja klopt, het opstellen van de gramatica is makkelijker. Toch heb je nog steeds ambiguiteiten die je moet verhelpen (if ... if ... else ...).

En daarom zou je in bepaalde situaties dan weer voor Generalized LR parsing kunnen kiezen .

Het opstellen van een grammatica is dan pas echt makkelijk. Het hoofddoel hiervan is niet om de ontwerper lui te laten zijn, maar om te helpen bij bijvoorbeeld language prototyping, reengineering en het samenstellen van talen. SGLR support de volledige klasse van context vrije grammatica's, waardoor grammatica's modulair kunnen worden opgezet en samengesteld kunnen worden. Dit is een unieke feature met interessante toepassingen ....