Crafting Interpreters：学习一-Aet

Bingliaolong 2026-08-20 11:01 Aet | 隐藏边栏 | 抢沙发 | 2 0

文章评分 2 次，平均分 5.0 ：

什么是解释器/编译器

解释器 vs 编译器：有什么区别

很多人以为"编译器把代码变成机器码，解释器直接执行代码"，这个说法不算错，但不够准确
1. 更准确的区分方式是看代码的"意义"（semantics）是何时、如何被实现的：
编译器（Compiler）：
1. 把源代码翻译成另一种语言（通常是更底层的，比如机器码、字节码，甚至是另一种高级语言），翻译完之后，"执行"这件事交给别人（CPU、虚拟机）去做
2. 编译器本身不负责运行你的程序，只负责翻译
解释器（Interpreter）：
1. 直接读取源代码（或者某种中间表示），一边理解一边执行，不产生一个独立的"翻译产物"交给别人运行

关键认知

这两者不是二选一，很多真实系统是混合体
Java：
1. 先编译成字节码（.class 文件），再由 JVM 解释执行或 JIT 编译成机器码
2. 编译 + 解释都用上了
V8（Chrome 的 JS 引擎）：
1. 先解释执行，热点代码再 JIT 编译成机器码
2. 同一段代码，执行路径会变

一段代码从文本到执行，中间发生了什么

不管是解释器还是编译器，前几个阶段几乎是通用的，可以想象成一条流水线

源代码（字符串）

│

▼

┌─────────────┐

│ 词法分析 │ 把字符串切成一个个有意义的"单词"（Token）

│ (Lexing) │ 例如: "var x = 1 + 2;" → [var] [x] [=] [1] [+] [2] [;]

└──────┬──────┘

▼

┌─────────────┐

│ 语法分析 │ 把 Token 序列按照语法规则组织成树状结构（AST）

│ (Parsing) │ 例如: 识别出这是一个"变量声明语句"，右边是一个"加法表达式"

└──────┬──────┘

▼

┌─────────────┐

│ 语义分析 │ 检查代码是否"有意义"：变量有没有定义、类型对不对

│ (可选，视语言) │ （很多动态类型脚本语言这一步很简化，或者延后到运行时检查）

└──────┬──────┘

▼

┌───┴───┐

▼ ▼

直接遍历AST 生成中间表示（字节码/IR）

执行(解释器) │

▼

虚拟机执行 / 进一步编译成机器码

这条流水线里，词法分析和语法分析这两步，不管你最终是做解释器还是编译器，几乎是完全一样的

几个贯穿全程的核心概念

Token（词法单元）：
1. 源代码里最小的、有意义的片段
2. 比如 1 + 2 里，1、+、2 各是一个 Token
3. 空格、注释这些通常在词法分析阶段就被丢弃或跳过
AST（抽象语法树，Abstract Syntax Tree）：
1. 把 Token 序列按语法规则组织成的树状结构，体现了代码的"层级关系"
2. 比如 1 + 2 * 3，AST 会体现出"乘法先算"这个优先级关系，而不是简单地从左到右排列
文法（Grammar）：
1. 描述一门语言"什么样的 Token 组合是合法的"的规则集合，是设计语法分析器之前必须先想清楚的东西
求值（Evaluation）：
1. 给一段代码/AST 一个具体的"运行结果"或"副作用"的过程，是解释器的核心动作

目标脚本语言

具备：
1. 基本数据类型：数字、字符串、布尔值、nil（空值）
2. 变量、赋值
3. 算术/比较/逻辑运算
4. 控制流：if/while/for
5. 函数（含闭包）
6. 简单的类（面向对象，可选深入）

示例

1	var age = 18 + 2;

token

var

age

;

光切开还不够，编译器还需要知道每一块是"什么性质"的东西


`#`	文本	类型	说明
`1`	`var`	关键字（`Keyword`）	语言保留字，有特殊含义，不能被用户当变量名用
`2`	`age`	标识符（`Identifier`)	用户自定义的名字（变量名/函数名/类名等）
`3`	`=`	运算符（`Operator`，具体是赋值运算符）
`4`	`18`	数字字面量（`Number Literal`）	一个具体的数值
`5`	`+`	运算符（`Operator`，具体是加法运算符）
`6`	`2`	数字字面量（`Number Literal`）
`7`	`;`	标点符号（`Punctuation`，具体是语句结束符）

问题一：age 和 var 都是字母开头，词法分析器怎么区分？
1. 分两步走，先按同一套规则识别，再做一次"关键字表查询"
2. 具体来说，词法分析器扫描到字母时，不会一开始就判断"这是关键字还是标识符"，而是统一按照"标识符规则"（字母/下划线开头，后面跟字母/数字/下划线）先把整个单词扫出来，比如扫出 var 这三个字符
3. 扫完之后，拿这个字符串去一张"关键字表"里查一下
4. 如果查到了（var 在表里），就标记为关键字类型；如果没查到（age 不在表里），就标记为标识符类型

