質問

I have to transform the following grammar into a non left recursive grammar:

S → aSb | bAS

A → AaA | bAA | AAa | bAb

This is what I came up with:

A → bAAA’| bAbA’

A’ → aAA’| AaA’| ε

S → aSb | bAS

As far as I can tell, there is no more left recursion because none of the leftmost symbols on the RHS are the same as the nonterminal on the left. However, assuming S is the starting symbol, there is still infinite recursion because A calls itself repeatedly. Is this expected? Or did I derive the non left recursive grammar incorrectly?

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top