05-编译原理-从字符到语法树

05 · 编译原理：从字符到语法树（上）

“编译器的设计，本质上是一场’如何在有限信息下做出判断’的博弈。“

---

开场：为什么 Go 的错误信息那么难懂

老陈：你写过 Go，也见过 Rust 的错误提示。告诉我两者的差别。

小林：Go 的错误信息特别简洁，比如 expected ';', found '}'。Rust 的却特别长，还会画出代码片段、给出修改建议。

老陈：为什么会有这个差别？是 Go 编译器偷懒吗？

小林：……可能是没做优化？

老陈：不对。Go 的错误信息之所以”简单粗暴”，是因为它的语法分析器看不到足够的信息。 这不是偷懒，是设计选择的必然结果。

小林：什么意思？

老陈：Go 的语法分析器用的是递归下降（Recursive Descent）。 它的特点是”预测式”——我站在当前位置，根据看到的下一个 token，猜测后面应该是什么。猜错了就报错。

而 LR 系（如 yacc 生成的）是”归约式”——它把所有可能的语法规则记在状态机里，出错时知道”当前状态下所有合法的 token 是什么”，所以能精确告诉你”这里应该是 X、Y 或 Z”。

小林：所以 Rust 能给出好错误，是因为它的分析器知道”当前所有可能的选项”？

老陈：对。这就是”信息量”的差异。信息越多，错误提示越好——但代价是分析器复杂得多。

小林：所以这是个取舍。

老陈：对。而且这个取舍贯穿编译器的每一个阶段。理解了这一点，你就能看懂为什么不同的语言会做出不同的编译器设计。

---

编译的五个阶段

源码:  "int add(int a, int b) { return a + b; }"
  │
  ▼ ① 词法分析 (Lexical Analysis)
Token 流: [int][id:add][(][int][id:a][,][int][id:b][)][{][return][id:a][+][id:b][;][}]
  │
  ▼ ② 语法分析 (Parsing)
AST:    FuncDecl
        ├── name: "add"
        ├── params: [a:int, b:int]
        └── body: Return(BinaryOp(+, Var(a), Var(b)))
  │
  ▼ ③ 语义分析 (Semantic Analysis)
带类型的 AST + 符号表（检查：a 声明过吗？类型能相加吗？返回类型匹配吗？）
  │
  ▼ ④ 中间代码生成 & 优化 (IR / SSA)
SSA IR
  │
  ▼ ⑤ 目标代码生成
机器码

每个阶段解决一个独立问题，且都会丢弃一些信息：

阶段	输出	丢弃/补充
词法	Token 流	丢弃：空白、注释、缩进
语法	AST	丢弃：括号、分号（结构已在树里）
语义	带类型 AST	补充：类型信息
IR	SSA IR	丢弃：变量名（变寄存器号）
代码生成	机器码	丢弃：类型（变内存布局）

老陈：注意”丢弃”这件事。编译是”信息不断丢失、也不断被补充”的过程。

为什么重要？ 因为你在后面阶段拿不到的信息，就没法做相应的优化。现代编译器都在往”保留更多信息”的方向走——Rust 的 MIR、Swift 的 SIL，都是在 IR 层保留类型信息以做更精确的优化。

---

阶段 ①：词法分析

理论基础：正则 → NFA → DFA

程序语言里的”单词”结构都很简单，都是正则语言：

标识符:  [a-zA-Z_][a-zA-Z0-9_]*
整数:    [0-9]+
浮点数:  [0-9]+\.[0-9]+([eE][+-]?[0-9]+)?

教科书流程：

正则表达式 → NFA（Thompson 构造）→ DFA（子集构造）→ 最小化 → 状态转移表

• NFA：一个状态读入同一字符可转到多个状态；可有 ε 转移
• DFA：一个状态读入一个字符只转到一个状态 → 每字符 O(1) 查表

但实践上没人这么干。 Go、GCC、Clang 全都是手写词法分析器。理由：

1. 性能：switch-case 比查表快，分支预测友好
2. 错误恢复：DFA 遇非法输入就是”死状态”；手写可”尽力恢复”（比如字符串没闭合，报错后继续扫）
3. 上下文相关规则：很多语言的词法不是纯正则的（见下面的 Go ASI）
4. 可维护性：生成的状态表是调试噩梦

理论仍然重要——它告诉你”什么样的词法规则可实现”，也是正则引擎的基础（Go 的 regexp 用 NFA 模拟而非 DFA，以保证 O(n) 匹配时间）。

