源代码字符串
↓
词法分析（lexer）教学用 tokenizer
↓
【语法分析（parser）】
├── 递归下降 ← 教的是这个
├── LR / LALR
├── Pratt
└── 其他方法
↓
AST（抽象语法树）
↓
解释 / 编译 / 求值
# 一、解释器的整体结构：REPL 循环
解释器的核心是一个 REPL 循环（Read-Eval-Print Loop）：
def repl():
while True:
try:
input_str = input(">>> ") # 读取输入
if input_str == "quit": break
ast = parse(input_str) # 将字符串解析为抽象语法树 (AST)
result = eval_scheme(ast, env) # 求值
print(result) # 打印结果
except Exception as e:
print(f"Error: {e}")
- Read (读取)：将用户输入的字符串（如
(+ 2 3)）解析成 Python 数据结构（通常是列表或元组，称为 AST，抽象语法树）。 - Eval (求值)：根据 AST 和当前环境，计算出表达式的值。
- Print (打印)：将结果以可读形式输出。
- Loop (循环)：持续等待用户输入，直到退出。
关键点：整个解释器就是不断运行这个循环！
# 二、词法分析(lexer)
教学这里的 tokenize_lines 就是一个 tokenizer 是简易的 lexer：
# 一、词法分析到底在做什么？
一句话版：
词法分析（Lexical Analysis）把“字符流”切分成“有意义的最小单位（token）”。
它只解决两个问题：
- 边界：一个 token 从哪开始，到哪结束？
- 类别：这是数字？符号？括号？
⚠️ 词法分析不解决：
- 结构关系
- 嵌套层级
- 程序含义
# 二、从字符流开始（Scheme 例子）
输入代码：
(+ 2 (* 3 4))
计算机最初看到的是：
'(' '+' ' ' '2' ' ' '(' '*' ' ' '3' ' ' '4' ')' ')'
这里只有字符，没有“词”。
# 三、词法分析的输出是什么？
对 61A Scheme 来说，词法分析的输出是：
['(', '+', '2', '(', '*', '3', '4', ')', ')']
特点：
- 每个 token 是 字符串
- 顺序不变
- 没有层级结构
# 四、一个极简 Scheme tokenizer（教学版）
下面这个代码非常接近 61A 的实现思想，而且一眼能懂。
def tokenize_line(line):
tokens = []
i = 0
while i < len(line):
ch = line[i]
# 1️⃣ 跳过空白
if ch.isspace():
i += 1
continue
# 2️⃣ 括号是单独 token
if ch == '(' or ch == ')':
tokens.append(ch)
i += 1
continue
# 3️⃣ 读一个“原子”（数字 / 符号）
start = i
while i < len(line) and not line[i].isspace() and line[i] not in '()':
i += 1
tokens.append(line[start:i])
return tokens
# 五、逐步跑一遍这个 tokenizer
点击展开
输入：
tokenize_line("(+ 2 (* 3 4))")第一步：读 '('
ch == '('- 直接加入 token
['(']第二步：读 '+'
- 不是空白
- 不是括号
- 进入"原子读取"
['(', '+']第三步：读 '2'
['(', '+', '2']第四步：读 '('
['(', '+', '2', '(']第五步：读 '*', '3', '4', ')', ')'
最终得到：
['(', '+', '2', '(', '*', '3', '4', ')', ')']📌 到这里为止，词法分析结束
# 六、注意：此时还没有 AST
这是很多人会混的点。
现在只有：
['(', '+', '2', '(', '*', '3', '4', ')', ')']
你无法仅凭它说：
- 哪个
(对应哪个) (* 3 4)是不是一个整体*是不是+的参数
👉 这些都需要 语法分析
# 七、token 是字符串，那类型什么时候确定？
在 Scheme / 61A 里：
'2'→ 整数 2'+'→ Symbol('+')
这些转换发生在 解析阶段：
def parse_atom(token):
try:
return int(token)
except ValueError:
return Symbol(token)
📌 lexer 不关心类型，只关心边界
# 八、词法分析 vs 语法分析（对照表）
| 阶段 | 输入 | 输出 | 关心 |
|---|---|---|---|
| 词法分析 | 字符 | token（字符串） | 边界 |
| 语法分析 | token | AST | 结构 |
| 求值 | AST | 值 | 语义 |
词法分析是编译/解释流程中的第一阶段，其作用是将源代码的字符流切分为一系列线性的 token。以 Scheme 为例，词法分析只识别括号、符号与数字等最小语法单元，并不建立任何层级或结构关系。AST 的构建发生在随后的语法分析阶段，而非词法分析阶段。
如果我给你 token：
['(', '+', '2', '(', '*', '3', '4', ')', ')']
你不能回答的问题是：
“这个表达式的根节点是什么？”
因为那是 parser 的工作。
# 三、语法分析 (parser)
语法分析（parsing）就是在 lexer 把字符变成 token 之后，负责把这一串线性的 token，按“语法规则”组装成一棵结构化的树——抽象语法树 AST。
可以用一句话概括：
lexer：这几个字符是一个“词”（token）；
parser：这些“词”怎么组成合法的“句子”（程序结构）。
# 1. 输入 / 输出长什么样？
继续用你之前的 Scheme 例子：
源代码：
(+ 2 (* 3 4))
lexer 输出的 token 流：
['(', '+', '2', '(', '*', '3', '4', ')', ')']
语法分析器（parser） 要做的事：
- 看这串 token 的“括号结构”和“排列方式”
- 按 Scheme 的语法规则，把它拼成一个嵌套结构（AST）
在 61A 的 Scheme 解释器里，这个 AST 大概是：
['+', 2, ['*', 3, 4]]
# 或者在项目里的真实形式：用 Pair / nil 表示
# Pair('+', Pair(2, Pair(Pair('*', Pair(3, Pair(4, nil))), nil)))
对应成一棵树画出来就是：
+
/ \
2 *
/ \
3 4
这一步“从线性变成树”的过程，就是语法分析。
# 2. 它和词法分析的本质区别
| 阶段 | 输入 | 输出 | 关心的事情 |
|---|---|---|---|
| 词法分析 | 字符 | token（字符串） | 这个 token 的边界和类别 |
| 语法分析 | token 序列 | AST（树结构） | 哪个是根，谁是子表达式，嵌套关系 |
所以：
- 词法分析不管括号配对、不管表达式嵌套；
- 括号成对出现、
(* 3 4)是一个整体、它是+的第二个参数——这些都是 parser 决定的。
# 3. 抽象一点：语法规则 & 语法树
在编译原理里，我们用“文法（grammar）”来描述语法，比如一个简单算术语言可以写成：
Expr → Expr "+" Term | Term
Term → Term "*" Factor | Factor
Factor → "(" Expr ")" | NUM
这叫 BNF（巴科斯范式）之类的东西。
parser 做的事情就是：
看着 token 流，按照这些产生式规则，一步一步“归约”出一棵树。
对应到结果就是“语法树 / AST”。
Scheme 因为是前缀 + 全括号，其实语法比 C / Python 简单很多：
- 每个以
(开头、以)结尾的都是一个“组合表达式（call 或 special form）” - 里面就是：第一个元素是 operator / 关键字，后面是参数
# 4. 具体到 CS61A Scheme：parser 如何工作？
在 61A 的 Scheme 项目里，语法分析的核心是两个函数：
scheme_read：读一个完整的 Scheme 表达式read_tail：在已经看到一个(之后，读这一对括号里的剩余部分
可以用伪代码描述一下（简化版）：
def scheme_read(tokens):
"""读出一个完整的表达式"""
token = tokens.pop(0)
if token == '(':
# 开始读列表里的内容
return read_tail(tokens)
elif token == ')':
# 语法错误：遇到多余的右括号
error
else:
# 原子：数字 / 符号
return parse_atom(token)
def read_tail(tokens):
"""已经读过一个 '('，继续读这个列表剩下的内容，直到匹配的 ')'"""
if not tokens:
error # 括号没闭合
if tokens[0] == ')':
tokens.pop(0) # 消费掉 ')'
return nil # 空列表结束
# 否则：读一个元素 + 递归读剩下的
first = scheme_read(tokens)
rest = read_tail(tokens)
return Pair(first, rest)
跑一遍你的例子：
token 流：
['(', '+', '2', '(', '*', '3', '4', ')', ')']
scheme_read看到'('→ 调用read_tailread_tail第一次：- 看到
'+'→ 调scheme_read，得到 symbol+ - 递归
read_tail继续读后面
- 看到
再次
read_tail：- 看到
'2'→scheme_read得到数字 2 - 递归
read_tail继续
- 看到
再次
read_tail：- 看到
'('→scheme_read又开始读一个子表达式(* 3 4) - 这个过程中又会递归调用
read_tail
- 看到
当读到对应的
')'时，read_tail返回nil，一层一层往外拼回去，就构成了嵌套的Pair结构，也就是一棵 AST。
这一整套递归，就是典型的“递归下降解析（recursive descent parsing）”。
# 5. 语法分析的几种常见方法（顺带提一句）
你一开始那张图里提到的：
- 递归下降（Recursive Descent）
- LL / LR / LALR
- Pratt parser
这些都是实现 parser 的不同策略。
在 CS61A 这种教学环境下：
- 用的是 递归下降：
- 对每个语法结构写一个递归函数
- 思路非常直观，便于教学
工业界编译器（像 GCC、Clang）为了性能、错误恢复等，会用更加复杂/自动化的 LR/LALR 等方法，但概念上做的是同一件事：把 token 串结构化成语法树。
# 小结一句话版
- 语法分析（parser）的任务：
从 token 序列 出发，根据语言的语法规则，构造出表达式的 树形结构（AST）。 - 在 61A 的 Scheme 项目里，就是
scheme_read+read_tail把：变成嵌套的['(', '+', '2', '(', '*', '3', '4', ')', ')']Pair/nil结构。
如果你愿意，下一步可以一起把 scheme_read / read_tail 逻辑画成一张“调用栈 + AST 构建过程”的图，会对整个解释器前半段彻底通透。
# 四、AST 是什么？Scheme 的 AST 有什么特别
- 什么是 AST（抽象语法树）
AST（Abstract Syntax Tree）是对程序 语法结构的抽象表示：
- 只保留“结构关系”
- 不关心空格、换行、具体括号形式
- 反映“谁包含谁”“谁是参数”
从一个例子看 AST 是如何被构建的： 输入：
(* (+ 1 2) 3)
词法分析后得到 token 流：
['(', '*', '(', '+', '1', '2', ')', '3', ')']
解析过程大致是：
- scheme_read 读到 (，进入 read_tail
- 递归读取 *
- 再次遇到 (，递归解析子表达式 (+ 1 2)
- 子表达式先构建出一棵 Pair 子树
- 返回后继续解析 3
- 最终拼出完整的 Pair 结构
语法分析后得到 AST：
*
/ \
+ 3
/ \
1 2