语法分析算法详解 - 递归下降、LL(1)、LR(1)

📚 第一节：语法分析基础概念

🔍 什么是语法分析（Parsing）？

输入：Token 序列（词法分析的输出）

输出：语法树（Parse Tree 或 AST）

任务：

1. 根据文法（Grammar）检查 Token 序列是否符合语法规则

2. 如果符合，构建语法树

3. 如果不符合，报告语法错误

📖 文法（Grammar）基础

// 一个简单表达式文法（巴科斯范式 BNF）

// 产生式规则
Expr  → Term Expr'
Expr' → + Term Expr' | ε
Expr' → - Term Expr' | ε
Term  → Factor Term'
Term' → * Factor Term' | ε
Term' → / Factor Term' | ε
Factor → ( Expr ) | number

💡 重要概念：
• 终结符（Terminal）：词法分析输出的 Token（如 +, -, *, /, number, id）
• 非终结符（Non-terminal）：文法符号（如 Expr, Term, Factor）
• 产生式（Production）：A → α（非终结符 → 符号串）
• 开始符号（Start Symbol）：文法中最重要的非终结符（如 Expr）

🎯 语法分析方法分类

自上而下（Top-Down）

思路：从开始符号出发，逐步展开，匹配输入串

代表算法：递归下降法、LL(1)

特点：构建语法树时，从根节点开始，逐步向下构建

自下而上（Bottom-Up）

思路：从输入串出发，逐步归约，最终归约到开始符号

代表算法：LR(1)、LALR

特点：构建语法树时，从叶子节点开始，逐步向上归约

🔄 第二节：递归下降法（Recursive Descent）

📖 算法原理

核心思想：为每个非终结符写一个函数，函数内部根据当前 Token 选择产生式。

工作流程：

1. 读取当前 Token（lookahead）

2. 根据当前 Token 和文法规则，决定调用哪个函数

3. 递归调用其他非终结符的函数

4. 匹配终结符时，消费当前 Token，读取下一个

🎯 示例：解析简单表达式

// 文法（无左递归版本）
Expr  → Term ExprRest
ExprRest → + Term ExprRest | - Term ExprRest | ε
Term  → Factor TermRest
TermRest → * Factor TermRest | / Factor TermRest | ε
Factor → number | ( Expr )

💻 递归下降法实现（Go语言示例）

// 递归下降法解析器（Go语言实现）

package main

type Parser struct {
    tokens []Token
    pos    int  // 当前 Token 位置
}

// Expr → Term ExprRest
func (p *Parser) parseExpr() *Node {
    term := p.parseTerm()
    exprRest := p.parseExprRest()
    return &Node{Type: "Expr", Children: []*Node{term, exprRest}}
}

// ExprRest → + Term ExprRest | - Term ExprRest | ε
func (p *Parser) parseExprRest() *Node {
    if p.pos < len(p.tokens) {
        if p.tokens[p.pos].Type == "PLUS" {
            p.consume("PLUS")  // 消费 '+'
            term := p.parseTerm()
            exprRest := p.parseExprRest()
            return &Node{Type: "+", Children: []*Node{term, exprRest}}
        } else if p.tokens[p.pos].Type == "MINUS" {
            p.consume("MINUS")  // 消费 '-'
            term := p.parseTerm()
            exprRest := p.parseExprRest()
            return &Node{Type: "-", Children: []*Node{term, exprRest}}
        }
    }
    return &Node{Type: "ε"}  // 空产生式
}

// Term → Factor TermRest
func (p *Parser) parseTerm() *Node {
    factor := p.parseFactor()
    termRest := p.parseTermRest()
    return &Node{Type: "Term", Children: []*Node{factor, termRest}}
}

// Factor → number | ( Expr )
func (p *Parser) parseFactor() *Node {
    if p.tokens[p.pos].Type == "NUMBER" {
        val := p.tokens[p.pos].Value
        p.consume("NUMBER")
        return &Node{Type: "number", Value: val}
    } else if p.tokens[p.pos].Type == "LPAREN" {
        p.consume("LPAREN")  // 消费 '('
        expr := p.parseExpr()
        p.consume("RPAREN")  // 消费 ')'
        return expr
    }
    panic("unexpected token")
}

