02140 Languages and parsing (Autumn 2004)

Aim: To give students a fundamental understanding of formal languages, simple automata models, simple syntax analysis and their applications. Introduction to functional programming.

Contents: Theory for and practical application of regular and context-free languages, including different kinds of representations, their properties and transformations among them, as well as applications to syntax analysis. Programming in SML, including practical construction of prototypes using LEX and YACC like tools.

SML: Information concerning SML may be obtained from here.

Prerequisites: Mastery of imperative programmering. Simple algorithms and datastructures, including representations of graphs and simple graph algorithms, e.g. depth-first search. Discrete mathematics: sets, functions, relations. Simple proof techniques. Covered by the courses: 02100, 02105, 02110 and 01016 (Grundlæggende Matematik for Dataloger).

Class Schedule: The course is taught in E2.

Form: The course consists of lectures and theoretical exercises and practical programming exercises. Please read the material and have a look at the exercises before the lectures.

Evaluation: Written examination and written reports on three sets of mandatory exercises.

A mark for the three mandatory exercises is computed from the two (best) of the three assignments. In the final mark for the course, the written examination counts 2/3 and the computed mark for the mandatory assignments 1/3.

Written examination: Look here

Curriculum for the written examination is found here

Mandatory assignments: Schedule

  1. First mandatory assignment must be turned in on October 8.
  2. Second mandatory assignment must be turned in on November 12.
    1. Test cases for Exercise 1 are described here.
    2. Test your program for Exercise 2 on the following two files (at least): ex1.ex and ex2.ex.
  3. Third mandatory assignment must be turned in on November 29.

Lectures: Monday 13.00 - 14.45 and Thursday 8.15 - 10.00, Building 308, Auditorium 12

Exercise classes:

Databar reservations: Monday 13.00 - 17.00 and Thursday 8.00 - 12.00, Building 303, Rooms 47+48

Teachers: Martin Fränzle and Michael R. Hansen.

Teaching assistant: Peter Eriksen, Anders Dohn Hansen, Jacob Irsberg, Francisc-Raul Kantor

Textbooks: Available in a "bundle" in the DTU bookstore. Price 1145 kr (before student discount)

A preliminary course plan: is found here.