Linke Rekursion und linkes Factoring - welches geht zuerst?

8

wenn ich eine Grammatik mit einer Produktion habe, die sowohl Linksrekursion als auch Linksfaktor enthält

FFBacDSc

Welches hat Priorität, linke Rekursion oder linkes Factoring?

Andrea Tucci
quelle
1
Welche Parsing-Strategie verwenden Sie? Bei rekursivem Abstieg muss eine Linksrekursion unbedingt vermieden werden. Left Factoring ist wichtig, wenn Sie beispielsweise eine LL-Analyse durchführen.
Ken Li
2
Entschuldigung, ich habe vergessen, es zu schreiben. Ich benutze Top-Down-Parser-Strategie (LL (1))
Andrea Tucci
Laut inst.eecs.berkeley.edu ist es dasselbe! (auf der 3. Übung)
Andrea Tucci

Antworten:

12

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

AAα0Aα1AαnBβ0Bβ1Bβn ,

Wir entfernen die linke Rekursion wie folgt:

AhBβ0Bβ1BβnAtα0α1αnAt+AtAt+AtAAhAt+Ah

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

Axyxz

Links Factoring Renditen:

AsyzAxAs

Nun, das führt die Transformationen in beiden Reihenfolgen durch.

Linkes Factoring zuerst

Lassen Sie uns die Grammatik der Frage berücksichtigen

FsDSεFFBacFs

und entfernen Sie dann die linke Rekursion:

FhcFsFtBaFt+FtFt+|FtFsDSεFFhFt+Fh

Linke Rekursion zuerst entfernen

Und für die andere Reihenfolge entfernen wir die linke Rekursion aus der Grammatik der Frage

FhcDScFtBaFt+FtFt+FtFFhFt+Fh

und dann links das Terminal :c

FhsDSεFhcFhsFtBaFt+FtFt+FtFFhFt+Fh

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.

codeah
quelle
Danke, sehr gut erklärt! Wenn ich also sowohl die linke Rekursion als auch das linke Factoring habe, kann ich auswählen, welche zuerst entfernt werden soll.
Andrea Tucci
"Im Allgemeinen ist es unentscheidbar, zu beweisen, dass zwei Grammatiken gleichwertig sind." - Meinst du, es ist unmöglich zu beweisen, oder gibt es keinen Algorithmus, der dies immer tut? Nur letzteres ist richtig. Es wäre auch nicht "katastrophal", wenn nur eine Reihenfolge die Sprache unverändert lassen würde: Dann müssten Sie die richtige Reihenfolge verwenden. Es ist jedoch sicher klar, dass beide Transformationen, wenn sie unabhängig voneinander verwendet werden sollen, die erzeugte Sprache nicht beeinflussen können.
Raphael
Beachten Sie, dass wir hier über ausgefeilte Formatierungswerkzeuge (Markdown und LaTeX) verfügen, um die Übersichtlichkeit zu verbessern. Ich habe Ihren Beitrag entsprechend bearbeitet, bitte schauen Sie.
Raphael
1
@ Raphael Die "beweisende" Sprache ist mehrdeutig und die "katastrophale" Formulierung, denke ich, ist eine Übertreibung. Guter Fang.
Codeah
@ Raphael Danke für die Hinweise zur Syntax.
Codeah