Formal Languages and Compilers

News

  • June 13th: Dear students due to a concurrent meeting tomorrow lesson cold start with some delay. Please note that there will be no lesson on the 15th, and the last lesson will be taught on June 22nd
  • May 23rd: Dear students due to a concurrent meeting next Thursday May 25th lesson is canceled
  • May 16th: Dear students tomorrow lesson will start at 2pm and will end at around 3:30 pm
  • May 8th: Dear students please note that next Wednesday lesson is canceled
  • April 25th: Dear students please note that this week lessons are canceled
  • April 18th: I would like to inform the students that tomorrow lesson will be delivered according to the usual schedule
  • September 7th, 2016: The page is on-line

General Information

Teacher:

Lessons schedule:

  • Wednesday, 2pm-4pm, room AB1
  • Thursday, 2pm-4pm, room AB1

Office Hours :

  • Thursday 12pm - 1pm (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. 2016/2017

  • July 5th and 19th, 2017 - 11am room AB1
  • September 6th and 20th, 2017 - 11am room AB1
  • February 7th and 21st, 2018 - 11am room AB1

Exam rules:

The Exam foresees three different papers:

  • Written paper – on the date fixed for the exam the students will be required to answer to some theoretical questions and to solve some practical exercises.
  • Project paper – the students will be asked to develop a small group project using ANTLR
  • Oral paper – students that, having passed the written paper would like to increase the mark

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