从BNF语法生成Scala代码的词法分析器/解析器

Question

我目前正在寻找一个词法分析器/语法分析器，可以从BNF文法(带有优先级和结合性的ocamlyacc文件)生成Scala代码。但是我很困惑，因为我几乎找不到关于如何做到这一点的任何资料。

对于语法分析，我找到了scala-bison（但是我使用起来遇到了很多问题）。所有其他工具都只是导入到Scala中的Java解析器（例如ANTLR）。

对于词法分析，我什么也没找到。

我还发现了Scala的著名的“parser combinators”（语法分析组合器），但是（如果我错了，请纠正我），即使它们非常吸引人，由于回溯，它们会消耗大量时间和内存。

所以我有两个主要问题：

• 为什么人们似乎只专注于“parser combinators”？
• 您最好的词法/语法分析生成器建议是什么？

- Vinz

Answer 1

作为ScalaBison论文的作者之一，我已经遇到过这个问题几次。 :-) 在Scala中，我通常会使用JFlex进行扫描。它与ScalaBison配合得非常好，我们所有的基准测试都是使用这种组合完成的。不幸的是，它确实会生成Java源代码，因此编译需要进行一些操作。我相信论文的主要作者John Boyland已经开发了JFlex的Scala输出模式，但我认为它还没有公开发布。

对于我的开发，我一直在研究无扫描器的解析技术。Scala 2.8的packrat parser combinators非常好，但仍然没有被广泛应用。我建立了一个实验性库，它在解析器组合框架内实现了通用解析。其渐进界限比传统的解析器组合器要好得多，但在实践中，常数时间开销更高（我仍在努力）。

- Daniel Spiewak

---

谢谢你的回答和gll组合器，我会尝试理解它是如何工作的 :) 但我想我会尝试将JFlex和Scala一起使用。 - Vinz

多谢您的许多教程（包括您在CodeCommit上的一些）帮助，我终于用解析器组合子做出了一个简单的词法分析器/语法分析器，并且避免了过多的递归......再次感谢！ - Vinz

Answer 2

Scala 2.8具有Packrat解析器。我在这里引用API文档的原话：

Packrat Parsing是一种实现回溯、递归下降解析器的技术，其优势在于它保证了无限向前看和线性解析时间。使用此技术，还可以接受左递归语法。

- Daniel C. Sobral

Answer 3

我知道这个问题很老，但是对于那些仍在寻找可以输出Scala代码的词法分析器生成器的人，我已经写了一个发射Scala而不是Java的JFlex的分支，包括相应的Maven和sbt插件。现在所有这些都可以在Maven Central上获得。

我们目前正在使用它（包括Maven/sbt插件）来标记英文文本，作为FACTORIE自然语言处理pipline的一部分--包含Scala 示例.flex文件的此处。

- Emma Strubell

---

太好了。我已经发布了JFlex 1.5 + scale https://github.com/moy/JFlex/releases，但是看起来你的版本更加更新，而且更容易找到。 - John Tang Boyland

@JohnTangBoyland，要是我在写之前发现了你的版本就好了！ - Emma Strubell