Grundlegende Parsingalgorithmen
Kursbeschreibung
| Studiengang | Modulkürzel | Leistungs- bewertung |
|---|---|---|
| BA-2010[100%|75%] | CS-CL | 6 LP |
| BA-2010[50%|25%] | (BS-CL) | 6 LP |
| BA-2010[25%] | BS-AC, BS-FL | 4 LP |
| BA-2010 | AS-FL | 8 LP |
| Dozent | Kurt Eberle |
| Veranstaltungsart | Proseminar |
| Erster Termin | 30.07.2018 |
| Zeit und Ort | 30.07.2017 bis 03.08.2017, 09:00–14:30, INF 327 / SR 4 |
| Commitment-Frist | tba |
Teilnahmevoraussetzungen
- Einführung in die Computerlinguistik
Leistungsnachweis
- Bestehen der Abschlussklausur
Inhalt
Das Seminar gibt eine Einführung in Parsingmethoden für eine Reihe von Grammatiktypen, mit Blick vor allem auf kontextfreie Phrasenstruktur-Grammatiken der Chomsky-Hierarchie, aber auch auf merkmalsbasierte Grammatiken (am Beispiel der sog. Definite-Clause-Grammatiken) und auf Dependenzgrammatiken Behandelt werden u.a. ableitungsorientierte Parser mit Backtracking, tabellengesteuerte Parser (LL, LR, Tomita), Chartparser (Earley, Left-Corner, CYK) und die Earleydeduktion für DCGs. Für Dependenzgrammatiken werden die Varianten arc-standard und arc-eager unterschieden. So die Zeit reicht werden jeweilige probabilistische Verfahren diskutiert.
Kursübersicht
Seminarplan
| Datum | Sitzung | Materialien |
|---|---|---|
| Mo 30.07 | ||
| 09.15 | Einführung & Formale Sprachen | FS |
| 11.00 | Top-Down & Bottom-Up Parsing | TD/BU |
| 13.00 | Tabellen-gesteuertes Parsing: LL Parsing | LL |
| Di 31.07 | Übung1 | |
| 09.15 | Tabellen-gesteuertes Parsing: LR Parsing | LR |
| 11.00 | xLR Erkenner | |
| 13.00 | Übungen | Übung2 |
| Mi 01.08 | ||
| 09.15 | Tomita-Parser | Tomita , BspGram |
| 11.00 | Chart Parser: CYK | CYK |
| 13.00 | Übungen | Übung2 Lösungen, LR-Tabellen-Berechnung, Übung3 |
| Do 02.08 | ||
| 09.15 | Chart Parser: Earley Parser | Earley Earley-Beispiel |
| 11.00 | Chart Parser: Left-Corner Parsing | LC LC-Beispiel |
| 13.00 | Übungen | Übung4 Übung4 Lösungen (teilweise) |
| Fr 03.08 | ||
| 09.15 | Grammatik-Transformationen, DCGs, Feature Constraints | Transfos Transfo-Beispiel DCG |
| 11.00 | Dependenzgrammatik-Parsing | Dep Dep2 |
| 13.00 | Statistisches Parsing |
Literatur
| Autor | Titel | Materialien |
|---|---|---|
| Jurafsky/Martin | Speech and Language Processing | |
| Aho/Ullman | The Theory of Parsing, Translation, and Compiling. Vol 1. | |
| Aho/Sethi/Ullman | Compilers: Principles, Techniques, and Tools | |
| Hopcroft/Ullman | Introduction to Automata Theory,Languages and computation | |
| Helmut Schmid | Script | |
| Grune/Jacobs | Parsing Techniques: A Practical Guide | |
| Nederhof/Satta | Tabular Parsing | |
| Kunert | LR(k)-Analyse für Pragmatiker | |
| Tomita | An efficient all-paths parsing algorithm for natural languages |
