2D1372 Artificiella språk och syntaxanalys, 3 poäng
Mål
Kursens mål är att
- ge de teoretiska grunderna för definition och analys av programspråk och andra artificiella språk,
- ge förmåga att utveckla lämpliga notationer för beskrivning av olika typer av problem,
- ge förmåga att konstruera översättare från en notation till en annan,
för att eleverna
- ska känna till kraftfullheten och begränsningarna hos automater och formella språk,
- i praktiska situationer ska kunna specificera lämpliga inmatningsnotationer för datorprogram och konstruera analysatorer för dem.
Förkunskaper
Motsvarande kursen 2D1340 (eller 2D1341) Introduktion till datalogi eller 2D1320 Tillämpad datalogi.
Kursinnehåll
Artificiella språk: reguljära uttryck, kontextfri grammatik, BNF och EBNF, frasstrukturspråk, Chomskyhierarkin.
Beräkningsmodeller: ändliga automater, stackautomater, turingmaskiner.
Analysmetoder: lexikal, syntaktisk och semantisk analys, rekursiv medåkning, tabellstyrd syntaxanalys (LL, LR och LALR).
Implementationsteknik: verktyg för lexikal och syntaktisk analys, attributgrammatik, interna representationer, generering av utdata.
Kursuppläggning
- Föreläsningar
- 24 h period 3
- Övningar
- 12 h period 3
- Laborationer
- 12 h period 3
Examination
En skriftlig tentamen (TEN1; 2 p).
Laborationsuppgifter (LAB1; 1 p).
Betygsskala: 3, 4, 5.
Fördjupningsnivå: C
Kurslitteratur
Enligt förteckning på institutionen.
2D1372 Artificial Languages and Syntax Analysis, 3 credits
Goals
The goals of the course are to give the students
- the theoretical foundations for definition and analysis of programming languages and other artificial languages,
- the ability to develop suitable notations for the description of different types of problems,
- the ability to construct translators from one notation to another
so that they will be able to
- realize the power and the limitations of automatas and formal languages,
- specify suitable input notations for computer programs and construct analyzers for these notations in practical situations.
Prerequisites
2D1340 (or 2D1341) Introduction to Computer Science or 2D1320 Applied Computer Science or the equivalent.
Contents
Artificial languages: regular expressions, context free grammars, BNF and EBNF, phrase structure languages, the Chomsky hierarchy.
Computational models: finite automata, push down automata, Turing machines.
Methods for language analysis: lexical, syntactic, and semantic analysis, recursive descent, table driven syntax analysis (LL, LR, and LALR).
Implementation techniques: tools for lexical and syntactic analysis, attribute grammars, internal representations, generation of output.
Examination
A written examination (TEN1; 2 cr.).
Laboratory assignments (LAB1; 1 cr.).
Grades: 3, 4, 5.
Required reading
Reading list available at the department.
Upp till kursens hemsida.
Senast ändrad 1996-04-16
<www-kurs@nada.kth.se>