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
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.