SYBSc Datavetenskap - Teoretisk kompilatorkonstruktion - Frågepapper
År: 2022
Längd: 3 timmar
Instruktioner:
Alla frågor är obligatoriska.
Alla frågor har lika betyg.
Avsnitt 1:
Beskriv Chomsky-hierarkin med hänvisning till finita automater, pushdown-automater och turingmaskiner.
Ge en kort översikt över huvudfunktionerna och komponenterna i en lexikalanalysator.
Diskutera de olika analysteknikerna som används i kompilatorer, med särskild uppmärksamhet på uppifrån och ner och nerifrån och upp-analysmetoder.
Förklara med relevanta exempel begreppet L-attribut och S-attributed grammatik.
Illustrera hur mellanrepresentation spelar en avgörande roll i sammanställningsprocessen.
Avsnitt 2:
Designa en lexikalanalysator för att identifiera identifierare och nyckelord i ett programmeringsspråk.
Skriv ett reguljärt uttryck för att söka efter giltiga e-postadresser.
Förklara hur en kompilator utför typkontroll och datatypkonverteringar.
Konstruera en LR(0)-analystabell för en given grammatik.
Utveckla en algoritm för att konstruera kontrollflödesgrafer för en mellanliggande representation.
Avsnitt 3:
Ge en översikt över de olika typerna av kodoptimeringstekniker som utförs under kompileringen.
Diskutera vikten och utmaningarna med att generera effektiv maskinkod.
Förklara begreppen lokal variabeltilldelning, spillkod och registerallokering i samband med kodgenerering.
Markera avvägningarna mellan att optimera för utrymme eller hastighet under kodgenerering.
Skriv korta anteckningar om följande:
Kodvikning
Kontrollera flödesutjämning
Eliminering av död kod
Slingavrullning
Registrera tilldelning
Lycka till!
