8

我正在为语法创建一个库，它将有 2 种不同的解释：1）基于语法解析字符串 2）以语法定义的语言生成字符串。

该库使用猫将语法的 AST 创建为自由单子。然而，它似乎不是完美的选择，因为自由单子创建了一个类似于列表的 AST 表示，这对于语句列表来说非常好，但是语法远离语句列表，更接近于任意树结构。

我设法通过使用~运算符表示连接的 2 个语法来实现我的树。AST 是一个本身就是任意 AST 的语法列表。

我的问题是：在自由单子中递归 AST 子树的好方法是什么？

我当前的实现在这里：

 def parserInterpreter: GrammarA ~> ParserInterpreterState =
new (GrammarA ~> ParserInterpreterState) {
  def apply[A](fa: GrammarA[A]): ParserInterpreterState[A] =
    fa match {
      case Regx(regexp) => parseRegex(regexp)
      case Optional(b)  => parseOptional(b.foldMap(this))
      case m @ Multi(g) =>
        def x: State[String, A] =
          State.apply(state => {
            g.foldMap(this)
              .run(state)
              .map {
                case (s, ParseSuccess(_))    => x.run(s).value
                case r @ (s, ParseFailure()) => (s, ParseSuccess(s).asInstanceOf[A])
              }
              .value
          })
        x
      case Choice(a, b) =>
        State.apply(state => {
          val runA = a.foldMap(this).run(state).value
          if (runA._2.asInstanceOf[ParseResult[_]].isSuccess)
            runA
          else {
            b.foldMap(this).run(state).value
          }
        })
    }
}

特别注意，该Multi案例使用不安全递归（即不是尾递归）来递归解释子树。有一个更好的方法吗？

请点击这里查看源代码。

4

1 回答 1

1

如果您正在构建 Parser/Pretty 打印机库，那么您正在操作的对象可能不是 monad。您可能想改用InvariantMonoidalcat' （而且它是免费的，FreeInvariantMonoidal）。相关教程有一个关于编解码器的部分，您可能会觉得有趣。

于 2016-11-10T14:03:20.143 回答