Haskell - 如何最佳地表示编程语言的语法？

Question

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

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

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

- Peter

---

凭借我所知，我建议查看http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours（它使用Parsec等），但我不会将其作为答案留下，因为这可能是一个可怕的答案。希望更专业的人会回答（然后我会删除此评论）。 - ShreevatsaR

Answer 1

您使用相互递归的代数数据类型来表示程序，为了解析程序，您使用解析组合器。有无数种风格; 您将在2009年3月23日星期一的我的课程日程安排上找到三篇有用的教程论文。它们是

• Graham Hutton和Erik Meijer，《Functional Pearl：Haskell中的单子解析》（1998）
• Graham Hutton，《Higher-order Functions for Parsing》（1992）
• Jeroen Fokker，《Functional Parsers》（1995）

Hutton和Meijer的论文是最短和最简单的，但它使用单子，这对业余爱好者来说并不明显。然而，他们有一个非常好的表达式语法和解析器。如果您还没有理解单子，请参考Fokker的教程。

- Norman Ramsey

---

太棒了..这些链接。你是这里的编程语言大师。谢谢。 - Surya

具有讽刺意味的是，我认为学习解析器组合子是理解单子的最佳方式。 - Zifre

解析器组合子的问题在于它们通常不支持左递归语法... - Callum Rogers

@CallumRogers 同样适用于手写递归下降解析器。Niklaus Wirth 多年前就指出了正确的方向：不要使用左递归，而是使用序列。 - Norman Ramsey

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

你的解析器需要将例如 x 转换为 Var "x"，将 true 转换为 Lit True，等等。即：

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

如果要编写解析器，你可以使用Norman答案中提到的技术自己制作，或者使用Parsec或者像Happy这样的解析器生成器。

- nominolo

Answer 3

也许你可以看一些实际项目来了解它们是如何做到的？

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

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

- Jörg W Mittag

Answer 4

从你的问题语气中我无法判断这是你第一次尝试编写编译器，还是你已经写过编译器并正在寻求特定于Haskell的建议。如果你已经是编译器大师，那么我所能提供的建议微不足道。 :)

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

一个快速的谷歌搜索可以找到Haskell的BNF语法，也许还有其他的语法，如果你想要写一个Haskell编译器的话（也许你想用Haskell写一个Haskell编译器？） C和Java的BNF语法似乎很受欢迎。

最后，如果你正在寻找一本关于编译器设计的书，经典的著作是“龙书”。

- Parappa

---

《龙书》确实是一部经典之作，但我听说当前编译器实现的思路已经超越了它（例如JIT运行时优化等）。我自己并不是权威，只不过是一个毫无顾忌的暗示传递者。8) - duffymo

感谢您的回复，我正在寻求更具体于Haskell的建议，并且我不想使用工具（我正在努力学习而不是让工具代替我的一切 :)）。 - Peter

在Haskell中编写编译器与在命令式语言中编写编译器相比，是一种非常不同（也更愉快）的练习。[而@duffymo：'暗示'可能不是你认为的意思：)] - ShreevatsaR

Answer 5

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

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

- duffymo