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

Question

所以最近我一直致力于编写一个简单的编译器来更好地理解编译器的概念。作为 stackoverflow 的勤奋读者，似乎有一个共识，即用函数式语言编写编译器比使用命令式语言更容易。为此，我想我会尝试杀死两只鸟并用 F# 编写一个编译器，以便同时学习函数式语言和编写编译器。

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

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

其次，是否值得尝试采用函数式方法进行解析，或者它真的是对中间代码的优化，使函数式语言大放异彩，而我还没有到达那里？也就是说，我是否应该使用命令式风格在 F# 中进行解析，然后切换到更实用的方法？

Answer 1

来自 this blog article 的答案:

So my question is what would a more traditional functional approach to parsing (i.e. few side effects) look like?

听起来您需要将功能性(如 Lisp、Scheme、Standard ML、CAML、OCaml、F#)与纯度(没有副作用，如 Haskell)和附带的语言特性(代数数据类型、模式匹配)分开。

由于代数数据类型、模式匹配和高阶函数，F# 非常适合解析，非常适合转换和代码生成，但大多数用 F# 编写的生产解析器并不纯。从历史上看，F# 主要源自(MetaLanguages，或 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 也可以使用 + 构建。 , -和 *运营商。

Second, is it worthwhile to try and adopt a functional approach to parsing, or is it really on optimizations to intermediate code that functional languages shine and I just haven't gotten there yet?

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

That is, should I fuddle through the parsing in F# using an imperative style and switch to a more functional approach later on?

完全取决于你想让什么功能。我会使用带有纯代码的 fslex 和 fsyacc 来在操作中构建 AST，但会使用诸如散列 consing 或生成唯一 ID 之类的杂质。

您可能会喜欢我在 this blog 上写的关于这个主题的以下文章(注意付费专区):

“使用 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 日)。