Nada

^ Upp till kursens hemsida.

Aktuell information om 2D1372, Artificiella språk och syntaxanalys

Senaste nytt

Ordinarie tenta 1997-03-01

Omtenta 1997-04-10

Omtenta 1997-08-22

Kursutvärdering

Resultaten från kursenkäten finns här.

Errata

Flera fel i kursboken har rapporterats in och jag har utökat erratalistan.

LR(1)-tabeller är som ni säkert har märkt svåra att få rätt. Ett nytt fel i uppgift 5.3 i övningshäftet har upptäckts:
I formeln (5.24) ska I2 bytas mot I7. Detta får som följd att 2 ska bytas mot 7 för inmatningen ( i tillstånd 2 i dom två LR(1)-tabellerna på sida 50.
I tillstånd 3 i LR(1)- och LALR(1)-tabellerna hittades ett fel redan på övning 5, nämligen att r2 skulle bytas mot r1, vilket leder till att det i LALR(1)-tabellen bara blir en skiftnings/reduceringskonflikt och ingen reducerings/reduceringskonflikt för inmatningen ( i tillstånd 3.

Restlabbar

Den som vill redovisa restlabbar ska vända sig till Viggo.

Vid redovisningen måste du ta med aktuella programlistor, samt för labb 5 också en användarhandledning och en kravspecifikation (se uppgiftslydelsen).

Labbresultat

Labbresultat 23 april 1997 finns här.

Modifierad föreläsningsplanering

Innehållet i dom fyra sista föreläsningarna i kursen är något omkastat. Följande planering kommer att gälla:
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)

Tillrättaläggande av uppgiftslydelsen för labb 3

Grammatiken i labblydelsen stämmer inte överens med den givna analysatorn casio.c. Byt därför ut reglerna 
          expr  ::= term
          expr  ::= term [ '+' term ]
          expr  ::= term [ '-' term ]
          
          term  ::= factor
          term  ::= factor [ '*' factor ]
          term  ::= factor [ '/' factor ]
mot 
          expr  ::= term   { ('+'|'-') term }
          term  ::= factor { ('*'|'/') factor }

Rättade labblydelser finns för Postscript och Acrobat.

Labba i Modula-3 om du vill

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

Kommandot module add modula-3 gör Modula-3-kompilatorn och m3bison tillgängliga.

Lärare

Kursledare och föreläsare är Viggo Kann, viggo@nada.kth.se. Mottagningstid tisdagar klockan 14.00-15.00. Övningsassistenter är Lars Engebretsen, enge@nada.kth.se (grupp 1) och Viggo Kann (grupp 2).

Kurslitteratur

Kurslitteraturen ska läsas på egen hand parallellt med kursen. Föreläsningar, övningar och laborationer täcker endast en del av kursmaterialet. Det finns en läsanvisning inför tentan.

Kursbok

"T W Parsons: Introduction to compiler construction", Computer Science Press, New York, 1992, ISBN 0-7167-8261-8. Pris: 350 kronor i kårbokhandeln. Det finns en erratalista till boken; den ändrades senast 19 juni 1997.

Kursbunt

Kursbunten kan köpas på första föreläsningen och därefter på Nadas elevexpedition för 20 kr. Papper som delas ut under kursens gång kommer att finnas i en pärm i hyllan utanför expeditionen.

Fördjupnings- och referenslitteratur

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

Schema

Notera att onsdagsföreläsningarna är i sal K2 och inte i D3 som det står i KTHs schema.

Schema för vecka 3, 1997

TidMåndagTisdagOnsdagTorsdagFredag
8Föreläsning
K2
9
10Övning
D34,D35
11
12
13Föreläsning
E3
14
15
16
17

Schema för vecka 4-8, 1997

TidMåndagTisdagOnsdagTorsdagFredag
8Föreläsning
K2
9
10Övning
D34,D35
11
12
13Föreläsning
E3		 Terminalövning
Spel-,Sporthallen
14
15
16
17

Schema för vecka 9, 1997

TidMåndagTisdagOnsdagTorsdagFredag
8
9
10
11
12
13 Terminalövning
Spel-,Sporthallen
14
15
16
17

Detaljschema

Följande tabell visar vad som preliminärt kommer att behandlas 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)
Ö5 LR-analys, Yacc (uppgift 5.1-5.3, 5.7)
TÖ4 labb 4: reguljära uttryck med Flex och Bison
vecka 8
F11 intern representation, kodgenerering, optimering, språkkonstruktion (5.1-5.3)
F12 attributgrammatik, Ox, felhantering, fortsättningskurser (5.4-5.8)
Ö6 attributgrammatik, Ox (uppgift 5.5, 5.8, 5.9)
TÖ5 arbete med labb 5
vecka 9
TÖ6 labb 5: en valfri översättare

Kursregistrering

Om du vill gå kursen ska du anmäla det i förväg till kansliet/studievägledningen för ditt utbildningsprogram. Ingen förhandsanmälan ska göras till Nada. Det finns ingen platsbegränsning.

Så snart kursen börjat måste du registrera dej på den. Detta görs med kommandot

res checkin syntax97

på någon av Nadas unixdatorer. Registrera dej så snart som möjligt efter att kursen börjat!

För din egen skull bör du också ge kommandot

course join syntax97

Detta kommando gör tre saker:

När du är klar med kursen ger du kommandot

course leave syntax97

för att återställa allt.

Laborationer

Labbkursen består av fem laborationer (fyra små och en lite större) som görs i grupper om högst två personer. Enstaka labbar får inte sparas till annan kursomgång. Om du inte fullgör alla fem labbarna inom ett år från kursens slut har kursledaren rätt att kräva att du gör samtliga labbar i den nya kursomgången.

Bonuspoäng

