0

我对遵循以下规则集有疑问：

L -> CL'
L' -> epsilon
       | ; L
C -> id:=G
      |if GC
      |begin L end

我已经计算出Follow(L)在Follow(L'). 也是Follow(L')在，Follow(L)所以它们都将包含：{end, $}. 但是，L'Nullable 也将Follow(L)包含Follow(C)?

我已经计算出Follow(C)=First(L')和Follow(C) subset Follow(L) = { ; $ end}.

在答案中Follow(L)and Follow(L')contains only {end, $}，但它不应该包含;as可以为 null 吗Follow(C)？L'

谢谢

4

1 回答 1

2

但是，L'Nullable 也将Follow(L)包含Follow(C)?

相反。Follow(C)将包含Follow(L). 想想下面的句子：

...Lx...

其中 X 是某个终端，因此在Follow(L). 这可以扩展为：

...CL'x...

并进一步：

...Cx...

所以跟在L之后的，也可以跟在C之后。相反的不一定成立。

要计算以下，请考虑一个图，其中节点是 (NT, n)，这意味着非终结NT符的标记长度如下（在 LL(1) 中，n为 1 或 0）。您的图表如下所示：

     _______
   |/_      \
(L, 1)----->(L', 1)         _(C, 1)
 |  \__________|____________/| |
 |             |               |
 |             |               |
 |   _______   |               |
 V |/_      \  V               V
(L, 0)----->(L', 0)         _(C, 0)
    \_______________________/|

其中(X, n)--->(Y, m)表示长度为 的跟随n，X取决于长度m为Y（当然，m <= n）的跟随。即计算(X, n)，首先你应该计算(Y, m)，然后你应该查看包含X在右侧和Y左侧的每个规则，例如：

Y -> ... X REST

将每个inREST扩展为长度，然后将每个结果与集合中的每个跟随连接起来。您可以在计算 的第一个时计算扩展的内容，只需持有一个标志，说明是完全扩展为第一个还是部分扩展。此外，添加first of with length如下。例如：n - mm[0, n)(Y, m)RESTRESTRESTRESTnX

S -> A a b c
A -> B C d
C -> epsilon | e | f g h i

然后找到长度为 3 的 B 的跟随（它们是e d a和d a b）f g h，我们看一下规则：

A -> B C d

我们拿这个句子C d，看看它可以产生什么：

"C d" with length 0 (complete):
"C d" with length 1 (complete):
    d
"C d" with length 2 (complete):
    e d
"C d" with length 3 (complete or not):
    f g h

现在我们把这些和合并follow(A, m)：

follow(A, 0):
    epsilon
follow(A, 1):
    a
follow(A, 2):
    a b
follow(A, 3):
    a b c

"C d" with length 0 (complete) concat follow(A, 3):
"C d" with length 1 (complete) concat follow(A, 2):
    d a b
"C d" with length 2 (complete) concat follow(A, 1):
    e d a
"C d" with length 3 (complete or not) concat follow(A, 0) (Note: follow(X, 0) is always epsilon):
    f g h

这是我们正在寻找的集合。所以简而言之，算法变为：

  • 创建跟随依赖关系图
  • 找到连接的组件并从中创建一个DAG。
  • 从末端（从没有任何依赖关系的节点）遍历 DAG，并使用上面的算法计算以下，事先计算好第一个。

值得注意的是，上述算法适用于任何 LL(K)。对于 LL(1)，情况要简单得多。

于 2014-05-08T11:21:56.560 回答