0

我无缘无故地实现了 LALR 解析表的自动构建。这个解析器有两种风格，LALR(0) 和 LALR(1)，其中的数字表示预读的数量。

我对前瞻意味着什么感到困惑。

如果我的输入流是“abc”并且我有以下产品，我需要 0 前瞻还是 1？

    P :== 一个 E

同样的问题，但我无法通过仅查看输入中的“a”来提前选择正确的 P 产品。

    P :== ab E
      | ab F

我还有另外的困惑，因为我认为在构建 LALR 解析器生成器时不会真正发生后一种 P-production。原因是当我们计算闭包时，语法会自动有效地左分解。

我正在浏览此页面并且没问题，直到我进入第一/后续部分。我的问题是我不知道我们为什么要计算这些东西，所以我很难在脑海中抽象出这个。

我几乎明白，前瞻与改变输入无关，而是决定何时减少。

我一直在读《龙》的书，但它和塔伦蒂诺的剧本一样线性。对于已经知道如何做到这一点的人来说，这似乎是一个很好的参考。

4

1 回答 1

5

在学习自下而上解析（例如 LALR）时，您需要做的第一件事是记住它与自上而下解析完全不同。自上而下的解析从非终结符开始，即产生式的左侧 (LHS)，并猜测使用哪个右侧 (RHS)。另一方面，自下而上的解析从识别 RHS 开始，然后计算出要选择的 LHS。

更具体地说，自下而上的解析器将传入的令牌累积到队列中，直到右侧位于队列的右侧。然后它通过用相应的 LHS 替换它来减少RHS，并检查适当的 RHS 是否位于修改后的累加输入的右侧边缘。它继续这样做，直到它决定在输入中的该点不再发生减少，然后读取一个新令牌（或者，换句话说，获取下一个输入令牌并将其转移到队列的末尾。 )

这一直持续到读取最后一个标记并执行所有可能的缩减，此时如果剩下的是作为“开始符号”的单个非终结符，则它接受解析。

解析器不必仅仅因为它出现在当前队列的末尾就减少 RHS，但它不能减少不在队列末尾的 RHS。这意味着它必须在转移任何其他代币之前决定是否减少。由于该决定并不总是显而易见的，它可能会检查一个或多个它尚未读取的标记（“前瞻标记”，因为它正在查看输入）以便做出决定。但它只能查看下一个k令牌的某个值k，通常为 1。

这是一个非常简单的例子；逗号分隔列表：

1. Start -> List
2. List  -> ELEMENT
3. List  -> List ',' ELEMENT

假设输入是：

ELEMENT , ELEMENT , ELEMENT

一开始，输入队列是空的，由于没有 RHS 是空的，唯一的选择是移位：

queue                   remaining input                 action
----------------------  ---------------------------     -----
                        ELEMENT , ELEMENT , ELEMENT     SHIFT

下一步，解析器决定使用产生式 2 进行归约：

ELEMENT                 , ELEMENT , ELEMENT             REDUCE 2

现在List队列末尾有 a，因此解析器可以使用生产 1 减少，但它决定不基于它,在传入输入中看到 a 的事实。这持续了一段时间：

List                    , ELEMENT , ELEMENT             SHIFT
List ,                  ELEMENT , ELEMENT               SHIFT
List , ELEMENT          , ELEMENT                       REDUCE 3
List                    , ELEMENT                       SHIFT
List ,                  ELEMENT                         SHIFT
List , ELEMENT          --                              REDUCE 3

现在，前瞻标记是“输入结束”伪标记。这一次，它确实决定减少：

List                    --                              REDUCE 1
Start                   --                              ACCEPT

并且解析成功。

这仍然留下了一些问题。首先，我们如何使用 FIRST 和 FOLLOW 集？

作为一个简单的答案，如果不知道可能跟随该非终结符的非终结符的 FIRST 集，就无法计算非终结符的 FOLLOW 集。我们可以决定是否应该执行归约的一种方法是查看前瞻是否在归约目标非终结符的 FOLLOW 集中；如果不是，则肯定不应该执行减少。该算法对于上面的简单文法来说已经足够了，例如： 的减少Start -> List是不可能的,，因为,is not in FOLLOW(Start)。可以以这种方式解决唯一冲突的语法是SLR语法（其中S代表“简单”，它肯定是）。

对于大多数语法来说，这还不够，还需要进行更多的分析。一个符号可能在非终结符的 FOLLOW 集中，但不在导致当前堆栈配置的上下文中。为了确定这一点，我们需要更多地了解我们是如何获得当前配置的；各种可能的分析导致LALR和IELR规范LR解析，以及其他可能性。

于 2014-11-16T18:13:55.380 回答