Formal Languages and Compilers
2021/2022

This page contains information for students of the Formal languages and compilers course in 2021/2022. It summarizes all the essential to complete the subject. The following information may change during semester.

Links

• Official page
• Previous year (2019/2020)

Lecturers

• Dominika Regeciova
• Adam Kovari

Lectures

Every week on Tuesday, M104, 8:00 - 10:50

Slides and other materials

Number	PDF	Topic
1		Alphabet, strings, and languages
2		Introduction to compilers
3		Models for regular languages
4		Variants of finite automata
5		Lexical analysis
6		Models for context-free languages
7		Top-down parsing
8		Bottom-up parsing
9		Syntax-directed translation and intermediate code
10		Optimization and code generation
11		Properties of regular languages
12		Properties of context-free languages
13		Beyond context-free languages

Other slides

Number	PDF	Topic
1		What are formal languages and compilers?

Study materials

Number	PDF	Topic
1		Mathematical Foundations of Formal Language Theory
2		Exercises

Midterm

The midterm exam will be held on October the 26th, at 08:00, in room M104. You can obtain up to 20 points.

Project

Your task is to implement a program which, given a composition of functions, like "add(5, mul(3, sub(10, pow(6, 4))))", transforms it to an equivalent mathematical expression, "5 + 3 * (10 - 6^4)" in this case. You can obtain up to 25 points.

• Functions: add(x, y) (addition), sub(x, y) (subtraction), mul(x, y) (multiplication), div(x, y) (division), mod(x, y) (modulo), pow (x, y) (power), where x, y are operands

• Operand: a number conforming to the following grammar

     <number> ::= <optional-sign> <digit-sequence> <optional-fraction> <optional-exponent>
     <optional-sign> ::= "" | "+" | "-"
     <optional-fraction> ::= "" | "." <digit-sequence>
     <optional-exponent> ::= "" | "e" <optional-sign> <digit-sequence>
     <digit-sequence> ::= <digit> | <digit> <digit-sequence>
     <digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
  

• Other elements: brackets ( and ) and whitespace (in the evaluated expression, there can be any number of whitespace characters, like spaces)

• Desired result: A mathematical expression equivalent to the specified composition of functions. Make sure the order of operation application stays the same. Unnecessary brackets should be omitted.

  The operator precedence has three levels, from lowest to highest:

     1: +, -
     2: *, /, %
     3: ^
  

  The ^ operator is right associative, other operators are left associative.

• Implementation language: You can use any programming language you like. However, do not use any of its features that would oversimplify the program. You have to implement all analyses (lexical, syntax, etc.) and interpretation by yourselves. Preferred languages are multi-platform languages, such as C, C++, Java, Python, Perl

• Recommendations: for lexical analysis, use regular expressions and finite automata; for syntax analysis, use context-free grammars and precedence-based parsing (we will talk about it during the semester)

There will be organized a special project lesson at the end of semester.

Deadline: 2021-12-14

You are allowed to take the final exam before submitting the project. The points from the final exam will be counted if and only if you obtain at least 5 points from the project.

Final Exam

Date: 2021-12-14 08:00, M104. You can obtain up to 55 points.

What we have covered in the lectures:

• Alphabet, strings, and languages (all slides)
• Introduction to compilers (all slides)
• Models for regular languages (all slides)
• Variants of finite automata (1- 35)
• Lexical analysis (1 - 7)
• Context-free grammars and pushdown automata (all slides)
• Top-down parsing (1 - 49)
• Precedence parsing (all slides)
• Syntax-directed translation and code generation (1 - 16)

What you have to know for the final exam:

• basic notions, like an alphabet, string, language, operations over strings and languages
• structure of a compiler, what every of its parts does
• regular expressions, create a regular expression for a given language, convert a regular expression into a finite automaton
• finite automata, create a finite automaton for a given language
• removal of e-moves from finite automata, make a finite automaton deterministic, remove inaccessible and non-terminating states, convert a finite automaton into a complete finite automaton
• context-free grammars, create a context-free grammar for a given language, convert a context-free grammar into a pushdown automaton (a general top-down or bottom-up parser)
• LL grammars, create an LL table from a given LL grammar
• precedence-based parsing, create a precedence table from a given grammar

To receive the points from the final exam, you have to obtain 20 points during the semester; out of these 20 points, at least 5 points have to be obtained from the project. To successfully finish the course, you have to obtain at least 50 points.