圍繞程式語言的詞法分析、語法解析和解釋執行，有以下幾個概念
- 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
本文簡單實現了一個加法解析器，後續我們將添加更多的語法規則。