Language Processors 201718 (F29LP)
Course overview
Welcome to the Language Processors 201718 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 …”
See this year’s course.
I’m co-lecturing this course with my colleague Arash Eshghi.
Lecture and lab times
- Mondays at 14:15 in EM3.36.
- Tuesdays at 10:15 in WA111.
- Tuesdays at 13:15 in EM2.44.
- Wednesdays at 9:15 in EM2.45.
Please also read the following:
- How to answer a programming question.
- Some comments on how to answer the question.
Lectures
The videos will be updated as they are created!
- Lecture of Monday 8 January at 14:15
- Watch it and/or read the slides for lecture 1.
See the regex resources. - Lecture of Tuesday 9 January at 10:15
- Watch it and read lecture 2, on formal grammars.
- Lecture of Tuesday 9 January at 13:15
- Watch it and read lecture 2, on formal grammars.
- Lecture of Tuesday 16 January at 10:15
- Watch it and read lecture 2, on formal grammars.
- Lecture of Tuesday 16 January at 13:15
- Watch it and read lecture 2.
- Lecture of Monday 22 January at 14:15
- Watch it.
- Lecture of Tuesday 23 January at 10:15
- Watch it.
- Lecture of Tuesday 23 January at 13:15
- Watch it.
- Lecture of Monday 29 January at 14:15
- Watch it.
- Lecture of Tuesday 30 January at 10:15
- Watch it.
- Lecture of Monday 5 February at 14:15
- Watch it and read lecture 6, on PDAs.
- Lecture of Tuesday 6 February at 10:15
- Watch it and read lecture 6, on PDAs.
- Lecture of Monday 19 February at 14:15
- Watch it. Delivered by Arash.
- Arash Lecture 1 (Tuesday 20 February at 10:15)
- Watch it.
- Arash Lecture 2
- Watch it.
- Arash Lecture 3
- Watch it.
- Arash Lecture 4
- Watch it.
- Arash Lecture 5
- Watch it.
See also last year’s lectures.
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.pdfExercises (Labs) …
… are here.
Tutorials
- Tutorial I.
- Tutorial II.
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:
- Crispian Jago’s alternative therapy flowchart.
- I note also his conspiracy theory flowchart.
- Or, you could read instructions for operating a digital watch. These are all automata.
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
- The Context-Free Grammar developer.
- 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.
- 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 formal languages.
- The Wikipedia page on the Chomsky hierarchy has a good cheat-sheet at the bottom.
Mock paper and past exams
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.
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.