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 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
• Methods for syntax-directed translation (SDT) and conditions for their application: during LR parsing (in detail); tree traversal; dependency graph.
• Application of SDT to the translation of programming languages: translation of expression, control structures, boolean expressions

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

Lectures, exercises.

Students with physical disabilities, Learning Disabilities or Special Education Needs can request specific services and tools via the Staff Sviluppo e Coordinamento Carriere e Servizi alle Studentesse e agli Studenti, consulting the University webpage: https://www.uniupo.it/en/services/services-students-physical-or-learning-disabilities Students with disabilities, learning disabilities or special education needs, once they have contacted the University Staff, can refer to the tutor in charge of the course to define the examination modalities, concerning academic aspects.

Written examination (oral examination is optional). It contains both practical exercises and theoretical questions about different topics. The evaluation is established jointly by the lecturers. The evaluation measures the proportion of achievement of the learning objectives.

- 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:
knowing and understanding 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, during syntax tree traversal, using the dependency graph, and conditions for their application.

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:
acquiring and adopting the rigorous terminology used in the theory of languages

Learning capacity:
recognizing classes of problems and face them adopting the appropriate methodologies. Capability of modeling and analyzing problems in a formal way.