parsing - 这个 'algorithm' 可以为空并且第一次工作(在解析器中)吗？

Question

为了好玩而解决这个问题:http://www.diku.dk/hjemmesider/ansatte/torbenm/Basics/

可为 null 的计算示例，并且首先使用定点计算。 (参见第3.8节)

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

如果您尝试通过递归实现可空或首先实现，那么很明显您将在像

这样的产生式上无限递归

N -> N a b

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

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

这似乎适用于可为空的情况。首先呢？

编辑:这是我从玩耍中学到的东西。源代码链接位于底部。

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

考虑:

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

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

这里我们不能忽略N:

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

如果我们忽略 N -> N a 中的 N，我们会推断 a 位于 first(N) 这是错误的。相反，我们看到 N 不可为空，因此在首先计算时，我们可以省略任何其中 N 被发现为 RHS 中第一个符号的产生式。

这会产生:

N -> M
M -> b

这告诉我们b在first(N)中。

源代码:http://gist.github.com/287069

那么...这听起来不错吗？

Answer 1

我建议继续阅读:)

3.13 重写 LL(1) 解析语法，特别是 3.13.1 消除左递归。

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

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

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

您可能想检查this paper这以更直接的方式解释了它。更少的理论:)