Many programs take a string of symbols as input. Almost always, such a string of symbols posseses some kind of structure. Examples of such strings are programs themselves, packages sent over the Internet, or information stored in files. Such structures are described with so-called grammars. From such a description, a program called parser can be automatically generated to recognize the structure. Recognizing structures is an important part of many programs (example: compilers). This course will introduce you to grammars, how to design grammars, how to construct parsers, and to use the results produced by parsers.
You will need to download and print the following lecture notes: Grammars and Parsing.
Note: as soon as I know the number of participants, I will arrange some prints of these lecture notes.
Johan Jeuring wrote an extra chapter about applications of grammars. It is not mandatory to read this, but it does
provide some additional background information.
Course plan (7 meetings)
The list of recommended exercises has been modified: the numbers now correspond to the new lecture notes (September 2006).
| Lecture | Topics | Chapters | Exercises |
| GP1 | - Grammar and parse trees | 1,2 |
2.1, 2.2, 2.3, 2.5
2.9, 2.10, 2.14, 2.17, 2.20, 2.21 2.27, 2.28, 2.29, 2.30, 2.32 2.34, 2.35, 2.40, 2.43, 2.45, 2.48 |
| GP2 + GP3 |
- Parser combinators - Grammar and parser design - Regular expressions |
3 - 5 |
3.7 - 3.9, 3.19 - 3.24
3.27, 3.30 - 3.34, 3.39, 3.41, 3.49 4.1, 4.3 5.1 - 5.3, 5.5, 5.7, 5.8, 5.12, 5.13, 5.16 |
| GP4 + GP5 |
- Compositionality - Computing with parser |
6 - 8 |
6.2, 6.6, 6.7, 6.11, 6.12 8.1 |
| GP6 + GP7 |
- Expressiveness - LL Parsing |
9,10 |
9.2 - 9.5, 9.9 - 9.13 10.2 - 10.7 |
Here is a trial exam. [Solution]
Also take a look at last year's exam (english). The correct answers for the multiple choice part are:
1A 2A 3B 4C 5D 6A 7D 8D 9A 10C