递归下降解析器和函数式编程

所以最近我一直致力于编写一个简单的编译器，以更好地理解编译器概念。作为 stackoverflow 的忠实读者，似乎有一个共识：用函数式语言编写编译器比命令式语言更容易。为此，我想尝试一下杀两只鸟，用 F# 编写一个编译器，既学习函数式语言，又同时编写编译器。

我一直在阅读龙书，并决定从用 F# 手工编写的递归下降解析器开始。然而，龙书几乎所有的代码示例都是命令式的。例如，匹配令牌函数的大部分工作都是通过副作用完成的。

所以我的问题是，更传统的函数式解析方法（即很少的副作用）会是什么样子？我知道 Haskell 编译器（GHC）是用 Haskell 编写的，但我希望有一个更小、更容易理解的代码示例。

其次，是否值得尝试采用函数式方法进行解析，或者函数式语言真正在中间代码的优化方面表现出色，而我只是还没有做到这一点？也就是说，我是否应该使用命令式风格来进行 F# 中的解析，然后再切换到更实用的方法？

答案源自这篇博客文章 http://fsharpnews.blogspot.com/2010/12/parsing-mathematical-expressions-using.html:

所以我的问题是，更传统的函数式解析方法（即很少的副作用）会是什么样子？

听起来你需要将功能性（如 Lisp、Scheme、Standard ML、CAML、OCaml、F#）与纯粹性（无副作用，如 Haskell）和附带语言功能（代数数据类型、模式匹配）分开。

得益于代数数据类型、模式匹配和高阶函数，F# 非常适合解析，也非常适合转换和代码生成，但大多数用 F# 编写的生产解析器都不是纯粹的。从历史上看，F# 的语言家族（元语言或 ML）主要源自专门为这种元编程而培育的语言。

这是一组非常简单的相互递归活动模式，用于解析和评估由单个数字组成的数学表达式，+ - *运算符和括号子表达式：

> let rec (|Term|_|) = function
    | Factor(e1, t) ->
        let rec aux e1 = function
          | '+'::Factor(e2, t) -> aux (e1 + e2) t
          | '-'::Factor(e2, t) -> aux (e1 - e2) t
          | t -> Some(e1, t)
        aux e1 t
    | _ -> None
  and (|Factor|_|) = function
    | '-'::Factor(e, t) -> Some(-e, t)
    | Atom(e1, '*'::Factor(e2, t)) -> Some(e1 * e2, t)
    | Atom(e, t) -> Some(e, t)
    | _ -> None
  and (|Atom|_|) = function
    | c::t when '0'<=c && c<='9' -> Some(int(string c), t)
    | '('::Term(e, ')'::t) -> Some(e, t)
    | _ -> None;;
val ( |Term|_| ) : char list -> (int * char list) option
val ( |Factor|_| ) : char list -> (int * char list) option
val ( |Atom|_| ) : char list -> (int * char list) option

这是一个用于解析和评估表达式的示例：

> let (Term e) = List.ofSeq "1+2*(3-4)*-5";;
val e : int * char list = (11, [])

这是一个纯粹的解决方案，使用 F# 的活动模式对列表进行模式匹配。实际上，您需要为抽象语法树定义一个类型并返回该类型的值。这在 F# 中非常简单：

type expr =
  | Int of int
  | Neg of expr
  | Add of expr * expr
  | Sub of expr * expr
  | Mul of expr * expr

  static member (~-) f = Neg f
  static member (+) (f, g) = Add(f, g)
  static member (-) (f, g) = Sub(f, g)
  static member (*) (f, g) = Mul(f, g)

let rec (|Term|_|) = function
  | Factor(e1, t) ->
      let rec aux e1 = function
        | '+'::Factor(e2, t) -> aux (e1 + e2) t
        | '-'::Factor(e2, t) -> aux (e1 - e2) t
        | t -> Some(e1, t)
      aux e1 t
  | _ -> None
and (|Factor|_|) = function
  | '-'::Factor(e, t) -> Some(-e, t)
  | Atom(e1, '*'::Factor(e2, t)) -> Some(e1 * e2, t)
  | Atom(e, t) -> Some(e, t)
  | _ -> None
and (|Atom|_|) = function
  | c::t when '0'<=c && c<='9' -> Some(Int(int(string c)), t)
  | '('::Term(e, ')'::t) -> Some(e, t)
  | _ -> None

let (Term e) = List.ofSeq "1+2*(3-4)*-5"

请注意，只需要对解析器进行一项微小的更改，因为 AST 也可以使用+, - and *运营商。

其次，是否值得尝试采用函数式方法进行解析，或者函数式语言真正在中间代码的优化方面表现出色，而我只是还没有做到这一点？

你说的是纯粹性，而不是函数式编程。纯度在解析文本的上下文中并不是特别有用，事实上，它可能是一个真正的障碍（例如，实习符号在 Haskell 中是一场噩梦）。然而，F# 还有许多其他优点可以很好地解决这组问题。特别是，尽管 OCaml 等其他语言有更好的解析工具，但我认为 F# 是在这种情况下最好的 .NET 语言。

也就是说，我是否应该使用命令式风格来进行 F# 中的解析，然后再切换到更实用的方法？

完全取决于你想要实现什么功能。我会使用 fslex 和 fsyacc 以及纯代码来在操作中构造 AST，但会使用哈希 consing 或生成唯一 ID 之类的杂质。

您可能会欣赏我在以下位置撰写的有关此主题的文章：这个博客 http://fsharpnews.blogspot.com（注意付费墙）：

• “使用 Lex 和 Yacc 解析文本”（2007 年 9 月 30 日）。
• “优化简单的字节码解释器”（2007 年 10 月 31 日）。
• “解析器组合器”（2007 年 11 月 30 日）。
• “面向语言的编程：术语级解释器”（2007 年 12 月 31 日）。
• “面向语言的编程：术语重写”（2008 年 8 月 16 日）。
• “运行时代码生成使用System.Reflection.Emit”（2008 年 8 月 31 日）。
• “解析和可视化二进制地理信息系统数据”（2009 年 11 月 30 日）。