简化 CFG：S -> SS | （小号） | ε

Question

是否可以进一步简化下一个 CFG？

S -> SS | (S) | ε

我已经删除了所有其他的 null 和 unit 产生式，但我相信可以进一步简化它。

Answer 1

怎么样

S -> (S)S | ε

这是否涵盖了原作的所有部分？

S -> (S) 被第二个 S 覆盖为 ε

S -> SS 是两个 ε，检查；或包含至少一对括号，检查

是的，看起来不错。你可以选择你更喜欢(S)S还是S(S)，效果应该是一样的。

注：不是很权威，我说的也只是一个模糊的概念