An exploration of the practical issues of using grammars to recognise structured pieces of text. Plus, an introduction to dealing with the parts of computer languages that grammars are not suited for, such as identifiers. Finally, a look at which facilities are necessary in computer languages.
Peter Aczel gives 11 weekly lectures about the "Power" part of the course-unit:
An examination of the underlying theory of grammars, including their limitations. The theory of automata, and the equivalence of grammars and automata, gives us practical methods for implementing recognisers for grammars e.g. to write a compiler. Finally, a look at the generality of computers and computations, and their fundamental limits.
We also offer a joint revision lecture, if students submit suitable questions. This may be the in the last scheduled lecture, or in January just before the exam.
Answers to the "Implementation" exercises are in the Undergraduate Resource Centre (and can also be found via the list of handouts). I am very happy to discuss them with you during labs or examples classes, or after lectures, or via email.
| Lab exercises | extra information & hints |
|---|---|
| Introduction & timetable | debugging flex, byacc and make |
| Exercise 1: | condensed man page for egrep and regular expressions used with flex and hints |
| Exercise 2: |
lex manual
and
strings and comments
characters [local] and pre-processing [local] and syntax [local] hints |
| Exercise 3: | yacc manual and use of %left etc. and examples |
| Exercise 4: | Infix and Postfix notations, man pages for bc and dc |
| Exercise 5: | grammar and strings and comments |
| Extra information about the labs |
|---|
| You are expected to run the labprint command before getting each exercise marked. |
Exercise 1: if you get an error message like:
/bin/sh: /tmp/t: Permission denied
you need a new version of the "makefile" i.e. cp $CS2121/p*/ex1/makefile .
(The problem is that the file /tmp/t already exists but is owned by someone else, so you can't overwrite it. I should have done a better job of inventing a filename - sorry.) |
| If the labmail program complains that it can't find "labmail_me", then run the command "make labmail" |
If your program crashes at run-time, making a "core" file,
and you want to find out what line it went wrong at etc.,
on Linux do:
gdb program_name core where quit(This relies on using the -g flag with gcc, as in
the makefiles provided.)
|
You can find copies of the exam from January 2002 here and here is my attempt at some answers to Q1 and Q2.
Just like January 2002,
this year's exam is in two sections (each containing two questions),
corresponding to the two parts of the course-unit - please answer the two
sections in separate answer-books.
You should answer 3 questions out of the 4, and each is worth 20 marks.
My two questions will be:
You might find the following, from CS2111/CS2112, useful:
Note: the resit (August/September) exam will have a similar format to the main (January) exam.
You are welcome to make educational, not-for-profit use of my work, but please give me credit when you do so.