5

我无法使用包含 epsilon 产生式的语法为 LR(1) 解析器构建项目集的集合。例如，给定以下语法（其中 eps 代表 epsilon）

S -> a S U
U -> b
  |  eps

State0 将是

S' -> .S, $
S -> .a S U, $

从 State0 用 'a' 移动会得到以下状态，我们称之为 State2

S -> a .S U, $
S -> .a S U, $/???

为了预测 State2 的第二项，我需要计算 FIRST(U$)。我知道 FIRST(U) = {'b', eps}。我的第一个问题是：State2 的第二项的前瞻是 $ 和 'b'？由于 U 可以是 eps，我的大脑告诉我，我也可以将 $ 作为前瞻，而不仅仅是“b”。如果 FIRST(U) 只是 {'b'}，它就只是 'b'。那是对的吗？

第二个问题：在某些时候，我将有如下状态

S -> a S .U, $
U -> .b, $
U -> .eps, $

我在这里做什么？我是否需要与 eps 一起移动并与该项目一起设置U -> eps., $？如果我有另一个终端作为前瞻，即X -> .eps, a/$？如果我搬家，最终有一套表格X -> eps., $，我会减少吗？

还有更多：我需要在解析表中插入 eps 作为符号吗？

谢谢

4

1 回答 1

7

  1. FIRST(U$)意思是“可以在”的推导中首先出现的一组符号U$。显然，如果U能导出空字符串，$肯定是这个集合的一部分。输入结束标记$确保我们永远不必担心FIRST集合中的 epsilon。（如果我们使用 LR(k) 而不是 LR(1)，我们将使用k结束标记，以便所有字符串都有长度。FIRSTkk

  2. 与U → （或U → ε如果您坚持的话）关联的项目是U → • 。换句话说，它是可约的，并且应该在匹配前瞻时触发减少操作。

  3. ε不是一个符号；我们只（有时）使用它来使空字符串可见。但是空字符串是空的。

于 2018-05-17T16:24:06.697 回答