Parser/Compiler bouw

[technocow]

Ik wil me verdiepen in parser/compiler ontwikkeling. Op internet heb ik naar boeken gezocht, daar kwam ik op: 'Compiler Principle Techniques' oftwel het 'Dragon Book'. Alleen dit boek komt uit `1986.
Is dit niet een beetje outdated? Kunnen jullie me goede boeken aanraden?

[mbravenboer]

Het is nog steeds een erg goed boek. Tegenwoordig wordt "Modern Compiler Implementation in Java/ML/C" van Andrew Appel ook wel goed gewaardeerd.

Hier vind je een korte beschrijving van een paar boeken:
http://www.cs.uu.nl/docs/vakken/ipt/material.html

[mbravenboer]

Knuth wil trouwens ook gaan werken aan een deel over parsers in zijn "The Art of Computer Programming" serie, maar ik betwijfel eerlijk gezegd of hij dat haalt

[Verwijderd]

Ik ben op het moment bezig met Modern Compiler Design. Verder een heel uitgebreid boek, maar volgens sommigen wat te abstract. Goeie punten van het boek zijn o.a. dat ook andere paradigma's worden behandeld (functioneel, distributed, oo, etc.), zowel voor implementatie- en targetlanguage.

[Verwijderd]

Een kritische noot:

ISBN = het DNA voor boeken.

[Verwijderd]

Verwijderd schreef op 01 April 2003 @ 19:28:
Een kritische noot:

ISBN = het DNA voor boeken.

Compilers: Principles, Techniques, and Tools - 0201100886
Modern Compiler Implementation in C : Basic Techniques - 0521586534
Modern Compiler Implementation in Java - 052182060X

[EfBe]

The dragon book is erg goed en zeker niet outdated.

Hier een link, die heb ik toch in control-c buffertje zitten, naar de LR(0) parser techniek met goede uitleg:
http://www.wikipedia.org/wiki/LR(0)_parser

[unclero]

Misschien ook een idee, de broncode van een compiler doorbladeren. Small C is bijvoorbeeld een kleine (en een van de eerste) C Compiler.

[mbravenboer]

Er is zelfs een boek geschreven over de source van een compiler: "A retargetable C compiler: design and implementation" (ISBN ga ik niet opzoeken ).

Het probleem van het bestuderen van de sources van een C compiler is met name dat een groot deel van het boek gaat over alle (soms merkwaardige) regels die gelden voor C. Daarom kiest Andrew Appel bijvoorbeeld voor een wat serieuzere speelgoed taal (Tiger). Deze taal wordt tegenwoordig veel gebruikt om allerlei ideeen over compilers (optimalisaties bijv) te implementeren en publiceren.

[alienfruit]

In de Delphi Magazine van een tijdschrift heeft de verantwoordelijke voor de compilers van Borland een artikel hierover geschreven. Dit was wel een intressant artikel het is dan wel Delphi-wise maar is makelijk te converten naar C(++).

Maar goed het is een goed idee om eerst alles uit te werken, en vervolgens aan de lexer te werken; en volgens een klasse die tokens verwerkt tot code. Zelfs vind ik het idee;
lexer -> executor -> running idee goed; dat je eerste alles omzet naar een soort assembler achtige psuedo code dat vervolgens via een runner/executor kan worden gerunned; bij een script-engine.

Maar ja, je moet als je een echte compiler natuurlijk assembler code gaan schrijven; die volgens de code kunnen uitspugen voor een executable (wordt uitgelegd in het artikel).

[mbravenboer]

alienfruit: Maar goed het is een goed idee om eerst alles uit te werken, en vervolgens aan de lexer te werken; en volgens een klasse die tokens verwerkt tot code.

Persoonlijk vind ik het helemaal geen goed idee om veel tijd in een lexer/parser te steken. Als je een compiler gaat schrijven die heel de wereld gaat gebruiken is het belangrijk dat een lexer/parser uitstekende performance heeft en dan kan handmatige implementatie hiervan interessant zijn.

Als je echter zelf wilt experimenteren met compilerbow, of een compiler moet schrijven die slechts beperkt gebruikt wordt en snel aangepast moet kunnen worden (omdat hij bijvoorbeeld werkt op een taal die nog in beweging is) dan wil je niet veel tijd besteden aan componenten die je ook uitstekend kan genereren. Lexers/parsers zijn het ultieme voorbeeld van een probleem waar code generatie nuttig is gebleken in de praktijk.

Parsers genereer je dus, compilers schrijf je. Een compiler mag tegenwoordig ook best op een AST werken.

[alienfruit]

Ja. Een parser maak je dus ook met de hand; die geneerde parsers zijn meestal langzaam. Overigens bedoelde ik met het uitwerken dus eerst op het papier schrijven hoe en wat qua regels van de taal en hoe je wilt opslaan etc. Compilers maken is overigens ook niet echt probleem Code Optimizing en EXE generatoring vind ik nou het rotste werk; ik werk nog steeds met een linker die van de genereerde asm code een executable maakt

Als je een idee hebt mbravenboer dan hoor ik het graag :-)

[mbravenboer]

alienfruit: Ja. Een parser maak je dus ook met de hand

Tja, dat mag jij gerust doen, maar ik doe het in ieder geval niet. Ik houd me liever bezig met zaken die relevant zijn voor een specifieke compiler en wat ik kan produceren door te specificeren (met een domein specifieke specificatie, in dit geval een context-vrije grammatica), ga ik niet met de hand schrijven.

Zoals ik al zei, performance wordt relevant als er een grote gebruikersgroep is die je niet kan belasten met een mindere performance van een compiler. Voor veel situaties kan je de gebruikers daar echter wel mee belasten omdat ze geinteresseerd zijn in wat de compiler doet en niet in hoe snel de compiler dat doet.

Compilers maken is overigens ook niet echt probleem

Dat hangt er maar vanaf wat je onder een compiler rekent. Instructie selectie en diverse optimalisatie stappen valt ook onder de overkoepelende naam compiler en is toch geen triviaal probleem. Het uitpoepen van een binary executable is een kwestie van specificaties lezen en rotwerk doen: daarom besteden we dat bij voorkeur ook uit aan een assembler .

Compilers zijn tegenwoordig te complex om ze als monolithisch geheel te zien. Vrijwel alle boeken presenteren het probleem van compiler implementatie in een aantal fasen, componenten. Op deze manier zouden ze in veel gevallen ook geimplementeerd moeten worden, waarbij je zoveel mogelijk bestaande tools gebruikt.

Maar een heel klein deel van alle geschreven compilers wordt gebruikt door een enorme gebruikersgroep (denk dan aan gcc, jikes, javac en dergelijke). De vereisten die gelden voor deze compilers moet je niet doorvoeren naar compiler implementatie in het algemeen: waarschijnlijk zal je nooit werken aan een compiler met deze requirements.

[stekkel]

alienfruit schreef op 02 April 2003 @ 10:38:
Ja. Een parser maak je dus ook met de hand; die geneerde parsers zijn meestal langzaam.

Tja, ik ben zelf druk bezig met een imap parser in PHP en die maak ik dus met hand maar ben ernstig aan het twijfelen of het niet beter is om een abstracte parser te maken waar ik de BNF in gooi, de functies aan hang zodat het breder te gebruiken is.
Er zijn zoveel parallellen tussen lappen server output van welk protocol dan ook (in mijn geval de imap responses) dat het wellicht de moeite waard is om daar wat meer tijd in te steken.

Het enige waar ik mij wel zorgen over maak is de snelheid van zo'n gegenereerde parser. Wellicht is het een idee om een soort compiler te schrijven die geoptimaliseerde PHP code uitspuugd en die je vervolgens weer in je script kan hangen.

Weet iemand of dat al eens gedaan is? Het wiel opnieuw uitvinden is namelijk een beetje zonde.

[mbravenboer]

stekkel: Het enige waar ik mij wel zorgen over maak is de snelheid van zo'n gegenereerde parser. Wellicht is het een idee om een soort compiler te schrijven die geoptimaliseerde PHP code uitspuugd en die je vervolgens weer in je script kan hangen.

Weet iemand of dat al eens gedaan is? Het wiel opnieuw uitvinden is namelijk een beetje zonde.

Uhme .... er bestaan letterlijk bergen parser generatoren, dus dat is zeker al eens gedaan . Deze parser generatoren werken allemaal op een grammatica definitie en produceren dan een parser. Soms kan je akties opnemen in de grammatica, soms kan je daarna op een AST representatie verder werken (waarbij het maken van de AST soms weer akties in een grammatica zijn). Er zijn veel verschillende parser generatoren. Ze verschillen met name in de subklasse van de context-vrije grammatica die ze accepteren (LR, LL bijvoorbeeld), in de programmeertaal waarin ze code produceren en in kwaliteit/snelheid van de gegenereerde code.

[Verwijderd]

Ik denk, in tegenstelling tot wat sommigen hier denken, dat gegenereerde parsers juist veel sneller zijn. Dan bedoel ik natuurlijk wel een parser voor een redelijk complex probleem (zoals voor een compiler). Een gegenereerde parser is namelijk het resultaat van een behoorlijke hoeveelheid precomputation.

Ik ga er vanuit dat bij een handgeschreven parser, je gebruik van een recursive descent parser (een bottom up is denk ik ietsje te complex ). Dan zit je al met het feit dat veel tokens meerdere keren moeten worden gecheckt. Een gegenereerde, bottom-up parser, heeft echter vaak aan een 'check' voldoende informatie om de volgende actie te bepalen. Ik durf dus wel het tegengestelde te beweren.

[mbravenboer]

Het hangt er natuurlijk nogal sterk vanaf hoeveel inspanning je stopt in de parser: ik ga er vanuit dat als je zo'n kreng al met de hand gaat schrijven, je daar een goede reden voor hebt en dat die reden onder andere performance is.

Er is nog wel een andere reden waarom je een parser met de hand zou willen schrijven voor een breed gebruikte compiler: de error-reporting is bij de meeste parser generatoren is nogal bagger .... Met kennis van de taal die geparsed wordt en alle heuristieken over het gebruik ervan (de gemaakte fouten) kan je in een handcrafted parser goed error reporting inbouwen....

In principe zou je ook een parser generator kunnen schrijven die naast een grammatica een specificatie van dergelijke gebruiksgegevens als input neemt en die gebruikt om error reporting te genereren. Ik ken echter geen parser generator die dat doet (gat in de markt? ).

[mbravenboer]

In het algemeen moet ik trouwens wel zeggen dat je een goed punt hebt dat een code generator het vaak beter kan doen dan handgeschreven code.

Met veel inspanning kan je die handgeschreven code uiteraard altijd weer beter maken. Voor een code generator krijg je met dezelfde (of misschien zelfs minder) inspanning een optimaliserend effect op alle gegenereerde code.

[.oisyn]

mbravenboer schreef op 02 April 2003 @ 19:44:
In principe zou je ook een parser generator kunnen schrijven die naast een grammatica een specificatie van dergelijke gebruiksgegevens als input neemt en die gebruikt om error reporting te genereren. Ik ken echter geen parser generator die dat doet (gat in de markt? ).

je kunt met yacc/bison speciale error rules toevoegen, en aan de hand daarvan kun je per rule een vrij mooie error genereren. Ook kun je hierdoor parse errors opnemen in je AST, en hoef je niet bij de eerste de beste parse error gelijk het hele parse proces te stoppen

Nadeel hiervan is wel dat je grammatica nogal vol komt te staan met al die lelijke error rules.

[Verwijderd]

mbravenboer schreef op 02 April 2003 @ 19:44:
Het hangt er natuurlijk nogal sterk vanaf hoeveel inspanning je stopt in de parser: ik ga er vanuit dat als je zo'n kreng al met de hand gaat schrijven, je daar een goede reden voor hebt en dat die reden onder andere performance is.

Het hangt denk ik van de grootte van het probleem af. Ik denk dat het vrijwel ondoenlijk is om een parser voor bijv. c++ met de hand te schrijven, laat staan deze sneller te maken dan een gegenereerde .

Er is nog wel een andere reden waarom je een parser met de hand zou willen schrijven voor een breed gebruikte compiler: de error-reporting is bij de meeste parser generatoren is nogal bagger .... Met kennis van de taal die geparsed wordt en alle heuristieken over het gebruik ervan (de gemaakte fouten) kan je in een handcrafted parser goed error reporting inbouwen....

Dit is idd een goed punt. De meeste gegenereerde parsers zijn LR, en zitten bij een fout opgescheept met een haf voltooide constructie en een stroom tokens. Ze kunnen dan vaak alleen aangeven welke tokens er verwacht werden. Een nog groter probleem is de error recovery.

In principe zou je ook een parser generator kunnen schrijven die naast een grammatica een specificatie van dergelijke gebruiksgegevens als input neemt en die gebruikt om error reporting te genereren. Ik ken echter geen parser generator die dat doet (gat in de markt? ).

Toevalig ben ik net bezig om dit punt in m'n eigen generator te verbeteren (Geeft nu nog de uiterst nuttige melding "Invalid token" ). Misschien dat ik hier eens wat mee kan experimenteren.

[Verwijderd]

mbravenboer schreef op 02 april 2003 @ 19:47:
In het algemeen moet ik trouwens wel zeggen dat je een goed punt hebt dat een code generator het vaak beter kan doen dan handgeschreven code.

Met veel inspanning kan je die handgeschreven code uiteraard altijd weer beter maken. Voor een code generator krijg je met dezelfde (of misschien zelfs minder) inspanning een optimaliserend effect op alle gegenereerde code.

Ik denk ook niet dat je slim bezig bent als je erg veel tijd gaat steken in het maken van een parser. Het effect op de snelheid van de uiteindelijke compiler zal minimaal zijn. Als je die tijd steekt in andere gedeelten (zoals context handling en code generatie) in bijv. het verbeteren van algoritmen (of vriendelijke errormessages ) dan zal het netto resultaat denk ik beter zijn.

[NetForce1]

De TS wil zich verdiepen in parser/compiler ontwikkeling, dit betekend imo dat hij er nog niets mee gedaan heeft. Ik denk dat het wel slim is om eerst eens een keer zelf een parser te schrijven, in dit soort gevallen moet je denk ik toch wel weten hoe zoiets nou in elkaar zit.
(misschien geen goed voorbeeld, maar technisch tekenen moet je op school toch ook eerst met de hand doen, en dan pas op de computer)

[Soultaker]

Als toevoeging op NetForce1: het lijkt me zeker wel nuttig om je een beetje rond in te lezen voordat je zelf dingen gaat schrijven; daardoor leer je veel sneller dan wanneer je alles zelf zou uitzoeken (wat ook wel leuk en leerzaam is, maar veel langer duurt en niet altijd de gewenste resultaten oplevert). Ik ben het er echter mee eens dat het niet zo zinnig is om direct een parser generator te gebruiken, als je doel het schrijven van een eigen parser was. Als je een ander doel hebt, kan ik me echter weer goed voorstellen dat je dit deel van het werk wilt delegeren aan een programma dat 't ook prima kan.

Samenvattend: het is altijd nuttig om te lezen over hoe dingen werken, maar echt leren doe je door eigen ervaring op te doen met de materie. Tools leren gebruiken is ook nuttig, maar daarvan leer je niet programmeren.

[Alarmnummer]

En dan te bedenken dat de parser eigelijk wel een van de minst interessante onderdelen is van een compiler

[Bananenplant]

wild idee: als je toevallig studeert kun je ook proberen of je een vak bij de afdeling informatica van je uni kan volgen. in Groningen gaat het vak vertalerbouw er geloof ik over.

[Alarmnummer]

ucchan schreef op 03 April 2003 @ 10:15:
wild idee: als je toevallig studeert kun je ook proberen of je een vak bij de afdeling informatica van je uni kan volgen. in Groningen gaat het vak vertalerbouw er geloof ik over.

Dat lijkt me trouwens nog wel een keer interessant om te volgen Op de RuG geven ze nu ook (eindelijk) design patterns, ik denk dat ik daar ook nog wel een keer kom te kijken

[Bananenplant]

offtopic:
eh, als je het vak 'softwareanalyse en -ontwerp bedoelt: dat is tijdverspilling, dat heb ik net gehad. en heb er geen flikker van geleerd.

[alienfruit]

Ach. Ik heb het niet zo op gegeneerde parser code; die maken toch brakek code imho
Dat is de grootste reden waarom ik het zelf doe

[.oisyn]

alienfruit schreef op 03 april 2003 @ 11:53:
Ach. Ik heb het niet zo op gegeneerde parser code; die maken toch brakek code imho
Dat is de grootste reden waarom ik het zelf doe

wat bedoel je met brakke code? Kun je dat eens onderbouwen?

[Soultaker]

alienfruit schreef op 03 april 2003 @ 11:53:
Ach. Ik heb het niet zo op gegeneerde parser code; die maken toch brakek code imho
Dat is de grootste reden waarom ik het zelf doe

Ik denk dat de kans dat jij een foutje maakt heel wat groter is, dan dat een automatische parser generator dat doet. Zo'n parser volgt immers simpelweg een aantal patronen. Wordt zo'n patroon eenmaal goed toegepast, dan zal dat altijd zo zijn.

[tomato]

Inderdaad, het met de hand schrijven van een parser blijf je niet doen als je wat serieuzer aan de slag gaat. Maar zoals anderen ook vonden denk ik dat het wel degelijk een goed idee is dat eerst juist wel te doen.

Ik weet niet hoe ver je je er in wilt verdiepen, hoe formeel je alles wilt hebben, waar je het voor wilt gebruiken etc, maar misschien vind je de 'Compiler Building Tutorial' van Jack W. Crenshaw iets. Weinig abstract en formeel geneuzel, maar gewoon doen en op die manier leren hoe het werkt. Wil je de theorie erachter echter goed in je hoofd krijgen is dit misschien niet de beste aanpak.

[edit] Linkje werkte niet meer, verwijst nu naar overzichtspagina waar je de PDF kunt downloaden.

[ Voor 9% gewijzigd door tomato op 05-04-2003 18:56 ]

[Verwijderd]

ucchan schreef op 03 April 2003 @ 11:09:

offtopic:
eh, als je het vak 'softwareanalyse en -ontwerp bedoelt: dat is tijdverspilling, dat heb ik net gehad. en heb er geen flikker van geleerd.

offtopic:
Dat is meer jou fout dan die van het vak. DPs zijn behandeld, er is een boek aangeraden, je moet ze kunnen toepassen en herkennen, wat verwacht je meer?

Maar goed ik breng het topic weer eens offtopic

[Verwijderd]

tomato schreef op 03 April 2003 @ 21:56:
Ik weet niet hoe ver je je er in wilt verdiepen, hoe formeel je alles wilt hebben, waar je het voor wilt gebruiken etc, maar misschien vind je de 'Compiler Building Tutorial' van Jack W. Crenshaw iets. Weinig abstract en formeel geneuzel, maar gewoon doen en op die manier leren hoe het werkt. Wil je de theorie erachter echter goed in je hoofd krijgen is dit misschien niet de beste aanpak.

Die heb ik inderdaad ook een keer doorgewerkt, veel van geleerd. Het is dan wel in pascal, maar dat doet in principe niet zo terzake.

[Alarmnummer]

[html:P]
Not Found
The requested URL /~michelou/links/compiler/compiler.pdf was not found on this server.
[/html:P]

[mbravenboer]

http://compilers.iecc.com/crenshaw/

[Janoz]

ucchan schreef op 03 April 2003 @ 10:15:
wild idee: als je toevallig studeert kun je ook proberen of je een vak bij de afdeling informatica van je uni kan volgen. in Groningen gaat het vak vertalerbouw er geloof ik over.

Ja, maar daar ga je juist met een generator aan de slag om een interpreter te bouwen. (Wel leuk trouwens dat je vervolgens met de simpele operatoren een leuke wortelfunctie kunt definieren , maar dat is natuurlijk vooral wiskunde )

[alienfruit]

Dit artikel op Delphi Informant is wel interessant is geschreven door een Borland medewerker die werkt aan de compilers:

https://www.delphizine.co...0204fv_f/di200204fv_f.asp

[ Voor 4% gewijzigd door alienfruit op 04-04-2003 13:33 . Reden: woeps ]

[NetForce1]

alienfruit schreef op 04 april 2003 @ 13:33:
Dit artikel op Delphi Informant is wel interessant is geschreven door een Borland medewerker die werkt aan de compilers:

https://www.delphizine.co...0204fv_f/di200204fv_f.asp

Helaas, members only

[alienfruit]

Als je wil kan ik de bestanden wel e-mailen, of je moet de auteur mailen die stuurt ze dan ook naar jouw op

[CyberSnooP]

Mocht dat punt nog niet helemaal duidelijk zijn: Leren doe je niet met generatoren.
Als je echter het principe van een parser begrepen hebt en je wil je op de andere compiler onderdelen storten is er niks mis met die dingen gebruiken. Bovendien dwingen ze je om op z'n minst een werkbare Grammatica te formuleren.

Daarnaast lijkt me het onderwerp compilers bij uitstek geschikt om aan de hand van een boek te behandelen. Bekijk / Leen (universiteits / faculteits bibliotheek?)/ Koop dus eens van de hier genoemde titels, dan kom je al een heel stuk verder.

Overigens verwacht ik dat de meeste boeken over compilers best wel wat voorkennis vereisen, dus schrik niet als je begint en zoek desnoods naar boeken die de auteur aanbeveelt als voorkennis.

[mbravenboer]

CyberSnooP: Mocht dat punt nog niet helemaal duidelijk zijn: Leren doe je niet met generatoren.

In het algemeen heb je zeker gelijk, maar het gaat er met name om wat je wilt leren. Voor het implementeren van nuttige compilers en programma transformaties in het algemeen heb je in principe geen kennis van parsing algoritmen nodig. Je zal uiteraard moeten weten wat een grammatica is, wat een abstract syntax tree is en wat een parser doet, maar er is geen enkele reden waarom je jezelf moet martelen met de details van specifieke parsing algoritmen en zeker niet met de implementatie ervan. Als je juist wilt leren hoe je een parser bouwt, tja, uiteraard moet je het in de situatie juist wel wel weten.

Ik kan dit simpel illustreren aan de hand van mijn eigen situatie. Ik ben full-time bezig met de implementatie van (programma) transformaties. Als ik nu zonder boek een parser zou moeten schrijven, zou ik echter een groot probleem hebben. Ik zou het absoluut niet redden. Ik heb nooit een volledige parser geimplementeerd in een imperatieve taal en in feite alleen maar grammaticas gedefinieerd in de diverse subklassen (of de volledige klasse ) van context-vrije grammaticas. Zou ik paraat willen hebben hoe ik handmatig parsers moet implementeren? Tuurlijk, geen bezwaar tegen. Belemmert dit gebrek me echter? Allerminst: het gaat niet om het schrijven van parsers, het gaat om het schrijven van goede transformaties. Parsers genereer ik uit context-vrije grammaticas. Voor veel van het werk wat ik doe zou conventionele parser technologie geeneens toereikend zijn en kan ik dus geeneens de bekende algoritmen toepassen. Als ik ooit een high performance parser moet gaan schrijven voor een specifieke taal, pak ik gewoon een boek en zoek het uit.

Moraal van het verhaal: beslis wat je wilt leren en verdoe je tijd niet met dingen die je niet wilt leren .