KOI: Instuderingsfrågor inför tentan
Frågorna på tentan kommer att likna de nedanstående.
Formlerna för vänsterfaktorisering och eliminering av vänsterrekursion kommer att finnas med på tentan.
Viktigast
Följande frågor måste man kunna svara på,
dvs om man svarar helt fel på någon av dem blir man underkänd på tentan.
- Man brukar dela in en kompilator i ett antal faser. Vad är en fas?
- Varför delar man upp kompilatorn i faser?
- Vad heter de olika faserna?
- Beskriv varje fas med några meningar.
- Vad är in- och utdata för respektive fas?
Fler frågor
Följande frågor bör man kunna svara på.
De ger poäng, och man ska ha ett visst antal poäng (ungefär hälften) för att bli godkänd,
precis som det ofta är på andra tentor.
När det står "grammatiken ovan", "följande programavsnitt" och så vidare,
är tanken att man ska kunna besvara den typen av frågor, med olika
givna grammatiker och programavsnitt. Titta på de gamla tentorna på
hemsidan
(både gamla och nya kursplanen)
för att få konkreta exempel.
- Ange vilka terminaler, dvs typer av tokens, som behövs för att man ska kunna skriva en grammatik för följande enkla språk.
- Skriv en grammatik för följande enkla språk.
- Rita upp parse-trädet för den här inmatningen, givet grammatiken ovan.
- Skriv en prediktiv recursive-descent-parser i något C-liknande språk för det språket.
(Kan innefatta vänsterfaktorisering och eliminering av vänsterrekursion.)
- Skriv en prediktiv recursive-descent-parser i något C-liknande språk för den här grammatiken.
(Kan innefatta vänsterfaktorisering och eliminering av vänsterrekursion.)
- Beskriv det språk som följande grammatik definierar.
- Ange tio olika strängar som ingår i det språk som beskrivs av följande grammatik.
- Är den här grammatiken tvetydig?
- Här är några fel i källkoden som upptäckts av kompilatorn.
I vilken fas är det troligt att respektive fel upptäcktes?
- Översätt följande programavsnitt i ett C-liknande språk till ett abstrakt syntaxträd, genom att rita upp trädet.
- Översätt följande programavsnitt i ett C-liknande språk till postfixkod för en stackmaskin.
- Översätt följande programavsnitt i ett C-liknande språk till treadresskod.
- Skriv ett reguljärt uttryck ("regexp") som matchar följande.
- Här är lite treadresskod. Dela in koden i basic blocks.
- Optimera koden med hjälp av de vanliga metoderna för optimering, såväl inom ett enskilt basic block som i flera block.
Beskriv inte bara resultatet, utan de olika stegen, gärna med namn.
- Flera olika typer av optimeringar kan göras på koden inuti ett enskilt basic block. Vilka? Beskriv dem, och använd treadresskod för att ge exempel på hur de fungerar.
- Här är ett C-program. Ett programs adressrymd kan delas upp i fyra delar: programkod och konstanter, statiska data, heap och stack. Rita upp hur stacken (med aktiveringsposter), heapen och statiska data ser ut när programkörningen kommer till kommentaren "Här!".
- Skriv en grammatikregel för den här satsen från språket C.
- Skapa ett syntaxstyrt översättningsschema, med produktioner och semantiska aktioner, för översättning av den satsen till mellankod. Välj själv om du vill generera ett abstrakt syntaxträd, postfixkod för en stackmaskin eller treadresskod. (Tala också om vilket du valde.)
- Antag att minnet innehåller dessa dataobjekt. Vi använder skräpsamlingsmetoden "mark and sweep". Vilka av objekten kommer att markeras i markeringsfasen?
- Vilka av objekten kommer att tas bort i sopfasen?
- Vi använder referensräkning. Ange värdet på referensräknaren för vart och ett av dataobjekten.
- Jämför mark and sweep med referensräkning. Vilja fördelar och nackdelar har de?
- Förklara kort följande begrepp från kompilatortekniken:
- aktiveringspost (på engelska: "activation record")
- anropskonventioner (på engelska: "call sequence")
- anropsstack
- basic block
- Bison
- call by value
- copy propagation
- DAG
- deterministisk ändlig tillståndsmaskin
- döda data ("dead data")
- död kod ("dead code")
- dynamisk
- eliminering av vänster-rekursion
- fas (på engelska: "phase")
- FIRST()-konflikt
- Flex
- front end (på engelska: "front end")
- grammatik
- heap
- intermediärkod
- interpretator
- kodgenerator
- kompilator
- konservativ skräpsamling
- länkare
- Lex
- lexem
- lexikalisk analys
- literal (på engelska: "literal")
- målprogram
- målspråk
- mark and sweep
- mark bit (vid skräpsamling)
- markeringsfas (vid skräpsamling)
- maskinberoende optimering
- maskinoberoende optimering
- mellankod
- mellankodsgenerator
- namnekvivalens (på engelska: "name equivalence")
- nyckelhålsoptimering ("peep-hole optimization")
- onåbara data ("unreachable data")
- optimering, kodoptimering
- parser
- parser-generator (på engelska: "parser generator")
- parseträd (ibland kallad "konkret syntaxträd")
- pass (på engelska: "pass")
- postfixkod
- referensräkning ("reference counting")
- registerallokering
- reguljärt uttryck
- reserverat ord
- rotmängd ("root set")
- run-time-omgivning
- scanner
- semantisk analys
- shift-reduce-konflikt
- skräpsamling ("garbage collection")
- stackmaskin
- statisk
- statiska data
- strukturekvivalens (engelska: "structural equivalence"), som är motsatsen till namnekvivalens (engelska: "name equivalence")
- symboltabell (engelska: "symbol table")
- syntaktisk analys
- syntaxträd (ibland kallad "abstrakt syntaxträd")
- token
- treadresskod
- tvetydig grammatik
- tvetydighet
- typsystem
- uppsamlingsfas (vid skräpsamling, på engelska: "sweep phase")
- vänsterfaktorisering
- Yacc
- Varför kallas kompilatorer för "kompilatorer"?
Thomas Padron-McCarthy
(thomas.padron-mccarthy@oru.se),
20 oktober 2014