Dat 2: Syntaks og semantik
En manual for studerende

Hans Hüttel

Foråret 2003


Indhold

Om denne manual

Dette er en manual over kurset `Syntaks og semantik'. På de følgende sider vil jeg prøve at besvare alle de vigtige og typiske spørgsmål, du måtte have som studerende.

Læs denne manual grundigt igennem inden kursets start og konsultér den sidenhen i tvivlstilfælde.

Om kursets indhold

Hvilke emner rummer kurset ?

I dette kursus stifter du bekendtskab med grundlæggende matematiske modeller for programmeringssprogs syntaks og semantik og den notation man bruger for dem. Programmeringssprogsteori er et vigtigt datalogisk område at kende, f.eks. hvis du skal designe et nyt programmeringssprog, lære dig et nyt programmeringssprog, skrive en compiler eller fortolker eller beskæftige dig med verifikation af programmer.

Jeg tager udgangspunkt i teorier om programmeringssprogs syntaks og semantik, men der bliver også eksempler på konkrete anvendelser af disse. Mit kursus er på 15 kursusgange (3 moduler) og falder, som titlen antyder, i to dele med hvert sit hovedemne:

Hvordan hænger kursets indhold sammen med SPO-kurset ?

Automater og grammatikker også bliver behandlet i kurset `Sprog og oversættere' i forbindelse med leksikalsk og syntaktisk analyse. Men synsvinklen er en helt anden: I `Syntaks og semantik' skal vi se på det teoretiske grundlag for leksikalsk og syntaktisk analyse - d.v.s. hvorfor de forskellige begreber hænger sammen. Samtidig er automater og grammatikker generelle begreber, der dukker op i en del sammenhænge uden for oversætterkonstruktion, f.eks. i områder som programverifikation eller genkendelse af naturlige sprog.

SPO-kurset omhandler desuden forhold i forbindelse med programudførelse, men SPO-kurset handler om forhold der er vigtige i forbindelse med konkret implementation af programmeringssprog, mens S&S-kurset tager udgangspunkt i situationer hvor det er nyttigt at kunne abstrahere fra konkrete implementationer.

Semantikdelen af dette kursus beskæftiger sig med det teoretiske grundlag for programmeringssprog. Vi kigger bag kulisserne og hinsides konkrete implementationer for at give et generelt og præcist billede af programmeringssprog.

Hvorfor skal vi lære om alle de små opfundne legetøjssprog ? Hvorfor kan vi ikke se på hele Java eller C eller ...?

Semantikdelen af kurset handler om hvordan man beskriver forskellige fænomener set isoleret, og derfor er det godt at vælge simple sprog der kun rummer disse fænomener. Senere skal I lære at betragte fænomenernes samspil i stadigt mere komplekse sammenhænge. En analogi: I et indledende kursus i mekanisk fysik lægger man heller ikke ud med at beskrive komplicerede mekaniske systemer med gnidningsmodstand, tyngdekraft osv. inddraget på samme tid.

Hvad er målene for kurset ?

Universitetskandidater siger ofte, at en af de vigtigste kvalifikationer, man får ud af en universitetsuddannelse, er selve det at kunne tilegne sig ny viden og at kunne bruge denne viden aktivt. Ethvert universitetskursus handler derfor om meget mere end `at lære kursets emner', men det bliver sjældent gjort klart, og alt for ofte gør undervisere ikke opmærksom på alle de læringsmål som ikke handler direkte om pensum. Men ved eksamen undersøger eksaminator og censor normalt i hvilket omfang den studerende har indarbejdet kursusformålene, også dem, kursusholderen har `glemt' at fortælle nogen om.

Et vigtigt, `glemt' formål med dette kursus er at du skal træne matematisk modenhed, så du bliver godt rustet til dette kursus og kommende kurser af samme art i dit studium. Måske har du allerede i kraft af dit tidligere studium - f.eks. hvis du har studeret matematik - arbejdet aktivt med matematiske emner. Andre formål er mere pensumspecifikke, og atter andre er helt generelle. I kurset `Syntaks og semantik' skal du

Hvorfor er der alle de beviser ?

