context-free-grammar - 使上下文无关语法更简单（更漂亮）

Question

我正在使用 CFG，每次我为特定语言编写规则时，我的 CFG 最终都会令人作呕。它以一行结束：

S->tooooooo much stuff

我知道将东西放入 chomsky 范式会使其格式正确，并且会更漂亮，但我想知道是否有任何想法可以让这些看起来不那么混乱。

即，朗：

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
   | ε