Syntaktische Fehlerkorrektur mit minimalen Kosten für deterministische Grammatiken

Bei deterministischen kontextfreien Grammatiken können Syntaxfehler durch Einfügungen und Löschungen von Symbolen an der Fehlerstelle korrigiert werden. Zur Berechnung der Fehlerkorrektur verwenden wir einen nichtdeterministischen Kellerautomaten. Betrachten wir die Möglichkeiten zur Berechnung einer Fehlerkorrektur, so erhalten wir einen baumartigen Suchraum. Da dieser bei einigen Fehlern sehr groß werden kann, versuchen wir, Zweige abzuschneiden. Dazu stellen wir einen modifizierten nichtdeterministischen Kellerautomaten vor. Wir beweisen die Existenz minimaler Fehlerkorrekturen für LR(1)-, LALR(1)- und sLR(1)-Grammatiken. Die Auswirkungen der Modifikationen am nichtdeterministischen Kellerautomaten und die Diskussion einer effizienten Implementierung am Beispiel von fehlerhaften Pascal- und Java-Programmen bilden den Schlussabschnitt