Syntaxanalyse

Lecturers:Schneider, H.
Coverage:2 SWS
Prerequisites:

Scheinerwerb: Literaturzusammenfassung

Dates & location:
  • Thursday, 16:00 - 18:00, H10
Literature:
  • O. Mayer, Syntaxanalyse, Mannheim, 1982
  • R.N. Moll et al., An Introduction to Formal Language Theory, Berlin, 1988
  • Naumann/Langer, Parsing, Stuttgart, 1994
Topics:

Die Syntaxanalyse spielt eine große Rolle sowohl in der Informatik, etwa in der Compilertechnik und bei der Überprüfung anderer Eingaben, als auch bei der Verarbeitung natürlicher Sprache. Im ersteren Fall kann man davon ausgehen, daß die zu analysierenden Texte eine eindeutige Struktur besitzen, während dies im zweiten Fall nicht immer gilt. In der Vorlesung werden beide Fälle ausschnittsweise behandelt. Vorrausetzung für das Verständnis der Vorlesung sind die formalsprachlichen Grundlagen, die in den Vorlesungen zur Algorithmik und zur Theoretischen Informatik im Grundstudium behandelt werden.

  • Kontextfreie und attributierte Grammatiken
  • Einige formale Grundlagen
  • Das Verfahren von Cocke-Kasami-Younger
  • Das Verfahren von Earley: Vorgehensweise
  • Das Verfahren von Earley: Beweise und Ergänzungen
  • Kellerautomaten
  • Syntaxanalysestrategien
  • LL(k)-Analyse
  • Starke LL(k)-Analyse
  • LR(k): Einführung
  • Gewinnung der LR(k)-Tabellen
  • Zur Theorie der kanonischen LR(k)-Analyse
  • Ein Syntaxanalyse-Generator
  • Ergänzungen
watermark seal