Learning outcomes

The student will be able to :

  • recognize problems that can be analyzed using regular expressions, context-free grammars, attribute grammars ;
  • formalize the problem and use software tools to execute this formalization (e.g. build a small compiler).
 
 
 

Goals

Learn the main theories and tools for language engineering, compilation, interpretation

 
 
 

Content

Syntax

  1. Regular expressions and finite state automata
  2. Context-free languages, grammars; LL, LR, and LALR parsers

Semantics

  1. Static semantics: type checking, attributed grammars.
  2. Code generation
  3. Denotational semantics (Scott's domains, abstract interpretation)
  4. Structured operational semantics.

 

 
 
 

Table of contents

Syntax

  1. Regular expressions and finite state automata
  2. Context-free languages, grammars; LL, LR, and LALR parsers

Semantics

  1. Static semantics: type checking, attributed grammars.
  2. Code generation
  3. Denotational semantics (Scott's domains, abstract interpretation)
  4. Structured operational semantics.
 
 

Exercices

The book for exercises (in French) is :

Théorie des Langages de Programmation : Syntaxe et Sémantique
Eléments Théoriques et Exercices - 163 pages
Michaël Marcozzi
(c) Presses universitaires de Namur, 2014, D/2014/1881/3, ISBN 978-2-87037-813-7
 
 
 

Assessment method

60% Written exam 

40% The evaluation of the project is done through automatic testing, a report, an individual exam.

 
 
 

Sources, references and any support material

  1. Aho, Sethi, Ullman: "Compilers: Principles, Techniques, and Tools" Addison Wesley (ISBN 9780201100884)
  2. R. Wilhelm, D. Maurer: "Compiler Design" Addison-Wesley
  3. Dick Grune, Henri E. Bal, Ceriel J.H. Jacobs, Koen G. Langendoen, "Modern Compiler Design", John Wiley & Sons
  4. John Levine, Tony Mason & Doug Brown « lex & yacc », ISBN 1-56592-000-7, 366 pages.
  5. M. Hennessy: "The semantics of programming languages: an elementary introduction using structural operational semantics", Wiley, 1990.
  6. G. Winskel: "The Formal Semantics of Programming Languages: An Introduction.", MIT Press, 1993.
  7. T. Parr: "The Definitive ANTLR Reference", The Pragmatic Bookshelf, 2013.
 
 
 

Language of instruction

English