5

我正在从事一个项目，该项目涉及在 Java 的一个非常小的子集中优化某些结构，并以 BNF 形式化。

如果我要在 Java 中执行此操作，我会使用 JTB 和 JavaCC 的组合来构建 AST。然后使用访问者来操纵树。但是，鉴于 Haskell 中有大量用于解析的库（parsec、happy、alex 等），我在选择合适的库时有点困惑。

所以，简单地说，当在 BNF 中指定一种语言时，哪个库提供了构建 AST 的最简单方法？在惯用的 Haskell 中修改这棵树的最佳方法是什么？

4

5 回答 5

7

在 Haskell 中有两种主要的解析方法，解析组合器或解析器生成器。由于您已经拥有 BNF，我建议您使用后者。

一个好人是亚历克斯。GHC 的解析器 IIRC 是使用它编写的，所以你会在好公司。

接下来，您将有一大堆数据声明来解析：

data JavaClass = {
    className :: Name,
    interfaces :: [Name],
    contents :: [ClassContents],
    ...
 }
  data ClassContents = M Method
                     | F Field
                     | IC InnerClass

以及表达式和您需要的任何其他内容。最后你会把这些组合成类似的东西

data TopLevel = JC JavaClass
              | WhateverOtherForms
              | YouWillParse

一旦你有了这个，你将把整个 AST 表示为一个TopLevel或一个列表，这取决于你解析的类/文件的数量。

从这里开始取决于你想要做什么。有许多库，例如syb(scrap your Boilerplate)，可以让您编写非常简洁的树遍历和修改。lens也是一种选择。至少签出Data.Traversable和Data.Foldable。

要修改树，你可以做一些简单的事情

ignoreInnerClasses :: JavaClass -> JavaClass
ignoreInnerContents c = c{contents = filter isClass $ contents c}
 --                           ^^^ that is called a record update
    where isClass (IC _) = True
          isClass _      = False

然后你可能会使用类似syb写的东西

 everywhere (mkT ignoreInnerClass) toplevel

这将遍历所有内容并应用于ignoreInnerClass所有内容JavaClasses。这也可以在lens许多其他库中执行，但syb非常容易阅读。

于 2013-09-10T11:49:16.067 回答
4

我从未使用过bnfc-meta（@phg 建议），但我强烈建议您查看BNFC（关于 hackage：http ://hackage.haskell.org/package/BNFC ）。基本方法是您以带注释的 BNF 样式编写语法，它会自动为语法生成 AST、解析器和漂亮的打印机。

BNFC 的适用程度取决于语法的复杂程度。如果它不是上下文无关的，那么您可能很难取得任何进展（我确实在破解上下文相关扩展方面取得了一些成功，但该代码现在可能有点腐烂了）。另一个缺点是您的 AST 将非常直接地反映语法规范。但是由于您已经有了 BNF 规范，为 BNFC 添加必要的注释应该相当简单，因此这可能是获得可用 AST 的最快方法。即使您决定走不同的路线，您也可以将生成的数据类型作为手写版本的起点。

于 2013-09-10T23:27:35.393 回答
4

亚历克斯+快乐。

有许多方法可以修改/调查已解析的术语 (AST)。要搜索的关键字是“数据类型通用”编程。但请注意：这是一个复杂的话题......

http://people.cs.uu.nl/andres/Rec/MutualRec.pdf

http://www.cs.uu.nl/wiki/GenericProgramming/Multirec

它有一个通用的拉链实现：

http://hackage.haskell.org/packages/archive/zipper/0.3/doc/html/Generics-MultiRec-Zipper.html

还结帐https://github.com/pascalh/Astview

于 2013-09-10T12:09:42.433 回答
2

由于您的语法可以用 BNF 表示，因此它属于可以使用 shift-reduce 解析器（LALR 语法）有效解析的语法。这种高效的解析器可以由解析器生成器 yacc/bison (C,C++) 或其 Haskell 等效的“Happy”生成。

这就是为什么我会在你的情况下使用“快乐”。它采用 BNF 形式的语法规则，并直接从中生成解析器。生成的解析器将接受语法规则描述的语言并生成 AST（抽象语法树）。Happy 用户指南非常好，可以让您快速入门： http ://www.haskell.org/happy/doc/html/

要转换生成的 AST，泛型编程是一个好主意。这是关于如何在 Haskell 中以实用的方式从头开始执行此操作的经典解释： http ://research.microsoft.com/en-us/um/people/simonpj/papers/hmap/

我正是使用它来为小型领域特定语言构建编译器，这是一个简单而简洁的解决方案。

于 2013-09-11T18:34:19.987 回答
2

您还可以查看 Haskell 编译器系列，它很好地介绍了使用 alex 并乐于解析 Java 的子集：http: //bjbell.wordpress.com/haskell-compiler-series/。

于 2013-09-11T00:39:26.697 回答