[DISC] Welke parser (generators) gebruiken jullie?

[Verwijderd]

Naar aanleiding van wat recente topics over mensen die zelf parsers aan het schrijven zijn, wilde ik parser generators maar eens onder de aandacht brengen, zoals het woord het al zegt genereer je hiermee, aan de hand van een specificatie van de taal, een parser die instanties van die taal kan parsen.

Ik zal maar beginnen met een Java parser die me zeer goed bevallen is:
CUP, werkt echt super, je kan je grammatica's gewoon opgeven op de volgende manier:

code:

expr_list ::= expr_list expr_part | expr_part
  expr_part ::= expr ';'
  expr  ::= expr '+' expr | expr '-' expr | expr '*' expr 
        | expr '/' expr | expr '%' expr | '(' expr ')'  
          | '-' expr | number

Het enige nadeel van CUP is dat het project een beetje dood is: er wordt al 3 jaar niet meer aan gewerkt

Het leek me wel leuk en vooral handig als jullie hier wat interessante links (graag met vb grammatica's) neerpleuren!

Op die manier zullen waarschijnlijk ook meer mensen inzien dat dit soort dingen eigenlijk helemaal niet zo moeilijk zijn om te (laten ) maken, en dat je eigenlijk wel gek zou zijn als je ze helemaal met de hand in elkaar gaat knutselen.

O ja, wat mij betreft mogen ze alle gangbare programeer talen als output hebben, maar het liefst natuurlijk C++/Java/VB/Delphi/etc zodat ze ook een beetje praktisch te gebruiken zijn...
Voor alle mensen van de UU: hou al die haskel parser generators dus maar bij je

[gjkamstra]

We moesten hier op de uni parsgen en slrpgen gebruiken. Dat zijn krengen. Genereren nog HP pascal code, voor ons inmiddels volledig achterhaalde en dus ook een paar jaar geleden afgescahfte terminal syteem.

[Alarmnummer]

Ik gebruik zelf ANTLR en SableCC. ANTLR kan gigantisch veel en ben er zeer tevreden over. En ik ben nu ook wat aan het experimenteren met SableCC. Deze heeft een (groot) aantal beperkingen zoals:
ik kan niet een willekeurige productie regel aanroepen
ik kan de tokenstream niet te pakken krijgen.

Maar hij zit object technisch beter in elkaar dan ANTLR.

aantal voordelen ANTLR:
llk grammatica
je kan overal bij komen
ambiguiteitscontrole met redelijke goeie foutmelding
zeer goeie documentatie
grote usergroup: zie www.jguru.com

ANTLR site:
http://www.antlr.org

sablecc:
http://www.sablecc.org

ik ga hier geen voorbeeld grammatica plaatsen omdat er uitstekende (vooral bij ANTLR) staan.

ps: er bestaat ook een ANTLR versie die C++ code uithoest

pps: je moet anders dit even doorlezen:
http://www.sablecc.org/thesis/thesis.html
hierin beschrijft hij een aantal parser generators, waaronder Yacc(Cub) JavaCC en ANTLR.

[Verwijderd]

erm, ik wil je feestvreugde niet vergallen hoor ( ) maar 'parser' checkt syntax op basis van tokens aangeleverd door de lexical analyzer. Een emitter genereert de code. Men ziet 'parser' vaak wel als 'het geval dat code genereert', maar dat is niet het geval. Dit ter nodeloze info

(Ik gebruik overigens soms code generator scripts die op basis van stored proc layout call code genereren)

[Alarmnummer]

Meestal als mensen zeggen een parser dan bedoelen ze impliciet ook de lexer. En bij ANTLR is dat een pot nat. Daarin druk je de lexer in dezelfde regels uit waarin je de parser ook uitdrukt. Alleen zijn ze allemaal capitalized.

vb:

code:

class CalcParser extends Parser;
options {
    buildAST = true;    // uses CommonAST by default
}

expr
    :   mexpr (PLUS^ mexpr)* SEMI!
    ;

mexpr
    :   atom (STAR^ atom)*
    ;

atom:   INT
    ;

class CalcLexer extends Lexer;

WS  :   (' '
    |   '\t'
    |   '\n'
    |   '\r')
        { _ttype = Token.SKIP; }
    ;

LPAREN: '('
    ;

RPAREN: ')'
    ;

STAR:   '*'
    ;

PLUS:   '+'
    ;

SEMI:   ';'
    ;

protected
DIGIT
    :   '0'..'9'
    ;

INT :   (DIGIT)+
    ;

[dusty]

Op donderdag 21 maart 2002 23:33 schreef hondass50 het volgende:
[..]
Voor alle mensen van de UU: hou al die haskel parser generators dus maar bij je

Door gebrek aan Joska doe ik het maar: Haskel Rules!

[Infinitive]

* Infinitive kent is nu bezig met Haskell te leren... vind het tot nu toe enorm leuk (veel haskell topics zijn in /14 niet te vinden)

Is Bison of Yacc geen parser generator?

[Alarmnummer]

Op vrijdag 22 maart 2002 00:12 schreef Infinitive het volgende:
* Infinitive kent is nu bezig met Haskell te leren... vind het tot nu toe enorm leuk (veel haskell topics zijn in /14 niet te vinden)

Is Bison of Yacc geen parser generator?

Ik werk zelf met Clean en ik vind het ook een hele leuke taal. Vooral omdat je dus met een hele andere manier met functies omgaat. Alleen heb ik de laatste tijd er niet veel tijd voor

en Bison en Yacc zijn parsers generator/ compiler compilers vanuit het Unix tijdperk

[Verwijderd]

Op vrijdag 22 maart 2002 00:16 schreef Alarmnummer het volgende:
..vanuit het Unix tijdperk

Way back when dinosaurs ruled the earth

[mbravenboer]

Op het moment gebruik ik SGLR in combinatie met SDF.

SGLR:

http://www.program-transformation.org/twiki/bin/view/Tools/GeneralizedLR
http://www.program-transformation.org/twiki/bin/view/Tools/SGLR
http://www.cwi.nl/projects/MetaEnv/sglr/

SDF:

http://www.program-transformation.org/twiki/bin/view/Tools/SDF

PGEN:

http://www.program-transformation.org/twiki/bin/view/Tools/PGEN
http://www.cwi.nl/projects/MetaEnv/pgen/

Smakken GrammarTools:

http://www.program-transformation.org/twiki/bin/view/Tools/GrammarTools

Werkt erg goed . Ik weet wel aardig wat van parsing technieken, maar ben ook weer niet zo'n kenner dat ik de bestaande tools echt goed kan vergelijken. Zie daarvoor de vele publicaties over de filosofie van SGLR .

Handmatig parsers schrijven in Haskell met behulp van parser combinators blijft echter toch echt een hogere vorm van kunst .

[Soultaker]

Op vrijdag 22 maart 2002 01:10 schreef mbravenboer het volgende:
Handmatig parsers schrijven in Haskell met behulp van parser combinators blijft echter toch echt een hogere vorm van kunst .

Als functionele programmeertalen ergens bij uitstek geschikt voor zijn, is het wel het converteren van gegevensstromen van en naar algebraïsche datastructuren. Parsers zijn daar natuurlijk het schoolvoorbeeld van.

Om 't lijstje aan te vullen; een mooie case study over parser combinators in Clean (maar waarschijnlijk ook wel om te zetten naar andere functionele talen zoals Haskell) is te vinden op de volgende URL:

ftp://ftp.cs.kun.nl/pub/Clean/papers/cleanbook/II.05.ParserCombinators.pdf

[marcusk]

Ik gebruik nu GOLD Parser. Deze bestaat uit 'Gold Parser Builder' met ingebouwde editor voor het maken van de grammatica. Deze genereert de DFA en LALR tabellen en slaat ze op in een 'Compiled Grammar Table' bestand. Je kunt het ook gebruiken voor het testen en 'debuggen' van je grammatica. Het gegenereerde CGT bestand kun je vervolgens inlezen met een 'Gold Parser Engine' (een implementatie van de werkelijke lexer en parser). Het voordeel van deze aanpak is dat de genenereerde grammatica in principe te gebruiken is met alle talen, zolang er een 'Engine' voor beschikbaar is. Ik heb zelf een .NET versie van geschreven in C# (zie de nieuwspagina) .

Site van GoldParser: http://www.devincook.com/goldparser/index.htm daar staan ook screenshots en voorbeelden.

[Verwijderd]

Ik gebruik helemaal geen tools, ik parse het zelf

[Alarmnummer]

Op vrijdag 22 maart 2002 12:02 schreef Zef het volgende:
Ik gebruik helemaal geen tools, ik parse het zelf

Mijn eerste parsers die heb ik ook allemaal met de hand geschreven. Eerst opstellen in ebnf (controleren op ambiguiteit) en dan met een vertaal schema naar code omzetten. Na een tijdje heb je het wel gehad en die vertaal slag kan geautomatiseerd worden: de compiler compiler

[Verwijderd]

Op vrijdag 22 maart 2002 12:31 schreef Alarmnummer het volgende:

[..]

Mijn eerste parsers die heb ik ook allemaal met de hand geschreven. Eerst opstellen in ebnf (controleren op ambiguiteit) en dan met een vertaal schema naar code omzetten. Na een tijdje heb je het wel gehad en die vertaal slag kan geautomatiseerd worden: de compiler compiler

Ik weet het, maar ik begin er ook net mee en dan is het nog wel leuk

[Verwijderd]

Op vrijdag 22 maart 2002 01:10 schreef mbravenboer het volgende:Handmatig parsers schrijven in Haskell met behulp van parser combinators blijft echter toch echt een hogere vorm van kunst .

hehe . Maar dan het liefst wel met een klein beetje hulp van de UU_Parsing_Core . Ook het AG systeem van de UU is best wel handig, voor het transformeren na het parsen ... alleen is het wel érg pittig af en toe , maar dat houd je scherp

[Verwijderd]

Op vrijdag 22 maart 2002 13:26 schreef Zef het volgende:

[..]

Ik weet het, maar ik begin er ook net mee en dan is het nog wel leuk

Bovendien zullen de (goeie) automatisch gegenereerde parsers waarschijnlijk ook een stuk efficienter+sneller zijn. Als ik bijvoorbeeld naar de gegenereerde CUP parsers kijk dan gebeuren daar een aantal slimme optimalisaties die je absoluut niet met de hand wilt doen...Nog een reden om parser generators te gebruiken!

[Alarmnummer]

Op vrijdag 22 maart 2002 16:27 schreef hondass50 het volgende:

[..]

Bovendien zullen de (goeie) automatisch gegenereerde parsers waarschijnlijk ook een stuk efficienter+sneller zijn. Als ik bijvoorbeeld naar de gegenereerde CUP parsers kijk dan gebeuren daar een aantal slimme optimalisaties die je absoluut niet met de hand wilt doen...Nog een reden om parser generators te gebruiken!

en wat dacht je van ambiguiteits controle..

[mbravenboer]

KoenM: Maar dan het liefst wel met een klein beetje hulp van de UU_Parsing_Core .

Die wil je idd niet zelf schrijven .

Ook het AG systeem van de UU is best wel handig, voor het transformeren na het parsen ...

Eerlijk gezegd vind ik dat weer een stuk minder . Het AG systeem van Swierstra is heel grappig, maar het is veel te beperkt voor een serieuze toepassing in een productie-compiler imho. Als je High-Performance Compilers of Software Generatie (Programma Transformaties gaat dat volgend jaar heten) gaat volgen maak je kennis met Stratego, een echte transformatie taal .

Stratego biedt veel meer perspectief voor serieuze toepassingen. Het is in principe een generieke transformatie-taal, maar je kunt het met name erg goed toepassen in programma-transformatie toepassingen. Anders toepassingen (richting XSLT achtige tranformaties) kunnen ook erg interessant zijn, maar op dit moment wordt het in feite alleen nog maar voor compilerbouw of andere programma-transformaties gebruikt Je kunt er buitengewoon fraai een volledige retargetable compiler in schrijven. Het AG-systeem is hiermee vergeleken niet echt een aantrekkelijke omgeving...

* mbravenboer is voor zijn afstuderen voornamelijk met Stratego bezig .

[igmar]

Op donderdag 21 maart 2002 23:33 schreef hondass50 het volgende:
Naar aanleiding van wat recente topics over mensen die zelf parsers aan het schrijven zijn, wilde ik parser generators maar eens onder de aandacht brengen, zoals het woord het al zegt genereer je hiermee, aan de hand van een specificatie van de taal, een parser die instanties van die taal kan parsen.

Ik gaat gewoon voor lex / yacc. Enige nadeel is dat ie redelijk grote code genereren (hoofdzakelijk door de lookup tables).

[Alarmnummer]

hehe.. eindelijk topic gevonden

een handige link:
http://catalog.compilertools.net/java.html

[CyberSnooP]

Wat ik ook nog wel aardig vind om de horen is:
Waarvoor gebruiken jullie de gegenereerde parsers in de praktijk?

[Alarmnummer]

hmmm... wilde gok... tekst parsen

[Verwijderd]

Kommop, zijn er niet meer mensen die nog goeie generators weten???

De laatste keer dat ik n parser generator nodig had was dat voor het parsen van een eigen IDL achtig taaltje om de interfaces te specificeren voor een eigen XMLRPCachtige implementatie. Ben ook wel benieuwd wat jullie ermee doen...

[Alarmnummer]

Op deze pagina`s staan wel de meeste parser generators voor java. Je moet deze link:
http://www.sablecc.org/thesis/thesis.html
anders maar even goed bekijken. Daarin geeft hij uitleg over een aantal java parser generators met alle plus en min punten erbij. Ik heb persoonlijk genoeg aan ANTLR.

[Verwijderd]

Op woensdag 03 april 2002 10:41 schreef Alarmnummer het volgende:
... Je moet deze link:
http://www.sablecc.org/thesis/thesis.html
anders maar even goed bekijken....

Kijk, das nou een interessante link (die had ik om een of andere reden in een vorige post van je over het hoofd gezien)! Erg handig dat de verschillende java PG's met elkaar vergeleken worden en de voor- en nadelen gegeven worden. Dat SableCC ziet er zo op het eerste gezicht erg goed uit, zal er binnenkort eens mee gaan spelen

[Alarmnummer]

deze link is ook aardig:
http://catalog.compilertools.net/java.html
(voor een overzicht)

Object technisch gezien zit SableCC heel leuk in elkaar, hij is al helemaal Visitor klaar en heeft ook een aantal Guide`s. Helaas zijn sommige dingen niet mogelijk zoals: token stream aanspreken en op een willekeurge productie regel beginnen. (alleen via omweg).