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 |