grammar - 语法 && LL 解析器

Question

所以我有一个家庭作业，我花了 2 多个小时试图找出为什么这个语法不适用于 LL 解析器：

<A> → a <B>
<A> → a b <C>
<B> → b d <D>
<C> → d <E>
<D> → m n
<E> → x y

有人可以指出我正确的方向吗？我知道 LL 可能被绊倒的一种方式是，如果它陷入无限循环，我不相信它在这里会发生。

谢谢

Answer 1

我认为 LL Parser 你的意思是 LL(1) 解析器（一个 LL Parser，前瞻为 1）

对于 LL(1) 解析器可以解析的文法，它必须是 LL(1)。语法必须遵守一些事情才能成为 LL(1)，如果它破坏了其中之一，则称为 LL(1) 冲突。

• 第一次/第一次冲突：

  对于每个非终结符，每个产生式都必须有一个不相交的 FIRST 集。（FIRST 集是可以从主语派生的句子开始的所有终结符的集合。）

  EG：在你上面的例子中，非终端有两个产生：

  <A> -> a <B>
  <A> -> a b <C>
  

  每个作品的第一组如下：

  FIRST(a <B>) = {a}
  FIRST(a b <C>) = {a}
  

  你可以很清楚地看到这两组相交。这是一个问题，因为在 LL 解析器中，如果到达 A 在堆栈上的点，并且要读取的下一个符号是 'a'，那么解析器不知道是选择<A> -> a <B>还是<A> -> a b <C>。

• FIRST/FOLLOW 冲突：

  这发生在，对于特定的非终端A；FOLLOW(A)和FIRST(A)相交A是NULLABLE。您的示例中没有出现这种特殊的冲突。

有关 FIRST、FOLLOW 和 NULLABLE 的更多详细信息，我会

有关这些冲突的更多详细信息以及一些示例，请参阅有关 LL(1) Conflicts 的 Wikipedia 页面。