Ateneo - UPO

Part 1 (6 credit)
Formal languages, context free grammars, automata, LR parsing.

Part 2 (3 credits)
Implementation of a recursive descent top-down compiler for an expression language

Part 1
S. Crespi Reghizzi , L. Breveglieri, A. Morzenti, Linguaggi formali e compilazione, Esculapio.
Part 2
Charles N. Fischer, Ron K. Cytron, Richard J. Le Blanch Jr., "Crafting a compiler", Addison-Wesley.

The course aims to introduce the fundamental concepts concerning lexical and syntactic analysis and the techniques of translation and interpretation in the context of formal languages. Theoretical and practical aspects are considered. For the theoretical part, the goal is to understand the relationships between languages ​​and automata and the expressiveness of the class of regular and context-free languages. For the practical part, the objective, through the implementation of a compiler, is to apply the theoretical notions introduced and also to learn how to structure a complex system in successive phases by identifying the data structures and functions that constitute the interfaces between the various phases.

Knowledge of the topics of Programming 1 and 2; Object Oriented Programming: Algorithms 1

Part 1
Teacher lessons in classroom, exercitations.
Part 2.
Initial (theoretical) lessons for about 5 lessons. Laboratory lessons for the development of the compiler

For laboratory lessons, students are invited to submit the developed parts weekly (partly in the laboratory and partly independently). Students' papers are commented in the classroom.
Students with physical disabilities, Learning Disabilities or Special Education Needs can request specific services and tools to the Staff of the "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.

The final evaluation is established jointly by the course teachers taking into account the knowledge and skills acquired by the student and verified by carrying out the two parts of the exam detailed below: on both components a minimum grade must be reached.

Part 1.
Written examination: 7-8 questions, that can be both applied exercise and theoretical questions on recognizers automata and on different types of languages showed and discussed

Part 2.
The exam consists of a written test and the presentation of the developed compiler with relative oral discussion.
The written assignment contains an exercise asking to determine whether a grammar is LL(1) and some derivations of strings of the language and three open-ended questions on the theory of formal languages ​​relative to the development of compilers. To achieve a pass, the student must demonstrate that he has completed the exercise with negligible errors.
The compiler must be presented to access the written test. The oral discussion is done together with the presentation of the result of the written test. The vote on the project depends on its correctness and the programming style adopted.
The Part 2 grade is the average of the project grade and the written assignment grade.

In the final evaluation the score of Part 1 weighs 2/3 and that of Part 2 weighs 1/3, according to the number of credits of the two parts.

Part 1
- Regular languages and expressions
- Context free grammars and languages
- Linear grammars, and correspondence to regular languages
- Attribute grammar
- 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))

Part 2.
- Introduction to compilers.
- Structure of compilers
- Lexical analysis: tokens and their production
-Syntactic analysis: top-down recursive descent parsing
- Abstract syntactic tree and Symbol table.
- Pattern visitor for type analysis and code generation.

Part 1
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

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) to recognize deterministic context free grammars

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

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.

Part 2
Knowledge and understanding: the student must become familiar with the transformation of formal concepts (such as automata and grammars) into tools for syntax direct translation of languages.

Applying knowledge and understanding: the student must be able to design and implement a syntax direct translation of a simple programming language, being able to independently design the necessary data structures and modularising its code

Making judgments: the student must be able to recognize the appropriateness of using different kinds of syntactic analyzers, highlighting the advantages and disadvantages.

Communication skills: the student must be able to expose and motivate both orally and in writing his/her own choices.