SYBSc Datalogi - Teoretisk kompilatorkonstruktion - Spørgepapir
År: 2022
Varighed: 3 timer
Instruktioner:
Alle spørgsmål er obligatoriske.
Alle spørgsmål har lige karakter.
Afsnit 1:
Beskriv Chomsky-hierarkiet med reference til endelige automater, pushdown-automater og turingmaskiner.
Giv et kort overblik over de vigtigste funktioner og komponenter i en leksikalsk analysator.
Diskuter de forskellige parsing-teknikker, der bruges i compilere, og vær særlig opmærksom på top-down og bottom-up parsing metoder.
Forklar med relevante eksempler begrebet L-tilskrevet og S-tilskrevet grammatik.
Illustrer, hvordan mellemrepræsentation spiller en afgørende rolle i kompileringsprocessen.
Afsnit 2:
Design en leksikalsk analysator til at identificere identifikatorer og nøgleord i et programmeringssprog.
Skriv et regulært udtryk for at tjekke for gyldige e-mailadresser.
Forklar, hvordan en compiler udfører typekontrol og datatypekonverteringer.
Konstruer en LR(0)-parsing-tabel for en given grammatik.
Udvikle en algoritme til at konstruere kontrolflowgrafer til en mellemrepræsentation.
Afsnit 3:
Giv et overblik over de forskellige typer kodeoptimeringsteknikker, der udføres under kompileringen.
Diskuter vigtigheden og udfordringerne ved at generere effektiv maskinkode.
Forklar begreberne lokal variable allokering, spildkode og registerallokering i sammenhæng med kodegenerering.
Fremhæv afvejningen mellem at optimere for plads eller hastighed under kodegenerering.
Skriv korte noter om følgende:
Kodefoldning
Kontroller flowudfladning
Fjernelse af død kode
Løkkeafrulning
Register tildeling
Held og lykke!
