Examenvragen CC 2014-2015 Misschien krijg je van sommige vragen slechts een deel op het examen, of een combinatie van stukken uit verschillende vragen. Lexical analysis De eerste fase van de compiler is de lexicale analyse. Hier zet de compiler de invoerstroom van karakters om naar een outputstroom van tokens m.b.v. eindige automaten. Hoe kan men dit implementeren? Wanneer noem je iets een token in deze context? Longest match en rule priority lossen ambigu¨ıteit in deze fase op. Leg beide concepten uit en geef telkens een voorbeeld. Hoe gaat men om met lexicale fouten? Hoe werken lexicale analysegeneratoren? Hoe communiceert de lexicale analyse met de syntactische analyse? Parsing Leg predictive (of recursive-descent) parsing uit. Waarom hebben we FIRST, FOLLOW en NULLABLE nodig en hoe worden ze gebruikt bij het opstellen van de predictive parsing table? Hoe worden die verzamelingen berekend? Hoe gebruik je de parsing table? Hoe komt het tot uiting dat je een programma in een taal met een zekere grammatica niet kan parsen? Ligt dit aan de grammatica of de taal en in welke gevallen kan je er iets aan doen? Leg uit. (LR-parsing) Wat is LR-parsing, hoe stel je een parse table op voor een LR(1) grammatica, hoe gebruik je die? Leg verschillende manieren uit om om te gaan met ambigu¨ıteiten in de grammatica, op het niveau van de grammatica, het gebruik van parse-tables, en een parsergenerator. Error recovery: In het boek staan 2 mechanismen: • Local error repair: Error symbol • Global error repair: Burke-Fisher methode Omschrijf en vergelijk beide mechanismen: • Wat is het? • Hoe werkt het? • Voor- en nadelen? • Kan je ze beide gebruiken voor LL en LR parsing? 1 Abstract Syntax - Semantic Analysis 1. Welke voordelen zijn er aan het omzetting van de parse tree naar een abstract syntax tree in deze fase? 2. Wat zijn symbooltabellen, hoe werken ze en waarom zijn ze nodig? Waarom zou je symbolen gebruiken en leg uit hoe deze kunnen worden ge¨ımplementeerd. Leg het gebruik van de symbooltabel uit voor type-checking van (algemeen) recursieve functies. 3. Bij het type checken worden de types van de variabelen vastgelegd. Waarvoor en in welke fase(s) wordt deze type-informatie nog gebruikt? In hoeverre iss Semantic Analysis nog machine-onafhankelijk? 4. Bij weak typing gebeuren er impliciete conversies tussen types. Wat/waar moet er aangepast worden aan een compiler om weak typing te implementeren? 5. Typchecking is in het boek behandeld onder het hoofdstuk Semantische Analyse. Andere semantische acties (vb liveness analyse) gebeuren echter tijdens een andere fase. Beargumenteer waarom dit zo gebeurt. Activation Records, Intermediate Code 1. Beschrijf de stack frame layout en welke informatie daarover nodig is tijdens de IRtranslatiefase, op een manier die zo machineonafhankelijk mogelijk is. 2. Toegang tot variabelen moet op verschillende manieren mogelijk gemaakt worden: bespreek toegang tot globale variabelen, lokale variabelen, variabelen in een lexicaal omsluitende procedure, een dynamisch omsluitende procedure, een parameter, een returnwaarde. 3. Kan het FP register niet eenvoudig vervangen worden door en/of gebaseerd worden op het SP register? Bespreek aan de hand van het principe van activatierecords en een stack. 4. Bespreek caller-save en callee-save registers. Op welke fase(s) van de compiler heeft het onderscheid tussen die twee effect? Welk? 5. Leg uit hoe Intermediaire Code wordt opgebouwd en waarom. In hoeverre is IC machineonafhankelijk? 2 Basic Blocks, Traces, Instruction Selection 1. Bespreek de algoritmes Maximal Munch en Dynamic Programming in de context van instructieselectie. Vermeld daarbij zeker de begrippen “optimum tiling” en “optimal tiling”. Resulteert een optimum tiling sowieso in de meest efficinte opeenvolgende instructies? Waarom wel/niet? Het effect van RISC/CISC is hierbij wellicht belangrijk. 2. Wat is het grote voordeel van canonical trees t.o.v. trees gegenereerd door de semantische analyse? Leg ook uit hoe men deze transformatie realiseert. Leg het nut uit van basic blocks en traces! Waarom gebruiken we basic blocks om traces te genereren? 3. Wat zijn basic blocks? Waaruit bestaan ze? Hoe maak je ze en waarom zijn ze nuttig? Zijn basic blocks optimaal? 4. In het boek staat een tile voor ´e´en machine-instructie. Bespreek mogelijk nuttige varianten daarvan. Liveness Analysis 1. Wat is liveness analyse, wanneer wordt het uitgevoerd in de compiler en waarvoor dient het? Hoe wordt liveness berekend door een compiler, in het bijzonder wat zijn de in- en outsets? Welke optimalisaties voor het berekenen van liveness zijn er en leg uit. 2. Wat wordt bedoeld met een conservative approximation in de liveness analyse en leg uit a.d.h.v statische en dynamische liveness. Op welke plaatsen in de compiler wordt verder nog conservative benaderingen gemaakt en van welke eigenschappen of constructies? 3. Toon het verband en de verschillen aan tussen control flow analysis en data flow analysis. Register Allocation 1. Leg het basis algoritme voor register allocatie uit. Vermeld zeker: (a) wat de overeenkomst is met het kleuren van graaf; (b) waarom een standaard algoritme voor een K-kleuring van een graaf te vinden toch niet gebruikt kan worden; (c) de vijf stappen van het algoritme en hoe deze samenwerken 2. Waarom willen we knopen samennemen en welke impact heeft dit op het kleuren door vereenvoudiging? Leg ook uit waarom. 3. Bij het kleuren door vereenvoudiging gaan we ´e´en voor ´e´en de knopen terug van de stack halen en kleuren. Maakt het uit welke kleur gekozen wordt voor: (a) de correctheid van het algoritme? (b) een optimale uitkomst? Motiveer de keuze. 3 4. Bij het samennemen van knopen zijn er 2 veilige strategien: Briggs en George. (a) Geven deze beide strategi¨en altijd dezelfde oplossing? (b) Mag je beide strategi¨en naast elkaar gebruiken? Motiveer de keuze, dit mag uiteraard ook met een voorbeeld. 5. Soms moeten sommige tijdelijke variabelen op een bepaald moment in een gegeven machineregister zitten. (a) Hoe gaat de registerallocator daar mee om? (b) Waarop moet de compiler letten om geen performantieproblemen te krijgen? 6. Leg het Sethi-Ullman labeling algoritme uit, eerst zonder spilling, dan met spilling. Hoe pas je het in in de algemene register allocatie? Garbage Collection 1. Welke fases van de compiler cycle moeten aangepast worden om een GC algoritme te ondersteunen? Maak het nodige onderscheid tussen mark-and-sweep/copy/reference counting/generational/incremental ... 2. Welke eigenschap(pen) heeft een functionele taal (e.g. Haskell/Scheme) die GC kan uitbuiten? 3. Leg het basic tri-color algoritme uit. Geef de 2 invarianten van dit algoritme. Hoe kunnen deze invarianten bewaard worden? 4. Om de root-set at runtime te berekenen worden pointer maps gebruikt. Schets kort hoe pointer maps worden opgesteld en hoe ze gebruikt worden. In welke fase van het compilatieproces kunnen ze (reeds) opgesteld worden? Zijn die pointer maps getypeerd? 5. Leg uit: mark-and-sweep, copy collection, reference counting, Baker’s algoritme. Geef karakteristieken (tijd/ruimte gebruik) en voor- of nadelen t.o.v. elkaar. JITcompilatie 1. Leg uit wat JITcompilatie is, wanneer het gebruikt kan worden, wanneer het absoluut nodig is, wat de voordelen en nadelen zijn. 2. Leg het linear scan register allocatie algoritme uit. Vergeet daarbij niet uit te leggen hoe liveness bepaald wordt (niet enkel de definitie!). Bespreek ook enkele verbeteringen aan het basis algoritme. Waarom voldoet het Chaitin-Briggs algoritme niet? 3. Welke andere fasen van een klassieke compiler moeten ook een JITversie hebben om aan JITcompilatie te kunnen doen? Op welk ogenblik wordt daarvoor informatie verzameld, bijvoorbeeld in de context van Java? 4 Functionele talen 1. Leg de basisprincipes van de implementatie van luie uitvoering uit. Je moet daarbij o.a. spreken over closures. Bespreek mogelijke nadelen en hoe die door bepaalde optimalisaties kunnen verholpen worden - denk daarbij zowel aan tijd als ruimte. Wat is het verschil met een thunk die gebruikt wordt om call-by-name of call-by-need te implementeren? 2. Implementaties van functionele talen moeten staartrecursie (of meer algemeen de laatste call in een body) optimiseren. Waarom? Hoe kan dat gebeuren? Kan je die principes ook gebruiken in niet-functionele talen? 3. Indien je bv. Haskell naar C zou vertalen, dan moet je oplossingen vinden voor staartrecursie, voor closures, voor functies als first-class objects (die gedeeltelijk at runtime kunnen gemaakt worden) en voor garbage collection. Beschrijf hoe je elk ervan zou aanpakken of wat de mogelijkheden zijn. Zijn die problemen verschillend als je Haskell vertaalt naar een machinearchitectuur en waar in een klassiek compilatieschema zou je elke ervan aanpakken? 5
© Copyright 2024 ExpyDoc
