使用Haskell定义编程语言

Question

我试图搜索关于使用Haskell定义简单语言的简单示例，但没有成功。

我在stackoverflow上找到了一篇类似的帖子，但当我实现它时，它似乎不起作用：

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

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

if true then x else (if false then y else true) 你的Haskell数据类型看起来像这样：

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

然而，当我将“if true then x else (if false then y else true)”输入控制台作为输入时，它抱怨无法解释“x”。它也不喜欢“true”和“false”。

编辑：最后我确实得出了“show”。

- user997112

---

使用变量x来引导lead；true和false应该是True和False。 - manuzhang

如果你将搜索范围扩大到 ML 和 OCaml，可能会有更好的运气。 - hugomg

Answer 1

创建编程语言的常见步骤有几个(当然还有其他步骤):

• 将程序文本解析成语法树
• 遍历语法树，执行某些操作（解释、编译、收集统计信息）

你所展示的 data Expr 是语法树的一部分。而 if true then ... 则是程序文本。你需要一种方法将文本转换为语法树：你需要一个解析器。

或者，你可以使用 Haskell 作为解析器，并将语法树编写为 Haskell 代码:

If True "it's true!" (If False "uh-oh" "it's false")

- Matt Fenwick

---

好的，让我们简单明了一点。如果我的编程语言是这样的：单词“desk”必须始终跟在单词“chair”后面，因此“chair desk”应该被允许，但“desk chair”不应该被允许。我该如何在Haskell中声明它？ - user997112

首先，您需要一个解析器，它只能在输入字符串“chair desk”上成功，并对所有其他输入失败。然后，您需要一个Haskell数据类型，类似于：data SimpleTree = DeskChair。解析器将在成功时返回DeskChair。 - Matt Fenwick

Answer 2

Parsec具有广泛的面向编程语言的工具，这是一个很好的起点。

你需要理解两个概念之间的区别，这可能需要一些时间：

• 作为文件保存的文本形式的编程语言。

• 该语言在Haskell中的表示形式。

这就是为什么你需要Lit True而不仅仅是true。 true是你的编程语言中的文本，Lit True是Haskell表示。将两者联系起来是解析器的作用。

回答你在评论中提出的另一个问题，“chair desk”问题的基本解决方案如下：

import Text.Parsec

data ProgrammableFurniture = ChairDesk 
                           | CouchCoffeeTable

--a parser for the text "chair desk"
chairDesk = do string "chair"
               char ' '
               string "desk" <?> "Chair must be followed by desk!"
               return ChairDesk

- Zopa

Answer 3

如果您想在您的小语言中表示if true then x else (if false then y else true)，您需要使用以下表达式：

If (Lit True) (Var "x") (If (Lit False) (Var "y") (Lit True))

如果你说的没错，那么Show将按输入的方式准确显示。

我不确定你想做什么！可能需要尝试的进一步操作包括：

- 编写评估函数。 - 编写自己的Show实例以使打印的表示更加美观。 - 为这个小语言编写解析器。

- yatima2975

---

嗨，我基本上想创建一组规则，以便我可以定义一种基本的编程语言。 - user997112

但是问题是，你肯定会解析一个实际编程语言的文本文件，所以你不需要 Lit True 吧？如果这是一个用 Haskell 编写的 Java 编译器，.java 文件中不会包含 Lit True，它只会写 True（甚至是 'true'）吧？ - user997112

Answer 4

与yatima2975的答案类似，您可以简单地派生Read。

data Expr = Var String
          | Lit Bool
          | If Expr Expr Expr
          deriving (Read, Show)

然后，如果您使用与yatima所示相同格式的字符串对read函数进行操作，它可以生成一个Expr对象。请注意，我必须转义内部字符串周围的"。

ghci> read "If (Lit True) (Var \"x\") (If (Lit False) (Var \"y\") (Lit True))" :: Expr
If (Lit True) (Var "x") (If (Lit False) (Var "y") (Lit True))

这比定义自己的Read实例更简单，但你也可以这样做。

- Dan Burton

Answer 5

很遗憾，语言语法和解析并不能定义一个编程语言。定义语言的语义是最重要的部分，如果定义得好（根据语言实现的符合性问题必须这样做），可以通过解释器或编译器来改善实现。

虽然Haskell是一种纯函数式语言，但是有人批评它的惰性求值会导致关于其性能的推理问题。

关于Haskell是否适合您的意图（一种简单的语言）-也许更重要的是首先界定您的意图，然后尝试验证Haskell或其他语言是否符合您的标准，作为定义编程语言的最佳候选语言。

在此过程中，您可能需要查看Dana Scott的指称语义，并查看Lambda演算作为定义编程语言的潜在语言（如果您有兴趣）。即使是简单的语言，为了有用，也应该在语义上定义清楚。

- Tom

---

我基本上理解为：“初学者程序员，你需要学习数学，然后发表论文，才能拥有一门编程语言，并且不要用你正在使用的语言进行。” - luqui

Answer 6

语言的设计和实现

W.Pratt是一本不错的书，读完后最好再读一下aho编译器的书。

但是在这之后，你需要一些编译器算法和一些应该遵循的原则。

例如，你应该编写一个扫描器，用于检查变量名称中的错误。

例如，C++扫描器将在以下代码中找到错误：

int 32xy=0;

因为C++变量不能以数字开头。

到目前为止，扫描器有一个保存错误的符号表。现在，扫描器将把符号表发送给解析器。

现在我们将编写一个解析器。

请注意，我的答案是无处不在的。

- S.A.Parkhid

---

这看起来严重像是从某个地方剪切和粘贴的一堆注释，甚至与Haskell毫不相关... - alternative

到目前为止，扫描器具有保存错误的符号表。现在，扫描器将发送符号表给解析器。 - alternative