构建编程语言 - 第一部分（创建 BrainLess）
4.92/5 (23投票s)
这是我们探索如何编写编译器系列文章的第一篇。
1. 引言
我将根据需要来构建这篇文章。就像我记得的“构建语言”这篇文章一样，由 Self 语言的创建者所写。我将在需要时引入术语，并尽量不进行定义，而是让术语成为结论。即使是数学，也会根据需要逐渐改变。我们不能脱离数学来理解这些事物的本质，但我会尽量不让文本充斥着奇怪的符号和虚数。我们将先构建一些东西，然后学习，最后进行形式化。编写编译器肯定比启迪一条龙要容易得多。我希望这些文章简单易懂，即使是历史专业的毕业生也能理解，但需要具备 C/C++ 的基本知识。
在本文中，我的目的是简要概述什么是语言，以及一些形式化的工具来研究语言。这些工具将使我们在编写编译器/翻译器的过程中事半功倍。
2. 什么是编程语言，它有什么用？
动物也会说话。只是我们通常无法理解。当鸟儿鸣叫时，尽管我们不理解它们的语言，但有时我们觉得它很舒缓，有时却感到烦躁。这是对某种我们未能很好遵循的协议的反应。当我们给它一个无法识别的文件格式时，它就会对我们大喊大叫，这就像这样。我先说清楚，语言为什么是对象之间的协议，而不是生物之间的？嗯，计算机确实会通信，而且它们不是生物。即使是物质也遵循某种通信协议，这就是为什么如果一个夸克反转它的自旋，另一个对应的夸克也会做同样的事情。这就是为什么当有引力拉扯时，物体会相互吸引。它们遵循某种协议，我们将其编码为“自然法则”。
现在我们将注意力转向人类交流。从文明的开端，我们就开始交流。我们使用手势，画图（书写也是一种画图），以及交谈。在所有这些方式中，我们都将一个特定的含义与一个特定的符号联系起来。当我们说话时，我们通过社会约定将一个意义或语义值与一个符号关联起来。这基本上是将意义与符号进行配对。在数学中，有一种优雅的方式来表示这些信息，即“关系”的概念。假设“S”是我们选择的所有符号的集合，而“M”是所有相关意义的集合。嗯，我想我们不能先有一个符号然后说“嘿，我想为它找个意思”，大多数情况下会是反过来的。为了表达一种意义，我们需要一个符号。所以我将通过符号 M->S 将意义映射到符号，或者仅仅是为了表示它是有序的，我们将其定义为一种关系
R: M->S
现在来说说符号；这些用来表示意义的符号是任意的。任何语法或语义规则都可以任意映射到任何符号。这只是一个普遍约定的惯例。如果你去改变符号，没有人会责怪你，但那意味着又要达成一致，这似乎是一件很无聊的事情。
2.1 什么是符号？
现在，我们来谈谈符号。符号并不意味着它只是一个字形。以英语为例。我们有一个“Alphabet”集合；我们从中创建一个新集合，称为单词。单词是由字形或符号组成的组合。我们可以将单词也看作一个非常大的符号，它是符号组的有序集合。现在我们可以说集合“S”实际上是单词的集合。其中“S”的每个符号都是由从称为“Alphabet”的集合中提取的更原始符号组合而成，简称“A”。我们再举一个例子。我们有一组 3D 对象，如螺母、螺栓、轮子等。这就是集合“A”。我们可以从这个集合中创建不太抽象或更有意义的 3D 对象，比如一个轮子，带有轮胎和内胎。这是从集合“A”中的 3D 对象组合而成的。这个集合就是“S”。但有一点是，只有从“A”中的对象进行特定组合的序列才能构成有用的东西。也许因为这是一个虚拟的 3D 环境，我们可以以某种奇怪的方式组合螺母和螺栓。但是，如果我们不从“A”中的对象制作轮子、方向盘或引擎，那么它对我们就没有用。只有这些东西可以被添加进来制造一辆合适的车辆。但是大家怎么能做出同一种轮子呢？嗯，我们需要一个蓝图。每个人都根据这个蓝图来构建这些对象，这个蓝图被称为“Grammar”。这是一组规则，每个人都需要遵循才能制造出有意义的东西。我们将这组规则称为“G”代表语法。
2.2 与计算机对话
现在让我们将注意力转向计算机的语言。编程语言甚至在计算机出现之前就存在了。这些语言曾被用来指导织布机（你看过好莱坞电影《Wanted》吗？他们会在衣服上编写代码信息）和自动演奏钢琴等机器的行为。阿拉伯人甚至制造了能够报时和播放音乐的机械表。编程语言是我们与计算机对话并指导它执行特定任务的协议。现在我们都知道计算机是一组开关，只能是“0”或“1”。所以计算机唯一能理解的语言是“0”或“1”。所以，例如，为了启动，我们需要下面的二进制位序列“0000”，然后是“1111”。但是用“0”和“1”写一些大的东西是一项艰巨的任务。它是机械的、容易出错的、重复的。我们知道计算机擅长做这样的任务。所以，如果我们能够付出一些辛勤的劳动并让计算机遵循指令，它就能让我们的生活更轻松。这时汇编语言就派上用场了。但计算机无法理解字母和单词。所以如果我写 MOV A, B, 计算机怎么会理解呢？假设我们写 ADD A, B 并将其保存在一个文件中。我们知道计算机理解二进制数。首先，我们说的计算机理解是什么意思？计算机有一个内置的解释器，那就是处理器。这里字母集是 A = {0, 1}。
我们目前知道“0000”后面跟着“1111”是一个重启指令。这是两个单词或符号。在这种情况下，每个符号由 4 个字母组成。
S = {“0000”, “1111”}
M = “0000” “1111” = reboot
现在我们应该有一套合适的规则，以便所有人都能够遵循，并且处理器能够理解每个人的语言。那么规则集是什么？
规则 G = {“S”的每个成员只能有 4 个“0”或“1”，或它们的组合；“M”的每个成员包含“S”的成员}
现在随着我们扩展 S 和 M 的集合，G 的集合也随之扩展。
回到我们保存的文件，比如 fl.txt。存储的信息是 ADD A, B。文件在二进制模式下将如下所示
“A 的二进制值” “D 的二进制值” “D 的二进制值” “空格的二进制值” “A 的二进制值” “,” 的二进制值“空格的二进制值” “B 的二进制值” “文件结束符的二进制值”
Say “Binary Value for A” = 0001
“Binary Value for D” = 0010
“Binary Value for SPACE” = 0011
“Binary Value for ,” = 0100
“Binary Value for EOF” = 0101
“Binary Value for B” = 0110
“Binary Value for ADD instruction” = “0001” “0011”
所以 ADD 指令应该看起来像 000100110110
01 代表变量/寄存器 A，10 代表 B。但相反，我们的文件看起来是
000100100010001100010100001101100101
如果我们把上面的语句输入到执行框中，它要么会报错，要么会给你一些乱码。那么我们该怎么办？我们将编写一个翻译器，它能理解这段代码并给我们 000100110110。 换句话说
R : 000100100010001100010100001101100101 -> 000100110110
所以我们并不是直接与计算机直接通信，而是与一个抽象实体通信，它为计算机翻译我们的信息。我们将这个翻译器称为“汇编器”。
3. 我们的第一门语言，BrainLess
说够了。我们也来做点实际工作。我们将创建我们的第一门语言。这是 BrainF 语言的一个变种，做了一些修改。一般来说，当我们阅读像英语这样的文本时，我们的大脑倾向于阅读“单词”而不是将单个字符分组然后形成一个单词。这就是为什么我不会用英语来写我们的第一门语言。它将是一种符号语言，这样我们就能知道我们的大脑在尝试阅读新语言时实际上做了什么。我们将在程序中生硬地应用它。下面是它的样子
3.1 BrainLess 虚拟机
想象我们有一个长度为 100 的磁带。我们可以在这个磁带机上进行操作。我们的语言将定义在这个磁带机上的操作；我们的编译器/解释器将读取指令并对这个磁带执行操作。我们有一个读写头，可以在磁带机上读写。我们有读取和写入、移动磁头的指令。如果我们想读取第 3 个槽的内容，我们首先将磁头定位在那里，然后发出读取指令。机器如图 1 所示。
我们有以下指令。
>>: 从用户那里读取一个值并存储在磁带上（C 语言中的 *p = getch()）
. : 显示磁头当前指向位置的值
! [N]: 显示从磁头当前指向的位置开始到第 N 个位置的堆栈内容。
++: 增加磁头当前指向的内容（++*p）
--: 减少磁头当前指向的内容（--*p）
+*: 取磁头当前指向的内容与下一个磁头指向的内容相加，C 语言术语是 *p = *p + *(p+1)
-* : 执行与上面相同的操作，但在此情况下是减法 *p = *p - *(p+1)
>: 将磁头增加一（p = p+1）
<: 将磁头减少一（p = p-1）
所以，让我们写一个小程序来打印“Hello World”。
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<![11]
现在让我们来解释一下。
黑色部分表示读取用户输入，红色部分表示增加磁头。
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<![11]
3.2 BrainLess 中的歧义及其解决
到目前为止都很好。但等等；我们也可以创建另一个含义，有 32 个“>”。所以它也可以表示将进度增加 32 次。现在整个意思都改变了。也可以有另一种含义，读取 16 个用户输入并存储在同一个位置。这句话是歧义的。只有当我们知道程序在做什么时，才能解释它，在这种情况下是打印 hello world。这让我们想到，尽管上面程序的语法是正确的，但含义/语义是歧义的。但你怎么告诉计算机呢？嗯，这个程序应该只告诉计算机，或者在这种情况下是我们磁带机。这类陈述被称为歧义陈述。它们出现在计算机科学、编译器、逻辑学、人工智能中。当我们继续前进时，我们会密切关注它们。现在，我们需要在我们的程序中避免它们。有很多方法，但我将使用一种简单的方法，即移动磁头一个位置，而不是使用‘>’，而是使用‘*’。这样程序就变成了
>>*>>*>>*>>*>>*>>*>>*>>*>>*>>*>><<<<<<<<<<![11]
现在假设我们想用另一种方式来做，我们将使用‘>*’来增加字符。那么程序就变成了
>>>*>>>*>>>*>>>*>>>*>>>*>>>*>>>*>>>*>>>*>><<<<<<<<<<![11]
现在让我们来解释一下这个程序。我们将只考虑一部分，即存储和增加磁头，即 >>>*
让我们按照我们的解析器将如何看待它的方式来做。我们将一个一个地读取字符
解析器首先看到的字符是‘>’。看到这个之后，我们有两个选择
- ‘>’后面可以跟另一个‘>’，在这种情况下，它将是从用户那里读取并存储的操作。
- ‘>’后面可以跟一个‘*’，在这种情况下，它将是增加磁头。
好吧，现在我们也有歧义了。去哪里？我们将根据下一个字符来决定。所以为了解释‘>’的含义，我们需要‘向前看’。让我们向前看一个字符，即‘*’。现在我们有了清晰的含义，“>*”。所以仅仅向前看一个字符就可以帮助我们解决歧义。这就是它的发生方式，从程序文件中读取字符，我们将从左边读取，然后向前看一个字符，即从左边，向前看 1 个字符。简而言之，这可以表示为 LL(1)。我们将更多地了解 LL 类，其中可以有“k”个字符向前看，表示为 LL(k)。
3.3 改进的 BrainLess
改进后的语言现在具有以下指令。
>>: 从用户那里读取一个值并存储在磁带上（C 语言中的 *p = getch()）
. : 显示磁头当前指向位置的值
! [N]: 显示从磁头当前指向的位置开始到第 N 个位置的堆栈内容。
++: 增加磁头当前指向的内容（++*p）
--: 减少磁头当前指向的内容（--*p）
+*: 将磁头当前指向的内容与下一个磁头指向的内容相加，C 语言术语是 *p = *p + *(p+1)
-* : 执行与上面相同的操作，但在此情况下是减法 *p = *p - *(p+1)
*: 将磁头增加一（p = p+1）
<: 将磁头减少一（p = p-1）
只是为了好玩，让我们看看二进制文件看起来是什么样的；如图 2 所示。
编写解析器时，我们将以二进制模式读取。
4. 形式化工具和模型来帮助我们
为了让我们的任务更容易，我们也将借助一些工具。这些被称为形式化方法，你可以随意称呼它们。在此之前，我将给出一些定义。让我们回到设想自己是解析器的地方。让我一个一个地给出一组随机字符。第一个字符是‘>’。当我们收到这个字符时，我们想到什么？好的，现在我们可能有一个‘>’，或者一个‘*’。这是我们当前的思维状态，我们正在等待更多字符，我们的思维是不确定的。我们将用圆圈来表示这些状态。当我们处于某个状态时，我们正在等待输入。根据这个输入，我们将转换到另一个思维状态。例如，如果我们得到一个‘*’，我们的思维就会确定它是一个磁头增加操作。输入将通过箭头给出。箭头的方向将告诉我们从什么状态转换到什么状态，箭头上的标签将告诉我们基于什么符号。我们以识别‘>*’为例。我们将为此目的构建一个抽象机器。在我们不向这台机器输入任何字符时，它将停留在不知道会发生什么的状态。这就是“开始”状态。请参见图 3。
如您所见，“开始”状态是“q0”。符号“>”将从“q0”转换到“q1”。当我们处于“q1”状态并得到“>”或“*”时，我们就将其识别为存储或移动磁头语句之一。因此，我们进入一个识别状态，该状态标志着识别特定标记的最终状态。这个最终状态由两个同心圆标记。这里的箭头标记使状态之间发生转换的条件。当我们处于“q0”状态时，只要我们得到“>”作为下一个字符，就会有向“q1”状态的转换。这就像化学反应，分子最初处于“q0”状态，“>”可以看作是提高温度。然后才会有向“q1”的转换。但是，在化学反应中，向另一种状态的转换可能取决于许多其他状态，例如引入化学物质“x”。我们该如何标记呢？它将像图 4 一样。
这里的黑色矩形表示，只有在满足两个条件的情况下，它才允许转换到“p1”状态。幸运的是，一开始我们只考虑一个条件。其他类型的多条件称为“Petri 网”。单条件转换称为“有限自动机”。这里所有的矩形/圆圈都称为“节点”，箭头称为“弧”。那么，节点和箭头的组合就是我们所说的“图”，或者更具体地说，是有向图。所以图是帮助我们研究语言的工具。这些自动机有很多属性，我们将在单独的线程中讨论它们。
这些标记中的每一个都可以由有限自动机识别。如果字符串为空后，有限自动机的状态不是最终状态，那么就存在错误。但这些只告诉我们如何识别标记。它们不给我们标记的含义，它们只是通过模拟其状态来告诉我们某个 字符串 是否满足某种结构。下面几张图给出了一些自动化。这绝不是一个完整的自动化。如果你愿意，可以完成完整的并寄给我。我会将其发布在此页面上，并在下面加上你的名字。
5. Brainless 解释器代码和示例
首先，我们将创建一个简单的解释器来解释我们简单的语言。我已将 BrainLess 简单语言的源代码附加在这篇文章中。在下一篇文章中，我们将增强语言/编译器。我创建了一个使用 Visual Studio C++ 2008 express edition 的解决方案。打开解决方案文件并进行编译。它将创建一个名为 BrainLess.exe 的可执行文件。您可以进入命令提示符，然后键入 BrainLess <文件名>。
我已将示例脚本文件“m.bl”与代码一起提供。我在源代码中添加了注释，以便于理解。
6. 下一篇文章有什么内容？
在下一篇文章中，我们将对 BrainLess 进行更多改进。我计划的改进是
- 为 BrainLess 添加函数
- 添加循环
- 添加条件语句
如果读者想要任何其他改进，他们可以提出来。我将尝试看看是否可以做到。
7. 结论
请提供您对本文的评论和反馈，并帮助我改进其他文章。您可以随意使用源代码，但如果您分发它，请不要忘记提及版权声明。我对这个语言的改进有一些想法，请告诉我您还想在这个语言中添加哪些功能。但有一点是，这个语言的目的是非常简单的，所以功能也应该是简单的。
8. 背景
网上关于语言的资料非常多，为什么还要写一篇文章？嗯，从逻辑上来说，假设有 N 本关于语言的书，为什么还要有第 N+1 本书呢？这意味着不同的书对语言有不同的看法，有些容易理解，有些则很枯燥。它们为不同人群提供了不同的视角。但我学习的视角略有不同。前段时间我给一位教授写了一封信，他给了我一个绝佳的建议：“如果你觉得你喜欢某样东西，就试着去教它，去实现它，并试着去写关于它的东西。这会增加你对它的了解，并且你发现的学习中的缺陷越多，你的知识就越完善。所以我想写几篇关于它的文章，并加以实现，所以它就诞生了。”
9. 历史
- BrainLess 诞生。版本 0.1
更新
我已将代码迁移到 Google Code。进一步的更新将在 http://code.google.com/p/brainless-labs/ 提供。