Course teached as: B018759 - INTERPRETI E COMPILATORI 3-years First Cycle Degree (DM 270/04) in COMPUTER SCIENCE
Teaching Language
Italian
Course Content
Languages and grammars; regular sets; context-free grammars; Chomsky and Greibach normal forms. Finite automata and regular languages; pumping lemma for regular and context-free languages; properties of context-free languages. Chomsky hierarchy, Turing machines.
Structure of a compiler. Lexical analysis, sintax analysis. Sintax-directed translation. Intermediate-code generation. Storage organization.
- Thomas A. Sudkamp
Languages and Machines
Addison-Wesley, 1997
- John E. Hopcroft, Rajeev Sethi, Jeffrey D. Ullman
Automi, linguaggi e calcolabilità
Pearson, 2009
- Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman
Compilatori: Principi, tecniche e strumenti
Pearson, 2009
Learning Objectives
Knowledge acquired:
Properties of formal languages and connection with grammars and automata; structure and functions of compilers, tools for analysis and translation.
Competence acquired:
competences in the theory of formal languages related to grammars, automata and analysis and translation phases in compilers.
Skills acquired (at the end of the course):
At the end of the course the students should be able to address and solve the problems connected with formal languages, the definition of grammars, the design of automata and the application of such techniques in the design of compilers.
Prerequisites
Courses recommended:
Programming
Algorithms and Data Structures
Teaching Methods
Number of hours for personal study and other individual learning: 135
Number of hours for classroom activities: 72
Number of hours for laboratory activities: 12
Number of hours per course tests: 6
Written exam consisting in exercises and questions about the theory.
Oral exam is optional.
The written exam can be splitted in two parts (in november and at the end of the course).
Course program
Languages and grammars: regular sets; regular grammars; context-free grammars; derivations and ambiguity; parsing; Chomsky and Greibach normal forms. Finite automata and regular languages: deterministic and nondeterministic finite automata; pumping lemma for regular languages; properties of regular languages. Pushdown automata and context-free languages: pushdown automata and context-free languages; pumping lemma for context-free languages; properties of context-free languages. Chomsky hierarchy: context-sensitive, recursive and recursively enumerable languages; Turing machines.
Structure of a compiler, lexical, syntax and semantic analysis. Top-down and bottom-up analysis. LL(1), LR(0) and LR(1) grammars. Syntax-directed translation. Attributed grammars. Intermediate-code generation, types and declarations, symbol table, translation of expressions. Storage organization, heap and stack.