# 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.

## Lecture times

- Mondays at 14:15 in EM3.36.
- Tuesdays at 10:15 in EM2.44.
- Tuesdays at 14:15 in EM1.82.
- There are also labs. I will discuss this in lectures.

## Lectures

Lecture of Monday 12 January at 14:15
Watch it and/or read the slides for lecture 1.
See the regex resources.
Lecture of Tuesday 13 January at 10:15
This was a chalkboard and piece of chalk experience. Very retro, and I rather enjoyed it. However, due to technical difficulties I was unable to record this.
Lecture of Tuesday 13 January at 14:15
Watch it and read lecture 2, on formal grammars.
Lecture of Monday 19 January at 14:15
Watch it and/or read the slides for lecture 3.
Lecture of Tuesday 20 January at 10:15
Watch it and read lecture 3.
Lecture of Tuesday 20 January at 14:15
Watch it and read lecture 3.
Lecture of Monday 26 January at 14:15
Watch it.
Lecture of Tuesday 20 January at 10:15
Watch it.
Lecture of Monday 2 February at 14:15
Watch it.
Lecture of Tuesday 3 February at 10:15
Watch it.
Lecture of Monday 9 February at 14:15
Watch it.
Lecture of Tuesday 10 February at 10:15
Watch it.

## 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.

## List of lecture slides

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

… are here.

## Regex resources

- debuggex, which draws pictures of the regex (see this example), is fantastic.
- The lightweight regexpal and rather heavier-weight regexr and regex101, 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.
- For examples of automata “in nature”, see the following:

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.

The following are not automata but they’re so funny, I’ll mention them anyway:

## Grammar resources

- See the online production grammar tool.
- Jison converts context-free grammars to Javascript, you can try it online.
- Here’s quite a nice parse tree generator
- And here’s another

## Other course resources

You might like to have a look at:

- I really like bits of Jarkko Kari’s notes on Automata and formal languages (from his course at the University of Turku in Finland).
- Eitan Gurari’s course notes on formal grammars (from Ohio State University in the USA).
- Andrew Black’s course on computational structures is a model of online accessibility.
- Computer science degrees often include a course on automata and formal languages. It is often called “Automata and Formal Languages”. Just search Google for automata and formal languages solutions, and explore.
- The Wikipedia page on the Chomsky hierarchy has a good cheat-sheet at the bottom.

## Mock paper and 2014 exam

A mock paper for my half of the course is available, along with the 2014 exam and resit:
- Without solutions (do this first).
- With solutions.
- The exam and resit from last year are in Vision under Learning Materials.

## 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.