左因数分解と左回帰の差

Question

Left FactoringとLeft Recursionの違いは何ですか？私はLeft factoringが予測的なトップダウン解析手法であることを理解しています。しかし、私はこれら二つの言葉を聞いて混乱します。

Answer 1

これは、私が使用する二つの用語を見てきた方法です。一つ以上の作品がイン間の消費なしのトークンと自分自身から到達することができます。

1. は、再帰を左。
2. 左の因数分解：文法を左回帰形式から等価な非左回帰形式に変換する変換プロセス。

Answer 2

左回帰：=左手の非終端記号は右手の非終端記号と同じです。 例： A-> A & | Bここで、&はアルファです。 この作品を同様に書き直して、左リサーチを削除することができます。

A-> BA」 A ' - > & A' |€

左要因べきでない非決定論productnを意味します。 。 例： A-> & A | | &C

Answer 3

左ファクタリングは、文法変換技術です。これは、2つ以上のプロダクションに共通する接頭辞を「ファクタリングアウト」することからなる。行くたとえば

、：

A - >αβ| αに

をγ： - >α '

A' -

A>β| γ

---

左再帰プロパティを使用すると、与えられた変数（非ターミナル）から1つ以上のステップで、同じ変数で始まるRHSを導き出すことができたときに文法が持っています。

例えば：

A - >α

又は

A - >

BαB -

γ> A

と呼ばれる文法変換手法があります。左回帰の除去は、左回帰文法を指定すると、等価で残りは再帰的ではない別の文法を生成する方法を提供します。

---

両方の用語との関係/混乱はおそらく両方の形質転換技術は、それのためにパーサを予測トップダウン導出できるようになる前に、文法に適用する必要があるかもしれないという事実に由来します。

Answer 4

左のファクタリングは、同じ非終端の2つのプロダクションに現れる共通の左の要素を削除しています。パーサによるバックトレースを避けるために行われます。パーサーがルックアヘッドを持っていると仮定し、この例を考えてみましょう。

A - > qB | qC
ここで、A、B、Cは非終端記号であり、qは文である。 この場合、パーサーは2つのプロダクションのどちらを選択するのか混乱し、バックトレースする必要があります。 > qD回

D - - 左ファクタリング後、文法は

Aツー変換され> B | C

この場合、先読みのあるパーサは常に適切なプロダクションを選択します。

左端再帰は、非終端記号の生成における左端の非終端記号が非終端記号（直接左回帰）であるか、または他の非終端記号定義を介して、 （間接的な左回帰）。 これらの例を検討 -

（1）A - >のAq（直接）

（2）A - >ベクレル B - > AR（間接）

左再帰場合は除去されなければなりません|>Aα - それは派生Aが存在するように非終端Aを持っている場合は文法が再帰残され ：パーサは、トップダウン解析する

Answer 5

左再帰を行い、 βここで、αとβはAで始まらない端末と非終端記号のシーケンスです。

トップダウンパーサーを設計する際に、左回帰が文法に存在する場合、パーサは無限ループに入ります。 AはA自身と一致しようとしていますが、これは不可能です。 上記の再帰を排除するには、問題のある生産を書き直します。>βA '

A' - -

A AS->αA」|イプシロン

左因子分解：左因子分解は、文法の非決定論を除去するために必要です。文法を仮定すると、S - > abS | aSb

ここで、Sは、非決定論に続く生産規則（同じ2つの選択肢S）で同じ端末aを導出しています。 > '

S' のように - - 私たちは

S AS-Sの決定を延期する生産を書き換えることができます> bSの| |> AB1 - A：

が与えられた文法をしてみましょう：このよう

Sbをは、S」はBS又はSbを

Answer 6

左の要因のために交換することができますab2 | ab3

1）すべてのプロダクションで、ここでプロダクションを選択すると共通のプレフィックス&があることがわかります。バックトラックする必要はないことが確認されていません。
2）生成を選択することができず、正しい構文解析ツリーを作成して目的の文字列に到達することができるため、非決定論的です。 しかし、決定論的な方法で文法を書き直し、バックトラッキングなしで可能な文字列を作成するのに十分な柔軟性をもたらします....

A - > aA ' 、 A ' - > b1 | b2 | b3 これで、文字列ab2の解析ツリーを作成するように求められたら、バックトラッキングは必要ありません。なぜなら、A 'を得るときには常に正しい生産を選ぶことができるからです。したがって、正しい解析木を生成します。

左帰納：

A - > Aa | b ここで、Aの左の子は、最初のプロダクションを選択すると常にAになることは明らかです。これは再帰になります。Aは何度も何度も繰り返し呼び出しています。 この文法から生成された文字列は次のようになります。これは文法にすることはできませんので、 BAは...私たちは書面による左再帰を排除 *：

A - > BA ' A' - > E | aA ' ここで、再帰を残さず、ba *を生成することもできます。