====== Formal Languages and Compilers ======
----
===== News =====
<WRAP center round important 95%>
  * **<wrap em>June 13th:</wrap>** 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 
</WRAP>

----
===== General Information =====
<WRAP box round 95% center>
**Teacher**: 
  * [[http://www.cs.unicam.it/polini|Andrea Polini]] 
**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)
</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_1617:01_introduzione.pdf |Course introduction}} - March 22nd
  * {{ :didattica:magistrale:flc:ay_1617:lexicalanalysis.pdf |Lexical Analysis}} - March 23rd, 29th, 30th, April 5th
  * {{ :didattica:magistrale:flc:ay_1617:syntaxanalysis.pdf |Syntax Analysis}} - April 6th, 12th, 13th, 19th, 20th, May 3rd, 4th, 11th
  * {{ :didattica:magistrale:flc:ay_1617:semanticanalysis1.pdf |Semantic Analysis - Syntax directed translation}} - May 17th, 24th, 31st, June 1st
  * {{ :didattica:magistrale:flc:ay_1617:semanticanalysisii.pdf |Semantic Analysis - Intermediate Code Generation}} - June 7th, 8th

  * {{ :didattica:magistrale:flc:ay_1617:project.pdf |Project paper}}
  * {{ :didattica:magistrale:flc:ay_1617:esamiflc_collection.tar.gz |Collection of previous exams}}
  * {{ :didattica:magistrale:flc:ay_1617:esercizi.pdf |Exercises}} - June 21st, 22nd
**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. 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 ^
|  |  |  |  |  | <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>