この左再帰と左因数分解のトピックは初めてです。この文法が再帰のままか、因数分解のままかを判断するのを手伝ってください。
S-> aAd | BD | あべ | ばえ | CA | cB
質問する
215 次
1 に答える
0
左再帰ですか？答え: いいえ。
定義によれば、「文法は、最終的にそれ自体を左記号とする文形を導出する何らかの非終端記号 A を見つけることができる場合、左再帰的です。」
例: 即時左再帰は、次の形式の規則で発生します。
A -> Aa | b
ここで、 aとbは非終端記号と終端記号のシーケンスであり、bはAで始まりません。
明らかにそうではありません:
S-> aAd | BD | あべ | ばえ | CA | cB
左因数分解ですか？答え: はい。
定義上、左因数分解では、非終端を展開するために、どの 2 つの代替生産を選択するかが明確ではありません。
このあいまいさは、同じターミナル/非ターミナルで始まる 2 つの代替プロダクションがある場合に発生します。あなたの場合、2つの代替パスが3回あることがわかります。
S-> aAd | aBe
S-> bBd | bAe
S-> cA | cB
左因数分解を削除すると、文法は次のようになります。
S-> aA'
A'-> Ad | Be
S-> bB'
B'-> Bd | Ae
S-> cC'
C'-> A | B
このスライドでは、同じことをより簡単な言葉で説明しています
于 2013-06-15T04:52:45.160 に答える