Go 的自动分号插入（ASI）：上下文相关的词法

Go 源码几乎不写分号，编译器在词法阶段自动插。规则是：一行末尾如果是标识符、字面量、break/continue/fallthrough/return、++/--、)、]、}，就插入分号。

这导致两个著名的坑：

// ❌ 分号插在 } 后面
if x > 0 {
}
else {          // syntax error: unexpected else
}
 
// ✅ 必须这样
if x > 0 {
} else {
}
 
// ❌ 致命陷阱：分号插在 return 后面
func foo() int {
	return        // ← 这里插了分号！返回零值
		compute()   // ← 这行是永远不执行的废代码
}

老陈：这是 Go 最具争议的语言特性之一。 好处是代码干净，坏处是引入了一类能编译通过但行为完全错误的 bug。

更深层的问题：这个设计把”美观”的优先级放在了”明确性”之上。 Rust 的选择完全相反——要求显式分号，错误时明确告诉你”是不是忘了分号”。

两种选择背后是两种哲学：Go 相信程序员会遵守约定，Rust 相信编译器应该抓住所有错误。

而且注意：ASI 让 Go 的词法不再是纯正则的——换行符在什么情况下算分号，依赖前一个 token 的类型。这正是”必须手写词法分析器”的理由。

动手：手写词法分析器

package main
 
import (
	"fmt"
	"strings"
	"unicode"
)
 
type TokenType int
 
const (
	TokEOF TokenType = iota
	TokIdent
	TokInt
	TokFloat
	TokString
	TokIf
	TokElse
	TokWhile
	TokReturn
	TokIntKW
	TokVoid
	// 运算符：长运算符要排在短的前面（最长匹配）
	TokLe        // <=
	TokGe        // >=
	TokEq        // ==
	TokNe        // !=
	TokAndAnd    // &&
	TokOrOr      // ||
	TokPlus
	TokMinus
	TokStar
	TokSlash
	TokLt
	TokGt
	TokAssign
	TokNot
	TokLParen
	TokRParen
	TokLBrace
	TokRBrace
	TokSemi
	TokComma
)
 
type Token struct {
	Type  TokenType
	Value string
	Line  int
	Col   int
}
 
var keywords = map[string]TokenType{
	"if": TokIf, "else": TokElse, "while": TokWhile,
	"return": TokReturn, "int": TokIntKW, "void": TokVoid,
}
 
type Lexer struct {
	src  []rune
	pos  int
	line int
	col  int
}
 
func NewLexer(src string) *Lexer {
	return &Lexer{src: []rune(src), line: 1, col: 1}
}
 
func (l *Lexer) peek(offset int) rune {
	if l.pos+offset >= len(l.src) {
		return 0
	}
	return l.src[l.pos+offset]
}
 
func (l *Lexer) advance() rune {
	c := l.src[l.pos]
	l.pos++
	if c == '\n' {
		l.line++
		l.col = 1
	} else {
		l.col++
	}
	return c
}
 
func (l *Lexer) skipTrivia() {
	for l.pos < len(l.src) {
		c := l.peek(0)
		if c == ' ' || c == '\t' || c == '\n' || c == '\r' {
			l.advance()
			continue
		}
		// 行注释
		if c == '/' && l.peek(1) == '/' {
			for l.pos < len(l.src) && l.peek(0) != '\n' {
				l.advance()
			}
			continue
		}
		// 块注释
		if c == '/' && l.peek(1) == '*' {
			l.advance()
			l.advance()
			for l.pos < len(l.src) {
				if l.peek(0) == '*' && l.peek(1) == '/' {
					l.advance()
					l.advance()
					break
				}
				l.advance()
			}
			continue
		}
		break
	}
}
 