1	关键字表 = { "var", "if", "while", "for", "fun", "class", "true", "false", "nil", ... }

问题二：18 要不要处理小数点？
1. 词法分析阶段需要考虑到，规则要设计得能兼容小数，即便这条语句里没用到

// 一个数字字面量的完整规则大概是：

数字 = 一串数字 (0-9)，可选地后面跟一个小数点和更多数字

例如: 18 合法

3.14 合法

.5 通常不合法（大多数语言要求小数点前必须有数字）

18. 是否合法，视语言设计而定（Lox 语言里我们会规定不合法，必须写成 18.0）

这就引出一个词法分析器设计上很实际的问题：
1. 扫描一个数字时，扫描器要"往前多看一个字符"（这个动作叫 lookahead，向前看/预读），才能判断到底要不要把小数点也吞进来
2. 比如扫描到 18 后面这个字符，如果是 . 并且 . 后面紧跟的还是数字，就继续吞进来组成 18.5；
3. 如果 . 后面不是数字，就不能把 . 也当作这个数字的一部分
这种"预读一个字符再决定"的技巧，是词法分析器实现中一个非常核心、会反复用到的手法

词法分析（`Lexer/Scanner`）实现

第一步：定义 `Token` 是什么

一个 Token 光有"文本内容"还不够，词法分析器至少要给每个 Token 附上这些信息

#ifndef TOKEN_H

#define TOKEN_H

#include <string>

enum class TokenType {

// 单字符 Token

LEFT_PAREN,

RIGHT_PAREN,

LEFT_BRACE,

RIGHT_BRACE,

COMMA,

DOT,

MINUS,

PLUS,

SEMICOLON,

SLASH,

STAR,

// 一到两字符 Token（需要预读判断）

BANG,

BANG_EQUAL,

EQUAL,

EQUAL_EQUAL,

GREATER,

GREATER_EQUAL,

LESS,

LESS_EQUAL,

// 字面量

IDENTIFIER,

STRING,

NUMBER,

// 关键字

AND,

CLASS,

ELSE,

FALSE,

FUN,

FOR,

IF,

NIL,

OR,

PRINT,

RETURN,

SUPER,

THIS,

TRUE,

VAR,

WHILE,

END_OF_FILE

};

struct Token {

TokenType type;

std::string lexeme; // 原始文本，比如 "18"、"age"

int line; // 所在行号，用于报错定位

// 字面量的值，数字和字符串各自存一份

// （先用简单方式存，后面几课我们会引入更通用的 Value 类型）

double numberValue = 0;

std::string stringValue;

};

#endif // TOKEN_H

为什么要记录 line（行号）？
1. 因为词法分析阶段发现的任何问题（比如遇到一个不认识的字符），都要能告诉用户"第几行出错了"，这是编译器友好性的基本要求，从一开始就要设计进去，不要等报错系统写不出来了再回头加

第二步：`Scanner` 类的骨架

词法分析的核心逻辑其实就是一个循环：
1. 不断地看当前字符是什么，决定要生成什么 Token，然后把"指针"往前移动

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

#include <iostream>

#include <string>

#include <unordered_map>

#include <vector>

#include "token.h"

