Grammars play a central role in Computer Science, thus this course provides an important conceptual support for the rest of your studies. In this course you learn to design grammars, how to build parsers from those, and how to further use the result of those parser. You will see how to generate code for a subset of the C# programming language. More precisely, after successful completion of this course you will be able to:
- describe structures (formulas, terms, ...) using context-free and regular grammars
- recognize or parse sequences of symbols into structures
- analyze grammars to see whether several properties hold
- put together different components such as parsers, analyzers, and code generators
- apply these techniques in the construction of different kinds of programs
- relate grammar formalisms to different sorts of automata
- understand why some programs may or may not be described using context-free and regular grammars
In this course we use Haskell to describe the different components. Knowledge of this language at the level of the course INFOFP Functioneel Programmeren is thus required.
The final grade depends on the two exams and three practical assignments. Let's call your grade for the midterm M1 and the final exam grade M2 (both are zero if you did not take them at all).
The final grade is computed as F = 0.5 × T + 0.5 × P. If you have done all the practicals and all exams, then the final result of the course is:
- The theory grade is T = 0.2 × M1 + 0.8 × M2 if M1 > M2, and T = M2 otherwise. You need T >= 5.0 to pass the course.
- The practical grade is P = 0.2 × first practical + 0.3 × second practical + 0.5 × third practical. You need P >= 5.0 to pass the course.
If you have not submitted one of the practical assignments, or have not taken the final exam, then the final result is:
- Passed with grade F (rounded to one decimal) if F >= 5.5, T >= 5.0, and P >= 5.0.
- Not passed with grade 5.0 if F >= 5.5, but T < 5.0 or P < 5.0
- Not passed with grade F otherwise.
- AANV if F >= 4.0
- NVD otherwise
Results from previous years are not transported to this year.
The repair test requires at least a 4 for the original test.
Many programs take a sequence of symbols as input. These sequences almost always have some structure. Examples of such sequences of symbols are: programs in any programming language; a packet of information sent over the Internet; or information written into a file by a program (with the intention of that information being later re-read).
The structure of those sequences is described with the help of grammars (grammatica's). From these descriptions one can automatically generate programs that recognize the corresponding structure, known as parsers (ontleders). This process of recognition is an important component of many programs, for example, a translator from one data type (say, a source code file) into another (the internal structures used by the compiler). The description of the process of translation makes use of a grammar formalism. By using some specific classes of grammars, we can not only express the structure of the sequence, but also ensure that the structure is easy to recognize; for example, that it can be recognized in linear time.
The load per week is:
Attendance is not strictly mandatory (albeit recommended).
- 2 × 2 h. lectures, on Tuesdays and Thursdays
- 1 × 2 h. practicals, on Tuesdays
- 1 × 2 h. practicals, on Thursdays
You are expected to do exercises from the lecture notes, listed on the website, by yourself. In case of questions, address yourself to the lecturer of the course.
We may deviate from the above due to Corona.
Lecture slides and lecture notes.