func (l *Lexer) Next() (Token, error) {
	l.skipTrivia()
	if l.pos >= len(l.src) {
		return Token{Type: TokEOF, Line: l.line, Col: l.col}, nil
	}
 
	startLine, startCol := l.line, l.col
	c := l.peek(0)
 
	// 1. 标识符或关键字
	if unicode.IsLetter(c) || c == '_' {
		var sb strings.Builder
		for unicode.IsLetter(l.peek(0)) || unicode.IsDigit(l.peek(0)) || l.peek(0) == '_' {
			sb.WriteRune(l.advance())
		}
		s := sb.String()
		if kw, ok := keywords[s]; ok {
			return Token{Type: kw, Value: s, Line: startLine, Col: startCol}, nil
		}
		return Token{Type: TokIdent, Value: s, Line: startLine, Col: startCol}, nil
	}
 
	// 2. 数字
	if unicode.IsDigit(c) {
		var sb strings.Builder
		isFloat := false
		for unicode.IsDigit(l.peek(0)) {
			sb.WriteRune(l.advance())
		}
		if l.peek(0) == '.' && unicode.IsDigit(l.peek(1)) {
			isFloat = true
			sb.WriteRune(l.advance())
			for unicode.IsDigit(l.peek(0)) {
				sb.WriteRune(l.advance())
			}
		}
		tt := TokInt
		if isFloat {
			tt = TokFloat
		}
		return Token{Type: tt, Value: sb.String(), Line: startLine, Col: startCol}, nil
	}
 
	// 3. 字符串
	if c == '"' {
		l.advance()
		var sb strings.Builder
		for l.pos < len(l.src) && l.peek(0) != '"' {
			if l.peek(0) == '\\' {
				l.advance()
				switch l.peek(0) {
				case 'n':
					sb.WriteRune('\n')
				case 't':
					sb.WriteRune('\t')
				case '0':
					sb.WriteRune(0)
				default:
					sb.WriteRune(l.peek(0))
				}
				l.advance()
				continue
			}
			sb.WriteRune(l.advance())
		}
		if l.pos >= len(l.src) {
			return Token{}, fmt.Errorf("第 %d 行: 字符串未闭合", startLine)
		}
		l.advance()
		return Token{Type: TokString, Value: sb.String(), Line: startLine, Col: startCol}, nil
	}
 
	// 4. 运算符 —— ★ 关键：最长匹配原则，先试双字符
	twoCharOps := map[string]TokenType{
		"<=": TokLe, ">=": TokGe, "==": TokEq, "!=": TokNe,
		"&&": TokAndAnd, "||": TokOrOr,
	}
	if l.pos+1 < len(l.src) {
		two := string(l.src[l.pos : l.pos+2])
		if tt, ok := twoCharOps[two]; ok {
			l.advance()
			l.advance()
			return Token{Type: tt, Value: two, Line: startLine, Col: startCol}, nil
		}
	}
 
	oneCharOps := map[rune]TokenType{
		'+': TokPlus, '-': TokMinus, '*': TokStar, '/': TokSlash,
		'<': TokLt, '>': TokGt, '=': TokAssign, '!': TokNot,
		'(': TokLParen, ')': TokRParen, '{': TokLBrace, '}': TokRBrace,
		';': TokSemi, ',': TokComma,
	}
	if tt, ok := oneCharOps[c]; ok {
		l.advance()
		return Token{Type: tt, Value: string(c), Line: startLine, Col: startCol}, nil
	}
 
	return Token{}, fmt.Errorf("第 %d 行第 %d 列: 无法识别的字符 %q",
		startLine, startCol, string(c))
}
 
func Tokenize(src string) ([]Token, error) {
	l := NewLexer(src)
	var tokens []Token
	for {
		tok, err := l.Next()
		if err != nil {
			return nil, err
		}
		tokens = append(tokens, tok)
		if tok.Type == TokEOF {
			break
		}
	}
	return tokens, nil
}

关键点：最长匹配原则。 <= 必须被识别成一个 token 而不是 < + =。这就是为什么 twoCharOps 必须在 oneCharOps 之前检查。

这是手写词法分析器最容易犯的错误。 用”正则 → NFA → DFA”自动构造时，DFA 会贪婪匹配最长串，问题自动解决；手写就得自己保证顺序。

---

阶段 ②：语法分析

两类主流算法

	LL（自顶向下）	LR（自底向上）
思路	从开始符号出发，预测式推导	从输入出发，移进-归约
典型实现	递归下降	Yacc/Bison、LALRPOP
左递归	❌ 不能（无限循环）	✅ 可以
错误提示	只知道”我猜错了”	知道”所有可能的选项”
实现难度	⭐⭐ 手写即可	⭐⭐⭐⭐⭐ 需工具生成
编译速度	快（函数调用，分支预测友好）	慢（查表，缓存不友好）
使用者	Go、Clang(C++)、TypeScript	Yacc 系、Java CUP

为什么递归下降不能处理左递归

E ::= E "+" T | T     // 左递归，最直观的写法

