4

我目前正在使用 BNF 语法，我希望能够将其转换为 LL(1) 形式。但是，我今天第三次手动完成了更改并为语法计算了新的 FIRST 和 FOLLOW 集，我已经厌倦了。一定有更好的方法！

有人可以建议一个工具，给定一个语法，自动计算所有非终端的第一个和后续集吗？

4

3 回答 3

3

一年前，我们在我就读的大学有一个学期项目，我们的任务是创建一种编程语言。作为一个团队，我们决定希望能够从头开始手写解析器，因此我们必须以 LL(1) 语法为目标，否则编写解析器是完全不现实的。

当然，我们的出发点远不是 LL(1)，所以我们也不得不把它弄到位。为此，我们使用了AtoCC包中的 kfgEdit 工具。您所要做的就是输入您的规则，然后单击按钮即可检查它是否为 LL(1) 语法。

一个公平的警告：该工具对它接受的内容有点挑剔。虽然您经常将 EBNF 用于真正的语法，但您可以编写 ? 和 * 和 + 表示该令牌必须在那里出现多少次，这是不受支持的。也不支持分组。您可能会发现这样做需要很长时间，并且您几乎肯定会在达到 LL(1) 后进行一些“重新排列”以使语法更接近可读。

当然，根据您处理的语法类型，这对您来说可能不是什么大问题。我们创建了一种 Pascal/C 混合体，具有一组相当有限的构造（过程、函数、只有内置的原始类型和它们的数组、ifs、我们自己想出的单个循环构造来代替标准的 3...)，我至少花了一周的时间才把它变成 LL(1) 语法——实际上可能是 2。请注意，这是总共大约 4 个月的时间，所以在那里花了很多时间。

如果你绝对必须有一个 LL(1) 语法，那么如果你遇到这样的情况，你显然需要继续前进，但是如果你被允许使用像 yacc/bison 或 SableCC 这样的解析器生成器，那么你会，在从长远来看，很可能会发现沿着这条路线走要容易得多。这并不意味着你应该走那条路——我发现实际上手写所有内容提供了一些我可能不会获得的洞察力——但在与当前情况不同的情况下获得这种洞察力可能会更好.

tl;dr 版本：使用 AtoCC 包中的kfgEdit。

于 2010-02-14T02:13:00.597 回答
0

对于递归下降解析，值得一看ANTLR。但是，我不确定它是否为您的问题提供了准确的答案 - 找到给定语法的 FIRST 和 FOLLOW 集。

于 2010-02-14T02:32:56.830 回答
0

DMS Software Reengineering Toolkit有一个解析器生成器，可以计算 FIRST 和 FOLLOW 集；它还可以让您检查它生成的 L(AL)R 状态机。

然而，如果你有一个合法的上下文无关文法，你就不必将它“纠缠”成 LL 形状；DMS 解析器生成器从任何上下文无关文法生成 GLR 解析器。

于 2010-10-15T20:35:21.867 回答