I et universitetsstudium skal man - uanset hvad man studerer - (blandt mange andre ting) erhverve sig en teoretisk indsigt, og dette indebærer at man skal kende til teoriområdernes argumentation. Angrebsvinklen i dette kursus er primært teoretisk, og de teorier, vi skal se på, er matematisk funderede teorier. Resultaterne i matematisk orienterede discipliner er matematiske sætninger, og argumentationsformen er derfor matematiske beviser. Så derfor er det denne argumentationsform, du vil få at se. Andre discipliner i datalogi benytter sig af andre argumentationsformer.

Samtidig er der også en læringsbetinget grund til at gøre beviserne for kursets sætninger til genstand for en nøjere betragtning. Alle interessante matematiske sætninger siger nemlig noget om, hvordan begreber hænger sammen og man kan dermed lære at relatere kursets begreber til hinanden ved at betragte beviserne. Et eksempel er resultatet om sammenhængen mellem pushdown-automater og kontekstfrie grammatikker (ITTTOC, Lemma 2.15) - beviset fortæller præcis hvordan man kan konstruere en grammatik ud fra en automat, og ved at du sætter sig ind i beviset, får du forhåbentlig en bedre forståelse af hvad grammatikker og pushdown-automater helt præcist er.

Beviserne er altså ikke en træls, unødvendig kæphest, men et vgtigt aspekt af stoffet, som man skal bruge tid på at lære at forstå. Mange af jer har ikke megen erfaring med matematiske beviser fra jeres tidligere studium eller gymnasium/HF, og derfor har jeg lagt elementer af kursets form (opgaveregning og spørgetimer) an så I kan lære at få det meget bedre med matematiske beviser.

Om eksamen

Hvordan bliver eksamen ?

Eksamen er mundtlig med 20 minutter pr. studerende. Eksamenspræstationen bedømmes af en ekstern censor efter 13-skalaen.

Hvad skal jeg kunne til eksamen ?

Mod kursets afslutning finder vi ved en fælles forhandling frem til eksamenspensum og fastlægger eksamensspørgsmålene - men det er ikke det samme som at vi afgør tingene på demokratisk facon. I sidste ende er det kursusholderen (mig), der bestemmer pensum under passende hensyntagen til deltagernes synspunkter.

Ved kursuseksamen tjekker censor og jeg hvor godt du gennem din læring har opfyldt kursets formål som beskrevet ovenfor. Vi tjekker om du kan formulere dig mundtligt og skriftligt om kursets emner, om du har overblik over stoffet osv. Min erfaring har vist mig, at den nemmeste indgang til en diskussion af eksamen består i at en frivillig studerende til spørgetimen inden eksamen udfører en `prøveeksamen', som jeg straks derefter kommenterer og diskuterer med jer.

Skal jeg kunne beviserne til eksamen ?

Ja og nej - det handler ikke om at `kunne' nogle beviser udenad og recitere dem ved eksamen. Det er helheden af resultater og argumentationen for dem, der er vigtig, og den du skal fokusere på når du læser og arbejder med stoffet. En af de vigtige ting i dette kursus er at du skal lære at forstå og i et vist omfang selv kunne opstille matematiske sætninger og argumentere for at de er sande.

Jeg kender eksempler på eksaminander, der til eksamen er startet på at bevise en sætning, som de til gengæld ikke kunne formulere. Omvendt har jeg også set eksaminander, der ikke havde nogen anelse om hvorfor en sætning er sand. Begge typer præstationer er uheldige. Selvfølgelig kan du ikke nå at give alle detaljer i et bevis til eksamen, men ved eksamen er jeg som eksaminator også interesseret i at finde ud af om du har set hvad der er de vigtige pointer og om du kan se, hvad der kun er sekundære pointer og mindre væsentlige detaljer. Detaljer i beviser kan vi altid komme ind på, hvis der er tid og behov. Det handler om at kunne have overblik og præcis forståelse.

Til sidst i kurset tager vi en snak om eksamen; her vil du kunne få svar på dine spørgsmål om eksamensform o.lign.

Om kursets form

Hvordan er en kursusgang opbygget?