Vi tillämpar ett bonussystem för att uppmuntra eleverna att ligga i fas med undervisningen. För varje labb som redovisas på rätt redovisningstillfälle erhålls en bonuspoäng. Summan av dessa poäng adderas till den på tentan uppnådda poängsumman. Detta gäller ett kalenderår räknat från kursstart. Bonuspoäng kan endast fås det året som labbresultatet rapporteras. När du är inloggad kan du se vilka labbar du är godkänd på genom att ge kommandot

res show syntax97

Hederskodex

Grundregeln är att det jobb du gör i kursen (labbar, inlämningsuppgifter, tentor m.m.) ska du göra själv, förutom att labbarna kan göras i tvåmannagrupper. Vid redovisning av labbar ska båda i gruppen kunna redogöra i detalj även för vad labbkompisen skrivit.

Ibland, speciellt när man skriver program, kan det vara nödvändigt att fråga någon annan (en kamrat eller en handledare) om hjälp med att hitta fel. Detta är tillåtet förutsatt att du uppfyller följande villkor.

Varje annan form av samarbete och utnyttjande av andras lösningar betraktas som ett brott mot hederskodexen och kan bestraffas, t ex genom att du förlorar alla bonuspoäng eller får göra en ny uppgift.

Detta är en översatt och omarbetad version av den hederskodex som används i kursen Introduction to computer science vid Stanford University. Den tillämpas i många av Nadas kurser.

Tentamen

Tid och plats för ordinarietentan är lördag den 1 mars 1997 klockan 8-13 i sal F31-F33. Första omtentatillfälle är torsdag den 10 april 1997 klockan 14-19 i sal D31.

Tentan består av en teoridel utan hjälpmedel och en problemdel med kursboken och föreläsningsanteckningarna som hjälpmedel. Hela skrivtiden är fem timmar. Efter två timmar måste teoridelen ha lämnats in, men du får gärna göra det tidigare. För godkänt krävs minst 25 poäng (inklusive maximala 5 poäng labbonus) av 50 poäng. Tentaresultatet anslås högst tre veckor efter tentan på institutionens anslagstavla på plan 3 (rakt under elevexpeditionen). Klagomål på rättning av tentan lämnas in skriftligen till kursledaren inom tre veckor från det att tentaresultatet anslagits.

Anmälan till tentan

Du behöver inte anmäla dej till tentan. (Tentaanmälan var tidigare obligatorisk för D- och E-teknologer men Nada använder sej inte av detta anmälningssystem längre.)

Kurskatalog

Kursen har en katalog på Unixdatorerna: /info/syntax97. På denna katalog finns textfiler, programskelett, program och liknande som har med kursen att göra.

Nadas terminalsalar

Det finns arbetsmiljöregler för terminalsalarna. Dessa talar om hur man ska bete sig i salarna.

Kommandot local-info plan5o talar om när terminalsalarna är bokade av andra kurser.

Synpunkter på kursen

Eftersom denna kurs kommer att ges för många elever under flera års tid är vi tacksamma för synpunkter på kursen. En datorstödd kursutvärdering håller på att göras. Synpunkter kan också lämnas direkt till lärarna.

Analysatorgeneratorer

I kursen använder vi Flex (som är nästan samma som Lex) och Bison (som är nästan samma som Yacc). Dessutom beskrivs programmet Ox. Den som vill får istället använda andra motsvarande program, till exempel Jack eller PCCTS. Nedan beskrivs hur man på Nada får tillgång till dom här nämnda programmen.
Lex
Lexikalanalysatorgenerator som finns i varje Unixsystem och genererar C-kod. Lex startas med kommandot lex som blir tillgängligt med module add lang. Dokumentation fås med man lex.
Flex
Gnuprojektets motsvarighet till Lex. Flex startas med kommandot flex som blir tillgängligt med module add gnu (som automatiskt görs om du skrivit course join syntax97). Dokumentation fås med man flex, i Info i Emacs och kan köpas på Nadas expedition.
Yacc
Syntaxanalysatorgenerator som finns i varje Unixsystem och genererar C-kod. Yacc startas med kommandot yacc som blir tillgängligt med module add lang. Dokumentation fås med man yacc.
Bison
Gnuprojektets motsvarighet till Yacc. Bison startas med kommandot bison som blir tillgängligt med module add gnu (som automatiskt görs om du skrivit course join syntax97). Dokumentation fås med man bison, i Info i Emacs och kan köpas på Nadas expedition.
Ox
En utvidgning av Lex och Yacc som klarar attributgrammatiker. Ox startas med kommandot ox som blir tillgängligt med module add ox (som automatiskt görs om du skrivit course join syntax97). Dokumentation fås med man ox. Det finns också en ganska lättläst beskrivning av Ox samt en fullständig referensmanual. Referensmanualen säljs på Nadas expedition. Under katalogen /usr/local/vol/ox-g1.04/grammars finns färdiga Oxgrammatiker för språken ADA, C, C++, Fortran och Pascal. Under katalogen /usr/local/vol/ox-g1.04/demo finns några enklare exempel på Oxgrammatiker.
Jack
Syntaxanalysatorgenerator som genererar Javakod. Jack startas med kommandot /info/syntax97/Jack/bin/jack. Dokumentation finns på /info/syntax97/Jack/doc och i www.
PCCTS
Purdue Compiler Construction Tool Set - ett modernt alternativ till Lex och Yacc som genererar C-kod. PCCTS startas med kommandona dlg (lexikalanalysatorgenerator) och antlr (syntaxanalysatorgenerator) som blir tillgängliga med module add pccts. Dokumentation fås med man pccts, men i www finns också information, en snabbkurs och en C++-grammatik för PCCTS.

Diverse länkar

^ Upp till kursens hemsida.

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