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

Question

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

我不太明白的是如何以 Haskell 式的方式表示语言的语法。 我的第一个想法是使用递归数据类型定义，但我不知道如何使用它们来匹配语言中的关键字（“if”）。

非常感谢

皮特的想法和建议

Answer 1

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

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

Hutton 和 Meijer 论文是最短、最简单的，但它使用了单子，这对于业余爱好者来说并不明显。 然而，他们有一个非常好的表达式语法和解析器。 如果您还没有了解 monad，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

然后，您的解析器会注意将例如 x 翻译为 Var " x”，和 true 到 Lit True 等。即：

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

为了编写解析器，您可以使用 Norman 的答案中提到的技术或使用 < a href="http://legacy.cs.uu.nl/daan/parsec.html" rel="noreferrer">Parsec 或使用解析器生成器，例如 快乐。

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 代码的工具； 我发现这个工具声称能够做到那。

通过 Google 快速搜索，找到了这个 Haskell 的 BNF 语法，并且如果您想为 Haskell 编写一个编译器（也许您想在 Haskell 中编写一个 Haskell 编译器？），那么可能还有其他的编译器。C 和 Java 的 BNF 语法似乎很流行。

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

Answer 5

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

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