Slides

Lectures 1 and 2, Tuesday 17 April.
(Introduction; Languages and grammars)

Lots of people turned up — keep it up. The lecture was rather heavy on ‘introducing stuff’ and rather low on exciting sexy things to do with your grammars. Still, not to worry: melodramatic tension cannot be taken for granted, it must be cultivated.

Lecture 1 [ps] [pdf]

Lecture 2 [ps] [pdf]

A video of the first two lectures is online.

Lectures 1 and 2 [video]

Lectures 3 and 4, Thursday 19 April.
(Left recursion, bad grammars, grammar transformation, regular expressions, LEX)

Lots of people turned up again. I nearly swooned.

I said I didn't want to spend a whole lecture going through 18 different ways of doing regular expressions, so I set a little competition on the forum. Hmm. So you turn up to lectures. But the million-dollar question is: do you realise that exercises have to be done?

Lecture 3 [ps] [pdf]

Lecture 4 [ps] [pdf]

A video of the third and (half of) the fourth lecture, is online.

Lectures 3 and 4 [video]

A video of the second half of the fourth lecture is online.

Lecture 4 (continued) [video]

Lecture 5, Thursday 26 April.
(Symbol table management I)

I used the word ‘backtracking’ in the lecture. Some instinct made me pause, look to the back of the lecture theatre, and ask a student (who looked just like Fidel Castro did when he was young) whether he knew the meaning of the word.

No.

Comerades! A lecture is like totalitarian government: for 60 minutes I seek to govern what you see, what you hear, and what you think. This government is not by the people (I am not a student). However it is for the people in the the best communist sense. If you do not benefit from them, say the word and I'd be happy to stay in bed.

As you know, in the USSR the situation came about that the state knew that all citizens were guilty and the question was merely what they were guilty of. Well, I know you're all ignorant. That's OK: it's why I'm lecturer and you're student — but I do not necessarily know what you are ignorant of.

I promise not to chain you up outside a hut in Siberia to starve to death if you admit to your ignorance. So go on, ask your question.

Lecture 5 [ps] [pdf]

A video of the fifth lecture is online.

Lecture 5 [video]

Lectures 6 and 7, Tuesday 1 May.
(Symbol table management II, and Table-driven parsing)

This one was quite fun. How to manage a symbol table really efficiently, and: production rules are useless without an algorithm to implement them; table-based parsing to the rescue!
(The wikipedia page on hash tables is excellent.)

Lecture 6 [ps] [pdf]

Lecture 7 [ps] [pdf]

Lectures 6 and 7 [video]

Lecture 8, Thursday 3 May.
(YACC)

What a cool program YACC is. I showed some code, and ran it, and it actually worked. If you're using linux, don't forget that you need automake, gcc, and libc6 installed.
The code I ran was all called ‘prop3-blah’ and it's online here.
(This page is quite fun, in an IBM kind of way.)

Lecture 8 [ps] [pdf]

Lecture 8 [video]

Lecture 9, Friday 4 May.
(Recursive descent parsing)

Oops. This lecture is a bit of a monster. I found this page which seems to explain things very nicely; might give you another angle on the material.

Lecture 9 [ps] [pdf]

Lecture 9 [video]