✅ 递归下降法的优缺点

✅ 优点

• 简单直观，容易手写

• 错误报告准确（可以精确定位）

• 容易添加自定义语法

• Go、Python 等语言的编译器使用

❌ 缺点

• 不能处理左递归文法

• 需要手动消除左递归和提取左公因子

• 递归调用可能栈溢出（深层递归）

• 不是所有文法都能用递归下降法解析

💡 Go 语言的解析器：
Go 编译器的语法分析器就是使用递归下降法手写的！
位于：src/cmd/compile/internal/syntax/parser.go

📐 第三节：LL(1) 算法

📖 算法原理

LL(1) 的含义：

• 第一个 L：从左到右（Left-to-right）扫描输入

• 第二个 L：最左推导（Leftmost derivation）

• 1：只需要向前看 1个 Token 就能决定使用哪个产生式

核心思想：用分析表（Parsing Table）指导解析过程，避免回溯。

🎯 LL(1) 分析表的构造

需要计算两个集合：

1. FIRST(α)：符号串 α 能推导出的第一个终结符的集合

2. FOLLOW(A)：非终结符 A 后面可能跟随的终结符的集合

填充分析表：

• 对于产生式 A → α，对于每个终结符 a ∈ FIRST(α)，设置 Table[A, a] = A → α

• 如果 ε ∈ FIRST(α)，则对于每个终结符 b ∈ FOLLOW(A)，设置 Table[A, b] = A → α

📊 示例：构造 LL(1) 分析表

// 文法
1. E → T E'
2. E' → + T E' | ε
3. T → F T'
4. T' → * F T' | ε
5. F → ( E ) | id

LL(1) 分析表

非终结符	id	+	*	(	)	$
E	E → T E'			E → T E'
E'		E' → + T E'			E' → ε	E' → ε
T	T → F T'			T → F T'
T'		T' → ε	T' → * F T'		T' → ε	T' → ε
F	F → id			F → ( E )

🎬 LL(1) 解析过程动态演示

解析输入串：id + id * id

速度： 1.5s

分析栈

$

E

输入缓冲区

id + id * id $

初始状态：栈中为 [E$]，输入为 [id + id * id $]

分析表（当前步骤高亮）

💻 LL(1) 解析器实现（Go语言示例）

// LL(1) 解析器（表驱动）

type LL1Parser struct {
    table   map[string]map[string]string  // 分析表
    stack   []string                        // 分析栈
    input   []Token                           // 输入 Token 序列
    pos     int                                 // 输入位置
}

func (p *LL1Parser) parse() bool {
    // 初始化栈
    p.stack = []string{"$", "E"}
    
    for len(p.stack) > 0 {
        top := p.stack[len(p.stack)-1]
        currentToken := p.input[p.pos].Type
        
        if isTerminal(top) {
            if top == currentToken {
                // 匹配成功，弹栈，消费 Token
                p.stack = p.stack[:len(p.stack)-1]
                p.pos++
            } else {
                return false  // 语法错误
            }
        } else {
            // 非终结符，查表
            production := p.table[top][currentToken]
            if production == "" {
                return false  // 语法错误
            }
            
            // 弹栈
            p.stack = p.stack[:len(p.stack)-1]
            
            // 如果产生式不是 ε，逆序压栈
            if production != "ε" {
                symbols := reverse(splitProduction(production))
                for _, sym := range symbols {
                    p.stack = append(p.stack, sym)
                }
            }
        }
    }
    
    return p.pos == len(p.input)  // 输入是否全部消费
}

💡 LL(1) 的局限性：
• 只能解析 LL(1) 文法（不是所有文法都能转换成 LL(1)）
• 需要手动构造分析表（或写工具生成）
• 实际编译器很少用纯 LL(1)（递归下降法更灵活）

🔄 第四节：LR(1) 算法

📖 算法原理

LR(1) 的含义：

