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

Question

我一直在研究Haskell,我非常想在其中编写一个编译器(作为一种学习练习),因为它的许多先天特性可以很容易地应用于编译器(特别是一个递归的体面编译器).

我无法理解的是如何用Haskell-ian方式表示语言的语法.我的第一个想法是使用递归数据类型定义,但我无法看到我如何使用它们来匹配语言中的关键字("if").

非常感谢的想法和建议,

皮特

Answer 1

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

Hutton和Meijer纸是最短最简单的,但它使用monad,这对业余爱好者来说并不明显.然而,他们有一个非常好的语法和解析表达式.如果你还没有grok 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的答案中提到的技术,或使用Parsec或使用像Happy这样的解析器生成器来自己编写解析器.