Pensum og Eksamensspørgsmål for SPO - F00

Eksamenspensum

Appel - Modern Compiler Implementation in JAVA:

Kapitel 1 - Introduktion til compiler konstruktion.
Kapitel 2 - Leksikalsk analyse.
Kapitel 3 - Parsing (dog ikke 3.3-3.5).
Kapitel 4 - Abstrakt syntaks.
Kapitel 5 - Statisk semantisk analyse.
Kapitel 6 - Activation records.
Kapitel 7 - Generering af mellemformat.
Kapitel 9 - Instruktionsvalg.
Kapitel 11 - Registertildeling (dog ikke 11.4).

Sethi - Programming Language - Concepts and Constructs:

Kapitel 3 - Struktureret programmering - statements.
Kapitel 4 - Struktureret programmering - data og typer.
Kapitel 5 - Struktureret programmering - procedurer og funktioner.

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 leksikalske analyse, regulære udtryk og endelige automater. 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. 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.

5. Realisering af rekursive 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.

6. 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).

7. Kodegenerering fra mellemformat

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

8. 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.

9. Sprogdesign - Statements.

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

10. 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.

11. 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.

Eksamensform

Mundtlig eksamen uden forberedelse (20 min). Der holdes et oplæg på basis af et trukket spørgsmål fra ovenstående liste. 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.
Til SPO hjemmesiden | Til DAT2 hjemmesiden
Josva Kleist <kleist@cs.auc.dk>
Last modified: Fri Mar 31 12:45:58 2000