如何创建自己的编程语言：从零开始编写一门简单的编程语言 - 第一部分
由 Mux 主办的 DEV 全球展示挑战赛：展示你的项目！
如果你是一名开发者，你肯定用过编程语言。它们是让计算机按照你的意愿运行的绝佳工具。或许你甚至深入钻研过汇编语言或机器代码。很多人从此就不想再碰它们了。但有些人却好奇：我该如何通过编写更多底层代码来“折磨”自己呢？我想了解更多关于编程语言是如何诞生的！玩笑归玩笑，编写一门新语言并没有想象中那么可怕，所以如果你哪怕只有一点点好奇心，我建议你留下来看看究竟是怎么回事。
这篇文章旨在简要介绍如何创建编程语言，以及如何创建你自己的专属语言。甚至可以用你的名字命名它。谁知道呢。
我也猜想，这看起来确实是一项艰巨的任务。别担心，我已经考虑到了这一点。我尽力用相对简单的语言解释所有内容，避免过多跑题。读完这篇文章，你将能够创建自己的编程语言（会分几个部分），但这还不是全部。了解底层原理能让你更好地进行调试。你会更深入地理解新的编程语言，以及它们做出各种决策的原因。如果我之前没提到的话，你甚至可以拥有一门以你的名字命名的编程语言。而且，这真的很有趣。至少对我来说是这样。
编译器和解释器
编程语言通常是高级语言。也就是说，你不需要直接查看 0 和 1，也不需要查看寄存器和汇编代码。但是，你的计算机只能理解 0 和 1，所以它需要一种方法，将你易于阅读的代码转换成机器易于阅读的代码。这种转换可以通过编译或解释来实现。
编译是将源语言的整个源文件转换成目标语言的过程。就我们的目的而言，我们将考虑如何从你最新开发的语言编译成可运行的机器代码。
我的目标是让“魔法”消失。
解释执行是指直接或间接地执行源文件中的代码。至于这其中的奥妙，就留给你们自己去体会吧。
那么，如何从易于阅读的源语言过渡到难以理解的目标语言呢？
编译器的各个阶段
编译器可以按多种方式划分阶段，但最常见的方式是这样的：第一次看到这种方式时可能不太容易理解，但还是简单介绍一下：
哎呀，我选错图了，不过这个也行。简单来说，就是先拿到源文件，把它转换成电脑能识别的格式（比如去掉空格之类的），再转换成电脑能流畅运行的格式，最后根据这个格式生成代码。当然还有更多细节，以后有机会再讲，或者如果你实在好奇的话，可以自己去研究。
词汇分析
又称“美化源代码”
请看下面这种完全虚构的语言，它本质上就是一个带有分号的计算器：
r
// source.ect
3 + 3.2;
5.0 / 1.9;
6 * 2;
计算机不需要那么多东西。空格只是我们这些心胸狭隘的人才会用的。换行符？根本没人需要。计算机会将你看到的这段代码转换成一系列标记，用来代替源文件。基本上，它知道 `i`3是一个整数，3.2`f` 是一个浮点数，以及+一个对这两个值进行运算的函数。这就是计算机运行所需的全部信息。词法分析器的工作就是提供这些标记，而不是源程序。
它的工作原理其实很简单：给词法分析器（一种听起来不那么高深的说法）一些预期的内容，然后告诉它遇到这些内容时该怎么做。这些内容被称为规则。举个例子：
cpp
int cout << "I see an integer!" << endl;
当词法分析器处理一个整数时，如果执行了这条规则，你会看到一个非常明显的“我看到一个整数！”的提示。这并不是我们使用词法分析器的方式，但了解代码执行的任意性很有用：没有规定你必须创建一个对象并返回它，它只是普通的代码。你甚至可以用花括号将代码括起来，使用多行代码。
顺便一提，我们会用一个叫FLEX的工具来进行词法分析。它用起来很方便，但你完全可以自己写一个程序来实现这个功能。
为了更好地理解我们将如何使用 flex，请看以下示例：
cpp
// scanner.lex
/* Definitions */
%{
#include <iostream>
using namespace std;
extern "C" int yylex();
%}
/* Rules next */
%%
[0-9]+.[0-9]+ cout << "FLOAT: (" << yytext << ")" << endl;
[0-9]+ cout << "INT: (" << yytext << ")" << endl;
"+" cout << "PLUS" << endl;
"-" cout << "MINUS" << endl;
"*" cout << "TIMES" << endl;
"/" cout << "DIVIDED BY" << endl;
";" cout << "SEMICOLON" << endl;
[\t\r\n\f] ; /* ignore whitespace */
%%
/* Code */
int main() {
yylex();
}
这引入了一些新概念，我们一起来了解一下：
%%用于分隔 .lex 文件的各个部分。第一部分是声明部分——主要是变量，用于提高词法分析器的可读性。导入语句也位于此部分，并用 `&` 和 ` %{&`括起来%}。
第二部分是规则，我们之前已经见过。这些规则基本上是一个大的if else if代码块。它会执行匹配长度最长的行。因此，即使你改变浮点数和整数的顺序，浮点数仍然会匹配，因为匹配 3 个字符的浮点数3.2比匹配 1 个字符的整数要长3。注意，如果没有匹配到任何规则，它会执行默认规则，直接将匹配到的字符打印到标准输出。然后你可以使用 `$("匹配到的字符") yytext` 来引用它找到的匹配该规则的内容。
第三部分是代码，它实际上是C或C++源代码，会在执行时运行。yylex();这是一个函数调用，用于运行词法分析器。你也可以让它从文件中读取输入，但默认情况下它从标准输入读取。
假设你创建了这两个文件，分别命名为 `.c++`source.ect和 `.c++ scanner.lex`。我们可以使用 `c++`flex命令（假设你已经flex安装了 C++）创建一个 C++ 程序，然后编译它，并将我们的源代码导入其中，从而实现我们强大的打印语句。让我们来实际操作一下！
bash
evan:ectlang/ $ flex scanner.lex
evan:ectlang/ $ g++ lex.yy.c -lfl
evan:ectlang/ $ ./a.out < source.ect
INT: (3)
PLUS
FLOAT: (3.2)
SEMICOLON
FLOAT: (5.0)
DIVIDED BY
FLOAT: (1.9)
SEMICOLON
INT: (6)
TIMES
INT: (2)
SEMICOLON
evan:ectlang/ $
嘿，酷！你只是在编写 C++ 代码，将输入与规则进行匹配以执行某些操作。
那么，编译器如何使用这些规则呢？通常情况下，每条规则不会直接打印任何内容，而是返回一个标记！这些标记可以在编译器的下一部分中定义……
语法分析器
又称“使漂亮的源代码可用”
是时候开始玩啦！到了这里，我们开始定义程序的结构。解析器会接收到一个词法单元流，它需要匹配这个流中的元素，才能使源代码拥有可用的结构。为此，它需要用到语法，你可能在理论课上见过，或者听过你那些有点怪的朋友滔滔不绝地讲过。语法功能非常强大，有很多东西可以深入探讨，但我只会讲解我们这个有点“傻”的解析器需要了解的内容。
简单来说，语法会将非终结符与终结符和非终结符的某种组合进行匹配。终结符是树的叶子节点；非终结符则有子节点。如果这让你感到困惑，别担心，代码可能会更容易理解。
我们将使用一个名为Bison的解析器生成器。这次，为了便于解释，我会将文件分成几个部分。首先是声明部分：
cpp
// parser.y
%{
#include <iostream>
using namespace std;
extern "C" void yyerror(char *s);
extern "C" int yyparse();
%}
%union{
int intVal;
float floatVal;
}
%start program
%token <intVal> INTEGER_LITERAL
%token <floatVal> FLOAT_LITERAL
%token SEMI
%type <floatVal> exp
%type <floatVal> statement
%left PLUS MINUS
%left MULT DIV
第一部分应该看起来很熟悉：我们正在导入想要使用的内容。之后的部分就稍微复杂一些了。
联合体是将一个“真实”的 C++ 类型映射到我们在本程序中将要使用的名称。因此，当我们看到 `T` 时intVal，你可以把它替换成 `T` int；当我们看到 `C` 时floatVal，你可以把它替换成 `C` float。稍后你会明白为什么。
接下来我们来看符号。你可以像之前讨论语法时那样，在脑海中将它们分为终结符和非终结符。大写字母表示终结符，所以它们不会继续扩展。小写字母表示非终结符，所以它们会继续扩展。这只是约定俗成的做法。
每个声明（以 `\n` 开头%）都声明了一个符号。首先，我们看到以一个非终结符 `\n` 开始program。然后，我们定义一些标记。<>方括号定义了返回类型：因此，INTEGER_LITERAL终结符 `\n` 返回一个 `\n` intVal。SEMI终结符 `\n` 不返回任何值。类似的操作也可以使用 `\n` 来实现，例如，当定义 ` \n` 为返回 `\n` 的非终结符时type，就可以看出这一点。expfloatVal
最后我们来谈谈优先级。我们都知道 PEMDAS（或者你可能学过的其他缩写），它告诉了我们一些简单的优先级规则：乘法先于加法，等等。现在，我们在这里以一种特殊的方式声明这一点。首先，列表中越靠后的优先级越高。其次，你可能会好奇这是什么left意思。这就是结合律：简单来说，如果我们有 x 和 y ，那么 x和 y应该一起a op b op c执行，还是 x 和y应该一起执行？我们的大多数运算符都遵循前者，即 x和 y先一起执行：这叫做左结合律。有些运算符，比如幂运算，则相反：它要求你先进行幂运算，然后再进行幂运算。不过，我们这里不讨论这种情况。如果你想了解更多细节，可以查看 Bison 的相关页面。abbcaba^b^cb^ca^(b^c)
好了，我可能已经用声明部分让你感到厌烦了，下面是语法规则：
cpp
// parser.y
%%
program: /* empty */
| program statement { cout << "Result: " << $2 << endl; }
;
statement: exp SEMI
exp:
INTEGER_LITERAL { $$ = $1; }
| FLOAT_LITERAL { $$ = $1; }
| exp PLUS exp { $$ = $1 + $3; }
| exp MINUS exp { $$ = $1 - $3; }
| exp MULT exp { $$ = $1 * $3; }
| exp DIV exp { $$ = $1 / $3; }
;
这就是我们之前讨论过的语法。如果你不熟悉语法，它其实很简单：左边可以转换成右边的任何一种形式，用|(逻辑or) 分隔。如果它可以有多条路径，那就不行，我们称之为二义性语法。这个语法之所以没有二义性，是因为我们声明了优先级——如果我们修改它，让加法不再是左结合的，而是声明为类似token，SEMI就会出现移位/归约冲突。想了解更多？查阅一下 Bison 的工作原理，提示一下，它使用了一种 LR 分析算法。
好的，所以exp它可以变成以下几种情况之一：一个 `a` INTEGER_LITERAL，一个 `b` FLOAT_LITERAL，等等。注意它也是递归的，所以exp可以变成两个 `a` exp。这允许我们使用复杂的表达式，例如 ` 1 + 2 / 3 * 5a`。记住，每个 `a`exp都返回一个浮点类型。
括号内的内容与词法分析器中的内容相同：任意的 C++ 代码，但语法糖更加复杂。这里，我们使用了以 `\` 开头的特殊变量$。变量$$本质上就是返回值。`\ $11` 表示第一个参数的返回值，$2`\2` 表示第二个参数的返回值，以此类推。这里所说的“参数”指的是语法规则的各个部分：例如，该规则exp PLUS exp包含参数 1 exp、参数 2PLUS和参数 3。exp因此，在代码执行过程中，我们将第一个表达式的结果加到第三个表达式的结果上。
最后，当程序回到program非终结符时，它会打印出语句的执行结果。在这种情况下，程序是由一系列语句组成的，语句是一个表达式，后跟一个分号。
现在我们来编写代码部分。以下是解析器实际运行的代码：
cpp
// parser.y
%%
int main(int argc, char **argv) {
if (argc < 2) {
cout << "Provide a filename to parse!" << endl;
exit(1);
}
FILE *sourceFile = fopen(argv[1], "r");
if (!sourceFile) {
cout << "Could not open source file " << argv[1] << endl;
exit(1);
}
// Sets input for flex to the file instead of standard in
yyin = sourceFile;
// Now let's parse it!
yyparse();
}
// Called on error with message s
void yyerror(char *s) {
cerr << s << endl;
}
好了，这开始变得有趣起来了。我们的主函数现在不再从标准输入读取数据，而是从第一个参数提供的文件中读取数据，并且我们还添加了一些错误代码。这部分内容很容易理解，注释也解释得很清楚，所以我把它留给读者自己去琢磨。你只需要知道，现在我们又回到了词法分析器，它负责将词法单元提供给语法分析器！以下是我们新的词法分析器：
cpp
// scanner.lex
%{
extern "C" int yylex();
#include "parser.tab.c" // Defines the tokens
%}
%%
[0-9]+ { yylval.intVal = atoi(yytext); return INTEGER_LITERAL; }
[0-9]+.[0-9]+ { yylval.floatVal = atof(yytext); return FLOAT_LITERAL; }
"+" { return PLUS; }
"-" { return MINUS; }
"*" { return MULT; }
"/" { return DIV; }
";" { return SEMI; }
[ \t\r\n\f] ; /* ignore whitespace */
嘿，现在体积确实小了！我们可以看到，现在不是直接打印，而是返回终端符号。对于某些终端符号，例如整数和浮点数，我们会先设置它们的值，然后再继续处理（`$($($($($($($($($($($($($($($( )`)`)``yylval是终端符号的返回值）。除此之外，它只是给解析器提供了一个终端标记流，供其自行处理。
好，那就运行吧！
bash
evan:ectlang/ $ bison parser.y
evan:ectlang/ $ flex scanner.lex
evan:ectlang/ $ g++ lex.yy.c -lfl
evan:ectlang/ $ ./a.out source.ect
Result: 6.2
Result: 2.63158
Result: 12
好了——我们的解析器打印出了正确的值！但这其实并不是一个编译器，它只是运行一段 C++ 代码来执行我们想要的操作。要实现编译器的功能，我们需要将它转换成机器代码。为此，我们还需要添加一些其他的东西……
下次再见……
我现在意识到这篇文章会比我想象的要长得多，所以我想就此打住。我们基本上已经有了可以正常工作的词法分析器和语法分析器，所以到此为止也算不错了。
我已经把源代码上传到我的 GitHub 仓库了，如果你有兴趣看看最终成品，可以去看看。随着更多文章的发布，这个仓库也会更加活跃。
有了词法分析器和语法分析器，我们现在可以生成代码的中间表示，最终可以将其转换为真正的机器代码，接下来我将向您展示具体如何操作。
其他资源
如果你想了解更多这里提到的内容，我已经提供了一些入门链接。我这里只是简单带过了很多内容，所以现在我来教你如何深入研究这些主题。
- Flex 代码库：https://github.com/westes/flex - 我们使用的词法分析工具。
- Bison 文档：https://www.gnu.org/software/bison/ - 我们使用的解析器生成器。这里的文档非常棒。
- LALR 解析：https://web.cs.dal.ca/~sjackson/lalr1.html - 对 LALR(1) 解析器（如 Bison 生成的解析器！）的工作原理进行了很好的解释。
- 解决解析冲突：http://www.cs.ecu.edu/karl/5220/spr16/Notes/Bottom-up/conflict.html - 如何修复移位/归约或归约/归约冲突，就像我们之前看到的那种冲突。
- 乔姆斯基层级结构：https://en.wikipedia.org/wiki/Chomsky_hierarchy - 虽然没有详细讲解，但我们使用的是上下文无关文法，所以 Bison 可以编译它。如果需要上下文相关的功能，那将在后续阶段实现。
- 符号表：https://www.tutorialspoint.com/compiler_design/compiler_design_symbol_table.htm - 使用符号表，编译器如何处理变量。
对了，如果你不喜欢我之前画的编译器阶段图，这里有一张实际的图。我还没画符号表和错误处理程序。另外，很多图都跟这个不一样，但这张图最能说明我们关注的重点。