• L：从左到右（Left-to-right）扫描输入

• R：最右推导的逆过程（Rightmost derivation in reverse）

• 1：向前看 1个 Token 来决定是否归约

核心思想：维护一个状态栈和符号栈，通过动作表（Action Table）和转移表（Goto Table）指导解析。

🎯 LR(1) 解析过程

两个核心数据结构：

1. 状态栈（State Stack）：存储 LR(1) 自动机的状态

2. 符号栈（Symbol Stack）：存储已匹配的符号

两种动作：

• 移进（Shift）：将当前 Token 移入符号栈，状态栈压入新状态

• 归约（Reduce）：用产生式 A → α 归约，弹出 |α| 个符号，压入 A

• 接受（Accept）：输入串解析成功

• 错误（Error）：无法继续解析

📊 LR(1) 分析表示例

LR(1) 分析表（简化版）

Action 表（终结符）

状态	id	+	*	(	)	$
0	s5			s4
1		s6				acc
2		r2	s7		r2	r2
3		r4	r4		r4	r4

Goto 表（非终结符）

状态	E	T	F
0	1	2	3
4	8	2	3

符号说明：

s5 = 移进到状态 5

r2 = 用第 2 条产生式归约

acc = 接受（解析成功）

数字 = Goto 到该状态

🎬 LR(1) 解析过程动态演示

解析输入串：id + id * id

速度： 1.5s

状态栈

0

符号栈

$

输入缓冲区

id + id * id $

