Ateneo - UPO

Formal languages, context free grammars, automata, LR parsing. Syntax-directed translation and its use for the translation of imperative programming languages.

Stefano Crespi Reghizzi “Sintassi, semantica e tecniche di compilazione Volume 1: Metodi Sintattici”, CLUP.
A. V. Aho, R. Sethi, J.D. Ullman: "Compilers Principles, Techniques and Tools", Addison-Wesley, 1986 oppure A. V. Aho, M.S. Lam, R. Sethi, J.D. Ullman: "Compilers Principles, Techniques and Tools", 2a edizione, Addison-Wesley, 2006

The students must have achieved the following Knowledge and capabilities:
• modeling regular and context-free languages (through regular expressions and -possibly linear- context-free grammars).
• Recognizing regular and context-free languages through automata (finite automata and pushdown automata)
• Knowing LR(0) and SLR(1) parsing, developing LR(0) and SLR(1) parsers staring from a context-free grammar
• Syntax-directed translation (SDT) during LR parsing (in detail); further options for SDT.

Basic notions acquired in the programming courses of the first two years.

Lectures, exercises.

Written examination (oral examination is optional). It contains both practical exercises and theoretical questions.

- Regular languages and expressions
- Context free grammars and languages
- Linear grammars, and correspondence to regular languages
- Context sensitive grammars (hints).
- Main syntactic structures and grammar rules to generate them
- Finite-state automata and relationships to regular languages
- Stack automata (deterministic and non-deterministic) and relationships to context
free languages
- Basic bottom up parsing theory, focusing on LR parsing (LR(0) e SLR(1)) .
- Syntax-directed translation: attribute grammars and translation schemes.
- Intermediate code generation

Knowledge and comprehension:
the students must know and understand the following basic notions:
regular languages and expressions, linear grammars, (deterministic and non-deterministic) finite automata
context free languages and grammars, (deterministic and non-deterministic) pushdown automata
LR(0) and SLR(1) parsing.
Syntax-directed translation (SDT) during LR parsing (in detail); further options for SDT.

Capacity to apply knowledge and comprehension:
modeling regular languages via regular expression
modeling languages via context free grammars
developing pushdown automata on the basis of context free grammars
developing deterministic pushdown automata to recognize deterministic context free languages
developing LR(0) and SLR(1) parsers to recognize deterministic context free grammars.
Application of syntax-directed translation to the compilation of programming languages.

Judgement autonomy:
recognize regular languages vs. context free languages
know the relationships between classes of languages, classes of grammars, and classes of automata
choosing the proper constructs to define context free grammars recognizing a given language. Being able to recognize whether SDT can be performed during LR parsing.

Communication abilities:
Students must acquire and adopt the rigorous terminology used in the theory of languages

Learning capacity:
Students must acquire the capabilities to recognize classes of problems and face them adopting the appropriate methodologies. They should also acquire the capability of modeling and analyzing problems in a formal way.