En kursusgang i `Syntaks og semantik' kommer til at forløbe sådan:

8.15-10.00 - i grupperum
Opgaver i stoffet fra foregående forelæsning.
10.10-10.15 - i auditorium
I besvarer en quiz om stoffet, I beskæftigede jer i opgavetiden.
10.15-12.00 - i auditorium
Forelæsning på 3 gange 30 minutter om nyt stof.

Jeg ville gerne have kunnet starte dagen med en kort repetition af stoffet fra gangen før, men lokalesituationen har gjort det umuligt. I stedet bliver den første opgave en repetition af stoffet.

Hvor meget tid skal jeg bruge på at forberede mig til en kursusgang?

Formodentlig lidt under et par timer, alt afhængig af stofmængden ved en kursusgang.

Hvad er quizzen ?

Efter hver opgaveregning holder jeg en ultrakort `quiz', som er et lille opgaveark med meget små opgaver, hvor de fleste er af `multiple choice'-typen. Opgavearket afleverer du naturligvis anonymt. Efter hver kursusgang offentliggør jeg de rigtige svar på kursets web-side.

Hvorfor har du lavet quizzen ?

Jeg vil gerne have en direkte tilbagemelding på hvad du ved og har lært efter en kursusgang. Jeg stiller spørgsmål om resultater og definitioner, men også i et vist omfang om notation. Det er nødvendigt at jeg som kursusholder ved hvad I ved, så jeg kan justere min undervisning (f.eks. typen af stillede opgaver) efter det. Men du kan også selv bruge quizzen til at tjekke din egen forståelse af stoffet. Det er derfor, jeg offentliggør svarene.

Hvor kan jeg se svarene på dagens quiz?

Via kursets hjemmeside.

Hvordan skal opgaveregningen i grupper forløbe?

Opgaveregningen er den vigtigste del af undervisningen. Regn opgaverne i fællesskab. Vælg en referent, og lad referentværdigheden gå på skift mellem gruppens medlemmer. Mens resten af gruppen i fællesskab regner opgaven på tavlen, noterer referenten løsningen ned. Ved at regne ved tavlen og tale med dine medstuderende lærer du at formulere dig mundtligt og skriftligt ved en tavle, ved at være referent, lærer du at formulere dig skriftligt.

De nedskrevne opgaveløsninger kan gruppen aflevere til sekretærerne efter kursusgangen. Alle opgaveløsninger vil komme til at sidde i kursusmappen, så I kan konsultere hinandens løsninger.

Der bliver ikke flere opgaver pr. opgaveregning end at alle grupper med en koncentreret indsats vil kunne nå opgaverne.

Der er et specielt incitament til at deltage i opgaveløsningen: Hvis en gruppe afleverer opgaveløsninger efter hver kursusgang og jeg ved at gruppen faktisk har været til stede, vil gruppens medlemmer få reduceret eksamenspensum yderligere.

Hvorfor er nogle opgaver sværere end andre ?