写成递归下降：

func parseE() Node {
	return parseE()   // ← 无限递归！还没消耗任何 token
}

必须改写成右递归：

E  ::= T E'
E' ::= "+" T E' | ε

func parseE() Node {
	left := parseT()
	return parseEPrime(left)
}
 
func parseEPrime(left Node) Node {
	if peek().Type == TokPlus {
		next()
		right := parseT()
		return parseEPrime(BinaryOp{Add, left, right})  // 累积器
	}
	return left
}

老陈：注意这里的问题：改写后 AST 结构会变。 左递归天然产生左结合树 ((a+b)+c)，右递归改写后要手动恢复结合性——这就是为什么 parseEPrime 要传 left 参数用累积器恢复左结合语义。

这是递归下降的隐性代价：你的文法不能写得太”自然”。

核心技巧：优先级爬升（Precedence Climbing）

手写表达式解析最优雅的方案，值得背下来：

var precedence = map[TokenType]int{
	TokAssign: 1,
	TokOrOr:   2,
	TokAndAnd: 3,
	TokEq: 4, TokNe: 4,
	TokLt: 5, TokGt: 5, TokLe: 5, TokGe: 5,
	TokPlus: 6, TokMinus: 6,
	TokStar: 7, TokSlash: 7,
}
 
// parseExpr 解析优先级 >= minPrec 的表达式
func (p *Parser) parseExpr(minPrec int) (Node, error) {
	left, err := p.parseUnary()
	if err != nil {
		return nil, err
	}
 
	for {
		tok := p.peek()
		prec, isBinary := precedence[tok.Type]
		if !isBinary || prec < minPrec {
			break
		}
		p.next()
 
		// 左结合 → prec+1；右结合（如赋值）→ prec
		rightMinPrec := prec + 1
		if tok.Type == TokAssign {
			rightMinPrec = prec
		}
 
		right, err := p.parseExpr(rightMinPrec)
		if err != nil {
			return nil, err
		}
		left = &BinaryExpr{Op: tok.Type, Left: left, Right: right}
	}
	return left, nil
}

为什么传 prec + 1 就得到左结合？

解析 1 + 2 * 3:
parseExpr(0):
  left = 1
  看到 + (prec=6), 6>=0, 消费
  right = parseExpr(7):      ← 注意是 7
      left = 2
      看到 * (prec=7), 7>=7, 消费
      right = parseExpr(8) = 3
      返回 2*3
  left = 1 + (2*3)           ✅

解析 1 * 2 + 3:
parseExpr(0):
  left = 1
  看到 * (prec=7), 消费
  right = parseExpr(8) = 2   ← peek 是 + (prec=6), 6 < 8, 停止
  left = 1*2
  看到 + (prec=6), 6>=0, 消费
  right = parseExpr(7) = 3
  left = (1*2) + 3           ✅

精髓：minPrec 控制”什么时候停止吸收右侧的运算符”。传 prec+1 意味着”只有比我优先级更高的运算符才能进入我的右子树”，从而实现左结合。

---

阶段 ③：语义分析

语法正确 ≠ 有意义

int x;
x = "hello" + 3.14;   // 语法正确，语义错误
foo();                 // 语法正确，foo 没声明

语义分析要做：符号解析、类型检查、作用域处理、重复定义检查、控制流检查。

符号表

type Symbol struct {
	Name    string
	Type    CType
	Kind    SymbolKind // 变量 / 函数 / 类型
	Offset  int        // 相对栈帧基址的偏移（代码生成用）
	IsParam bool
}
 
type Scope struct {
	symbols map[string]*Symbol
	parent  *Scope
}
 
func (s *Scope) Lookup(name string) (*Symbol, bool) {
	if sym, ok := s.symbols[name]; ok {
		return sym, true
	}
	if s.parent != nil {
		return s.parent.Lookup(name) // 向外层作用域找
	}
	return nil, false
}
 
func (s *Scope) Enter() *Scope {
	return &Scope{symbols: make(map[string]*Symbol), parent: s}
}

作用域是栈，符号查找是链。

老陈：真实编译器不会真的为每个作用域建 map——函数调用时创建作用域太频繁，map 开销大。常见优化：

• 用一个全局 []Symbol 切片 + “作用域起始索引”栈
• 查找时从后往前线性扫（缓存局部性好，实际很快）

类型检查：指针运算的特殊规则

