这个可为null的“算法”和first(在解析器中)有效吗?

为了好玩,完成这项工作: http://www.diku.dk/hjemmesider/ansatte/torbenm/Basics/

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

如果您尝试通过递归实现nullable或first,那么应该很清楚,您将在类似

N -> N a b

通过维护一组出现在产生式规则左侧的非终结符,并在我们对它们进行一次解释后忽略它们,可以递归地解决这个问题吗?

这似乎适用于nullable。首先呢?

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

在计算第一个时不能忽略非端子,除非它们可以为空。

考虑:

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

N 在里面 N a 因为 可为空。我们可以替换 N -> N a N -> a 由此推断 a first(N) .

N :

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

在里面 N->N a A. 第一(N) N

N -> M
M -> b

这告诉我们 b 在 第一(N)

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

所以这听起来可以吗?