Programming Techniques in Computational Linguistics
Original title (German): Programmiertechniken der Computerlinguistik
A lecture series on programming techniques in computational linguistics, taught from winter semester 1997/98 through summer semester 1999. The winter part introduces Prolog and basic parsing techniques; the summer part goes deeper into chart parsing, efficient Prolog techniques, and formal language hierarchies. It comes with six downloadable Prolog programs as starting points for exercises.
University of Zurich, Department of Informatics, Computational Linguistics — winter semester 1997/98 through summer semester 1999.
I designed this course from scratch. Prolog wouldn’t necessarily have been my first choice for it — I’m a systems programmer at heart — but the department insisted I teach exactly this language. It looks fairly odd from today’s vantage point, but back in the 1990s, Prolog, together with Lisp, was the language of choice in artificial intelligence.
Winter Semester
- Introduction
- Structures
- Control Flow
- Recursion
- Tracing
- Lists
- Arithmetic
- Term Predicates
- Occurs Check
- Introduction to Parsing
- Review
- Input/Output
- Parsing Review
- Definite Clause Grammars
- Shift-Reduce Parsing
- Control Constructs
- Sample Solutions for All Exercises
Summer Semester
- Introduction
- Tokenizer
- Parsing Review
- Morphology
- Selection Restrictions
- Chart Parsing
- Bottom-Up Chart Parsing
- Earley Parsing
- Edge Subsumption
- Efficient Prolog Techniques
- Faster Parsing
- Finite Automata
- Language Hierarchy; Non-Context-Freeness of Zurich German
- Feature Structures
- Keyword Recognition
Prolog Programs to Download
- Tokenizer
- A simple Prolog tokenizer.
- Definite Clause Grammar
- A very simple definite clause grammar, meant as a starting point for an exercise.
- Shift-Reduce Parser
- A simple shift-reduce parser in Prolog.
- Bottom-Up Chart Parser
- A simple bottom-up chart parser in Prolog.
- Earley Parser
- A simple chart parser in Prolog using the Earley algorithm. Note: two bugs are left as exercises to fix!
- Keyword Recognition
- A Prolog program that recognizes certain keywords in natural-language (English) input and issues corresponding “database” queries. Requires the Tokenizer.