DM565: Formal Languages and Data Processing

Study Board of Science

Teaching language: Danish or English depending on the teacher
EKA: N330042102
Assessment: Second examiner: External
Grading: 7-point grading scale
Offered in: Odense
Offered in: Autumn
Level: Bachelor

STADS ID (UVA): N330042101
ECTS value: 10

Date of Approval: 25-03-2019


Duration: 1 semester

Version: Archive

Comment

New course autumn 2019

Entry requirements

None

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

The aim of the course is to enable the student to express formal languages using different formalisms, including selecting the appropriate formalism for a given problem, taking efficiency into account.

There exist thousands of data formats and realistic projects will often draw on a variety at the same time. The course will enable the students to process data formats through automated processes, and transform one data format to another.

One of the most advanced forms of data transformation is the one a compiler realizes by the translation from a high-level to a low-level language. The course will equip the students with knowledge of the essential techniques in such processes.

Finally, the students will be introduced to innovative processes, concretized through a project of their own.
The course builds on knowledge acquired in courses on algorithms and data structures, discrete mathematics, and computer architecture, and gives and academic basis for studying complexity and computability, placed later in the education.

In relation to the competence profile of the degree, the focus of the course is to give the students the necessary competences to express specifications of formal languages through the profession's most important formalisms, recognize essential elements of data formats, and be able to transform simple as well as complex formats to others, including being able to choose the most appropriate technique for a given problem. In addition, the student will acquire competences in value creation through innovative processes by using central elements from the course in combination with techniques taught earlier.

Expected learning outcome

The learning objective of the course is that the student demonstrates the ability to:

  • 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

The following main topics are contained in the course:

  • 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

See Blackboard for syllabus lists and additional literature references.

Examination regulations

Exam element a)

Timing

January

Tests

Written exam and project with oral defence

EKA

N330042102

Assessment

Second examiner: External

Grading

7-point grading scale

Identification

Student Identification Card

Language

Normally, the same as teaching language

Examination aids

Allowed, a closer description of the exam rules will be posted under 'Course Information' on Blackboard.

ECTS value

10

Additional information

At the final assesment the written exam is weighted highest .
The examination form for re-examination may be different from the exam form at the regular exam.

Indicative number of lessons

62 hours per semester

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.

Teacher responsible

Name E-mail Department
Kim Skak Larsen kslarsen@imada.sdu.dk

Timetable

Administrative Unit

Institut for Matematik og Datalogi (datalogi)

Team at Educational Law & Registration

NAT

Offered in

Odense

Recommended course of study

Profile Education Semester Offer period