使上下文无关语法更简单（更漂亮）

Question

我正在使用 CFG，每次我为特定语言编写规则时，我的 CFG 都会变得令人厌恶。它最终变成一行：

S->tooooooo much stuff

我知道将事物放入乔姆斯基范式会将其置于正确的格式，并且事物会更漂亮，但我想知道是否有任何想法可以记住，以使这些看起来不那么混乱。

即，lang：

a^n b^m, where n >= m

我的CFG（粗略）：

S -> Sa|Sab|Sba|aS|aSb|abS|bSa|baS|ε

有人可以帮助我改掉我的坏习惯吗？

Answer 1

你真的需要用CFG来描述这种简单的语言吗？只计算 a 和 b 会容易得多。

但假设这只是一个例子......

真实解析器中的 CFG 通常将其分成每行一个产生式，并以某种合理的方式将它们分组。

S -> a b S
   | b a S
   | a S
   | a S b
   | b S a
   | ε