====== Formal Languages and Compilers ======
----
===== News =====
<WRAP center round important 95%>
  * <wrap em>**July 3rd, 2016**</wrap>: 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 
</WRAP>

----
===== General Information =====
<WRAP box round 95% center>
**Teacher**: 
  * [[http://www.cs.unicam.it/polini|Andrea Polini]] 
**Lessons schedule**:
  * Tuesday 11am - 1pm 
  * Wednesday 3pm - 5 pm
**Office Hours **:
  * Tuesday 5pm - 6pm (better if you announce yourself via e-mail)
</WRAP>
----
===== Course Objectives =====

<WRAP box round 95% center>
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.
</WRAP>

----
===== Course Contents =====

<WRAP round 95% center box>
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
</WRAP>
----
===== Study Material =====
<WRAP box round center 95%>
**Course Slides**
  * {{:didattica:magistrale:flc:ay_1516:01_introduzione.pdf|Course Introduction}} - March 1st
  * {{:didattica:magistrale:flc:ay_1516:lexicalanalysis.pdf|Lexical Analysis}} - March 8th, 9th, 15th
  * {{:didattica:magistrale:flc:ay_1516:syntaxanalysis.pdf|Syntax Analysis}} - March 16th, 22nd, 30th, April 12th, 19th, 26th, 27th, May 3rd, 4th.
  * {{:didattica:magistrale:flc:ay_1516:semanticanalysis1.pdf|Semantic Analysis I}} - May 17th, 24th, 25th
  * {{:didattica:magistrale:flc:ay_1516:semanticanalysisii.pdf|Semantic Analysis II}} - May 31st, June 7th
  * {{:didattica:magistrale:flc:ay_1516:esercizi.pdf|Exercises}} - June 1st, 8th


**Textbooks**
  * [ALSU] Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman, [[http://dragonbook.stanford.edu/|Compilers -- Principles, Techniques and Tools]], 2nd Edition,  Addison-Wesley, 2007.
  * [TP] Terence Parr [[https://pragprog.com/book/tpantlr2/the-definitive-antlr-4-reference|The Definitive ANTLR4 Reference]], The Pragmatic Programmers, 2012.
</WRAP>
----
===== Exams =====
<WRAP box round center 95%>
**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 ^
|  |  |  |  |  | <wrap em></wrap> |

  * Solutions
    * {{:didattica:magistrale:flc:ay_1516:20160614_solution.pdf|June 14th, 2016}}
    * {{:didattica:magistrale:flc:ay_1516:20160705_solution.pdf|July 5th, 2016}}
</WRAP>