Principles and Implementation of Programming Languages (Laurea Magistrale LM-18)

Instructor: Elena Zucca

Aim

To be able to understand and implement formal descriptions of syntax, type system and execution models of programming languages.

AulaWeb a.a. 15/16

AulaWeb a.a. 14/15

AulaWeb a.a. 13/14

Topics

• Syntax and language recognition
  • Basic definitions: alphabet, string, language
  • Regular languages, regular expressions, DFAs and NFAs. Pumping lemma. Lexical analysis.
  • Context-free grammars, PDAs, Chomsky hierarchies, context-sensitive languages.
  • Syntactic analyisis (parsing), top-down parsing, predictive parsing, LL(k) grammars, bottom-up parsing, LR(k) grammars.
  • Abstract syntax. Internal representation (AST).
  • Using ANTLR for lexical analysis, parsing and AST construction.
• Execution models
  • Abstract machines (small-step semantics), example of natural and boolean expressions.
  • Lambda calcolus, imperative extension, extension with error/exceptions.
  • Featherweight Java.
  • Using ANTLR for developing interpreters/code generation.
• Type systems
  • Type system for the language of boolean and natural expressions, soundness, progress and type preservation.
  • Simply-typed lambda calculus, type systems for the extensions.
  • Type system for Featherweight Java.
  • Using ANTLR for developing type checkers.

  Textbooks and links

  • Course notes in italian (current version available on Aulaweb).
    For an english version you can read:

    Introduction to Automata Theory, Languages, and Computation (3rd Edition) by Hopcroft, Motwani, and Ullman.
    

    Compilers: principles, techniques, and tools by Aho, Lam, Sethi, Ullman.
    

    Types and Programming Languages by Pierce, available in the library. [Chapters 3, 5, 8, 9, 11 (1-6, 11), 13, 14, 19]

  • The Definitive ANTLR reference: building domain-specific languages, by Parr.

  Exam

  The exam consists of a written test, an oral test and the development of a small project (see Aulaweb for project topics).
  To try the oral exam you should get at least 18 at the written test. The written test grade is kept for the two following exam sessions.

  Examples of exercises for the written test

  You can refer to the file of previous exams Moreover:

  For the second and third topic (execution models and type systems), you can also find some examples in the file of exams of the (old) course "Informatica Teorica".
  
  
  Back to previous page
  

  ---

  Last change: November, 27, 2015