Language Processors (F29LP)

Course overview

Welcome to the Language Processors webpage. In a nutshell, this course says:

“What is a computer language, really? Well, let’s generate the language by recursive rules (or automata—same thing) … then let’s give the language semantics …”

For historical reference.
See this year’s course.

I’m co-lecturing this course with my colleage Gudmund Grov.

Regex resources

- debuggex, which draws pictures of the regex (see this example), is fantastic.
- The lightweight regexpal and rather heavier-weight regexr, which you could test on The Jabberwocky.
- A page on regular expressions in Perl.
- This tutorial on regular expressions.
- This advanced page on sed.

Automata resources

Lewis Maitland kindly drew my attention to these two great tools:
- An automaton simulator.
- A tool for converting a regex to an NFA or DFA.
If you find an online tool for generating parse trees given a grammar, or for converting between context-free grammars, PDAs, and parsers, then please let me know (I couldn’t find anything).

Other course resources

Mock paper

A mock paper for my half of the course is now available:
- Without solutions (do this first).
- With solutions.

Lectures

Lecture of Monday 13 January at 14:15: Watch it and/or read the slides for lecture 1 (lecture 1).
See the regex resources above.
Lecture of Tuesday 14 January at 10:15: Watch it and/or read lecture 1 and lecture 2.
See the online production grammar tool.
Lecture of Tuesday 14 January at 14:15: Watch it and read lecture 2, on formal grammars.
See the other course resources above.
Lecture of Monday 20 January at 14:15: Watch it and read lecture 2 and lecture 3.
Lecture of Tuesday 21 January at 10:15: This was tutorial I.
Lecture of Monday 27 January at 14:15: Watch it and read lecture 3 and lecture 4.
We started on deterministic finite automata today. My lecture notes on this topic, while comprehensive, are gleefully outclassed by Crispian Jago’s alternative therapy flowchart. I note also his conspiracy theory flowchart, and also his Venn diagram of irrational nonsense and his science map.
Or, you could read instructions for operating a digital watch. These are all automata.
Lecture of Tuesday 28 January at 10:15: Watch it and read lecture 4.
Lecture of Tuesday 28 January at 14:15: For this lecture, please go to EM2.50 and study Assignment 1 and Assignment 2 (see also solutions to Assignment 1 and solutions to Assignment 3). Then do Homework 5, question 3 (and its solutions).
These links are to Andrew Black’s course on computational structures, which is frighteningly well-produced and is worth a browse.
Lecture of Monday 3 February at 14:15: Watch it and read lecture 5.
Lecture of Tuesday 4 February at 10:15: Watch it and read lecture 6.
Lecture of Tuesday 4 February at 14:15: I seem to have misplaced the video for this (I’ll look for it next week); we finished off lecture 6.
Lecture of Monday 17 February at 14:15: Watch it. We discuss PDAs.

Tutorials

- Tutorial I of Tuesday 21 January at 14:15.

List of lecture slides

lecture-1.pdf lecture-2.pdf lecture-3.pdf lecture-4.pdf lecture-5.pdf lecture-6.pdf

Exercises …

… are here.

Class times

- Mondays at 14:15 in EM3.36.
- Tuesdays at 10:15 in EM2.44.
- Tuesdays at 14:15 in EM1.82.

The Rules

1. Turn up!
2. Understand lecture materials as you get them.
3. A student who thinks “I don’t understand this now; I’ll sort it out during the holidays” is in denial (look at 1m03s).
4. Rules 1-3 above apply especially to those who believe rules 1-3 above don’t apply to them.

Suggested films

You might like to watch:
- Jumper, for illustrating the importance of the initial state of a system (you don’t want the initial state of your otherwise perfect system be 100 feet up in thin air).
- Warm Bodies, for daring to imagine that Romeo and Juliet can be remade as a Zombie teen romance.
- Finding Nemo (for the sharks scene),
- Despicable Me (for minions).
- Terminator and 12 Monkeys (for logically valid but undesirable attempted implementations of the specification “bring peace to Earth”),
- Star Wars (for Obi-Wan’s comment to Luke about truths depending on one’s point of view),
- Blade Runner (for a personal lecture by Rutger Hauer), and
- RoboCop, for Murphy’s assertion that “\( \text{coming with me}(x,y) \)” is a tautology, where \( x:\mathsf{PERP} \) and \( y:\mathsf{LIFESTATE} \) and \( \mathsf{LIFESTATE} ::= \mathsf{dead} \mid \mathsf{alive} \).
- Scanners, for the totally realistic portrayal of what happens to undergraduate students who think about quantifiers.

A bit about me

I am a researcher in theoretical computer science. My research is mostly in formal logic.
Everybody calls me Jamie but my name is actually Murdoch. You can contact me by e-mail on “gabbay at macs hw ac don’ttypethis uk”. My office is G.50 Earl Mountbatten Building.

The students …

… should be mostly third year undergraduate students.

If you don’t know what an undergraduate student looks like, think of minions, but less yellow.

Misc