语法中可以存在跟随冲突吗？

Question

我知道 First/First 和 First/Follow 语法中存在冲突，这使得语法 "not LL(1)"。我只是想知道语法中是否存在 Follow/Follow 冲突。

Answer 1

是的，这是可能的，但它需要不寻常的配置才能实现。考虑以下语法，它增加了一个新的开始符号：

S' → S$

S → tT

T → A | B

A → ε

B → ε

现在，让我们想象一下尝试填写我们的 LL(1) 解析 table，如下所示：

          $          t
     +----------+----------+
 S'  |          | S' -> S$ |
     +----------+----------+
 S   |          | S -> tT  |
     +----------+----------+
 T   | T -> A   |          |
     | T -> B   |          |
     +----------+----------+
 A   | A -> e   |          |
     +----------+----------+
 B   | B -> e   |          |
     +----------+----------+

请注意 (T, $) 的条目中有两项。这是有道理的：如果我们有活动的非终结符 T 并看到 $，我们知道我们需要 select 一个将展开为空字符串的产生式。我们有两种不同的方法来做到这一点：我们可以使用 T → A 或 T → B，最终目标是将每个非终结符扩展为空字符串。这是一个问题 - 我们无法预测要走哪条路线。

现在，这是什么样的冲突？它不可能是 FIRST/FIRST 冲突，因为 FIRST(A) = {ε} 和 FIRST(B) = {ε}，所以 A 和 B 在其第一组中都没有任何终端。出于同样的原因，它不能是 FIRST/FOLLOW 冲突。

这意味着这是罕见的 FOLLOW/FOLLOW 冲突 - 我们知道我们会根据 A 和 B 的 FOLLOW 集合中的内容来选择制作，但它们彼此完全相同并且所以解析器无法明确地选择下一步要做什么。

Answer 2

这可能是一个更简单的例子

S → A a 
A → B | C
B → ε
C → ε

这里，由于a同时在B和C的FOLLOW中，所以在(A, a)上会出现[=16之间的冲突=] 和 A → C。注意没有其他冲突。

语法中可以存在跟随冲突吗？

Can a follow-follow conflict exist in a grammar?

parsing

compiler-construction

ll