parsing - 带有 epsilon 转换的简单 CFG 解析器

Question

我偶然发现了许多不同的算法（CYK 和 Earley）来检查字符串是否是提供 CFG 的 CFL 的一部分。我正在寻找一些易于理解和实施的东西。我需要知道的是字符串是否在 CFG 中。CFG 通常以以下形式给出

S->S1 S2
S1->S1 a | a
S2->S2 b | b

该解决方案也应该接受 epsilon 转换，例如 S1-> a | e

有任何想法吗？

Answer 1

我在这个项目上找到了一种非常直接的方法

https://code.google.com/p/cykparser/downloads/list

与其他经过不​​必要的语法验证的 CYK 解析器不同。这个解析器是一个非常好的概念证明，它只是用基本语法实现了 CYK 算法。

代码在python中。