编译原理工程实践—04处理语义分析实现简易脚本解释器

上一章实现的简易语法分析器能够解析简单的表达式、变量声明和初始化语句、赋值语句，生成简化的AST。但距离一门真正的语言还相差甚远，例如未处理作用域、面向对象等等特性，这些往往是在语义分析阶段来处理的，本章将讲述语义分析的实现。

1. 语义分析之作用域(Scope)

1.1 实现块作用域和函数作用域

作用域是编程语言的一个重要概念，虽然各门语言的设计各有特性，但运行机制都类似，都会用栈和堆来做内存管理。在上一章虽然语法分析阶段生成了 AST，还需要进行语义分析，例如处理作用域，建立起作用域的树结构，让每个变量被正确引用，程序才能正确地执行。

开发语言通常有三种作用域：块作用域(Block)、函数作用域(Function)和类作用域(Class)。例如，在 js-es5 中变量通过 var 关键字声明到全局作用域，js-es6 中支持了 const/let 声明块作用域。

由于变量的生存期和作用域一致，因此本地变量一般使用栈进行管理，在本次案例中，临时用一种简单的方式存放变量：

private variables: Map<string, number | null> = new Map();

1.2 实现面向对象中数据和方法的封装

大多数语言支持面向对象(OOP)方式，其重要特点是封装，尽可能地隐藏内部细节，只保留一些接口与外部发生联系。

类主体里要需要声明类成员，可以临时简化为类属性和类方法两种成员。类成员变量的声明和普通变量声明在语法上没什么区别，类方法 method 也可以和函数统一设计为 function。

1.3 闭包(Closure)的作用域机制

在 es6 以前，前端面试中必问如何用闭包特性实现面向对象编程。

在 JavaScript 中，外层函数返回一个内层函数后，这个内层函数能一直访问外层函数中的本地变量。这看起来不符合前面讲述的作用域和生命周期的设计，因为函数中的本地变量只能在函数内部访问，函数退出后，函数作用域对应的栈桢被弹出，占用的内存会被收回。

function createCounter() {
  let count = 0; // 局部变量
  // 返回一个内部函数，形成闭包
  return function() {
    count += 1; // 内部函数可以访问外部函数的变量count
    return count;
  };
}
const counter = createCounter();
console.log(counter()); // 输出: 1
console.log(counter()); // 输出: 2

根本原因是因为函数能作为值传递，造成了作用域不匹配的情况，闭包是语言为了正常执行所提供的一个解决方案。不过，闭包是很有用的，在编写库时能隐藏内部实现细节。这么看来，闭包的实现机制有两个条件：

• 语言是静态作用域的：目前大多数语言都是静态作用域的，在编译时构建 Scope 树，即词法作用域(Lexcical Scope)。

• 函数作为一等公民 在 JavaScript 和 Python 等语言里，函数可以像普通数值一样使用，如变量赋值、作为参数传递、作为函数返回值等，利用这个特性可以实现函数式编程(functional programming)，简洁且安全。

闭包把函数在静态作用域中访问的变量的生存期拉长，形成一份只能由这个函数单独访问的数据。这个特点和 OOP 不谋而合，因此在 es6 以前，完全可以使用闭包的特性实现面向对象编程。

了解了闭包的作用域机制后，困扰前端er的 JavaScript 中的 this 指向问题也就迎刃而解了。

2. 语义分析的上下文处理场景

语义分析的本质是遍历AST，添加上下文相关信息，如：

• 类型和作用域解析
• 引用消解
• 类型检查
• 语义合法性检查
• ......

2.1 类型系统

高级语言的类型系统能够极大地降低计算出错的概率。

静态类型语言的类型检查在编译时执行，程序更稳定，运行时性能更高；动态类型语言的类型检查在运行时执行，编程更加灵活，各有千秋。目前的趋势是，动态类型语言在尝试增加编译时检查，如 TypeScript 编译为 JavaScript，而静态类型语言在设计一些方案绕过编译时检查，增强灵活性。

强类型语言指变量的类型声明后不能改变，弱类型语言的变量类型在运行时可以改变。

2.2 引用消解

语义分析阶段需要将程序里使用的变量、函数、类等符号标记对应的定义的位置。例如，在集成开发环境中，点击某个变量、函数或类时可以跳转到定义，重构变量名称时会同步修改所有引用，就是引用消解的应用。

2.3 属性计算

