compiler-construction - Haskell - 如何最好地表示编程语言的语法？

Question

我一直在研究 Haskell，我很想在其中编写一个编译器（作为学习练习），因为它的许多固有特性可以很容易地应用于编译器（尤其是递归下降编译器）。

我无法完全理解的是如何以 Haskell-ian 方式表示语言的语法。我的第一个想法是使用递归数据类型定义，但我看不出如何使用它们来匹配语言中的关键字（“if”）。

非常感谢您的想法和建议，

皮特

Answer 1

您使用相互递归的代数数据类型来表示程序，并使用解析组合器来解析程序。有一百万种口味；你会在 2009 年 3 月 23 日星期一的课程表上找到三篇有用的教程论文。它们是

• Graham Hutton 和 Erik Meijer，Functional Pearl：Haskell 中的一元解析(1998)
• Graham Hutton，用于解析的高阶函数(1992)
• Jeroen Fokker，函数式解析器(1995)

Hutton 和 Meijer 论文是最短和最简单的，但它使用单子，这对业余爱好者来说并不明显。但是，它们具有非常好的表达式语法和解析器。如果你还没有 grok monads，Fokker 的教程就是其中之一。

Answer 2

递归数据类型对此很好。例如，给定语言：

expr ::= var
      |  "true"
      |  "false"
      |  "if" expr "then" expr "else" expr
      |  "(" expr ")"

这种语言的一个示例表达式是：

if true then x else (if false then y else true)

您的 Haskell 数据类型如下所示：

data Expr = Var String
          | Lit Bool
          | If Expr Expr Expr

然后，您的解析器会负责翻译，例如xintoVar "x"和trueintoLit True等。即：

parse "if x then false else true" 
  ==  If (Var "x") (Lit False) (Lit True)

对于编写解析器，您可以使用 Norman 的回答中提到的技术，或者使用Parsec或使用像Happy这样的解析器生成器来自己编写解析器。

Answer 3

也许你可以看看一些现实世界的项目，看看他们是如何做到的？

不到一周前，Language-Python项目在Haskell-Cafe 邮件列表上公布。它是在 Haskell 中实现的Python解析器，使用Happy解析器生成器和Alex词法分析器生成器。

当然，还有Pugs，它是在 Haskell 中的Perl 6实现（Perl 6的第一个实现，它符合 Perl 6 规范的重要子集）。

Answer 4

从您的问题的语气中我无法判断这是您第一次尝试编写编译器，还是您以前编写过编译器并正在寻找特定于 Haskell 的建议。如果您已经是编译器专家，那么我提供的任何小建议都无济于事。:)

编程语言语法通常以BNF 形式表示，可供 Yacc 或 Bison 等工具用于解析源代码。我不知道这是否算作 Haskell 式的做法，但这是我听说过的唯一方法。通过一些挖掘，您可能会挖掘出一个从 BNF 语法生成 Haskell 代码的工具；我发现这个声称能够做到这一点的工具。

快速的谷歌搜索发现了Haskell 的 BNF 语法，可能还有其他的，以防你想为 Haskell 编写一个编译器（也许你想用 Haskell 编写一个 Haskell 编译器？） C 和 BNF 语法Java似乎很流行。

最后，如果你正在寻找一本关于编译器设计的书，经典的文本是“The Dragon Book”。

Answer 5

不幸的是， ANTLR没有 Haskell 语法，但也许您可以使用上面引用的链接来创建一个。ANTLR 是一个很棒的基于 Java 的解析器生成器。

如果您需要更多动力，Steve Yegge 有一个关于编写编译器的不错的博客。这很有趣。