PROGRAMMING LANGUAGES AND COMPILERS
Academic year and teacher
If you can't find the course description that you're looking for in the above list,
please see the following instructions >>
- Versione italiana
- Academic year
- 2017/2018
- Teacher
- MARCO GAVANELLI
- Credits
- 6
- Didactic period
- Secondo Semestre
- SSD
- ING-INF/05
Training objectives
- In the course students are presented the main aspects of programming languages theory, of formal definition of programming languages, and of the theoretical and computational aspects necessary for the translation and execution of a program written in a high-level language on the electronic computer.
Programming paradigms are studied as well, with emphasis on functional programming, using Haskell as an example of functional programming language.
The acquired knowledge includes:
- defining and classifying grammars
- concept of computability
- main methodologies for development of parsers, interpreters and compilers for regular languages and context-free languages
- functional programming, lazy evaluation of the arguments of a function, higher-order functions
The main abilities are
- defining formally a grammar and classifying it in the Chomsky hierarchy
- defining and recognizing the relationships between grammars and generated languages
- design parsers for regular languages
- design parsers for context-free grammars using LL(1) and LR(0) methodologies
- design interpreters and sketches of compilers for a simple grammar
- develop programs in functional programming languages exploiting higher-order functions and lazy evaluation of arguments. Prerequisites
- Knowledge of languages of imperative programming and object oriented programming.
Finite state automata Course programme
- Provide a description of the main concepts of programming languages, relating them to the various computational models that form the bases of the various languages and the problem of recognizing languages.
Detailed contents: Formal description and implementation of languages: formal grammars and their properties, Chomsky classification. Relation between grammars and recognizer automata. Lexical analysis and techniques of top-down and bottom-up syntactic analysis for regular languages and context-free languages. Introduction to formal description of semantics. Organization and construction of interpreters and compilers, together with their run-time supports. Semi-automatic tools for the generation of lexical and syntactic analyzers.
Introduction to non-imperative programming styles.
Functional programming and the Haskell programming language. Lambda expressions, Currying, higher order functions. Pattern-matching, list comprehensions. Eager and Lazy evaluation of arguments. Graph reduction techniques to improve the lazy evaluation of arguments. Memory leaks in Haskell. Didactic methods
- The course consists of frontal lessons, with the projection of slides. Students will be able to download the slides before each lesson.
Lessons and exercises are interleaved, by interleaving one concept or linguistic construct with the related examples. Further exercises are given during the lesson either in classroom or in the lab. Learning assessment procedures
- The exam consists of
a lab test, which evaluates the skill of the students to use the programming languages learned during the course, and evaluates the knowledge of the software tools learned during the course;
a written test, with exercises on grammars and theoretical aspects of the course.
The lab test and the written test are held the same day.
The final mark is the sum of the marks obtained in the two tests.
During the exam, using written material or computers (except those in the lab) is forbidden. However, during the lab test, the students have access to the documentation of the software packages they are using.
The exam is passed if the knowledge and skills given in the objectives of the course have been acquired by the student.
Upon request, the exam can be given in English. Reference texts
- REFERENCE MATERIAL:
- slides projected during the lessons, available on the course web site
RECOMMENDED BOOKS FOR INSIGHTS ON LANGUAGE THEORIES AND COMPILING
Maurizio Gabbrielli, Simone Martini. Linguaggi di programmazione - Principi e paradigmi. McGraw-Hill, 2001.
A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman. Compilers: Principles, Techniques and Tools. Second edition, Pearson/Addison-Welsley, 2006.
J. E. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata theory, Languages and Computation, third edition, Pearson/Addison-Wesley, 2009.
S. Crespi Reghizzi, L. Breveglieri, A. Morzenti. Linguaggi formali e compilazione. Società editrice Esculapio 2015.
RECOMMENDED BOOKS FOR INSIGHTS ON THE HASKELL LANGUAGE
Graham Hutton. Programming in Haskell. Cambridge University Press, 2007
Bryan O'Sullivan, Don Stewart, and John Goerzen. Real World Haskell. O'Reilly Media, 2008.
Miran Lipovaca. Learn You a Haskell for Great Good!: A Beginner's Guide. 2011
