Formale Sprachen #39 - Linksrekursion entfernen
Вставка
- Опубліковано 15 вер 2024
- Wir sehen uns ein Verfahren an, um linksrekursive Regeln aus einer kontextfreien Grammatik zu entfernen. Linksrekursion zu entfernen ist unter anderem ein Schritt bei der Umwandlung einer kontextfreien Grammatik in Greibach-Normalform.
Ich hab mir mal gedacht dass ich unter das neueste Video der Reihe kommentiere und mich dafür bedanke. Die Videos sind echt super zum nebenbei schauen ohne sich dabei schlecht zu fühlen, dass ich meine Zeit verschwende. Danke schön
Sie sollten bei einer Uni beibringen. Danke Ihnen für so tolle Sache, die Sie hier veröffentlichen.
Verständlich und effizient erklärt. Danke dafür
4:16 Alternative wäre aus T -> Tb | a folgende rechts-lineare Grammatik zu formen:
T' -> aT'
T' -> bT' | ε
nur um nochmal zu zeigen dass es mehr als eine Lösung gibt die dieselbe Sprache akzeptieren.
Falsch, aaaaaaaaaab wäre in deiner Sprache aber nicht in seiner
@@Dystopie173 Ich glaube das erste T' ist ein Tippfehler, aber sonst hast du recht haha
Gutes Video aber mir fehlt die Verwendung von ε, das leere Wort. (Wahrscheinlich wurde das auch absichtlich ausgelassen, da es nicht in den weiterführenden Videos verwendet wird, für die Richtung in die dieser Kanal geht nicht verwendet wird, etc. Das ist keine so richtige Beschwerde.) Aber für alle die ε benutzen das komplizierte Beispiel lässt sich mit
T -> baRT' | avaT' cTT'
T' -> bSbT' | aST' | ε
leichter lösen.
Danke!
Wenn man die Linksrekursion durch Rechtsrekursion ersetzt, erhält man beim Parsen im Allgemeinen einen anderen Parsebaum als bei der ursprünglichen Grammatik. Dadurch kann sich die Semantik des Wortes ebenfalls ändern. Beispiel: Wenn ich in der Grammatik "Expr -> Expr - number | number" die Linksrekursion entferne und durch Rechtskursion ersetze, dann wird die Minusoperation rechtassoziativ und ich erhalte bei der Auswertung "falsche" Ergebnisse. Weißt du zufällig, wie man die ursprüngliche Semantik wiederherstellen kann oder wie man dieses Problem am besten löst?
Doofe Frage, aber unsere Dozentin ist nicht so die Beste im Erklären: Wird die Elimination von Linksrekursion nur bei Regeln verwendet die direkt auf sich selbst konkateniert mit NT oder T ableiten? Oder können wir das auch auf Regeln anwenden, die erst durch Ableitung mithilfe von anderen Regeln eine Linksrekursion ergeben?
So viel zu online-corona Semestern... :D
Um die Greibach-Normalform zu erstellen müssen wir nur den hier gezeigten Fall lösen, also nur Regeln, die "direkt" linksrekursiv sind, müssen eliminiert werden.