Nada

Faktiskt innehåll i 2D1372, Artificiella språk och syntaxanalys 1997

Tid

Kursen gick i period 3 1995/1997, dvs januari-februari 1997 och tentades 1 mars. Tentan var rättad samma dag.

Elever

Kursen var inte obligatorisk för någon, men ingår i kompetensinriktningarna programsystemteknik och teoretisk datalogi.

Antal elever: 60, varav 36 från D, 11 från F, 2 från E, 5 från M, en från T, 4 från SU och en systemvetare.

Lärare

Kursledare, föreläsare och övningsassistent var Viggo Kann, lektor på Nada, datorpost viggo@nada.kth.se. Övningsassistent var också Lars Engebretsen.

Kurslitteratur

"T W Parsons: Introduction to compiler construction". Computer Science Press, New York, 1992, ISBN 0-7167-8261-8. Pris: 350 kronor i kårbokhandeln.

Läsanvisning

KapitelNivå
kapitel 1-5 2
kapitel 6-8 0
appendix A 2
appendix B 1

0. Ingår inte alls.
1. Läs översiktligt, inga tentafrågor.
2. Ingår i detalj.

Dessutom ingick föreläsningsanteckningarna. Det finns nämligen några saker som tas upp i föreläsningsanteckningarna men inte i boken (till exempel KMP-automater, BDD och stackautomater).

Kursbunt

Fördjupnings- och referenslitteratur

Följande litteratur var det inte nödvändigt att ha eftersom den finns tillgänglig i Info i Emacs eller på kursens hemsida, men den som var extra intresserad kunde köpa den på Nadas elevexpedition.

Kursinnehåll

Kursen bestod av 12 föreläsningar, 6 övningar och 6 terminalövningar. Labbkursen bestod av fem laborationer (fyra små och en lite större) som gjordes i grupper om högst två personer.

Följande tabell visar vad som behandlades under föreläsningarna, övningarna och terminalövningarna.

vecka 3
F1 hur en kompilator fungerar i stort (1.1-1.10)
F2 ändliga automater, DFA=NFA, minimal DFA (2.1-2.5, appendix A)
Ö1 automater (uppgift 1.1-1.7)
vecka 4
F3 formella språk, reguljära uttryck, RE=DFA, reguljära uttryck i Unix. (2.6-2.10)
F4 Lex, hur Lex fungerar (appendix B.1)
Ö2 reguljära uttryck, Lex (uppgift 2.1, 2.2, 2.5, 2.7)
TÖ1 labb 1: simulering av NFA
vecka 5
F5 grammatik, syntaxträd, BNF, grammatik för naturliga språk (3.1.1-3.1.5)
F6 stackautomat (PDA), Turingmaskin (TM), Chomskyhierarkin (3.1.6-3.1.8)
Ö3 grammatiker, PDA, TM (uppgift 1.8, 1.9, 3.1, 3.3-3.5)
TÖ2 labb 2: lexikal analys med Flex
vecka 6
F7 uppifrån-och-ner-syntaxanalys, rekursiv medåkning (3.2-3.5)
F8 botten-och-upp-syntaxanalys, Yacc (4.1, appendix B.2)
Ö4 LL-analys, Yacc (uppgift 4.1, 4.2, 4.3, 4.5, 5.4)
TÖ3 labb 3: rekursiv medåkning
vecka 7
F9 hur Yacc fungerar, LR(k), LALR(1) (4.2-4.4)
F10 avancerad Yacc (appendix B.2)
vecka 8
F11 språkkonstruktion, intern representation, kodgenerering, optimering, fortsättningskurser (5.1-5.3)
F12 attributgrammatik, Ox, felhantering (5.4-5.8)
vecka 9
TÖ6 labb 5: en valfri översättare
Labbarna i kursen kan när det är möjligt göras i valfritt programspråk. I labblydelserna föreslås språket C eftersom Flex och Bison är avpassade för just C, men i allmänhet går C++ precis lika bra.

Den som hellre vill använda Modula-3 kan göra det i alla labbar utom Flexlabben (labb 2).

Laboration 5

I sista labben i kursen skulle man konstruera en praktiskt användbar översättare från en notation till en annan eller granskare som kollar syntaxen och ger vettiga felmeddelanden om inmatningen är felaktig. Här är ett antal förslag på uppgifter.

^ Upp till kursomgångar.


Sidansvarig: <viggo@nada.kth.se>
Senast ändrad 21 maj 1997
Tekniskt stöd: <webmaster@nada.kth.se>