context-free-grammar - 找到一个 LL(1) 语法？

Question

我如何找到该语言的 LL(1) 语法：

L=a ^m b ⁿ c ^m+n

其中 m 和 n 是自然元素的元素？我的上下文无关语法是：

S → AB

A → acA | 交流

B → bcB | 公元前

谁能告诉我我是否走在正确的轨道上？

编辑：我的新 CFG 是

S → aSc | 乙

B → bBc | 公元前

但是我认为我可能对 LL(1) 有一个错误，因为 B 的两个推导都以 b 开头。这是正确的吗？

编辑 谢谢你我想我明白了：

S → aSc | 乙

B → bBc | 拉姆达

Answer 1

你的语法有两个主要问题：

1. 您目前可以生成一些不是该语言的字符串。例如，您的语法可以生成 acacbcbc，它不在该语言中。

2. 您的语法不是 LL(1)，因为您有许多 FIRST/FIRST 冲突。例如，产生式 A → acA 和 A → ac 都以 a 开头，因此给定非终结符 A 和字符 a，您无法确定应用哪个产生式。

作为提示，您的语言中的字符串正是 a ^m b ⁿ c ⁿ c ^m形式的字符串。也就是说，试试看能不能在前面生成 m a，在后面生成 m c，然后切换生成 n b 和 n c 匹配。^{您可能想先尝试为m} c ^m找到一个语法，然后看看是否可以调整它。

编辑新语法：这看起来好多了！但是，您的作品中仍然存在 FIRST/FIRST 冲突

B → bBc

和

B → 公元前

此外，您的语法无法生成字符串ac或 ε。您应该能够通过修复 FIRST/FIRST 冲突来解决这两个问题。作为一个提示：你怎么能用一个让你不生成字符的产品替换第二个产品？

希望这可以帮助！