Teaching directory
Course 2022-2023

Language theory: syntax and semantics [INFOB314]

  • 5 credits
  • 30h+30h
  • 2nd quarter
Language of instruction: French / Français

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).
 
 

Objectives

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.
 

Exercises description

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
 
 

Prerequisites

The teaching units from one of the following lists:

  1. Algorithmique [INFOB237] et Fondements mathématiques pour l'informatique (2e partie) [INFOB221]
  2. Systèmes d'exploitation [INFOB231]

Teaching methods

The lectures focus on the underlying theoretical bases. The exercises will apply the theory to simple examples.

Alarge assigment aims at compiling a simple language.

 
 

Evaluations

60% Written exam 

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

 
 

Recommended readings

  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

French / Français

Location for course

NAMUR

Organizer

Faculté d'informatique
rue Grandgagnage 21
5000 NAMUR
P. 081725252
F. 081724967
secretariat.info@unamur.be

Degree of Reference

Undergraduate Degree