私の文法で左回帰を解決する

Question

私の文法では、第6の生成規則で左回帰のケースがあります。

私はこのような規則6および7を交換することによって、これを解決：私はこの文法で任意の間接的な左再帰を見つけることができませんでした

。

唯一気になるのは、2つの非端末で囲まれた端末を持つ最終的な制作ルールです。

私の二つの質問は次のとおりです。

• は正しい私の解決左再帰ですか？
• 最終的な制作ルールは左回帰ですか？私はどのように この特殊なケースを扱うか分からない。

Answer 1

はい、解決は正しいです。使いやすさのためにイプシロン規則を削除したいかもしれませんが、受け入れられた文字列は正しいです。チェックとして

X -> - 
X -> -Z 
Z -> + 
Z -> +Z 
Z -> X + Y 
... and Y is of the form 0* 1 (no syntax collisions) 

、あなたはが今Xの各拡張のための1つの、二つの新しいルールで、この最終規則を置き換えることができることに注意してください：

Z -> - + Y 
Z -> -Z + Y 

これは、Zルールから完全にXを削除します各Zルールは端末で始まります。

いいえ、最終生産ルールはもはや左回帰的ではありません。 Xは、非終端記号で始まる文字列に解決する必要があります。

しかし、私は言語の使い方が不思議です。 :-)