Direkt zum Inhalt

Lexikon der Mathematik: Syntaxanalyseproblem

manchmal auch einfach nur Analyseproblem genannt, zu einer Klasse K von Grammatiken gehörende Frage nach einem Algorithmus, der zu jedem GK und jedem Wort w eine Ableitung von w aus G bestimmt, falls w zu der von G erzeugten Sprache LG gehört. Für wLG wird normalerweise verlangt, daß eine Ableitung für das längste noch zu LG gehörende Anfangsstück von w bestimmt wird. Es gibt allgemeine Analyseverfahren für kontextsensitive Grammatiken. Effiziente Verfahren sind für Klassen kontextfreier Sprachen (LL(k)-Grammatik, LR(k)-Grammatik) und die Klasse regulärer Sprachen bekannt.

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.