Formal Languages and Compilers

News

  • July 3rd, 2016: The exam on July 5th has been anticipated to 9.30am
  • May 22nd, 2016: On Wednesday 24th an additional lesson is planned from 9am to 11am, in place of the Software Engineering II course.
  • May 2nd, 2016: There will be no lesson in the week May 9-13. In the same days I'll be attending the Learn PAd EU research project periodic meeting.
  • April 19th, 2016: Tomorrow Wednesday April 20th starting from 3pm I need to attend at the “Consiglio di Scuola”. The lesson will not be held
  • April 12th, 2016: Tomorrow Wednesday April 13th there will be a session of thesis defences. The lesson will not be held
  • March 18th, 2016: The lesson of Wednesday March 23rd is cancelled. Next lesson after the Easter period will be on Wednesday March 30th.
  • March 2nd, 2016: From March 8th lessons will be held in room D.M.Ritchie
  • February 27th, 2016: As per request of some student, on Wednesday March 2nd there will be no lesson
  • February 22nd, 2016: There will be no lessons in the week April 4th - April 8th
  • February 22nd, 2016: The page is on-line

General Information

Teacher:

Lessons schedule:

  • Tuesday 11am - 1pm
  • Wednesday 3pm - 5 pm

Office Hours :

  • Tuesday 5pm - 6pm (better if you announce yourself via e-mail)

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) need 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

The course will delve into the following topics (for students convenience chapters in the textbook are indicated within parenthesis)

  • 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, patterns, and lexemes
    • Regular expressions and definitions
    • Finite Automata
      • DFA - Deterministic Finite Automata
      • NFA - Non Deterministic Finite Automata
    • From RegExp to NFA
    • From NFA to DFA
    • DFA Minimization
    • 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 (section 5.5 excluded)]
    • Syntax-Directed Definitions
    • Inherited and Synthesized Attributes
    • Dependency Graphs
    • Syntax-Directed Translation Schemes
  • Intermediate Code Generation [ALSU - Ch. 6 (sections 6.7,6.8,6.9 excluded)
    • Three-Address Code
    • Type Checking
    • Control Flow Translation schemes

Study Material

Course Slides

Textbooks

Exams

Exam Dates A.Y. 2015/2016

  • June 14th and July 5th, 2016
  • September 6th and 27th, 2016
  • February 7th and 21st, 2017

Exam rules:

The Exam foresees two different papers:

  • Written paper – on the date fixed for the exam the students will be required to solve some theoretical and practical exercises.
  • Oral paper – the student that have passed the previous paper

Results

Results for the written paper of xxx (in red marks below the threshold):

Matr. N. Ex.1 Ex.2 Ex.3 Ex.4 Mark