Abstract
Dit proefschrift handelt over het ontwerp van de compilergenerator Elegant. Een compiler
generator is een computer programma dat vanuit een speci??catie een compiler kan genereren.
Een compiler is een computer programma dat een gestructureerde invoertekst kan vertalen
in een uitvoertekst. Een compiler generator is zelf een compiler welke de speci??catie vertaalt
in de programmatekst van de gegenereerde compiler. Dit heeft het mogelijk gemaakt om
Elegant met zichzelf te genereren. Van een compilergenerator wordt verlangd dat deze een
krachtig speci??catie formalisme vertaalt in een eÆci??ent programma, een eis waar Elegant
aan voldoet.
Een compiler bestaat uit een aantal onderdelen, te weten een scanner, een parser, een
attribuutevaluator, een optimalisator en een codegenerator. Deze onderdelen kunnen door
het Elegant systeem geneneerd worden, ieder uit een aparte speci??catie, met uitzondering
van de parser en attribuutevaluator, welke gezamenlijk worden beschreven in de vorm van
een zogenaamde attribuutgrammatica.
De scanner wordt gegenereerd met behulp van een scannergenerator en heeft tot taak de
invoertekst te splitsen in een rij symbolen. Deze rij symbolen kan vervolgens ontleed worden
door een parser. Daarna berekent de attribuutevaluator eigenschappen van de invoertekst
in de vorm van zogenaamde attributen. De attributenwaarden vormen een datastructuur.
De vorm van deze datastructuur wordt gede??nieerd met behulp van typeringsregels in de
Elegant programmeertaal. De optimalisator en codegenerator voeren operaties op deze
datastructuur uit welke eveneens beschreven worden in de Elegant programmeertaal.
Dit proefschrift beschrijft de invloed die functionele programmeertalen hebben gehad op
het ontwerp van Elegant. Functionele talen zijn programmeertalen met als belangrijkste
eigenschap dat functies een centrale rol vervullen. Functies kunnen worden samengesteld
tot nieuwe functies, ze kunnen worden doorgegeven aan functies en worden opgeleverd als
functieresultaat. Daarnaast staan functionele talen niet toe dat de waarde van een variable
wordt gewijzigd, het zogenaamde nevene??ect, in tegenstelling tot imperatieve talen die zo'n
nevene??ect wel toestaan. Deze laatste beperking maakt het mogelijk om met behulp van
algebra??ische regels een functioneel programma te herschrijven in een ander functioneel programma
met dezelfde betekenis. Dit herschrijfproces wordt ook wel progammatransformatie
genoemd.
De invloed van functionele talen op Elegant omvat:
?? Het beschrijven van ontleedalgorithmen als functionele programma's. Traditioneel
worden ontleedalgorithmen beschreven met behulp van de theorie van stapelautomaten.
In hoofdstuk 3 wordt aangetoond dat deze theorie niet nodig is. Met behulp
van programmatransformaties zijn vele uit de literauur bekende ontleedalgorithmen
af te leiden en worden ook nieuwe ontleedalgorithmen gevonden. Deze aanpak maakt
het bovendien mogelijk om de vele verschillende ontleedalgorithmen met elkaar te
combineren.
?? De evaluatie van attributen volgens de regels van een attribuutgrammatica blijkt eveneens
goed te kunnen worden beschreven met behulp van functionele talen. Traditioneel
bouwt een ontleedalgorithme tijdens het ontleden een zogenaamde ontleedboom op.
Deze ontleedboom beschrijft de structuur van de invoertekst. Daarna wordt deze
ontleedboom geanalyseerd en worden eigenschappen ervan in de vorm van attributen
berekend. In hoofdstuk 4 van het proefschrift wordt aangetoond dat het niet nodig
is de ontleedboom te construeren. In plaats daarvan is het mogelijk om tijdens het
ontleden functies die attributen kunnen berekenen samen te stellen tot nieuwe functies.
Uiteindelijk wordt er zo ??e??en functie geconstrueerd voor een gehele invoertekst.
Deze functie wordt vervolgens gebruikt om de attribuutwaarden te berekenen. Voor
de uitvoering van deze functie is het noodzakelijk gebruik te maken van zogenaamde
"luie evaluatie". Dit is een mechanisme dat attribuutwaarden slechts dan berekent
wanneer deze werkelijk noodzakelijk zijn. Dit verklaart de naam Elegant, welke een
acroniem is voor "Exploiting Lazy Evaluation for the Grammar Attributes of Non-
Terminals".
?? Scanners worden traditioneel gespeci??ceerd met behulp van zogenaamde reguliere expressies.
Deze reguliere expressies kunnen worden afgebeeld op een eindige automaat.
Met behulp van deze automaat kan de invoertekst worden geanalyseerd en gesplitst
in symbolen. In hoofdstuk 5 wordt uiteengezet hoe functionele talen het mogelijk
maken om scanneralgorithmen te construeren zonder gebruik te maken van automatentheorie.
Door een reguliere expressie af te beelden op een functie en de functies
voor de onderdelen van samengestelde reguliere expressies samen te stellen tot nieuwe
functies kan een scannerfunctie geconstrueerd worden. Door gebruik te maken van
programmatransformaties kan deze scanner deterministisch worden gemaakt en minimaal
worden gehouden.
?? Het typeringssysteem van Elegant wordt beschreven in hoodstuk 6 en vormt een
combinatie van systemen die in functionele en imperatieve talen worden gevonden.
Functionele typeringssystemen omvatten typen welke bestaan uit een aantal varianten.
Elk van deze varianten bestaat uit een aantal waarden. Bij een dergelijk
typeringssysteem wordt een functie gede??ni??eerd door middel van een aantal deeelfuncties.
Elke deelfunctie kan met behulp van zogenaamde patronen beschrijven voor
welke van de varianten hij gede??ni??eerd is. Het blijkt dat imperatieve typesystemen
welke subtypering mogelijk maken een generalisatie zijn van functionele typesystemen.
In deze generalisatie kan een patroon worden opgevat als een subtype en een
deelfunctie als een parti??ele functie. Het Elegant typesystemen maakt deze vorm van
typering en functiebeschrijving mogelijk. Bij toepassing van een functie wordt de bijbehorende
deelfunctie geselecteerd door de patronen te passen met de waarden van
de actuele functieargumenten. In dit proefschrift wordt een eÆci??ent algorithme voor
dit patroonpassen met behulp van programmatransformaties afgeleid uit de de??nitie
van patronen.
Het Elegant typeringssystemen bevat ook typen voor de modellering van luie evaluatie.
De aanwezigheid van nevene??ekten maakt het mogelijk om drie verschillende
luie typen te onderscheiden, welke verschillen in de wijze waarop de waarde van een
lui object stabiliseert.
?? In hoofdstuk 7 wordt aangetoond dat de regels uit een attribuutgrammatica ook
kunnen worden gebruikt om eigenschappen van een datastructuur te berekenen in
plaats van eigenschappen van een invoertekst. Elegant biedt de mogelijkheid om
zulke attribuutregels te gebruiken voor dit doel.
?? In hoofdstuk 8 tenslotte worden de Elegant programmeertaal en de eÆci??entie van
de Elegant vertaler en door Elegant gegenereerde vertalers ge??evalueerd. Het blijkt
dat de imperatieve Elegant programmeertaal dankzij abstractie mechanismen uit
functionele talen een zeer rijke en krachtige taal is. Daarnaast zijn zowel Elegant
zelf als de door Elegant gegenereerde vertalers van hoge eÆci??entie en blijken geschikt
voor het maken van compilers voor professionele toepassingen.
Original language | English |
---|---|
Qualification | Doctor of Philosophy |
Awarding Institution |
|
Supervisors/Advisors |
|
Award date | 7 Oct 1993 |
Place of Publication | Eindhoven |
Publisher | |
Print ISBNs | 90-74445-04-7 |
DOIs | |
Publication status | Published - 1993 |