和词法、语法分析阶段使用正则文法和上下文无关文法类似，在语义分析阶段需要使用属性文法(Attribute Grammar)来指定语义规则。而属性计算是指基于属性文法规则，在语法解析或形成 AST 后增加与语义处理有关的规则，或是执行一些计算。例如，解析加法表达式 1+2 时得到一个 AST，基于属性文法规则可以知道这是一个加法表达式，从而实现加法运算。

3. 源码实现简易脚本解释器

SimpleScript 脚本解释器源码如下，支持变量，包括变量的声明语句、表达式语句、赋值语句：

import SimpleParser, { ASTNodeType, ASTNode } from 'SimpleParser';
/**
 * 一个简单的脚本解释器
 * 支持变量，包括变量的声明语句、表达式语句、赋值语句
 */
class SimpleScript {
  // 临时用一种简单的方式存放变量
  private variables: Map<string, number | null> = new Map();
  /**
   * 遍历 AST 计算值
   * @param {ASTNode} node AST节点
   * @param {string} indent 缩进字符串
   * @returns {number|null} 计算结果
   */
  public evaluate(node: ASTNode, indent: string): number | null {
    let result: number | null = null;
    switch (node.getType()) {
      case ASTNodeType.Programm:
        for (const child of node.getChildren()) {
          result = this.evaluate(child, indent);
        }
        break;
      case ASTNodeType.Additive: {
        const child1 = node.getChildren()[0];
        const value1 = this.evaluate(child1, indent + '\t');
        const child2 = node.getChildren()[1];
        const value2 = this.evaluate(child2, indent + '\t');
        if (node.getText() === '+') {
          result = value1! + value2!;
        } else {
          result = value1! - value2!;
        }
        break;
      }
      case csxiaoyao.comASTNodeType.Multiplicative: {
        const child3 = node.getChildren()[0];
        const value3 = this.evaluate(child3, indent + '\t');
        const child4 = node.getChildren()[1];
        const value4 = this.evaluate(child4, indent + '\t');
        if (node.getText() === '*') {
          result = value3! * value4!;
        } else {
          result = Math.floor(value3! / value4!); // 整数除法
        }
        break;
      }
      case ASTNodeType.IntLiteral:
        result = parseInt(node.getText(), 10);
        break;
      case ASTNodeType.Identifier: {
        const varName = node.getText();
        // 变量处理
        if (this.variables.has(varName)) {
          const value = this.variables.get(varName) || null;
          if (value !== null) {
            result = value;
          } else {
            throw new Ercsxiaoyao.comror(`variable ${varName} has not been set any value`);
          }
        } else {
          throw new Error(`unknown variable: ${varName}`);
        }
        break;
      }
      case ASTNodeType.AssignmentStmt: {
        const assignVarName = node.getText();
        // 获取变量
        if (!this.variables.has(assignVarName)) {
          throw new Error(`unknown variable: ${assignVarName}`);
        }
      }
      // 接着执行下面的代码
      // eslint-disable-next-line no-fallthrough
      case ASTNodeType.IntDeclaration: {
        const declVarName = node.getText();
        if (node.getChildren().length > 0) {
          const child = node.getChildren()[0];
          result = this.evaluate(child, indent + '\t');
          this.variables.set(declVarName, result);
        } else {
          this.variables.set(declVarName, null);
        }
        break;
      }
      default:
      // 其他类型不处理
    }
    if (indent === '') {
      // 顶层的语句
      if (
        node.getType() === ASTNodeType.IntDeclaration ||
        node.getType() === ASTNodeType.AssignmentStmt
      ) {
        console.log(`${node.getText()}: ${result}`);
      } else if (node.getType() !== ASTNodeType.Programm) {
        console.log(result);
      }
    }
    return result;
  }
}

编写测试方法：

const testSimpleCalculator = () => {
  const parser = new SimpleParser();
  const script = new SimpleScript();

  let scriptText = 'int age = 1+2; age+3;'; // age:3, 6
  let tree = parser.parse(scriptText);
  parser.dumpAST(tree, '');
  script.evaluate(tree, '');

  scriptText = 'int a = 1+2;';
  tree = parser.parse(scriptText);
  parser.dumpAST(tree, '');
  script.evaluate(tree, '');
};
testSimpleCalculator();

控制台输出如下：

Programm demo
  IntDeclaration age
      Additive +
          IntLiteral 1
          IntLiteral 2
  Additive +
      Identifier age
      IntLiteral 3
age: 3
6

Programm demo
  IntDeclaration a
      Additive +
          IntLiteral 1
          IntLiteral 2
a: 3

可以看到变量正确地执行了计算并输出了值，至此，编译原理核心三步介绍完成。