Linksrekursion und links Factoring - welches geht zuerst?

Question

Wenn ich eine Grammatik mit einer Produktion habe, die sowohl linksrekursion als auch links enthält, wie links

$ qquad displaystyle f to fba Mid CDS Mid C $

Welches hat Priorität, linke Rekursion oder Linksfaktor?

Answer 1

Transformationen wie das linke Faktor oder die Entfernung der linken Rekursion haben keine Vorrangregeln. Offensichtlich können die resultierenden Grammatiken unterschiedlich sein, aber sie werden dieselbe Sprache erkennen.

Die beispielhafte Grammatik der Frage ist schwieriger als das typische Problem der Hausaufgaben. Es wird also nützlich sein, unsere Arbeit zu zeigen.

Linksrekursion

Lassen Sie uns eine Transformation definieren, die die linke Rekursion beseitigt.

Gegeben

$ qquad displayStyle a to a alpha_0 mid a alpha_1 mid dots mid a alpha_n mid b beta_0 mid b beta_1 mid dots mid b beta_n $,,,,,,,,,,,,,,,,,,,,,,,,,

Wir entfernen die linke Rekursion wie diese:

$ qquad displaystyle begin {align} a_h & to b beta_0 mid b beta_1 mid dots mid b beta_n a_t & to alpha_0 mid alpha_1 mid dots mid alpha_n a_ {t^+} & to a_t a_ {t^+} mid a_t a & to a_h a_ {t^+} mid a_h end {Align} $

Die Allgemeinheit von oben wird in den Compiler -Texten normalerweise nicht angegeben, aber das Parsen von Texten wie Grune & Jacobs decken dies ab. Die linke Faktorierung kann auf die obige transformierte Grammatik angewendet werden, werden jedoch nur zusätzliche Regeln einführen, die die Antwort nicht ändern. Wir werden vereinfachen Die Präsentation ohne zusätzliche Faktorierung wird durchgeführt.

In dieser Antwort werden wir keine indirekten Probleme mit der linken Rekursion behandeln, da wir uns nur mit den Regeln eines einzelnen Nicht-Terminals befassen. Beachten Sie jedoch, dass indirekte linke Rekursion behandelt werden kann. (Öffnen Sie eine separate Frage, wenn dies wichtig ist.)

Links Factoring

Das Entfernen der linken Faktorierung ist in den meisten Einführungs -Compiler -Texten wie diese. Gegeben

$ qquad displaystyle a bis xy Mid xz $

Linksfaktorendrenditen:

$ qquad displaystyle begin {align} a_s & bis y mid z a & bis x a_s end {align} $

Dies führt die Transformationen beider Reihenfolge durch.

Links zuerst Factoring

Lassen Sie uns die Grammatik der Frage faktorieren

$ qquad displaystyle begin {align} f_s & to ds Mid varepsilon f & bis fb a mid c f_s end {align} $

und dann die linke Rekursion entfernen:

$ qquad displayStyle begin {align} f_h & to c f_s f_t & to b a f_ {t^+} & to f_t f_ {t^+} | F_t f_s & to ds mid varepsilon f & to f_h f_ {t^+} mid f_h end {align} $

Zuerst entfernen

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

$ qquad displaystyle begin {align} f_h & to c ds mid c f_t & bis b a f_ {t^+} & to f_t f_ {t^+} mid f_t F & bis F_H F_ {T^+} MID F_H END {Align} $

und faktor dann das Terminal $ C $:

$ qquad displaystyle begin {align} f_ {hs} & to ds mid varepsilon f_h & bis c f_ {hs} f_t & to b a f_ {t^+} & to f_t f_ {t^+} mid f_t f & to f_h f_ {t^+} mid f_h end {align} $

Aha, die resultierenden Grammatiken sind gleich!

Im Allgemeinen ist das Beweisen, dass zwei Grammatiken gleichwertig sind. Wenn also eine Serie -Grammatik -Transformationen die beeinflussen könnten Sprache, die erkannt wird Dann wäre es katastrophal.