parsing - 这个“算法”是否适用于可空和第一个工作（在解析器中）？

Question

可空值的计算示例首先使用定点计算。（见第 3.8 节）

我在 Scheme 中做事并且非常依赖递归。

如果您尝试实现可为空的或首先通过递归实现，那么很明显您将在像这样的生产中无限地重复

N -> N a b

其中 N 是非终结符，a,b 是终结符。

这是否可以通过维护一组在生产规则左侧看到的非终结符递归地解决，并在我们考虑它们一次后忽略它们？

这似乎适用于可为空的。先说什么呢？

编辑：这是我从玩耍中学到的。源代码链接在底部。

非终结符在 first 的计算中不能被忽略，除非它们可以为空。

考虑：

N -> N a
N -> X
N ->

在这里我们可以忽略N，N a因为它可以N为空。我们可以替换N -> N a为N -> a并推断它a是的成员first(N)。

在这里我们不能忽视N：

N -> N a
N -> M
M -> b

如果我们忽略Nin，N -> N a我们会推断出a哪个first(N)是假的。相反，我们看到 N 不可为空，因此在首先计算时，我们可以省略任何N在 RHS 中作为第一个符号找到的产生式。

这产生：

N -> M
M -> b

这告诉我们b在first(N).

所以……这听起来好吗？

score 1 · Accepted Answer

我建议继续阅读:)

3.13 Rewriting a grammar for LL(1) parsing尤其是3.13.1 Eliminating left-recursion。

请注意，您也可能遇到间接左递归：

A -> Bac
B -> A
B -> _also something else_

但是这里的解决方案与消除第一个示例中的直接左递归非常相似。

您可能想查看这篇论文，它以更直接的方式解释了它。少理论:)

1 回答 1