wenn ich eine Grammatik mit einer Produktion habe, die sowohl Linksrekursion als auch Linksfaktor enthält
Welches hat Priorität, linke Rekursion oder linkes Factoring?
formal-languages
formal-grammars
parsers
left-recursion
Andrea Tucci
quelle
quelle
Antworten:
Transformationen wie das Links-Factoring oder das Entfernen der linken Rekursion haben keine Vorrangregeln. Offensichtlich können die resultierenden Grammatiken unterschiedlich sein, aber sie erkennen dieselbe Sprache.
Die Beispielgrammatik der Frage ist schwieriger als das typische Hausaufgabenproblem für Studenten. Es wird also nützlich sein, unsere Arbeit zu zeigen.
Linke Rekursion
Definieren wir eine Transformation, die die linke Rekursion entfernt.
Gegeben
Wir entfernen die linke Rekursion wie folgt:
Die Allgemeingültigkeit des oben Gesagten wird normalerweise nicht in Compilertexten angegeben, aber Parsing-Texte wie Grune & Jacobs decken dies ab. Left Factoring kann auf die oben transformierte Grammatik angewendet werden, führt jedoch nur zusätzliche Regeln ein, die die Antwort nicht ändern. Daher werden wir die Präsentation vereinfachen, ohne dass ein zusätzliches linkes Factoring durchgeführt wird.
In dieser Antwort werden wir keine indirekten Rekursionsprobleme behandeln, da wir uns nur mit den Regeln eines einzelnen Nicht-Terminals befassen. Beachten Sie jedoch, dass die indirekte Linksrekursion behandelt werden kann. (Öffnen Sie eine separate Frage, wenn dies wichtig ist.)
Linkes Factoring
Das Entfernen des linken Factorings wird in den meisten einführenden Compilertexten wie folgt ausgeführt. Gegeben
Links Factoring Renditen:
Nun, das führt die Transformationen in beiden Reihenfolgen durch.
Linkes Factoring zuerst
Lassen Sie uns die Grammatik der Frage berücksichtigen
und entfernen Sie dann die linke Rekursion:
Linke Rekursion zuerst entfernen
Und für die andere Reihenfolge entfernen wir die linke Rekursion aus der Grammatik der Frage
und dann links das Terminal :c
Aha, die resultierenden Grammatiken sind die gleichen!
Im Allgemeinen ist es unentscheidbar, zu beweisen, dass zwei Grammatiken gleichwertig sind. Wenn also eine Reihe von Grammatiktransformationen die dann erkannte Sprache beeinflussen könnte , wäre dies katastrophal.
quelle