文脈自由文法を左と右の再帰的にすることができますか？

Question

ex。

S-> S + T | T

T-> U-T | U

U - > ID | N

連合性は明らかに保持されません。しかし、私はそれがとにかく曖昧であるとは見えません。だから、これはあいまいではないcfgですか？

Answer 1

文法は、あなたのように左と右の両方の再帰を持つことができますが、あまり意味はありません。 （文法が正規でない限り、同じものではなく、一貫して）すべての再帰を左右のどちらかであるので、任意の文法を書き換えることができます。

A -> B A C 

は次のようになります。

A -> B X 
X -> A C 

あなたは今、相互再帰を持っています1つのルールでは左にあり、別のルールでは右側にあります。質問のあなたの文法は明白であるように見えますが、実際には左回りまたは右回帰とは関係ありません。