| 自制Monkey语言编译器：实现函数闭包功能和为语言增加复杂数据结构 | 您所在的位置：网站首页 › 编译原理中的闭包 › 自制Monkey语言编译器：实现函数闭包功能和为语言增加复杂数据结构 |
自制Monkey语言编译器：实现函数闭包功能和为语言增加复杂数据结构
|
Monkey语言有点类似于JS，它的函数可以当做参数进行传递，而且语法支持函数闭包功能，例如下面代码： let newAdder = fn(x) { return fn(y) { return x + y;};}; let addTwo = newAdder(3); addTwo(2);在上面代码中，我们把newAdder定义为一个函数变量，该函数里面又返回一个函数，在第二次定义变量addTwo时，它对应的是上面函数返回另一个函数，而且上面函数已经把x变量定义为3，于是addTwo(2)在执行时，它的返回值是5.为了实现这种函数闭包功能，我们必须为每个函数变量配置一个绑定环境，因此对上节代码做相应修改如下： case "FunctionLiteral": var props = {} props.token = node.token props.identifiers = node.parameters props.blockStatement = node.body var funObj = new FunctionCall(props) funObj.enviroment = this.newEnclosedEnvironment(this.enviroment)上面代码为函数构建符号对象时，会专门配置一个绑定环境对象，于是上面代码addTwo(3)执行时，它遇到变量x，就能在函数对应的绑定环境中查询到。我们在函数的解析执行部分做如下修改： case "CallExpression": .... // change 12 执行函数前保留当前绑定环境 var oldEnviroment = this.enviroment //设置新的变量绑定环境 this.enviroment = functionCall.enviroment //将输入参数名称与传入值在新环境中绑定 for (i = 0; i < functionCall.identifiers.length; i++) { var name = functionCall.identifiers[i].tokenLiteral var val = args[i] this.enviroment.set(name, val) } //执行函数体内代码 var result = this.eval（functionCall.blockStatement) //执行完函数后，里面恢复原有绑定环境 this.enviroment = oldEnviroment ....上面代码执行时，在执行调用函数前会将解析器的变量绑定环境设置为要执行函数的变量环境，这样一来在函数体内定义的变量，即使在函数体外查询不到，但是当函数执行时，还是能通过它自带的变量绑定环境找到对应变量的值，完成上面代码后，我们就可以解释执行开头的Monkey代码，执行结果如下：
示例中的newAdder称之为高阶函数，所谓高阶函数就是能返回函数对象或是接收函数对象作为参数的函数。由于它返回的函数包含着自己的变量绑定环境，因此我们也称newAdder为一个函数闭包。 接下来我们要为Monkey语言增加复杂数据结构的支持，目前我们的语言智能识别整数，Boolean，这两种很基础的数据类型，为了语言的表达力能更强，我们要添加相应的复杂数据类型，例如字符串，哈希表，数组等，接下来我们先添加的数据类型是字符串。 所谓字符串就是双引号中包含一连串字符，例如”Hello World”，我们现在lexer里面增加相应token标志,在MonkeyLexer.js中添加： initTokenType() { .... //change 1 this.STRING = 25 } nextToken () { .... // change 2 case '"': var str = this.readString() tok = new Token(this.STRING, str, lineCount) break .... } // change 3 readString() { // 越过开始的双引号 this.readChar() var str ="" while (this.ch != '"' && this.ch != this.EOF) { str += this.ch this.readChar() } if (this.ch != '"') { return undefined } return str }词法解析器读取第一个双引号时，构造一个类型为STRING的token，然后依次读取后面字符作为token对象内容，直到读取第二个双引号为止。完成上面代码后，词法解析器就成功构造了类型为字符串的Token。接下来我们在语法解析器中构造对应的语法节点。在MonkeyCompilerParser.js中添加如下代码： class StringLiteral extends Node { constructor(props) { super(props) this.token = props.token this.tokenLiteral = props.token.getLiteral() this.type = "String" } } .... class MonkeyCompilerParser { constructor(lexer) { ... this.prefixParseFns[this.lexer.STRING] = this.parseStringLiteral ... } ... } parseStringLiteral(caller) { var props = {} props.token = caller.curToken return new StringLiteral(props) }上面代码定义了一个语法树节点StringLiteral，然后在语法解析器的构造函数将字符串的解析函数parseStringLiteral注册到前缀表达式解析函数调用表中，一旦类型为STRING的token对象传递给语法解析器时，它会调用parseStringLiteral构造一个StringLiteral语法节点。接下来我们要做解析器中，增加对字符串节点对象的解析执行。在evaluator.js中添加如下代码： class BaseObject { constructor (props) { ... //change 7 this.STRING_OBJ = "String" } } //change 8 class String extends BaseObject { constructor(props) { super(props) this.value = props.value } inspect() { return "content of string is: " + this.value } type() { return this.STRING_OBJ } } class MonkeyEvaluator { .... eval（node) { var props = {} switch (node.type) { case "program": return this.evalProgram(node) // change 9 case "String": props.value = node.tokenLiteral return new String(props) .... } .... } evalInfixExpression(operator, left, right) { .... //change 9 增加字符串加法操作 if (left.type() === left.STRING_OBJ && right.type() === right.STRING_OBJ) { return this.evalStringInfixExpression(operator, left, right) } } //change 10 实现字符串加法操作 evalStringInfixExpression(operator, left, right) { if (operator != "+") { return this.newError("unknown operator for string operation") } var leftVal = left.value var rightVal = right.value var props = {} props.value = leftVal + rightVal console.log("reuslt of string add is: ", props.value) return new String(props) } .... }代码在解释器中先增加了一个String类型的符号对象，一旦从语法解析器接收到String类型的语法对象时，解析器就会构造对应的符号对象。接着我们增加了对“+”操作符的处理，当做加法时，如果解析器发现加号两边对应的都是字符串对象，那么就把两个字符串前后串联起来，当上面代码完成后，我们在编辑框中输入如下代码： let s1 = "hello "; let s2 = "world!"; let s3 = s1 + s2;点击底下的parsing按钮得到的结果为：
从运行结果上看，我们的编译器正确实现了两个字符串变量的加法操作。 更多技术信息，包括操作系统，编译器，面试算法，机器学习，人工智能，请关照我的公众号：
|
【本文地址】