Hauptseminar Parsing
WS 1999/2000

H.Leiß, CIS

Contents

1  Vorbesprechung: Do. 4.11.99, 11.15 Uhr, Raum 1.15
2  Themenvorschläge
3  Terminänderung

1  Vorbesprechung: Do. 4.11.99, 11.15 Uhr, Raum 1.15

Das Seminar wird mit dem Inhalt der gleichnamingen Vorlesung abgestimmt. In der Vorlesung werden die Grundversionen verschiedener Parser behandelt, während im Seminar auf neuere Aufsätze, speziellere Versionen der Algorithmen und Implementierungsfragen eingegangen wird.

Da die Vertiefung im Seminar ein Verständnis der wesentlichen Algorithmen voraussetzt, ist es sinnvoll, in der ersten Hälfte des Semesters die Vorlesung (4-stündig) und in der zweiten Hälfte des Semesters das Seminar (4-stündig) abzuhalten. Das wird in der ersten Woche mit den Teilnehmern abgesprochen.

2  Themenvorschläge

  1. Spezielle Parser in der Theorie

    1. Entwicklung eines GLR-Parsers aus dem Parser von Earley [1]
    2. Ein Head-Corner-Parser ohne Redundanzen [10,6]
    3. Ein O(n4)-Parser für Baumadjunktionsgrammatiken (TAG's) [4]
    4. Ein `optimaler' Tabellenparser [9]
    5. Ein LALR-Parser für Definite Clause Grammars [3]
    6. Syntaktische Beschreibung in konstruktiver Typentheorie [12,13]

  2. Implementierungen in Prolog

    1. Deduktives Parsing mit Optimierungen [15]
    2. Vorberechnung von Eigenschaften bei DC-Grammatiken [15,16]
    3. Erzeugung von Parsern durch partielle Auswertung [11]
    4. Implementierung eines Left-Corner-Parsers in Prolog
    5. Implementierung eines Common-Prefix-Parsers in Prolog
    6. Implementierung eines Earley-Parsers für DCG's in Prolog [8]

  3. Implementierungen in SML und Haskell

    1. Earley-Parser mit Optimierungen (in SML) [7]
    2. ML-Yacc [2]
    3. Grammatical Framework von A.Ranta (in Haskell) [13]
    4. Ein Chart-Parser für Unifikationsgrammatiken [8,14,17] (vgl. (ii) f)

  4. Implementierungen in Oz oder Constraint Logic Programming

    1. Parsing durch Lösen von Constraints []

Die Implementierungen sollen durch Zeit- und Platzvergleiche an (vorgegebenen) Beispielgrammatiken für Fragmente des Deutschen verglichen werden.

Je nach Interesse der Teilnehmer können auch weitere oder andere Arbeiten besprochen werden, z.B.

3  Terminänderung

Auf Wunsch der Teilnehmer wird z.Zt. versucht, die Termine von
Vorlesung und Seminar auf Mo 9-13 Uhr
zu verschieben. Es ist aber noch unklar, ob dafür ein Raum gefunden werden kann. Am kommenden Montag, 7.11.99, treffen wir uns im
Raum B 110, Besprechungsraum des CIS, Oettingenstr.67
Der Raum ist für Vorlesung und Seminar denkbar ungeeignet; falls keine anderen Räume gefunden werden, müssen wir auf die ursprünglichen Termine zurückkommen (wenn das noch geht ...).

References

[1]
M. A. Alonzo, D. Cabero, and M. Vilares. Construction of efficient generalized LR parsers. In D. Wood and S. Yu, editors, Automata Implementation, LNCS 1436, Berlin, 1998. Springer Verlag.

[2]
A. W. Appel and D. R. Tarditi. ML-Yacc, version 2.1. documentation for release version. Technical report, Carnegie Mellon University and Princeton University, 1991. In: Distribution files of SML of New Yersey.

[3]
M. V. Ferro and M. A. A. Pardo. An LALR extension for DCGs in dynamic programming. In M. Vide, editor, Mathematical Linguistics, volume II. John Benjamins Publishing Company, 1998?

[4]
K. Harbusch. Effiziente Analyse natürlicher Sprache mit TAGs. In I. B'atory, editor, Computerlinguistik und ihre theoretischen Grundlagen, volume 195 of Informatik-Fachberichte, pages 79-103, Berlin, 1987. Springer Verlag.

[5]
Third International Workshop on Parsing Thechnologies, Tilburg (The Netherlands) and Durbury (Belgium), August 1993.

[6]
K.Sikkel and R. op den Akker. Predictive head-corner chart parsing. In [5], pages 267-276, 1994.

[7]
H. Leiss. On Kilbury's modification of Earley's algorithm. ACM Transactions on Programming Languages and Systems, 12:610-640, 1990.

[8]
S. Naumann and H. Langer. Parsing. Leitfäden und Monographien der Informatik. B. G. Teubner, Stuttgart, 1994.

[9]
M.-J. Nederhof. An optoimal tabular parsing algorithm. In 32nd Annual Meeting of the ACL, pages 117-124, 1994.

[10]
M.-J. Nederhof and G. Satta. An extended theory of head-driven parsing. In 32nd Annual Meeting of the ACL, pages 210-217, 1994.

[11]
F. C. Peireira. Prolog and Natural-Language Analysis. CSLI Lecture Notes. Stanford University, Stanford, 1987.

[12]
A. Ranta. Type-Theoretical Grammar. Oxford University Press, 1994.

[13]
A. Ranta. GF-Grammatical Framework. version 0.5, june 18, 1999. Technical report, Xerox, Grenoble, 1998. http://www.xrce.xerox.com/research/mltt/gf/.

[14]
S. M. Shieber. An Introduction to Unification-Based Approaches to Gramar. 1986.

[15]
S. M. Shieber, Y. Shabes, and F. C. N. Pereira. Principles and implementation of deductive parsing. Journal of Logic Programming, 24:3-36, 1995.

[16]
K. Sikkel. Parsing Schemata. A Framework for Specification and Analysis of Parsing Algorithms. EATCS Monographs. Springer Verlag, Berlin, 1998.

[17]
J. Wedekind. Approaches to unification in grammar: A brief survey. In P. Blackburn and M. de Rijke, editors, Specifying Syntactic Structure, pages 245-280. CSLI Publications, 1997.


File translated from TEX by TTH, version 2.54.
On 5 Nov 1999, 10:09.