func checkBinary(op TokenType, lhs, rhs CType) (CType, error) {
	// 指针运算特判 —— C 类型系统最微妙的部分
	if lp, ok := lhs.(*PtrType); ok {
		if op == TokPlus || op == TokMinus {
			if _, ok := rhs.(*PrimType); ok {
				return lp, nil // 指针 ± 整数 = 指针
			}
		}
		if op == TokMinus {
			if rp, ok := rhs.(*PtrType); ok && lp.String() == rp.String() {
				return &PrimType{Kind: Int}, nil // 指针 - 指针 = 整数（元素个数差）
			}
		}
	}
	// ... 算术运算要求两边都是基本类型
}

对应 C 的规则：

int *p, *q;
p + 1;   // 合法，地址实际 +4（不是 +1！）
p - q;   // 合法，结果是元素个数差
p + q;   // 非法：两个指针不能相加
p * 2;   // 非法

老陈：“指针 + 整数”的增量 = 整数 × 指向类型的大小。 背后的思想是：指针运算的单位是”元素”而不是”字节”，这让 p[i] 和 *(p+i) 完全等价。

Go 保留了这个语义（切片索引），但禁止了裸指针算术。这是”保留便利、移除危险”的典型取舍。

---

第三层追问：为什么 Go 编译这么快

老陈：Go 编译中等项目几秒，C++ 要几分钟。你以为是 Go 语法简单？

小林：不全是因为这个吧？

老陈：语法简单只占一小部分。三个设计决策：

① 包级符号表——不用重新解析头文件（C++ 的 #include 是文本复制，改一个头文件要重编几百个 .cpp） ② 手写递归下降——不是 yacc 生成的表驱动分析器。函数调用比查表快，分支预测和指令缓存友好 ③ 扁平的 IR——Go 用 SSA，但没有 LLVM 那种多层级 IR（AST → IR → SelectionDAG → MachineInstr）。层数少，转换快，优化少

小林：所以 Go 是用”优化少”换”编译快”？

老陈：对。 Go 生成的代码性能通常比 GCC -O2 差 5~15%。但 Go 团队认为，在大规模工程里，“迭代速度”比”运行时性能”更值钱。

小林：这个判断对吗？

老陈：在 Google 的语境下对——几千个工程师改同一代码库，编译从 10 分钟降到 10 秒，生产力提升远超那 10% 的性能损失。但对写数据库、游戏引擎的人，这个取舍不一定对。

---

更深层的发问

问题 A：为什么不能写一个”完美的”语法分析器？

乔姆斯基层级给出了理论限制：

类型	自动机	分析复杂度	能描述
3 型（正则）	有限自动机	O(n)	词法
2 型（上下文无关）	下推自动机	O(n³) 通用，O(n) 对 LL/LR	大部分语法
1 型（上下文有关）	线性有界自动机	PSPACE-完全	罕见特性
0 型	图灵机	不可判定	自然语言

关键结论：通用上下文无关文法分析是 O(n³)。LL/LR 能做到 O(n)，是因为它们只处理文法的子集。不存在能处理所有 CFG 的线性时间算法——这是理论限制，不是工程问题。

而且有些语言特性根本不是上下文无关的。 C 的著名歧义（typedef 问题）：

typedef int T;
T * b;    // 声明：b 是指向 T 的指针
 
int T;    // 去掉 typedef
T * b;    // 表达式：T 乘以 b

T * b; 到底是声明还是乘法？纯语法层面无法确定，必须查符号表（语义信息）。

解决方案：C 编译器在词法阶段维护”类型名表”，语法分析时查表消歧。这叫词法反馈（lexer feedback），是把语义信息倒流回语法层的 hack。

老陈：这就是为什么”纯粹的分层”在真实系统里总是被打破。 教科书说”词法→语法→语义”是严格流水线，但真实编译器里语义信息经常要倒流回去。

Go 怎么避免的？ 声明用 var/type/func 开头，一眼能区分声明和表达式。这是”为了编译器简单而改变语言设计”的典型例子。

问题 B：如果让你给 Go 加”更好的错误提示”？

方向 1 · 记录期望集合

type Parser struct {
	expected []TokenType  // 累积所有"期望但没等到"的 token
}
 
func (p *Parser) expect(t TokenType) (Token, error) {
	if !p.at(t) {
		p.expected = append(p.expected, t)
		return Token{}, p.makeError()  // 报错时列出所有期望
	}
	// ...
}

