Nada

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

Tid

Kursen gick i period 3 1995/1996, dvs januari-februari 1996 och tentades 4 mars. Tentan var rättad den 6 mars.

Elever

Kursen var obligatorisk för kompetensinriktningen programsystemteknik i D3 (ca 40 elever). Cirka 5 elever från kognitionsinriktningen, en elev från teleinformatikinriktningen, 5 D-yngre, 5 från F, en från M, en från I och 5 utom-KTH-are följde också kursen.

Lärare

Kursledare, föreläsare och assistent var Viggo Kann, lektor på Nada, datorpost viggo@nada.kth.se.

Kurslitteratur

Pars
"T W Parsons: Introduction to compiler construction". Computer Science Press, New York, 1992, ISBN 0-7167-8261-8. Pris: 320 kronor i kårbokhandeln.
BDD
"S Arnborg: Automata and BDDs - new tools in verification and optimization".

Läsanvisning

Kapitel/avsnitt    Nivå
=======================
Pars 1-5            2
Pars 6-8            0
Pars appendix A     2
Pars appendix B     1
BDD avsnitt 1-4     2
BDD avsnitt 5-7     1

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

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 14 föreläsningar, 7 ö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, KMP-automat för textsökning, BDD
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
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
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 Yacc
TÖ3 labb 3: rekursiv medåkning
vecka 7
F9 Yacc, åtgärder (appendix B.2)
F10 hur Yacc fungerar, LR, LALR(k) (4.2-4.4)
Ö5 (i sal K2) Yacc, felhantering
TÖ4 labb 4: reguljära uttryck med Flex och Bison
vecka 8
F11 intern representation, kodgenerering, optimering (5.1-5.3)
F12 attributgrammatik, Ox (5.4-5.8)
Ö6 attributgrammatik, Ox
TÖ5 arbete med labb 5
vecka 9
F13 att konstruera egna språk, verktyg för översättning
Ö7 tentatal
TÖ6 labb 5: en valfri översättare
F14 sammanfattning

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 1 april 1996
Tekniskt stöd: <webmaster@nada.kth.se>