DM565: Formal Languages and Data Processing
Comment
Entry requirements
Academic preconditions
Students following the course are expected to have knowledge of central elements in courses on algorithms and data structures and discrete mathematics, including trees, recursive definitions, basic proof techniques, search trees, and hash tables, as well as having programming experience, including assembler programming.
The course cannot be chosen by students who have taken DM546.
Course introduction
Expected learning outcome
- construct finite automata and regular expressions for simple languages and be able to convert between these.
- formulate context-free grammars and context-free languages.
- transform between a selection of data formats.
- express languages using regular expressions and use these to construct scanners for lexical analysis.
- decide if a grammar is LL(1) or LR(1) and adjust it if it is not, and be able to construct parsers for the syntax analysis based on the corresponding language classes.
- design abstract syntax trees and build these during parsing.
- use abstract syntax trees for a variety of purposes, e.g., for type-checking programming languages using symbol tables.
- transform abstract syntax tree for a high-level language to a low-level language.
- execute a process focused on innovative information processing through a project, where existing data is extracted, transformed, and combined to create new value, with a business model as a starting point.
Content
- regular expressions
- finite automata
- context-free grammars
- data formats and transformation
- LL(1) and LR(1) languages and grammars
- top-down and bottom-up parsing techniques
- internal representation
- type-checking
- translation/compilation
- innovation
Literature
Examination regulations
Exam element a)
Timing
Tests
Written exam and project with oral defence
EKA
Assessment
Grading
Identification
Language
Examination aids
ECTS value
Additional information
The examination form for re-examination may be different from the exam form at the regular exam.
Indicative number of lessons
Teaching Method
At the faculty of science, teaching is organized after the three-phase model ie. intro, training and study phase.
A modified variant of a classic lecture is used in the intro phase, where foundational concepts and methods are presented theoretically as well as through examples on concrete data. Questions and discussions are encouraged. The skill training phase revolves around exercises and discussion topics relating to the material introduced in the preceding intro phase hours. During the skill training hours, the students can work specifically with the more challenging topics. In the study phase, the students work with a project and its relation to the subject terms. Questions that arise can be brought up during meeting times.
Study phase activities: The students work with a project and its relation to the subject terms. Questions that arise can be brought up during meeting times.