Formal Languages and Compilers

News

  • March 4th, 2015: In the results section you can find the marks for February 24th exam. Next Monday March 9th at 11am (Turing Lab) I'll present and discuss the solutions to the exercises. At the same time I'll give back the written papers to the exam candidates.
  • February 15th, 2015: In the results section you can find the marks for February 10th exam. Next Thursday February 19th at 3pm (Turing Lab) I'll present and discuss the solution, and I'll give back the written papers to the exam candidates.
  • February 5rd, 2015: Here you can download the exercises on Semantic analysis discussed during last monday lesson.
  • February 3rd, 2015: Here you can download the exercises on Lexical and Syntax analysis discussed during last monday lesson. In the next days I will upload the exercises on Semantic Analysis with solutions.
  • January 17th, 2015: timetable for next weeks lessons:
    • Tuesday 20th, 3pm - 6pm
    • Wednesday 21th, 10am-1pm
    • Tuesday 27th, 3pm-6pm
    • Wednesday 28th, 3pm-6pm
  • January 7th, 2015: The description of the class project is available here
  • December 18th, 2014: By the end of the year I will publish here the assignment for the compiler constuction project.
  • December 17th, 2014: I apologize but due to some delayed administrative duties, that I have to close by tomorrow and related to tomorrow defenses, I have to cancel tomorrow lesson. Next lesson will be on January 13th. I wish to all students a nice Christmas period.
  • November 23, 2014: Due the participation to a European Project Meeting I will not be able to be in Camerino on next Thursday, November 27th
  • November 19th, 2014: Here the solution for the exercise started during the last class.
  • November 5th, 2014: Dear students the course this year seems unlucky. I've got the flu and I'll not be able to come to Camerino tomorrow.
  • November 3rd, 2014: I apologize but due to a deadline related to the management of the Computer Science curriculum I'll not be able to make the lesson tomorrow (November 4th). Next class will be on November 6th.
  • October 28th, 2014: due to previous engagements I cannot be in Camerino on October 30th. Next class will be on Tuesday - November 4th.
  • October 17th, 2014: the course web site is now on-line

General Info

Teacher:

Lessons schedule:

  • Tuesday, from 3pm to 5pm - room Turing
  • Thursday, from 3pm to 5pm - room Turing

Students reception hours:

  • Thursday from 2pm to 3pm

Course Objectives

The course intends to provide to the students the theoretical background to understand how a language compiler can be built. The general architecture of a compiler is presented and which are the tools and mechanisms (theoretical and practical) needed in order to derive a real compiler. Competences are put in place with the construction of a simple compiler for a simple language.

Course Contents

  • General Introduction to Compilers construction [ALSU - Ch.1]
    • Structure of a compiler
    • Evolution of programming languages
    • Generalities on programming languages
  • Lexical Analysis [ALSU - Ch.3]
    • Lexical analysis objectives and issues
    • Tokens and lexemes
    • Regular expressions and definitions
    • Finite Automata
      • DFA - Deterministic Finite Automata
      • NFA - Non Deterministic Finite Automata
    • From rexp to NFA
    • From NFA to DFA
    • Recongnition of tokens
  • Syntax Analysis [ALSU - Ch.4]
    • Introduction to CF grammars and Push-Down automata
    • Parse tree and derivations
    • Ambiguity
    • Top-down parsing
      • Left recursion and left factoring
      • Recursive descent parsing
      • FIRST and FOLLOW sets
      • Non recursive predictive parsing
      • Error recovery in predictive parsing
    • Bottom-up parsing
      • Reductions, Handles
      • Shift-reduce parsing
      • LR(0) automaton and table
      • SLR table
      • LR(1) automaton and table
      • LALR table
      • Error recovery in LR parsing
  • Syntax-Directed Translation [ALSU - Ch.5]
    • Syntax-Directed Definitions
    • Inherited and Synthesized Attributes
    • Dependency Graphs
    • Syntax-Directed Translation Schemes

Study material

Course Slides

Warning: slides are distributed to help students in their preparation to the exam. In no way they intend to substitute text books. Instead the thorough study of books constitutes the most wise strategy to maximize the chances to pass the exam.

Reference books

  • [ALSU] Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman, Compilers - Principles, Techniques, and Tools, 2nd Edition, Pearson Education 2007.
  • [ANT] Terence Parr, The Definitive ANTLR 4 Reference, The Pragmatic Programmers, 2012

Exams

Exam Dates A.Y. 2014/2015

  • February 10th, 2015 - from 3pm to 5pm - Boole Lab. Palazzo Battibocca
  • February 24th, 2015 - from 3pm to 5pm - Boole Lab. Palazzo Battibocca
  • June 9th, 2015 - from 3pm to 5pm
  • July 7th, 2015 - from 3pm to 5pm
  • September 8th, 2015 - from 3pm to 5pm
  • September 29th, 2015 - from 3pm to 5pm
  • February 9th, 2016 - from 3pm to 5pm
  • February 23th, 2016 - from 3pm to 5pm

Exam Results