Linksrekursion

Grammatiktests > Linksrekursion

Ein weiterer möglicher Grammatikfehler ist die Linksrekursion. Die folgende Regel ist das einfachste Beispiel einer Linksrekursion:

a = a | B

Die Prüfung, ob diese Regel auf einen Eingabetext passt führt zu einem unendlichen Regress. Um die Regel a zu testen, muss bevor die Alternative b geprüft werden kann a nochmals getestet werden, usw. Linksrekursionen sind demnach in TETRA nicht zulässig, können aber nicht durch einen Grammatiktest erkannt werden.

Glücklicherweise lassen sich Linksrekursionen vermeiden. Die linksrekursive Regel:

a = a C | B

kann umgeschrieben werden. a muss gewiss mit B beginnen. Auf B kann C folgen und auf B C kann ein weiteres C folgen. Das formale Resultat ist also:

a = B C *

Angewandt auf das erste Beispiel wäre C ein leeres Symbol und für a gilt:

a = B

Anmerkung:

Produktionen für den weit verbreiteten Parsergenerator Yacc sind häufig linksrekursiv. Yacc hat damit kein Problem, da er nicht wie TETRA ein Topdown-, sondern einen Bottomup-Parser ist. (Yacc kommt dafür nicht mit Rechtsrekursionen zurecht.) Will man eine für Yacc geschriebene Grammatik in eine TETRA-Grammatik übersetzen, so hilft die eben genannte Regel weiter.

Diese Seite gehört zur TextTransformer Dokumentation