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

Question

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

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

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

Answer 1

在 Haskell 中有两种主要的解析方式，解析组合器或解析器生成器。既然你已经有了 BNF，我建议后者。

好的是alex . 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很容易阅读。