Opgaveregningen vil komme til at indeholde `typiske' opgaver - som f.eks. opgaver om at konstruere en DFA ud fra en NFA - som tager udgangspunkt i bestemte begreber eller resultater, men der vil også være ikke-rutineprægede opgaver, hvis formål er at lære dig at at relatere begreber og resultater eller at lære dig at forstå de præcise detaljer i centrale definitioner og resultater.

Hvad er det for noget med afleveringsopgaver?

Jeg har lavet et antal opgavesæt, der dækker kursuspensum. Disse opgaver kan du aflevere senest på den dato, jeg har angivet på de pågældende sæt.

Skal jeg aflevere afleveringsopgaverne? Hvad får jeg ud af det?

Det er ikke obligatorisk at aflevere opgaverne. Du behøver heller ikke at deltage i kursusgangene. Men begge dele er yderst fornuftige. Afleveringsopgaverne er der for at du kan arbejde med at formulere dig skriftligt om kursets emner og på den måde skærpe din tænkning. Afleveringsopgaverne er til for at du kan øve dig i fred og ro; alle besvarelser vil blive kommenteret af mig uden karaktergivning. Der bliver en eller to opgaver hver gang og en fire-fem sæt.

Hvis du afleverer et antal opgaver og får dine løsninger godkendt af mig, får du et yderligere nedslag på 10% i eksamenspensum.

Kan jeg få opgaveløsningerne udleveret?

Hvis du selv afleverer et opgavesæt, får du mine kommentarer igen.

Bliver der en større opgave ?

I kursusgang 14 er der ingen forelæsning, men derimod en lidt større semantikopgave, hvis formål er at lære dig at beskrive et lille programmeringssprog ved hjælp af operationel semantik. Stoffet fra opgaven bliver del af eksamenspensum og vil figurere som et spørgsmål. Vær allerede nu opmærksom på at du skal bruge tid på denne semantikopgave!

Jeg formulerer et antal opgaver baseret på projektarbejdet på semesteret.

Kursusmateriale

Hvilken bog skal jeg bruge?

I syntaksdelen er grundbogen (forkortet ITTTOC i det følgende):

Michael Sipser: Introduction to the Theory of Computation, PWS Publishing Co. 1998.

Bogen kan købes hos Centerboghandelen. Jeg vil til en enkelt kursusgang udlevere en kort supplerende note; du vil kunne finde denne note i kursusmappen og være tilgængelig fra hjemmeside.

I semantikdelen skal du bruge

Hans Hüttel: Pilen ved træets rod, Aalborg Universitet 2003.

som du vil kunne købe i Centerboghandlen i løbet af februar. Denne bog skal du ikke bruge før 8. kursusgang.

Det er en dyr syntaksbog, og så kun til knap halvdelen af kurset!

Jo, ITTTOC er desværre temmelig dyr - men den skal også bruges som eneste bog i kurset `Beregnelighed og kompleksitet' på Dat 3/F7D/BS3, så tænk på det som en langtidsinvestering.

Har `Syntaks og semantik' en WWW-side ?

Selvfølgelig - den er 

http://www.cs.auc.dk/~hans/Dat2/SyntaksOgSemantik/

På siden vil der komme til at ligge kursusplan, spisesedler, afleveringsopgaver og denne manual - alt sammen i Postscript-format. Der vil også blive aktuelle informationer om kurset i øvrigt - ændringer i pensum, eventuelle aflysninger osv. Jeg vil gå ud fra at I alle læser web-siden.

Har du lavet en kursusplan?

Ja, det har jeg da. Den er herunder:

Syntaks - regulære sprog

Kursusgang Emne:  Litteratur:
1 Sprog; endelige automater  ITTTOC forord, 0.2, 1.1
2 Nondeterministiske automater  ITTTOC afs. 1.2
3 Regulære udtryk  ITTTOC afs. 1.3
4 Sprog der ikke er regulære  ITTTOC afs. 1.4

Syntaks - kontekstfrie sprog

5 Kontekstfrie grammatikker  ITTTOC afs. 2.1
6 Pushdown-automater  ITTTOC afs. 2.2
7 Sprog der ikke er kontekstfrie  ITTTOC afs. 2.3



Semantik - operationel semantik

8 Introduktion til operationel semantik  HH, kap. 1, 2 og 3
9 Operationelle semantikker for Bims  HH, kap. 4
10 Udvidelser af Bims  HH, kap. 5
11 Blokke og procedurer  HH, kap. 6
12 Parametermekanismer  HH, kap. 7
13 Funktionsorientede sprog  HH, kap. 12
14 Semantikopgaven  Afhænger af opgaven

Teoretisk grundlag

15 Rekursive definitioner  HH, kap. 14, afsnit 14.1.1, 14.1.3, 14.1.4, 14.2-14.5, 14.6.1,14.6.2

Er spisesedlerne klar ?

Ja og nej - mange af dem er tilgængelige fra WWW-siden allerede nu, men de vil sandsynligvis blive revideret undervejs. Nogle af de sidste mangler enkelte oplysninger i skrivende stund.

Hvad skal jeg gøre hvis min spiseseddel bliver væk, og jeg ikke er i nærheden af WWW?

Kig i kursusplanen ovenfor, så du kan se hvad du skal læse til næste gang.



Hans Hüttel