# 01｜实现一门超简单的语言最快需要多久？ 你好，我是宫文学。 说到实现一门计算机语言，你肯定觉得这是一个庞大又复杂的工程，工作量巨大！ 这个理解，我只能说部分正确。其实，有的时候，实现一门语言的速度也可以很快。比如，当年兰登·艾克（Brendan Eich）只花了10天时间就把JavaScript语言设计出来了。当然，语言跟其他软件一样，也需要不断迭代，至今JS的标准和实现仍在不停的演化。 如果我说，你也完全可以在这么短的时间内实现一门语言，甚至都不需要那么长时间，你一定会觉得我是在哗众取宠、标题党。 别急，我再补充说明一下，你马上就会认可我的说法了。这个让你一开始实现的版本，只是为了去探索计算机语言的原理，是高度简化的版本，并不要求马上能实用。你可以把它看做是一个原型系统，仅此而已，实现起来不会太复杂。 好吧，我知道你肯定还在心里打鼓：再简单的计算机语言，那也是一门语言呀，难度又能低到哪里去？ 这样，先保留你的疑虑，我们进入今天的课程。**今天我就要带你挑战，仅仅只用一节课时间，就实现一门超简洁的语言。**我会暂时忽略很多的技术细节，带你抓住实现一门计算机语言的骨干部分，掌握其核心原理。在这节课中，你会快速获得两个技能： * 如何通过编译器来理解某个程序； * 如何解释执行这个程序。 这两个点，分别是编译时的核心和运行时的核心。理解了这两个知识点，你就大致理解计算机语言是如何工作的了！ ## 我们的任务 这节课，我们要让下面这个程序运行起来： ```plain //一个函数的声明，这个函数很简单，只打印"Hello World!" function sayHello(){ println("Hello World!"); } //调用刚才声明的函数 sayHello(); ``` 这个程序做了两件事：第一件是声明了一个函数，叫做sayHello；第二件事，就是调用sayHello()函数。运行这个程序的时候，我们期待它会输出“Hello World！”。 这个程序看上去还挺像那么回事的，但其实为降低难度，我们对JavaScript/TypeScript做了极度的简化：它只支持声明函数和调用函数，在我们的sayHello()函数里，它只能调用函数。你可以调用一个自己声明的函数，如foo，也可以调用语言内置的函数，如示例中的println()。 这还不够，为了进一步降低难度，我们的编译器是从一个数组里读取程序，而不是读一个文本文件。这个数组的每一个元素是一个单词，分别是function、sayHello、左括号、右括号等等，这些单词，我们叫它Token，它们是程序的最小构成单位。注意，最后一个Token比较特殊，它叫做EOF，有时会记做$，表示程序的结尾。 ![图片](https://static001.geekbang.org/resource/image/7a/be/7aea783003f9758f40bd3efdd2de48be.jpg?wh=1920x329 "图1：Token串（图中不同的颜色代表不同类型的Token） ") 好了，现在任务清楚了，那我们开始第一步，解析这个程序。 ## 解析这个程序 解析，英文叫做Parse，是指读入程序，并形成一个计算机可以理解的数据结构的过程。能够完成解析工作的程序，就叫做解析器（Parser），它是编译器的组成部分之一。 那么，什么数据结构是计算机能够理解的呢？很简单，其实就是一棵树，这棵树叫做**抽象语法树，英文缩写是AST（Abstract Syntax Tree）**。针对我们的例子，这棵AST是下面的样子： ![图片](https://static001.geekbang.org/resource/image/c3/37/c3109f472253e98057f255f7dbf57c37.jpg?wh=1920x1080 "图2：示例代码对应的AST") 你仔细看一下这棵树，你会发现它跟我们程序想表达的思想是一样的： * 根节点代表了整个程序； * 根节点有两个子节点，分别代表一个函数声明和一个函数调用语句； * 函数声明节点，又包含了两个子节点，一个是函数名称，一个是函数体； * 函数体中又包含一个函数调用语句； * 而函数调用语句呢，则是由函数名称和参数列表构成的； * …… 通过这样自顶向下的层层分析，你会发现这棵树确实体现了我们原来的程序想表达的意思。其实，这就跟我们自己在阅读文章的时候是一样的，我们的大脑也是把段落分解成句子，再把句子分解成主语、谓语、宾语等一个个语法单元，最终形成一棵树型的结构，我们的大脑是能够理解这种树型结构的。 总结起来，**解析器的工作，就是要读取一个Token串，然后把它转换成一棵AST**。 好了，知道了解析的工作目标后，我们就来实现这个解析器吧！ 可是，这怎么下手呢？ 你可以琢磨一下，你的大脑是如何理解这些程序，并且把它们在不知不觉之间转化成一棵树的。我们假设，人类的大脑采用了一种自顶向下的分析方式，也就是把一个大的解析任务逐步分解成小的任务，落实到解析器的实现上也是如此。 首先，我们的目的是识别Token串的特征，并把它转换成AST。我们暂时忽略细节，假设我们能够成功地完成这个解析，那么把这个解析动作写成代码，就是： ```plain prog = parseProg()； ``` 我们再具体一点，看看实现parseProg()需要做什么事情。 parseProg()需要建立程序的子节点，也就是函数声明或者函数调用。我们规定一个程序可以有零到多个函数声明或函数调用。我们把这个语法规则用比较严谨的方法表达出来，是这样的： ```plain prog = (functionDecl | functionCall)* ; ``` 咦？这个表达方式看上去有点熟悉呀？这个式子的格式叫做EBNF格式（扩展巴科斯范式）。你可以看到，它的左边是一个语法成份的名称，右边说的是这个语法成份是由哪些子成分构成的。这样，整个式子就构成了一条语法规则。 不过，编译原理的教科书里，有时会用产生式的格式。EBNF格式和产生式是等价的，区别是产生式不允许使用？、\*和+号，而是用递归来表示多个元素的重复，用ε来表示不生成任何字符串。如果我们把上述语法规则用产生式来表示的话，相当于下面四条： ```plain prog -> statement prog prog -> ε statement -> functionDecl statement -> functionCall ``` 你马上就能看出来，还是EBNF格式更简洁吧？ 好了，根据这条语法规则，一个程序要么是由函数声明构成的，要么是由函数调用构成的，那么我们就把它们一一解析出来，变成prog的子节点就好了！ 可是，我们如何知道接下来遇到的是函数声明还是函数调用呢？ 有办法！办法就是：试试看！ 什么叫试试看？就是先试试是不是函数声明。如果成功的话，解析器就会返回一棵代表函数声明的子树；如果不成功的话，解析器就会返回null，然后你可以再试试看是不是函数调用。你可能会问：就这么简单？对，就这么简单。 实现上述逻辑的代码如下： ```plain parseProg():Prog{ let stmts: Statement[] = []; let stmt: Statement|null|void = null; while(true){ //每次循环解析一个语句 //尝试一下函数声明 stmt = this.parseFunctionDecl(); if (stmt != null){ stmts.push(stmt); continue; } //如果前一个尝试不成功，那么再尝试一下函数调用 stmt = this.parseFunctionCall(); if (stmt != null){ stmts.push(stmt); continue; } //如果都没成功，那就结束 if (stmt == null){ break; } } return new Prog(stmts); } ``` 现在我们再往下一层，看看如何解析函数声明。 函数声明包括function关键字、函数名称、一对括号和函数体。我们依然将它表达成语法规则，是这样的： ```plain functionDecl: "function" Identifier "(" ")" functionBody; ``` 注意，在这个新的语法规则里，我们发现了“function”、“Identifier”这样的元素，这些元素是不能再展开的，我们把它们叫做终结符。你会发现，终结符都是从Token转化而来的。而像“functionBody”这些用小写字母开头的元素，还可以再继续展开，所以叫做非终结符。 那这该怎么解析呢？ 还是得挨个去试。先试一下第一个Token是不是“function”，再试下第二个Token是不是一个合法的标识符，接着试第三个Token是不是左括号，依此类推就行了。 其实，在函数声明的语法规则里，像“function”、“Identifier”这些，都已经是最终的Token了，所以直接把它们从Token串中取出来就行了，其中“Identifier”变成了AST中的函数名称。 而函数声明中的另一部分，也就是函数体，是一个比较复杂的结构，所以我们将它拆出来单独定义。体现在AST中，它就是函数声明的子节点。这里，我索性把剩余的有关函数体、函数调用的语法规则都写出来。 ```plain functionBody : '{' functionCall* '}' ; functionCall : Identifier '(' parameterList? ')' ; parameterList : StringLiteral (',' StringLiteral)* ; ``` 解析上述语法规则对应的程序如下： ```plain /** * 解析函数声明 * 语法规则： * functionDecl: "function" Identifier "(" ")" functionBody; */ parseFunctionDecl():FunctionDecl|null|void{ let oldPos:number = this.tokenizer.position(); let t:Token = this.tokenizer.next(); if (t.kind == TokenKind.Keyword && t.text == "function"){ t = this.tokenizer.next(); if (t.kind == TokenKind.Identifier){ //读取"("和")" let t1 = this.tokenizer.next(); if (t1.text=="("){ let t2 = this.tokenizer.next(); if (t2.text==")"){ let functionBody = this.parseFunctionBody(); if (functionBody != null){ //如果解析成功，从这里返回 return new FunctionDecl(t.text, functionBody); } } else{ console.log("Expecting ')' in FunctionDecl, while we got a " + t.text); return; } } else{ console.log("Expecting '(' in FunctionDecl, while we got a " + t.text); return; } } } //如果解析不成功，回溯，返回null。 this.tokenizer.traceBack(oldPos); return null; } /** * 解析函数体 * 语法规则： * functionBody : '{' functionCall* '}' ; */ parseFunctionBody():FunctionBody|null|void{ let oldPos:number = this.tokenizer.position(); let stmts:FunctionCall[] = []; let t:Token = this.tokenizer.next(); if(t.text == "{"){ let functionCall = this.parseFunctionCall(); while(functionCall != null){ //解析函数体 stmts.push(functionCall); functionCall = this.parseFunctionCall(); } t = this.tokenizer.next(); if (t.text == "}"){ return new FunctionBody(stmts); } else{ console.log("Expecting '}' in FunctionBody, while we got a " + t.text); return; } } else{ console.log("Expecting '{' in FunctionBody, while we got a " + t.text); return; } //如果解析不成功，回溯，返回null。 this.tokenizer.traceBack(oldPos); return null; } /** * 解析函数调用 * 语法规则： * functionCall : Identifier '(' parameterList? ')' ; * parameterList : StringLiteral (',' StringLiteral)* ; */ parseFunctionCall():FunctionCall|null|void{ let oldPos:number = this.tokenizer.position(); let params:string[] = []; let t:Token = this.tokenizer.next(); if(t.kind == TokenKind.Identifier){ let t1:Token = this.tokenizer.next(); if (t1.text == "("){ let t2:Token = this.tokenizer.next(); //循环，读出所有 while(t2.text != ")"){ if (t2.kind == TokenKind.StringLiteral){ params.push(t2.text); } else{ console.log("Expecting parameter in FunctionCall, while we got a " + t2.text); return; //出错时，就不在错误处回溯了。 } t2 = this.tokenizer.next(); if (t2.text != ")"){ if (t2.text == ","){ t2 = this.tokenizer.next(); } else{ console.log("Expecting a comma in FunctionCall, while we got a " + t2.text); return; } } } //消化掉一个分号：; t2 = this.tokenizer.next(); if (t2.text == ";"){ return new FunctionCall(t.text, params); } else{ console.log("Expecting a comma in FunctionCall, while we got a " + t2.text); return; } } } //如果解析不成功，回溯，返回null。 this.tokenizer.traceBack(oldPos); return null; } } ``` 到这里你会发现，我们做语法分析的思路很简单： * **首先，写出语法规则**，比如说用EBNF格式。 * **第二，根据语法规则，分别匹配每个子元素。**如果这个语法规则中用到了另一个语法规则，就像函数声明里用到了函数体，那么我们就需要递归地匹配这条语法规则。这个层层下降的匹配过程，叫做“**递归下降（Recursive Descent）**”，这就是我们刚刚采用的算法，Java、V8等很多编译器也都采用了这个递归下降算法。 * **第三，如果一条语法规则可能有多个展开方式**，就像程序里面既可以是函数声明，也可以是函数调用，**那么我们就要依次尝试去匹配**。如果尝试失败，就回退，再去尝试另一个展开方式。 好了，你也知道了，我们刚才用到的方法就是大名鼎鼎的“递归下降算法”。当然，这是它的初级版本，会存在一些缺陷，这个我们后面会讲。不过，即使是像JDK里的Java编译器、V8的JaveScript编译器、Go语言的编译器这些成熟的编译器，采用的都是递归下降算法，所以你应该足够重视它。 ## 做一点简单的语义分析 好了，现在我们已经完成了语法分析工作，并形成了AST。但是，在解释执行这个程序之前，我们还要做一点微小的工作：就是**引用消解（Refrence Resolving）**。 这是什么意思呢？ 在我们的程序中有两处函数调用：一处是println()，我们现在把它看做内置函数就好了，而另一处，是调用我们自定义的函数sayHello()。那么**引用消解，就是把函数的调用和函数的定义关联到一起**，否则，程序就没法正常运行。由于我们目前的语言很简单，所以引用消解工作也很简单，你可以看看下面的参考代码： ```plain //遍历prog中的所有语句，找到一个名称匹配的函数声明 private findFunctionDecl(prog:Prog, name:string):FunctionDecl|null{ for(let x of prog?.stmts){ let functionDecl = x as FunctionDecl; if (typeof functionDecl.body === 'object' && functionDecl.name == name){ return functionDecl; } } return null; } ``` 引用消解是语义分析过程中必须要做的一项工作，其他更多的语义分析工作我们仍然可以忽略。做完了语义分析以后，AST上增加了一些信息： ![图片](https://static001.geekbang.org/resource/image/31/f0/3136fc4f3d74f607e0edc9454d71e6f0.jpg?wh=1920x1080 "图3：在AST增加了引用信息，可以找到函数的定义") 在上图中，你可以看到对sayHello()函数做调用的AST节点，指向了sayHello的函数声明节点。这样，在解释器里执行sayHello()的时候，就能找到该执行什么代码了！ ## 做一个简单的解释器来运行这个程序 好了，完成好上面各项准备工作，接下来要实现解释器了。 解释器怎么运行呢？很简单，自顶向下、深度优先地遍历一下AST就行了。 具体过程是这样的： ![图片](https://static001.geekbang.org/resource/image/0e/ff/0e90bfdb9ec8fb4dc1866025d72d18ff.jpg?wh=1920x1080 "图4：通过遍历AST来解释执行程序") 第1步，我们要来访问prog节点。 第2步，接着访问prog的第一个子节点的，但这个子节点是一个函数声明，函数声明是不能直接运行的，所以此时访问这个节点不会产生任何动作。 第3步，访问prog的第二个子节点。这个子节点是一个函数调用，由于我们已经做了引用消解，我们已经知道这个函数在AST中的位置了。 第4步，我们要跳到函数定义的位置去执行这个函数，然后在第5步中执行这个函数的函数体。 第6步，我们再执行函数体的下一级节点，也就是println(“Hello World”)。这实际上是调用一个内置函数，因此我们把“Hello World”作为参数传递给内置函数就行了。 到此，程序执行完毕，输出了“Hello World”。 为了加深你的理解，我再举一个例子。 假如我们的语言现在已经支持表达式了，那么对于2+3\*5这样一个表达式，解析器也会自动形成一棵AST。这时，对表达式求值的过程，也就是遍历AST的过程。 ![图片](https://static001.geekbang.org/resource/image/3c/ae/3cf0eb845e3e03f54b81a14ffe7cc9ae.jpg?wh=1920x917 "图5：通过遍历AST来计算表达式的值（图中标号，是完全访问完毕一棵子树的顺序）") ## 课程小结 好了，这就是我们今天的全部内容了。虽然我们做了很多的简化，但我们毕竟已经能让一个程序运行起来了。你还可以把示例程序改写一下，比如多写几个自定义的函数，多做几个函数调用，打印出调用过程，等等。 例如，在下面的示例程序中，我又新声明了一个函数bar，并在bar中调用foo，检验一下多级函数调用是否会正常运行。 ```plain function foo(){ println("in foo..."); } function bar(){ println("in bar..."); foo(); } bar(); ``` 你看，虽然我们的程序特性很少，但毕竟能玩起来了。你只要遵守语言的特性，编写出来的任意程序都是能正确执行的，这就是计算机语言最有魅力的地方！而且，你也可以亲手实现。 我给你把这节课的要点总结一下： * 要实现一门计算机语言，首先要有一个编译器来把程序转化成计算机可理解的数据（这里是AST），然后需要有一个解释器来执行它。 * 编译器有很多功能，词法分析功能在这讲被我们故意跳过了。在语法分析部分，我们了解了如何用EBNF格式来表达语法规则，并初步介绍了递归下降算法；在语义分析部分，我们做了函数的引用消解。 * 我们当前版本的解释器，是通过遍历AST来运行程序的，方便你理解原理。在后面的课程中，我们会把AST转换成更适合解释执行的中间代码（Intermediate Representation，IR），就像Java的字节码一样，然后我们再实现一个新的解释器。 这节课我们忽略了很多技术细节，别担心，之后的课程，我们会一一补上这些知识点，让你平滑地学到实现一门语言的所有技能。 ## 思考题 我们今天的课程就到这里了，我给你布置了两个思考题来巩固下今天学习的内容。 问题1：在这节课讲述的语法规则中，我们做了一些简化，比如在函数声明的时候，我们并没有管参数。如果加上参数，你会怎样改写一下语法规则呢？另外，我们目前用的还是JavaScript的语法，如果改成TypeScript的语法，带上类型声明，语法规则又会是什么样子呢？你可以练习一下。 问题2：在今天的课程里，我们的语法分析的算法是“递归下降”算法。不知道你有没有发现，我们的程序里并没有出现函数的递归调用呀，为什么还要说它是递归的呢？ 感谢你和我一起学习，如果你觉得我这节课讲得还不错，也欢迎你把它分享给更多对编程语言感兴趣的朋友。我是宫文学，我们下节课见。 ## 资源链接 [这节课的示例代码在这里！](https://gitee.com/richard-gong/craft-a-language/blob/master/01/play.ts)