間接的な左回帰の排除

Question

この文法で左回帰を削除する方法のオンライン説明を理解するのに問題があります。私は直接再帰を削除する方法を知っていますが、私は間接的な処理方法を明確にしていません。それは誰でも説明できますか？

A --> B x y | x 
B --> C D 
C --> A | c 
D --> d 

Answer 1

これを行う方法は、違反している非終端記号の1つをそれぞれの展開で置き換えることです。この場合、我々は最初にその拡張でBを置き換える：

A --> C x y | D x y | x 
C --> A | c 

：

A --> B x y | x 
B --> C D 

は今

A --> C x y | D x y | x 

となり、我々は同じ非終端記号についてCを行います

は

A --> A x y | c x y | D x y | x 

のみ、他の残りの文法規則ので、あなたもあるので、何の間接左再帰は、今ありません

A --> A x y | c x y | d x y | x 

としてあなたの全体の文法を残し、その交換を行うことができます

D --> d 

です間接的なものではありません。

hereも参照してください。

A -> x A' 
A' -> xyA' | cxyA' | dxyA' | epsilon 

：

---

は、「 Aを導入し、完全に（だけではなく間接的左再帰）（この明確化と完成のためのOPにクレジット）独自の材料から記号を左再帰を排除するために、 naomikのコメント

から

---

レスポンス

はい、文法には興味深いプロパティがあり、文法規則の制約の点で特定の意味機能を特徴付けることができます。特定の種類の解析問題を処理する変換アルゴリズムがあります。この場合

は、我々は、左再帰削除する：文法の望ましい特性は、任意ルールマストの使用は、少なくとも一つの入力トークン（終端記号）を消費することです。左回帰は、パーサの無限再帰への扉を開く。

私は、これらのことを何年も前に「Foundations of Computing」と「Compiler Construction」クラスで学びました。特定の文法に適応するパーサーを書くのではなく、私たちが望むパーサースタイルに合わせて文法を変換します。