Aims of Syntactic Analysis
- Build a parse tree（构建语法树）
- Root: distinguished symbol, e.g.
<program> - Leaves: token sequence from lexical analysis
- Each branch point sanctioned by a grammar rule
- Root: distinguished symbol, e.g.
- Optional tasks:
- Carry out semantic checks（语义检查）
- Generate intermediate code or machine code incrementally
- Provide helpful error messages if syntax is invalid
一句话解释什么是 Syntactic Analysis 语法分析：“ Syntactic Analysis 就是将 token 组成“结构正确的句子/语法树” ”
Two Parsing Strategies
| 类型 | 思路 | 推导方式 | 代表 |
|---|---|---|---|
| Top-down | 从 S 开始 | Leftmost | LL(1) |
| Bottom-up | 从输入开始 | Rightmost（逆） | LR |
Criteria for Parsing Strategy（解析策略的评估标准）
| 标准 | 说明 |
|---|---|
| Power | 能否处理目标语言的语法？Earley/CYK 可处理任意 CFG，但 LL/LR 仅适用于子集 |
| Back-tracking | 回溯效率低，需撤销符号表、中间代码等副作用；本课程策略无需回溯 |
| Lookahead | 通过预读下一个 token 辅助决策；通常 k=1 足够（LL(1)/LR(1)） |
| Efficiency | 时间复杂度应为 O(n)，n 为输入长度 |
| Small Size | 解析器体积尽量小，避免生成过大的分析表 |
lookahead = 偷看下一个 token，用来选规则
LL(k) vs LR(k) Meaning
First L: Left-to-right scanning of input Second L/R:
- L → Left-most derivation (Top-down)
- R → Right-most derivation (Bottom-up)
k: number of lookahead tokens (usually 0 or 1)