初始状态：状态栈 [0]，符号栈 [$，输入为 [id + id * id $]

💻 LR(1) 解析器实现（Go语言示例）

// LR(1) 解析器（表驱动）

type LR1Parser struct {
    action map[int]map[string]string  // 动作表
    goto   map[int]map[string]int     // 转移表
    prods  []string                           // 产生式列表
}

func (p *LR1Parser) parse(input []string) bool {
    stateStack := []int{0}
    symbolStack := []string{"$"}
    input = append(input, "$")
    pos := 0
    
    for {
        state := stateStack[len(stateStack)-1]
        token := input[pos]
        
        action := p.action[state][token]
        
        if strings.HasPrefix(action, "s") {
            // 移进
            nextState := parseInt(action[1:])
            stateStack = append(stateStack, nextState)
            symbolStack = append(symbolStack, token)
            pos++
        } else if strings.HasPrefix(action, "r") {
            // 归约
            prodIdx := parseInt(action[1:])
            prod := p.prods[prodIdx]  // 格式：A → α
            
            // 弹出 |α| 个符号和状态
            alphaLen := len(splitProduction(prod))
            stateStack = stateStack[:len(stateStack)-alphaLen]
            symbolStack = symbolStack[:len(symbolStack)-alphaLen]
            
            // 压入 A
            A := getLHS(prod)
            symbolStack = append(symbolStack, A)
            
            // Goto
            topState := stateStack[len(stateStack)-1]
            nextState := p.goto[topState][A]
            stateStack = append(stateStack, nextState)
        } else if action == "acc" {
            return true  // 解析成功
        } else {
            return false  // 语法错误
        }
    }
}

💡 LR(1) 的优势：
• 能解析几乎所有编程语言（比 LL(1) 强大得多）
• 不需要消除左递归
• Yacc/Bison、GCC、LLVM 都使用 LR 系列算法
• LALR(1) 是 LR(1) 的优化版，状态数更少（Yacc/Bison 默认使用）

⚖️ 第五节：三种算法对比

对比维度	递归下降法	LL(1)	LR(1)
解析方向	自上而下（Top-Down）	自上而下（Top-Down）	自下而上（Bottom-Up）
实现方式	手写递归函数	表驱动（分析表）	表驱动（Action + Goto 表）
是否需要分析表	❌ 不需要	✅ 需要 LL(1) 分析表	✅ 需要 Action + Goto 表
能解析的文法	LL(1) 文法（需消除左递归）	LL(1) 文法	LR(1) 文法（更强大）
是否支持左递归	❌ 不支持（会无限递归）	❌ 不支持	✅ 支持
错误报告	✅ 精确（可以自定义错误信息）	⚠️ 一般（分析表查不到就是错误）	⚠️ 一般（需要额外处理错误恢复）
实现难度	✅ 简单（容易手写）	⚠️ 中等（需要构造分析表）	❌ 复杂（需要构造 LR(1) 自动机）
实际使用	Go、Python、手写解析器	教学、简单语言	Yacc/Bison、GCC、LLVM

🍳 厨房类比（帮你理解）

递归下降法 = 按食谱做菜（自上而下）

• 从"做鱼香肉丝"开始，逐步分解成"切肉"、"炒菜"等步骤

• 每遇到一个步骤，就调用对应的函数

LL(1) = 查表做菜（自上而下，但有菜谱表）

• 有一个"菜谱表"，看到当前的食材，查表决定下一步做什么

• 不需要自己判断，严格按照表来

LR(1) = 从成品反推做法（自下而上）

• 看到桌上的菜（输入串），逐步归约成"这是鱼香肉丝"

• 更强大，能处理更复杂的菜谱（文法）

🎬 第六节：完整解析过程动态演示

选择一个算法查看完整解析过程

请选择一个算法查看动态演示

📝 第七节：总结

核心要点

1️⃣ 递归下降法：手写递归函数，简单直观，Go 编译器使用

2️⃣ LL(1)：表驱动，自上而下，只能解析 LL(1) 文法

3️⃣ LR(1)：表驱动，自下而上，能解析几乎所有编程语言

4️⃣ 选择建议：手写解析器用递归下降法，自动生成用 LR(1)（Yacc/Bison）

🎓 学习建议：
• 先理解递归下降法（最直观）
• 再学习 LL(1) 的分析表构造（理解 FIRST/FOLLOW 集合）
• 最后学习 LR(1) 的自动机构造（最复杂但也最强大）
• 推荐实践：用递归下降法写一个简易计算器（四则运算）
• 推荐工具：ANTLR（支持 LL(*)，可以自动生成解析器）

🎉 恭喜你完成了语法分析算法的学习！

现在你应该理解了递归下降、LL(1)、LR(1) 三种算法的原理和实现。

# 推荐资源
# 1. 书籍
《编译原理》（龙书） - Alfred V. Aho 等
   # 语法分析章节讲得非常详细

《Modern Compiler Implementation》 - Andrew Appel
   # 有 C、Java、ML 三个版本

# 2. 在线工具
ANTLR: https://www.antlr.org/  # 自动生成解析器
Grammar Explorer: https://mdkrajnak.github.io/grammar-explorer/  # 可视化文法

# 3. 实战项目
1. 用递归下降法写一个计算器（四则运算 + 括号）
2. 用 ANTLR 生成一个 JSON 解析器
3. 阅读 Go 编译器的 parser.go（递归下降法实战）

🔬 语法分析算法详解

📚 第一节：语法分析基础概念

🔍 什么是语法分析（Parsing）？

📖 文法（Grammar）基础

🎯 语法分析方法分类

自上而下（Top-Down）

自下而上（Bottom-Up）

🔄 第二节：递归下降法（Recursive Descent）

📖 算法原理

🎯 示例：解析简单表达式

💻 递归下降法实现（Go语言示例）

✅ 递归下降法的优缺点

✅ 优点

❌ 缺点

📐 第三节：LL(1) 算法

📖 算法原理

🎯 LL(1) 分析表的构造

📊 示例：构造 LL(1) 分析表

🎬 LL(1) 解析过程动态演示

💻 LL(1) 解析器实现（Go语言示例）

🔄 第四节：LR(1) 算法

📖 算法原理

🎯 LR(1) 解析过程

📊 LR(1) 分析表示例

🎬 LR(1) 解析过程动态演示

💻 LR(1) 解析器实现（Go语言示例）

⚖️ 第五节：三种算法对比

🍳 厨房类比（帮你理解）

🎬 第六节：完整解析过程动态演示

📝 第七节：总结

核心要点