Ruprecht-Karls-Universität Heidelberg
Bilder vom Neuenheimer Feld, Heidelberg und der Universität Heidelberg

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 pdf
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 pdf
Grune/Jacobs Parsing Techniques: A Practical Guide pdf
Nederhof/Satta Tabular Parsing pdf
Kunert LR(k)-Analyse für Pragmatiker pdf
Tomita An efficient all-paths parsing algorithm for natural languages pdf

» weitere Kursmaterialien

zum Seitenanfang