Forslag til eksamensspørgsmål i SPO - F00

Eksamensform

Mundtlig eksamen uden forberedelse (20 min). Der holdes et oplæg på basis af et trukket spørgsmål fra en delmængde af nedenstående liste. Ved 75% af kursets indhold som eksamenspensum, så skal der udvælges ca. 11 spørgsmål. En del af spørgsmålene er ret omfangsrige, der er naturligvis jeres opgave af vælge en passende delmængde ud som I vil tale om.

Mulige eksamensspørgsmål

1. Struktur af en compiler - moduler og interfaces.

Beskrive de forskellige dele som en compiler er opbygget af og hvad deres opgave er, husk af komme ind på hvilke mellemformater der binder de forskellige dele sammen.

2. Leksikalsk analyse.

Beskriv (kort) formålet med den leksiskalske analyse, regulære udtryk og endelige automatker. Beskriv hvordan vi konstruerer en endelig automat udfra regulære udtryk, og hvordan vi konverterer en NFA til en DFA (der er ikke tid til at gå i dybden med begge delspørgsmål, så vælg ét).

3. LL(k) (top-down, predikativ) parsing.

Beskriv (kort) princippet og implementation af en top-down parser. Beregning af first og follow mængder og hvad de bruges til. Kom eventuelt ind på problemer for top-down parsere (venstre rekursion og venstre faktorisering) og hvad man gør ved dem.

4. LR(k) (bottom-up) parsing.

Beskriv (kort) princippet i en bottom-up parser, herunder hvordan en skift-reduce parser virker og forholdet mellem derivationer og reduktioner. Kom eventuelt ind på hvordan en LL(1) parsetabel opbygges.

5. Statisk semantisk analyse.

Hvad er formålet med statisk semantisk analyse og hvordan udføres den? Hvad bruge symboltabellen til (også efter den statisk semantiske analyse)? Diskuter eventuelt effektiv implementation af symboltabeller.

6. Realisering af rekrusive funktioner og procedurer

Forklar hvordan vi vha. køretids stakken kan implementere rekursive funktioner og procedurer med lokale variable. Gennemgå parameter overførsel og adgang til variable i yderliggende scopes.

7. Mellemformater

Hvorfor bruger vi mellemformater istedetfor at generere maskinkode direkte udfra det abstrakte parsetræ? Giv en kort introduktiontion til mellemformatet IR-træer og forklar hvordan man genererer IR-træer udfra det abstrakte parsetræ (eventuelt vha. et eksempel).

8. Kodegenerering fra mellemformat

Forklar princippet i tiling, hvad er forskellen mellem optimum og optimal tiling. For enten virkemåden af Maximum munc eller dynamisk programmerings algoritmen til kodegenering.

9. Liveness analyse

Hvad er liveness analyse, hvad er formålet, og hvordan foregår det?

10. Registertildeling

Beskriv kort hvorfor vi ønsker så god en register tildeling som muligt, og forklar derefter virkemåden af simplifikations algoritmen og gennemgå udvalgte dele i detaljer.

11. Garbage collection

Der ønskes en kort motivation for hvorfor garbage collection er ønskværdigt, en gennemgang af en udvalgt garbage collection teknik og en diskussion af inkrementel garbage collection.

12. Oversættelse af objekt-orienterede sprog

Hvad er det, der gør oversættelse af objekt-orienterede sprog til noget særligt og hvad gør man ved det?

13. Sprogdesign - Statements.

Der ønskes en gennemgang af designprincipperne bag forskellige typer statements og eksempler på eksisterende statements og deres relation til design principperne.

14. Sprogdesign - Data og Typer

Hvad er ideen bag typer? Beskrive de forskellige slags typer vi har i imperative sprog og hvordan deres layout er i hukommelsen.

15. Sprogdesign - Procedurer og Funktioner

Der ønskes en gennemgang af designprincipperne bag abstraktionsmekansimer som procedurer og funktioner. Husk at medtage de spørgsmål som sprogdesigneren skal tage stilling ( hvordan parameter mekanismen skal fungere, scoperegler etc.) til.

Til SPO hjemmesiden | Til DAT2 hjemmesiden

Josva Kleist <kleist@cs.auc.dk>

Last modified: Thu Apr 8 14:35:32 1999