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
Propedeutic courses:
- Programming
- Algorithms and Data Structures
- Computer Architecture
- Discrete Mathematics and Mathematical Logics
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
Further information
Office hours:
Monday and Thursday 14-15.30 or by appointment
Contact:
Viale Morgagni, 65 - 50134 Firenze
Phone: 055 2751482 / 329 2985755
E-mail: elena.barcucci@unifi.it
Web: e-l.unifi.it
Type of Assessment
Written exam consisting in exercises testing the ability to apply the studied methodology and questions about the theoretical aspects.
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.