2

このアルゴリズムが示すように、間接再帰を削除してから直接再帰を削除することにより、CFG から左再帰を削除しようとしています。

私はこの文法を使用します：

A = A a | A B C | B C | D D

i = 1でj = 1の場合、 A -> A rの形式のすべてのプロダクションを次のように置き換えます。

A -> δ 1 γ | δ 2 γ | .. | δ k γ

したがって、一致する A -> A aを見ると、次のように置き換える必要があります

A -> A a a | A B C a a | B C a | D D a

どちらが間違っていると確信していますか

プロダクション自体に置き換えるときに、プロダクションを置き換える方法について誰かが正しい方向に向けることができますか?

注：また、私は最初のルールだけに固執しているので、簡単にするために他のルールを省略しました

どんな助けでも大歓迎です

[更新]元のギリシャ記号にできるだけ近いものを見つけました。また、おそらくこれに間違った方向でアプローチしていますか。i=1かつj=1の場合、A j -> A a | ABC | 紀元前 | 紀元前 DD、しかし、A j -> BC |を使用する必要があります。DD もしそうなら、私は得るでしょう：

A -> B C A | B C B C | D D A | D D B C | B C | D D

これにより、そのプロダクションでの再帰が排除されます。これはより良い方向ですか？

4

1 に答える 1

3

これはレシピです：

A → Aα1 | ... | Aαm | β1 | ... | βn

次のように変換する必要があります。

A → β1 A' | ... | βn A'
A' → α1 A' | ... | αm A' | ε

あれは：

  1. 再帰的なプロダクションを、再帰が右側にある新しいプロダクションに置き換えます。そのためには、新しい非終端記号を使用してください。
  2. 右側が空のプロダクションを新しい非ターミナルに追加します。
  3. 非再帰生成の右側に新しい非終端記号を追加します。

あなたの文法のために：

A = A a | A B C | B C | D D

あなたは得るでしょう：

A  = B C A' | D D A'
A' = a A' | B C A' | ε
于 2011-02-27T18:05:49.247 に答える