围绕编程语言的词法分析、语法解析和解释执行，有以下几个概念
- Token（标记）：Token 是编程语言中的基本单位，它代表了语法中的一种语义元素。比如在算术表达式中，加号 (+)、减号 (-)、数字 (123) 都可以是 Token。 每个 Token 有一个类型（如 Plus, Minus, NumberLiteral），以及一个模式（用正则表达式定义），用于在源代码中识别这些 Token。
- Lexer（词法分析器）：Lexer 是将源代码字符串转换为一系列 Token 的工具。它负责识别语言的基本构成单位（Token）。 Lexer 会跳过不必要的字符（如空格），并生成有用的 Token 给后续的语法分析器处理。
- CST（Concrete Syntax Tree，具体语法树）：CST 是一种数据结构，用于表示源代码的具体语法结构。它包含了所有语法元素及其关系。 CST 允许解析器理解源代码的结构，提供对语法的完整视图，便于后续处理（如语义分析和代码生成）。
- AST（Abstract Syntax Tree，抽象语法树） 是一种表示程序结构的树形数据结构，广泛应用于编译器和解释器中。与 CST（Concrete Syntax Tree，具体语法树）不同，AST 只关注程序的逻辑结构，而忽略了语法的具体细节（如空格、括号等）。
- Parser（解析器）：Parser 是处理 Token 序列并生成 ST 的组件。它会根据语言的语法规则，判断 Token 的组合是否符合预期的结构。
- 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
本文简单实现了一个加法解析器，后续我们将添加更多的语法规则。