如何从Haskell中的语法规范构建抽象语法树？

Question

我正在开发一个项目,该项目涉及在一小部分Java中优化某些构造,在BNF中形式化.

如果我在Java中这样做,我会使用JTB和JavaCC的组合来构建AST.然后访客用于操纵树.但是,考虑到在Haskell中解析庞大的库(parsec,happy,alex等),我在选择合适的库时有点困惑.

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

Answer 1

在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(废弃样板),可以编写非常简洁的树遍历和修改.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很容易阅读.

Answer 2

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

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