方向 2 · 错误恢复 + 多错误报告（收益最大）

不要遇错就停，而是跳到”同步点”（语句边界）继续，一次报告多个错误：

func (p *Parser) advance(syncSet map[TokenType]bool) {
	for {
		t := p.peek().Type
		if syncSet[t] || t == TokEOF {
			return
		}
		p.next()
	}
}

实际开发中你往往有多个错误，一次全报出来能省好几轮”改-编译-改”循环。

方向 3 · “你是不是想写 X”建议（Rust 的 did you mean）

用编辑距离（Levenshtein）找最相似的 token，距离 ≤ 2 时给建议。

方向 4 · 保留位置信息：每个 AST 节点记 Pos，才能画出代码片段。

---

思考题 1 ·【理解层】

为什么词法用正则（有限自动机），语法需要下推自动机（带栈）？举例说明”正则无法描述、CFG 可以描述”的语言。

参考答案

核心区别：有限自动机没有”记忆”（除有限个状态），下推自动机有栈（无限记忆）。

经典例子：括号匹配

L = { n 个 '(' 后跟 n 个 ')' , n ≥ 1 }
  = { (), (()), ((())), ... }

有限自动机无法识别。 设有 k 个状态的 DFA，输入 k+1 个左括号：

读入:  (  (  (  ...  (     共 k+1 个
状态:  q0 q1 q2 ... q_k  q_j   ← 某个状态必然重复

若 q_i 在读入第 a 个和第 b 个 '(' 后都出现（a < b）
则 DFA 无法区分"已读 a 个"和"已读 b 个"
后续输入 a 个 ')' 时两者最终状态相同
但 (^a )^a 应接受，(^b )^a 应拒绝 → 矛盾

这就是泵引理（Pumping Lemma）的直观解释：有限状态 ⇒ 对足够长的输入必有状态重复 ⇒ 重复部分”泵”任意次后 DFA 无法察觉。

下推自动机可以：每读 ( 压栈，每读 ) 弹栈，结束时栈空则接受。栈深记录了”还有几个左括号未匹配”——无界计数。

---

对应到编程语言：

正则能描述（词法）：标识符、数字、字符串、运算符。共同点：不需要计数、不需要配对。

需要栈（语法）：

• 括号配对 ((a+b) * (c-d))
• if...else 嵌套配对
• 嵌套代码块 { { { } } }
• f(g(h(x)))

这些都要求”记住开了几个、还有几个没闭”——无界计数。

---

实践意义：

1. 解释了为什么编译要分两阶段

合并成一个更强的分析器理论上可行，但状态空间爆炸，且无法复用（不同语言词法差异大，语法结构相似）。分层让每层只处理自己那个复杂度的问题。

2. 解释了为什么”用正则解析 HTML”是错的

<div><div><span>text</span></div></div>

嵌套 = 需要栈 = 不是正则语言。正则匹配嵌套超过一定深度必然失败。

SO 上著名回答：用正则解析 HTML 会召唤克苏鲁。 严肃版本：正则无法计数，而嵌套需要计数。

3. 解释了为什么括号匹配是编译器基本操作

所有嵌套结构（代码块、函数、类型）本质上都是括号匹配，都要用栈。递归下降用函数调用栈（隐式），LR 用显式栈。这是两者”自顶向下”和”自底向上”的本质区别。

4. 边界案例：Go 泛型的解析歧义

func Map[T any](s []T) []T
var a [N]int   // 数组

解析 [ 时，要通过后续 token 判断是泛型参数还是数组长度。又一次”语法层无法确定，需语义信息”——跟 C 的 typedef 问题同构。

---

为什么编程语言都停在 2 型文法？

• 2 型已经足够表达需要的结构
• 1 型分析是 PSPACE-完全，0 型不可判定
• 语言设计者会主动避开需要 1 型文法的特性，以保证编译器可实现

这是”理论约束塑造工程实践”的绝佳例子。 编译原理的这些理论不是象牙塔游戏——它们直接决定了语言能长什么样。

---

下一节

05 · 编译原理（下）：动手实现

下篇会实现一个完整的表达式解析器 + 求值器（含词法、语法、语义三阶段串联），并讨论自定义运算符对解析器设计的冲击。

老陈的预告：如果一门语言允许用户自定义运算符的优先级（像 Haskell 那样），静态的递归下降就彻底失效了。这时候你会看到三种截然不同的解法，而每一种都对应一种语言哲学。