这个“算法”会吗？对于可为空和第一个工作（在解析器中）？
有趣地完成这个工作： http://www.diku.dk/hjemmesider/ansatte /torbenm/Basics/
可空计算示例，并且首先使用定点计算。 （参见第3.8节）
我正在Scheme中做事并且很大程度上依赖于递归。
如果您尝试首先通过递归实现可为 null 或，那么很明显您将在类似
N ->; 的产生式上无限递归。 N a b
其中 N 是非终结符，a,b 是终结符。
通过维护一组在生产规则左侧看到的非终结符，并在我们考虑它们一次后忽略它们，可以递归地解决这个问题吗？
这似乎适用于可为空。首先呢？
编辑：这是我从玩耍中学到的东西。源代码链接在底部。
非终结符在first 的计算中不能被忽略，除非它们可以为空。
考虑一下：
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， N aa 位于 first(N) 中，这是错误的。相反，我们看到 N 不可为空，因此在首先计算时，我们可以省略任何在 RHS 中发现 N 作为第一个符号的产生式。
这会产生：
N -> M
M -> b
它告诉我们 b 位于 first(N) 中。
源代码： http://gist.github.com/287069
那么......这听起来不错吗？
Working through this for fun: http://www.diku.dk/hjemmesider/ansatte/torbenm/Basics/
Example calculation of nullable and first uses a fixed-point calculation. (see section 3.8)
I'm doing things in Scheme and relying a lot on recursion.
If you try to implement nullable or first via recursion, it should be clear you'll recur infinitely on a production like
N -> N a b
where N is a non-terminal and a,b are terminals.
Could this be solved, recursively, by maintaining a set of non-terminals seen on the left hand side of production rules, and ignoring them after we have accounted for them once?
This seems to work for nullable. What about for first?
EDIT: This is what I have learned from playing around. Source code link at bottom.
Non terminals cannot be ignored in the calculation of first unless they are nullable.
Consider:
N -> N a
N -> X
N ->
Here we can ignore N in N a because N is nullable. We can replace N -> N a with N -> a and deduce that a is a member of first(N).
Here we cannot ignore N:
N -> N a
N -> M
M -> b
If we ignored the N in N -> N a we would deduce that a is in first(N) which is false. Instead, we see that N is not nullable, and hence when calculating first, we can omit any production where N is found as the first symbol in the RHS.
This yields:
N -> M
M -> b
which tells us b is in first(N).
Source Code: http://gist.github.com/287069
So ... does this sound OK?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我建议继续阅读:)
3.13 重写 LL(1) 解析语法，尤其是3.13.1 消除左递归。请注意，您也可能遇到间接左递归：
但这里的解决方案与消除第一个示例中的直接左递归非常相似。
您可能需要查看这篇论文，其中对此进行了一些解释更直接的方式。理论较少：）
I suggest to keep on reading :)
3.13 Rewriting a grammar for LL(1) parsingand especially3.13.1 Eliminating left-recursion.Just to note you can run into indirect left recursion as well:
But the solution here is quite similar to eliminating the direct left recursion as in your first example.
You might want to check this paper which explains it in a little bit more straight-forward way. Less theory :)