围绕编程语言的词法分析、语法解析和解释执行，有以下几个概念

1. Token（标记）：Token 是编程语言中的基本单位，它代表了语法中的一种语义元素。比如在算术表达式中，加号 (+)、减号 (-)、数字 (123) 都可以是 Token。  每个 Token 有一个类型（如 Plus, Minus, NumberLiteral），以及一个模式（用正则表达式定义），用于在源代码中识别这些 Token。
2. Lexer（词法分析器）：Lexer 是将源代码字符串转换为一系列 Token 的工具。它负责识别语言的基本构成单位（Token）。 Lexer 会跳过不必要的字符（如空格），并生成有用的 Token 给后续的语法分析器处理。
3. CST（Concrete Syntax Tree，具体语法树）：CST 是一种数据结构，用于表示源代码的具体语法结构。它包含了所有语法元素及其关系。 CST 允许解析器理解源代码的结构，提供对语法的完整视图，便于后续处理（如语义分析和代码生成）。
4. AST（Abstract Syntax Tree，抽象语法树） 是一种表示程序结构的树形数据结构，广泛应用于编译器和解释器中。与 CST（Concrete Syntax Tree，具体语法树）不同，AST 只关注程序的逻辑结构，而忽略了语法的具体细节（如空格、括号等）。
5. Parser（解析器）：Parser 是处理 Token 序列并生成 ST 的组件。它会根据语言的语法规则，判断 Token 的组合是否符合预期的结构。
6. Visitor（访问者模式）：访问者模式是一种设计模式，允许在不修改对象结构的情况下对其进行操作。在此上下文中，它被用来遍历 CST，并执行相应的操作（如计算表达式的值）。

AST 与 CST 的比较

CST:

• 表示代码的具体结构，包括所有的语法细节。
• 包含所有的语法元素，例如括号、分号、空格等。

AST:

• 提供更简洁的视图，只关注语法的语义部分。
• 省略不必要的细节，比如多余的空白符和分隔符。

假设有如下简单的表达式：

1 + 2 * 3;

其 AST 可能表示如下：

     +
    / \
   1   *
      / \
     2   3

在这个树中：
根节点是 + 运算符。左子节点是操作数 1。
右子节点是 * 运算符，它的左子节点是操作数 2，右子节点是操作数 3。

AST 提供了一种高效的方式来表示和操作程序的结构，抽象出源代码的语法信息。通过使用 AST，编译器和解释器能够更容易地进行代码分析、优化和生成，从而提高代码处理的效率和灵活性。

代码

我们从一个简单的加减法 Parser 开始，逐步实现一个简单的加法解析器，然后我们再一步一步添加更多的语法。

首先需要安装Chevrotain
大部分人使用 pnpm 也就是

pnpm install chevrotain

我个人更喜欢使用 bun

bun i chevrotain

bun add v1.1.20 (ae194892)
installed [email protected]
[271.00ms] done

安装完毕之后，创建一个 index.ts 文件

导入

import {
  createToken,
  Lexer,
  CstParser,
  tokenMatcher,
  CstNode,
} from "chevrotain";

导入 Chevrotain 的相关方法和类，用于创建词法分析器和语法解析器。

创建 Token

// AdditionOperator: 创建一个表示加法运算符的 Token，但使用 Lexer.NA，表示这个 Token 不会被直接匹配（它是个类别）。
const AdditionOperator = createToken({
  name: "AdditionOperator",
  pattern: Lexer.NA,
});
// Plus 和 Minus: 分别创建表示加号（+）和减号（-）的 Token，它们都是 AdditionOperator 的子类。
const Plus = createToken({
  name: "Plus",
  pattern: /\+/,
  categories: AdditionOperator,
});
const Minus = createToken({
  name: "Minus",
  pattern: /-/,
  categories: AdditionOperator,
});
// NumberLiteral: 创建表示数字的 Token，正则表达式 /[1-9]\d*/ 匹配 1 到 9 开头的整数（即不以 0 开头）。
const NumberLiteral = createToken({
  name: "NumberLiteral",
  pattern: /[1-9]\d*/,
});
// WhiteSpace: 创建一个表示空格的 Token，使用 Lexer.SKIPPED 表示在词法分析中跳过它（即不产生 Token）。
const WhiteSpace = createToken({
  name: "WhiteSpace",
  pattern: /\s+/,
  group: Lexer.SKIPPED,
});

词法分析器配置

const allTokens = [WhiteSpace, Plus, Minus, NumberLiteral, AdditionOperator];
// 将所有定义的 Token 放入数组 allTokens 中，并创建一个新的词法分析器 CalculatorLexer。
const CalculatorLexer = new Lexer(allTokens);

创建语法解析器

class CalculatorPure extends CstParser {
  constructor() {
    super(allTokens);

    const $ = this;
    // expression 规则: 这个规则对应一个表达式，包含一个加法表达式，后面我们再添加更多的表达式：例如乘法。
    $.RULE("expression", () => {
      $.SUBRULE($.additionExpression);
    });

    // additionExpression 规则: 这个规则定义了加法表达式的结构，首先消费一个 NumberLiteral 作为左操作数（lhs），然后消费零个或多个加法运算符和右操作数（rhs）。
    $.RULE("additionExpression", () => {
      $.CONSUME(NumberLiteral, { LABEL: "lhs" });
      $.MANY(() => {
        $.CONSUME(AdditionOperator);
        $.CONSUME2(NumberLiteral, { LABEL: "rhs" });
      });
    });

    this.performSelfAnalysis();
  }
}

创建解析器实例

const parser = new CalculatorPure();
const BaseCstVisitor = parser.getBaseCstVisitorConstructor();

class CalculatorInterpreter extends BaseCstVisitor {
  constructor() {
    super();
    this.validateVisitor();
  }

  expression(ctx) {
    return this.visit(ctx.additionExpression);
  }
  // additionExpression 方法: 处理加法表达式的逻辑。首先获取左操作数的值，然后遍历右操作数并根据运算符进行加法或减法。
  additionExpression(ctx) {
    let result = Number.parseInt(ctx.lhs[0].image, 10);

    if (ctx.rhs) {
      ctx.rhs.forEach((rhsOperand, idx) => {
        let rhsValue = Number.parseInt(rhsOperand.image, 10);
        let operator = ctx.AdditionOperator[idx];

        if (tokenMatcher(operator, Plus)) {
          result += rhsValue;
        } else {
          result -= rhsValue;
        }
      });
    }

    return result;
  }
}

这段代码定义了一个简单的加法和减法计算器，能够解析表达式并计算结果。它使用了 Chevrotain 的功能来创建 Token，构建语法规则，并实现了解释器逻辑。

执行

function eval(input: string) {
  const lexResult = CalculatorLexer.tokenize(input);
  parser.input = lexResult.tokens;
  const cst = parser.row();
  return new CalculatorInterpreter().visit(cst);
}

console.log(eval("1 + 2 + 3")); // 6
console.log(eval("1 + 2 - 3")); // 0

本文简单实现了一个加法解析器，后续我们将添加更多的语法规则。

项目地址： https://github.com/oboard/moonrepl