class Scanner {

public:

Scanner(const std::string& source) : source(source) {}

std::vector<Token> scanTokens() {

while (!isAtEnd()) {

start = current; // 每次循环开始，记录这个 Token 的起始位置

scanToken();

}

tokens.push_back({TokenType::END_OF_FILE, "", line});

return tokens;

}

private:

std::string source;

std::vector<Token> tokens;

int start = 0; // 当前 Token 的起始下标

int current = 0; // 当前正在看的字符下标

int line = 1;

bool isAtEnd() { return current >= (int)source.size(); }

// 读取当前字符并前进一位（类似"消费"掉这个字符）

char advance() { return source[current++]; }

// 只看当前字符，不前进（这就是"预读"，lookahead）

char peek() {

if (isAtEnd())

return '\0';

return source[current];

}

// 看当前字符的下一个字符（预读两位，扫小数点时会用到）

char peekNext() {

if (current + 1 >= (int)source.size())

return '\0';

return source[current + 1];

}

// 如果当前字符是期望的字符，就消费掉它并返回 true（用于扫两字符运算符）

bool match(char expected) {

if (isAtEnd())

return false;

if (source[current] != expected)

return false;

current++;

return true;

}

void addToken(TokenType type) {

std::string text = source.substr(start, current - start);

tokens.push_back({type, text, line});

}

void scanToken() {

char c = advance();

switch (c) {

// 单字符 Token，直接对应

case '(':

addToken(TokenType::LEFT_PAREN);

break;

case ')':

addToken(TokenType::RIGHT_PAREN);

break;

case '{':

addToken(TokenType::LEFT_BRACE);

break;

case '}':

addToken(TokenType::RIGHT_BRACE);

break;

case ',':

addToken(TokenType::COMMA);

break;

case '.':

addToken(TokenType::DOT);

break;

case '-':

addToken(TokenType::MINUS);

break;

case '+':

addToken(TokenType::PLUS);

break;

case ';':

addToken(TokenType::SEMICOLON);

break;

case '*':

addToken(TokenType::STAR);

break;

// 一到两字符 Token，需要 match() 预读判断

case '!':

addToken(match('=') ? TokenType::BANG_EQUAL : TokenType::BANG);

break;

case '=':

addToken(match('=') ? TokenType::EQUAL_EQUAL : TokenType::EQUAL);

break;

case '<':

addToken(match('=') ? TokenType::LESS_EQUAL : TokenType::LESS);

break;

case '>':

addToken(match('=') ? TokenType::GREATER_EQUAL : TokenType::GREATER);

break;

// 斜杠比较特殊：可能是除号，也可能是注释的开头 "//"

case '/':

if (match('/')) {

// 是注释，一路吃到这一行结束，不生成 Token

while (peek() != '\n' && !isAtEnd())

advance();

} else {

addToken(TokenType::SLASH);

}

break;

// 空白字符，直接跳过，不生成 Token

case ' ':

case '\r':

case '\t':

break;

case '\n':

line++;

break;

// 字符串字面量

case '"':

scanString();

break;

default:

if (isDigit(c)) {

scanNumber();

} else if (isAlpha(c)) {

scanIdentifier();

} else {

// 遇到不认识的字符，报错（这里先简单打印，后面几课会做统一的错误处理机制）

std::cerr << "[line " << line << "] Unexpected character: " << c

<< std::endl;

}

break;

}

void scanString() {

while (peek() != '"' && !isAtEnd()) {

if (peek() == '\n')

line++; // 允许字符串跨行，同时记得更新行号

advance();

}

if (isAtEnd()) {

std::cerr << "[line " << line << "] Unterminated string." << std::endl;

return;

}

advance(); // 吃掉结尾的 "

// 取出引号之间的内容（掐头去尾，去掉两边的引号本身）

std::string value = source.substr(start + 1, current - start - 2);

Token token{TokenType::STRING, source.substr(start, current - start), line};

token.stringValue = value;

tokens.push_back(token);

}

bool isDigit(char c) { return c >= '0' && c <= '9'; }

void scanNumber() {

while (isDigit(peek()))

advance();

// 关键的一步：预读判断是否有小数部分

if (peek() == '.' && isDigit(peekNext())) {

advance(); // 吃掉小数点

while (isDigit(peek()))

advance();

}

std::string text = source.substr(start, current - start);

Token token{TokenType::NUMBER, text, line};

token.numberValue = std::stod(text);

tokens.push_back(token);

}

bool isAlpha(char c) {

return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == '_';

}

bool isAlphaNumeric(char c) { return isAlpha(c) || isDigit(c); }

// 关键字表，作为类的静态成员或全局常量

const std::unordered_map<std::string, TokenType> keywords = {

{"and", TokenType::AND}, {"class", TokenType::CLASS},

{"else", TokenType::ELSE}, {"false", TokenType::FALSE},

{"for", TokenType::FOR}, {"fun", TokenType::FUN},

{"if", TokenType::IF}, {"nil", TokenType::NIL},

{"or", TokenType::OR}, {"print", TokenType::PRINT},

{"return", TokenType::RETURN}, {"super", TokenType::SUPER},

{"this", TokenType::THIS}, {"true", TokenType::TRUE},

{"var", TokenType::VAR}, {"while", TokenType::WHILE}};

void scanIdentifier() {

while (isAlphaNumeric(peek()))

advance();

std::string text = source.substr(start, current - start);

// 先按标识符扫完整个单词，再去关键字表里查一次

auto it = keywords.find(text);

TokenType type =

(it != keywords.end()) ? it->second : TokenType::IDENTIFIER;

addToken(type);

}

};

第三步：处理字符串字面量

void scanString() {

while (peek() != '"' && !isAtEnd()) {

if (peek() == '\n') line++; // 允许字符串跨行，同时记得更新行号

advance();

}

if (isAtEnd()) {

std::cerr << "[line " << line << "] Unterminated string." << std::endl;

return;

}

advance(); // 吃掉结尾的 "

// 取出引号之间的内容（掐头去尾，去掉两边的引号本身）

std::string value = source.substr(start + 1, current - start - 2);

Token token{TokenType::STRING, source.substr(start, current - start), line};

token.stringValue = value;

tokens.push_back(token);

}

注意这里一个容易被忽略的设计点：
1. lexeme（原始文本，含引号）和 stringValue（真正的字符串内容，不含引号）我们分开存了两份
2. 这是因为将来做错误提示时，你可能想显示用户写的原始文本
3. 而解释器求值时，用的是去掉引号后的真实值
4. 原始文本和"语义值"是两个不同的东西，要分开保存，这个设计思路后面在数字、布尔值上也会延续

第四步：处理数字字面量（预读小数点）

bool isDigit(char c) { return c >= '0' && c <= '9'; }

void scanNumber() {

while (isDigit(peek())) advance();

// 关键的一步：预读判断是否有小数部分

if (peek() == '.' && isDigit(peekNext())) {

advance(); // 吃掉小数点

while (isDigit(peek())) advance();

}

std::string text = source.substr(start, current - start);

Token token{TokenType::NUMBER, text, line};

token.numberValue = std::stod(text);

tokens.push_back(token);

}

这里 peek() == '.' && isDigit(peekNext()) 这一行
1. 必须同时满足"当前是小数点"和"小数点后面紧跟数字"，才把小数点吞进来，否则像 18. 这种后面没有数字的情况就不会被错误地当成小数处理

第五步：处理标识符与关键字

bool isAlpha(char c) {

return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == '_';

}

bool isAlphaNumeric(char c) { return isAlpha(c) || isDigit(c); }

// 关键字表，作为类的静态成员或全局常量

const std::unordered_map<std::string, TokenType> keywords = {

{"and", TokenType::AND}, {"class", TokenType::CLASS},

{"else", TokenType::ELSE}, {"false", TokenType::FALSE},

{"for", TokenType::FOR}, {"fun", TokenType::FUN},

{"if", TokenType::IF}, {"nil", TokenType::NIL},

{"or", TokenType::OR}, {"print", TokenType::PRINT},

{"return", TokenType::RETURN}, {"super", TokenType::SUPER},

{"this", TokenType::THIS}, {"true", TokenType::TRUE},

{"var", TokenType::VAR}, {"while", TokenType::WHILE}

};

void scanIdentifier() {

while (isAlphaNumeric(peek())) advance();

std::string text = source.substr(start, current - start);

// 先按标识符扫完整个单词，再去关键字表里查一次

auto it = keywords.find(text);

TokenType type = (it != keywords.end()) ? it->second : TokenType::IDENTIFIER;

addToken(type);

}

语法分析（`Parsing`）

目标

设计 AST（抽象语法树）节点
写一个递归下降解析器（Recursive Descent Parser），把 token 序列变成 AST
用一个 AstPrinter 把树打印出来验证

上下文无关文法（`Context-Free Grammar`）

专门描述"表达式该怎么解析"
→ 读作"由...组成"，左边是一个语法规则的名字，右边是它的定义
表示"或者"（几选一）
( ... ) 只是分组，跟数学里的括号一个作用
* 表示"前面这坨内容可以重复 0 次或多次"（跟正则表达式里的 * 一个意思）
全大写的 NUMBER、STRING 是终结符（terminal）
1. 对应Scanner 吐出来的具体 token，不能再往下展开了
小写的 equality、comparison 这些是非终结符（non-terminal）
1. 还得继续展开成别的规则，直到展开成终结符为止

expression → equality

equality → comparison ( ( "!=" | "==" ) comparison )*

comparison → term ( ( ">" | ">=" | "<" | "<=" ) term )*

term → factor ( ( "-" | "+" ) factor )*

factor → unary ( ( "/" | "*" ) unary )*

unary → ( "!" | "-" ) unary | primary

这套规则在干嘛：编码"优先级"
1. 这 6 行规则其实是从低优先级到高优先级排的一条链：

expression （最外层，优先级最低）

→ equality

→ comparison

→ term (+ -)

→ factor (* /)

→ unary (! -，一元运算符)

→ primary （最底层：数字、字符串、括号...）

为什么这么排？
1. 因为递归下降解析器是"从外往里剥洋葱"的：
2. 先假设整个表达式是最低优先级的运算（== !=），如果没有就往里剥一层看是不是 > < >= <=，再往里剥是不是 + -，再往里是 * /，最后剥到最里面才是一个具体的数字/字符串/括号表达式
3. 这样"层层剥"天然就实现了优先级——* 比 + 先被"看到"（更靠里），所以会先结合
逐条对着看

equality → comparison ( ( "!=" | "==" ) comparison )*

// 意思是：

// 一个"相等性表达式"，先是一个 comparison，后面可以跟任意多次"!= 或 == 再接一个 comparison"。

// → 这就是为什么 a == b == c 能被解析（多个 == 链在一起），对应你 Parser 里会写一个 while 循环

comparison → term ( ( ">" | ">=" | "<" | "<=" ) term )*

// 右边分两部分

// 开头必须是一个 term（也就是一个加减表达式，比如 1 + 2）

// 这是"起手式"，任何比较表达式都得先有个左操作数

// 后面跟着 ( ( ">" | ">=" | "<" | "<=" ) term )*

// 意思是"整体重复 0 次或多次"。每重复一次，就是：

// 先匹配一个比较运算符：>、>=、<、<= 里选一个（| 是或）

// 再跟一个 term（右操作数）

term → factor ( ( "-" | "+" ) factor )*

// 一个"加减表达式"：先是一个 factor，后面可以跟任意多个 + factor 或 - factor。

// → 对应 1 + 2 - 3 + 4

factor → unary ( ( "/" | "*" ) unary )*

// 左边 factor：代表"一个乘除表达式"

// 右边：

// 先必须有一个 unary（一元表达式，比如 -5 或 !true 或单纯一个 5）

// 后面可以跟任意多组「/ 或 * 再接一个 unary」

// 一个乘除表达式 = 一个 unary，后面跟 0 个或多个「(/ 或 *) + unary」

unary → ( "!" | "-" ) unary | primary

// 这条不一样，是"二选一"而不是"重复"：

// 要么是 ! 或 - 后面跟一个 unary（自己调用自己，处理 !!true、--5 这种连续一元运算符）

// 要么直接就是一个 primary（没有一元运算符了，往下剥到底）

// 最底层，剥无可剥了：

// 要么是一个具体字面量，要么是 ( expression )

// 注意这里又绕回 expression，这就是为什么括号里能嵌套任意复杂的表达式，比如 (1 + (2 * 3))

用一个例子走一遍

// 拿 1 + 2 * 3 举例，按上面的规则展开会长这样

expression → equality → comparison → term

term: factor(1) ... 匹配到 "+" ... factor(2*3)

↑ 这里 factor 会继续展开:

factor → unary → primary(2) ... 匹配到 "*" ... unary → primary(3)

// 结果就是 1 和 (2 * 3) 用 + 结合，而不是 (1 + 2) 和 3 用 * 结合

// * 因为在更靠里的 factor 层，天然比 term 层的 + 先被处理

// 优先级就这样"免费"地编码进了文法结构里，不需要额外写优先级判断逻辑

解读

任意一个表达式首先可以把它按是一个相等表达式来解析

相等表达式又可以按是比较表达式和其右部（右部可以出现0到n次）（右部由 ==,!=这两个符号中的一个和另一个比较表达式组成）组成来解析

比较表达式又可以按是加减表达式和其右部（右部可以出现0到n次）（右部由 >,>=,<,<=这四个符号中的一个和另一个加减表达式组成）组成来解析

加减表达式又可以按是乘法表达式和其右部（右部可以出现0到n次）（右部由 -,+这两个符号中的一个和另一个乘法表达式组成）组成来解析

乘法表达式又可以按是一元表达式和其右部（右部可以出现0到n次）（右部由 /,*这两个符号中的一个和另一个一元表达式组成）组成来解析

一元表达式最后可以按要么是一个基本表达式，要么是!,-这两个符号中的一个结合一个右部（右部还是一个一元表达式）来解析

基本表达式是NUMBER,STRING,true,false,nil，表达式（如果是表达式，又可以进行细化解析了）中的一个

`AST` 节点定义

对应 AST 只需要 4 种节点：Binary、Grouping、Literal、Unary
1. 文法有 7 条规则，但 AST 只需要 4 种节点，因为好几条规则最终产生的树形状是一样的
关键区分：规则管"怎么解析"，节点管"树长什么样"

// equality、comparison、term、factor 这 4 条规则

// 虽然处理的运算符不同（==/!=，>/<，+/-，*//）,但它们的结构完全相同：

// 都是"左操作数 + 运算符 + 右操作数"

// 这四种情况在树上长得一模一样——都是一个节点，带一个左子树、一个运算符、一个右子树

// 所以它们共用同一种节点类型：Binary

// 所以：4 条规则（equality/comparison/term/factor）收敛成 1 种节点（Binary）

// unary 对应 Unary

// primary 分裂成 Literal 和 Grouping 两种

// expression 本身不对应任何节点

为什么要故意这样设计
1. 文法规则的"层数"是为了编码运算符优先级——层数越多，优先级判断越精细
2. 但 AST 只关心"这段代码最终该怎么求值/怎么执行"

`Expr.h`

#ifndef EXPR_H

#define EXPR_H

#include <any>

#include <memory>

#include <string>

#include "token.h"

struct Expr;

using ExprPtr = std::shared_ptr<Expr>;

struct Binary;

struct Grouping;

struct Literal;

struct Unary;

struct Variable;

// 所有对 AST 的操作（打印、求值...）都实现这个接口

struct ExprVisitor {

virtual std::any visitBinaryExpr(const Binary& expr) = 0;

virtual std::any visitGroupingExpr(const Grouping& expr) = 0;

virtual std::any visitLiteralExpr(const Literal& expr) = 0;

virtual std::any visitUnaryExpr(const Unary& expr) = 0;

virtual std::any visitVariableExpr(const Variable& expr) = 0;

virtual ~ExprVisitor() = default;

};

struct Expr {

virtual std::any accept(ExprVisitor& visitor) = 0;

virtual ~Expr() = default;

};

struct Binary : Expr {

ExprPtr left;

Token op;

ExprPtr right;

Binary(ExprPtr left, Token op, ExprPtr right)

: left(std::move(left)), op(std::move(op)), right(std::move(right)) {}

std::any accept(ExprVisitor& v) override { return v.visitBinaryExpr(*this); }

};

struct Grouping : Expr {

ExprPtr expression;

explicit Grouping(ExprPtr expression) : expression(std::move(expression)) {}

std::any accept(ExprVisitor& v) override {

return v.visitGroupingExpr(*this);

}

};

// Literal 直接用 std::any 存字面量的值：double / std::string / bool / 或空(nil)

struct Literal : Expr {

std::any value;

explicit Literal(std::any value) : value(std::move(value)) {}

std::any accept(ExprVisitor& v) override { return v.visitLiteralExpr(*this); }

};

struct Unary : Expr {

Token op;

ExprPtr right;

Unary(Token op, ExprPtr right) : op(std::move(op)), right(std::move(right)) {}

std::any accept(ExprVisitor& v) override { return v.visitUnaryExpr(*this); }

};

// primary → ... | IDENTIFIER

struct Variable : Expr {

Token name;

explicit Variable(Token name) : name(std::move(name)) {}

std::any accept(ExprVisitor& v) override {

return v.visitVariableExpr(*this);

}

};

#endif // EXPR_H

`AstPrinter.h`

#ifndef AST_PRINTER_H

#define AST_PRINTER_H

#include "expr.h"

#include <sstream>

struct AstPrinter : ExprVisitor {

std::string print(Expr& expr) {

return std::any_cast<std::string>(expr.accept(*this));

}

std::any visitBinaryExpr(const Binary& e) override {

return parenthesize(e.op.lexeme, {e.left.get(), e.right.get()});

}

std::any visitGroupingExpr(const Grouping& e) override {

return parenthesize("group", {e.expression.get()});

}

std::any visitLiteralExpr(const Literal& e) override {

if (!e.value.has_value())

return std::string("nil");

if (e.value.type() == typeid(double))

return std::to_string(std::any_cast<double>(e.value));

if (e.value.type() == typeid(std::string))

return std::any_cast<std::string>(e.value);

if (e.value.type() == typeid(bool))

return std::string(std::any_cast<bool>(e.value) ? "true" : "false");

return std::string("?");

}

std::any visitUnaryExpr(const Unary& e) override {

return parenthesize(e.op.lexeme, {e.right.get()});

}

std::any visitVariableExpr(const Variable& e) override {

return e.name.lexeme;

}

private:

std::string parenthesize(const std::string& name,

std::initializer_list<Expr*> exprs) {

std::ostringstream ss;

ss << "(" << name;

for (auto* e : exprs)

ss << " " << std::any_cast<std::string>(e->accept(*this));

ss << ")";

return ss.str();

}

};

#endif // AST_PRINTER_H

`Parser.h`

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

#ifndef PARSER_H

#define PARSER_H

#include <iostream>

#include <memory>

#include <stdexcept>

#include <vector>

#include "expr.h"

#include "stmt.h"

#include "token.h"

class Parser {

public:

Parser(const std::vector<Token>& tokens) : tokens(tokens) {}

std::vector<StmtPtr> parse() {

std::vector<StmtPtr> statements;

while (!isAtEnd()) {

statements.push_back(declaration());

}

return statements;

}

private:

// declaration → varDecl | statement

StmtPtr declaration() {

try {

if (match({TokenType::VAR}))

return varDeclaration();

return statement();

} catch (const std::runtime_error&) {

synchronize(); // 出错时跳到下一条语句，尽量继续解析、多报几个错误

return nullptr;

}

// varDecl → "var" IDENTIFIER ( "=" expression )? ";"

StmtPtr varDeclaration() {

Token name = consume(TokenType::IDENTIFIER, "Expect variable name.");

ExprPtr initializer = nullptr;

if (match({TokenType::EQUAL})) {

initializer = expression();

}

consume(TokenType::SEMICOLON, "Expect ';' after variable declaration.");

return std::make_shared<Var>(name, initializer);

}

// statement → exprStmt | printStmt

StmtPtr statement() {

if (match({TokenType::PRINT}))

return printStatement();

return expressionStatement();

}

// printStmt → "print" expression ";"

StmtPtr printStatement() {

ExprPtr value = expression();

consume(TokenType::SEMICOLON, "Expect ';' after value.");

return std::make_shared<Print>(value);

}

// exprStmt → expression ";"

StmtPtr expressionStatement() {

ExprPtr expr = expression();

consume(TokenType::SEMICOLON, "Expect ';' after expression.");

return std::make_shared<Expression>(expr);

}

// 恐慌模式恢复：出错后跳到下一条语句的开头，避免一个错误引发一连串虚假错误

void synchronize() {

advance();

while (!isAtEnd()) {

if (previous().type == TokenType::SEMICOLON)

return;

switch (peek().type) {

case TokenType::CLASS:

case TokenType::FUN:

case TokenType::VAR:

case TokenType::FOR:

case TokenType::IF:

case TokenType::WHILE:

case TokenType::PRINT:

case TokenType::RETURN:

return;

default:

break;

}

advance();

}

private:

const std::vector<Token>& tokens;

int current = 0;

// ---- 7 条规则，对照文法一条一条来 ----

// expression → equality

ExprPtr expression() { return equality(); }

// equality → comparison ( ( "!=" | "==" ) comparison )*

ExprPtr equality() {

ExprPtr expr = comparison();

while (match({TokenType::BANG_EQUAL, TokenType::EQUAL_EQUAL})) {

Token op = previous();

ExprPtr right = comparison();

expr = std::make_shared<Binary>(expr, op, right);

}

return expr;

}

// comparison → term ( ( ">" | ">=" | "<" | "<=" ) term )*

ExprPtr comparison() {

ExprPtr expr = term();

while (match({TokenType::GREATER, TokenType::GREATER_EQUAL, TokenType::LESS,

TokenType::LESS_EQUAL})) {

Token op = previous();

ExprPtr right = term();

expr = std::make_shared<Binary>(expr, op, right);

}

return expr;

}

// term → factor ( ( "-" | "+" ) factor )*

ExprPtr term() {

ExprPtr expr = factor();

while (match({TokenType::MINUS, TokenType::PLUS})) {

Token op = previous();

ExprPtr right = factor();

expr = std::make_shared<Binary>(expr, op, right);

}

return expr;

}

// factor → unary ( ( "/" | "*" ) unary )*

ExprPtr factor() {

ExprPtr expr = unary();

while (match({TokenType::SLASH, TokenType::STAR})) {

Token op = previous();

ExprPtr right = unary();

expr = std::make_shared<Binary>(expr, op, right);

}

return expr;

}

// unary → ( "!" | "-" ) unary | primary

ExprPtr unary() {

if (match({TokenType::BANG, TokenType::MINUS})) {

Token op = previous();

ExprPtr right = unary(); // 递归：处理 !!true、--5 这种连续一元符

return std::make_shared<Unary>(op, right);

}

return primary();

}

ExprPtr primary() {

if (match({TokenType::FALSE}))

return std::make_shared<Literal>(false);

if (match({TokenType::TRUE}))

return std::make_shared<Literal>(true);

if (match({TokenType::NIL}))

return std::make_shared<Literal>(std::any{});

if (match({TokenType::NUMBER})) {

return std::make_shared<Literal>(previous().numberValue);

}

if (match({TokenType::STRING})) {

return std::make_shared<Literal>(previous().stringValue);

}

if (match({TokenType::IDENTIFIER})) {

return std::make_shared<Variable>(previous());

}

if (match({TokenType::LEFT_PAREN})) {

ExprPtr expr = expression(); // 绕回顶层，支持任意嵌套

consume(TokenType::RIGHT_PAREN, "Expect ')' after expression.");

return std::make_shared<Grouping>(expr);

}

throw error(peek(), "Expect expression.");

}

// ---- 辅助函数：跟 Scanner 里的 peek/advance/match 是同一套思路 ----

bool match(std::initializer_list<TokenType> types) {

for (auto type : types) {

if (check(type)) {

advance();

return true;

}

return false;

}

bool check(TokenType type) {

if (isAtEnd())

return false;

return peek().type == type;

}

Token advance() {

if (!isAtEnd())

current++;

return previous();

}

bool isAtEnd() { return peek().type == TokenType::END_OF_FILE; }

Token peek() { return tokens[current]; }

Token previous() { return tokens[current - 1]; }

Token consume(TokenType type, const std::string& message) {

if (check(type))

return advance();

throw error(peek(), message);

}

std::runtime_error error(const Token& token, const std::string& message) {

std::cerr << "[line " << token.line << "] Error";

if (token.type == TokenType::END_OF_FILE)

std::cerr << " at end";

else

std::cerr << " at '" << token.lexeme << "'";

std::cerr << ": " << message << std::endl;

return std::runtime_error(message);

}

};

#endif // PARSER_H

`Token.h`

#ifndef TOKEN_H

#define TOKEN_H

#include <string>

enum class TokenType {

// 单字符 Token

LEFT_PAREN,

RIGHT_PAREN,

LEFT_BRACE,

RIGHT_BRACE,

COMMA,

DOT,

MINUS,

PLUS,

SEMICOLON,

SLASH,

STAR,

// 一到两字符 Token（需要预读判断）

BANG,

BANG_EQUAL,

EQUAL,

EQUAL_EQUAL,

GREATER,

GREATER_EQUAL,

LESS,

LESS_EQUAL,

// 字面量

IDENTIFIER,

STRING,

NUMBER,

// 关键字

AND,

CLASS,

ELSE,

FALSE,

FUN,

FOR,

IF,

NIL,

OR,

PRINT,

RETURN,

SUPER,

THIS,

TRUE,

VAR,

WHILE,

END_OF_FILE

};

struct Token {

TokenType type;

std::string lexeme; // 原始文本，比如 "18"、"age"

int line; // 所在行号，用于报错定位

// 字面量的值，数字和字符串各自存一份

// （先用简单方式存，后面几课我们会引入更通用的 Value 类型）

double numberValue = 0;

std::string stringValue;

};

#endif // TOKEN_H

`main.cpp`

#include <fstream>

#include <iostream>

#include <sstream>

#include "ast_printer.h"

#include "expr.h"

#include "interpreter.h"

#include "parser.h"

#include "scanner.h"

#include "token.h"

void run(const std::string& source) {

// 1. 词法分析：源码 -> token 流

Scanner scanner(source);

std::vector<Token> tokens = scanner.scanTokens();

// 调试：把 token 打出来看看（跟你之前 demo 里的输出一样）

std::cout << "---- Tokens ----\n";

for (auto& token : tokens) {

std::cout << (int)token.type << "\t" << token.lexeme << "\n";

}

// 2. 语法分析：token 流 -> AST

Parser parser(tokens);

std::vector<StmtPtr> statements = parser.parse();

std::cout << "Parsed " << statements.size() << " statement(s).\n";

// 3. 打印 AST，肉眼验证树的结构对不对

// std::cout << "---- AST ----\n";

// AstPrinter printer;

// std::cout << printer.print(*expression) << std::endl;

Interpreter interpreter;

interpreter.interpret(statements);

}

// 从文件读取源码并运行

void runFile(const std::string& path) {

std::ifstream file(path);

if (!file) {

std::cerr << "Could not open file: " << path << std::endl;

return;

}

std::stringstream buffer;

buffer << file.rdbuf();

run(buffer.str());

}

// 交互式 REPL：一行一行输入表达式，立刻看到 AST

void runPrompt() {

std::string line;

std::cout << "Lox AST REPL (输入表达式，Ctrl+D / Ctrl+Z 退出)\n";

while (true) {

std::cout << "> ";

if (!std::getline(std::cin, line))

break;

if (line.empty())

continue;

run(line);

}

int main() {

std::string source = "var a = 10.2; var b = 2; print a + b;";

run(source);

return 0;

}

什么是解释器/编译器
解释器 vs 编译器：有什么区别
关键认知
一段代码从文本到执行，中间发生了什么
几个贯穿全程的核心概念
目标脚本语言
示例
词法分析（Lexer/Scanner）实现
第一步：定义 Token 是什么
第二步：Scanner 类的骨架
第三步：处理字符串字面量
第四步：处理数字字面量（预读小数点）
第五步：处理标识符与关键字
语法分析（Parsing）
目标
上下文无关文法（Context-Free Grammar）
AST 节点定义
Expr.h
AstPrinter.h
Parser.h
Token.h
main.cpp

声明：本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！

Bingliaolong 关注：0 粉丝：0

Everything will be better.

你可能也喜欢

热评文章

* 暂无

什么是解释器/编译器

解释器 vs 编译器：有什么区别

关键认知

一段代码从文本到执行，中间发生了什么

几个贯穿全程的核心概念

目标脚本语言

示例

词法分析（`Lexer/Scanner`）实现

第一步：定义 `Token` 是什么

第二步：`Scanner` 类的骨架

第三步：处理字符串字面量

第四步：处理数字字面量（预读小数点）

第五步：处理标识符与关键字

语法分析（`Parsing`）

目标

上下文无关文法（`Context-Free Grammar`）

`AST` 节点定义

`Expr.h`

`AstPrinter.h`

`Parser.h`

`Token.h`

`main.cpp`

你可能也喜欢

热评文章

发表评论

标签云集

2026 年 8 月
一	二	三	四	五	六	日
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

Crafting Interpreters：学习一

什么是解释器/编译器

解释器 vs 编译器：有什么区别

关键认知

一段代码从文本到执行，中间发生了什么

几个贯穿全程的核心概念

目标脚本语言

示例

词法分析（Lexer/Scanner）实现

第一步：定义 Token 是什么

第二步：Scanner 类的骨架

第三步：处理字符串字面量

第四步：处理数字字面量（预读小数点）

第五步：处理标识符与关键字

语法分析（Parsing）

目标

上下文无关文法（Context-Free Grammar）

AST 节点定义

Expr.h

AstPrinter.h

Parser.h

Token.h

main.cpp

你可能也喜欢

热评文章

发表评论

标签云集

词法分析（`Lexer/Scanner`）实现

第一步：定义 `Token` 是什么

第二步：`Scanner` 类的骨架

语法分析（`Parsing`）

上下文无关文法（`Context-Free Grammar`）

`AST` 节点定义

`Expr.h`

`AstPrinter.h`

`Parser.h`

`Token.h`

`main.cpp`