Syllabus for Computerlinguistik I

Tom Cornell

Winter 1999--2000






1 (25.10.) Introduction: Languages Formal and Natural

String Languages
Formal languages---grammars and derivations---automata---closure properties and constructions---generalizations and hierarchies.
Term Languages
Terms over a ranked alphabet---terms with variables and substitution---terms as trees---trees as a generalization of strings---finite tree automata
Übung
Logging on---using xemacs---using SICStus Prolog -- etc.

2 (1.11.) Prolog for CL

Prolog Review
Resolution---unification---definite clauses---negation as failure.
Meta-programming in Prolog
Predicates that change the program itself---writing compilers in Prolog
Übung
User Input: Converting a string of characters to a set of clauses.

3 (8.11.) Basic Automata Theory

String Automata
In Prolog---Running automata---constructions on automata---Determinization and Minimization---Reachable states
Übung
Removing epsilon transitions from a finite state automaton.

4 (15.11.) Tree Automata. First look at Phrase Structure Grammars.

Tree Automata
In Prolog---Running them---constructions on tree automata---Reachable states
Context Free Grammars
Pushdown automata---trees and tree traversals---Parsing strategies: top-down, bottom-up, left-corner and others.
Normal Forms
e-free CFGs---Chomsky normal form---Greibach normal form---effects on derivation trees
Übung
A context free grammar for a tiny (but infinite) fragment of a natural language.

5 (22.11.) Categories of the Grammar

Features and State
Grammar skeleta and properties of categories---Agreement---subcategorization---Control?---The lexicon---lexicalized grammars?
Features, State and Storage
Manufacturing complex feature values---Long distance dependencies---Extraction---Binding---Scope.
Übung
Extending the grammar fragment.

6 (29.11.) Basic Parsing Algorithms

Top Down Parsing
Recursive descent---problems with left recursion---transforming the grammar---recovering the intended derivation structures
Bottom Up Parsing
Shift Reduce parsers---problems with empty productions---transforming the grammar again
Übung
A shift reduce parser in Prolog.

7 (6.12.) General Approaches to Parsing

Deduction systems
Items: information about the state of the parser---Bottom up approaches to logic programming---the Semi-Naïve Algorithm.
Tabular Parsing
The CYK algorithm---Parsing with Tree Automata.
Übung
The Semi-Naïve Algorithm for tabular parsing.

8 (13.12.) Chart Parsing

Earley's Algorithm
Items for partial parses---The active chart.
Übung
Earley's algorithm as a deduction system. Indexing the chart.

9 (20.12.) Tabular and Chart Methods for DCGs

Restriction
Earley Deduction
Chart items as logical Lemmas.

10 (10.1.) Generalized Left Corner Parsing

Left Corner Parsing
Head Parsing
And other ``non-geometric'' control strategies.

11 (17.1.) Semantic Interpretation.

12 (24.1.)

13 (31.1.) Generation.

14 (7.2.)

15 (14.2.)

Course Coordinates:

My phone: (29)70734
My office: Wilhelmstr. 133, Rm. 61 
mailto:cornell@sfs.nphil.uni-tuebingen.de
http://tcl.sfs.nphil.uni-tuebingen.de/~cornell/cl1
This document was translated from LATEX by HEVEA.