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
- 2021/2022
- Teacher
- MARCO GAVANELLI
- Credits
- 6
- Didactic period
- Secondo Semestre
- SSD
- ING-INF/05
Training objectives
- The main objectives of the course are two:
1. to learn the main theoretical and practical knowledge required to define a programming language and to develop a translator for such language (interpreter or compiler), with particular emphasis on the recognition phase (tokenization and parsing)
2. develop programs in a functional programming language (that is one of the four programming paradigms), using and implementing higher order functions.
For the first objective, the main acquired knowledge consists of
- knowledge of the language types according to the Chomsky classification, linking the language expressivity with the complexity of the corresponding recognizer automata
- main methodologies for developing recognizers, interpreters and compilers for regular languages and context-free languages.
The main abilities for the first objective will be:
- formally defining languages and corresponding grammars
- know the relations between grammars and languages
- classify formal grammars in the Chomsky hierarchy
- design recognizers for regular grammars
- design recognizers for context-free grammars with the LL methodology
- design interpreters and sketches of compilers for a simple grammar
- capability to use tools for automatic generation of regular language recognizers
For the second objective, the acquired knowledge will include
- describe the main characteristics of functional programming and differences with the imperative and object-oriented paradigms
- development of programs in a purely functional language
- describe and use during programming lazy parameter passing
- develop programs using higher order functions; develop new higher order functions
- develop programs using the input/output monad, to keep separate purely functional programming and input/output with imperative-like syntax.
The main ability for the second objective will be to develop programs in a functional language (Haskell) using the main features of functional languages, including
- develop and use higher-order functions
- use of lazy evaluation of argument to improve efficiency or to avoid infinite loop cases
- usage of the input/output monad Prerequisites
- Knowledge of languages of imperative programming and object oriented programming.
Finite state automata Course programme
- The course provides a description of the problem of recognizing programming languages, relating their expressivity of the language with the machine necessary to recognize it.
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 LL for 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
- In this course the method of the "flipped classroom" is be adopted.
Students will be provided video-lessons, that can be accessed autonomously before the lessons.
In the classroom, or in the computer science laboratory, the video-lessons will be discussed, students will be able to ask explanations about the video-lessons, and exercises will be proposed to the students, that will carry out them collectively, in small groups, or individually.
In order to obtain the first objective (knowledge of programming language specifications and their interpretation), frontal lessons are given in the classroom, projecting slides. The slides are provided online on the course web site. During the lessons, exercises will also be carried out on the blackboard; to stimulate student intervention and to improve learning, some exercises will be carried out by building the solution together with the students.
In order to achieve the second objective (knowledge of functional programming), the lectures on this topic will be divided into two parts. The first part of the lesson will be given in the classroom, projecting slides and with exercises on the blackboard. The second part will be in the computer lab, where students will be able to practice, by writing programs in Haskell language, the knowledge acquired in the first part of the lesson.
In the lessons in the computer lab, students will also be able to develop programs in the Haskell functional language, with the help of the professor. Learning assessment procedures
- In order to assess the student's knowledge of grammar, languages ¿¿and recognizers, a written test is done, in which the student can be asked to
- write a grammar related to a simple language
- classify a grammar according to the Chomsky hierarchy
- write an LL recognizer automaton for a context-free language
- write, given a regular grammar, a regular expression to describe the same language or vice versa (from regular expression derive a corresponding grammar).
In order to assess the student's knowledge of functional programming, a computer laboratory test is performed. In this test, the student will have to write a program in Haskell language.
The two tests take place on the same day, for example one in the morning and the other in the afternoon.
The final grade is given by the sum of the marks in the two tests.
During the exams, it is not allowed to use paper material, notes, etc. In the laboratory test, students can access the documentation, installed in the computers of the laboratory, associated with the various software packages and languages.
The exam can be taken in English, upon request at least one week in advance.
In case the exam cannot be done in presence, due to rules for social distancing, the exam will consist of
1. a homework program to be developed in the Haskell language. The work must be agreed upon with the professor, and it is typically on the part of the programme on languages and grammars.
2. an oral in which the student is requested to
a. present his/her homework program in Haskell
b. do exercises
c. answer questions on the theory. Reference texts
- REFERENCE MATERIAL:
- video-lelessons provided by the professor
- slides projected during the lessons, available on the course web site
RECOMMENDED BOOKS FOR INSIGHTS ON LANGUAGE THEORIES AND COMPILERS
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.
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
