徐术挺-漫思录

05-编译原理-下-动手实现

34分钟阅读

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

“看十遍不如写一遍。这一节我们把词法、语法、语义三个阶段串起来，做一个能跑的东西。“

动手一：完整的表达式解析器 + 求值器

这个小程序完整展示了编译器前三个阶段，能解析并执行一段类 C 的脚本：

package main
 
import (
	"fmt"
	"strconv"
)
 
// ============ AST 节点 ============
 
type Node interface {
	Eval(env *Env) (int, error)
	String() string
}
 
type IntLit struct{ Value int }
 
func (n *IntLit) Eval(env *Env) (int, error) { return n.Value, nil }
func (n *IntLit) String() string             { return strconv.Itoa(n.Value) }
 
type VarRef struct{ Name string }
 
func (n *VarRef) Eval(env *Env) (int, error) {
	if v, ok := env.Get(n.Name); ok {
		return v, nil
	}
	return 0, fmt.Errorf("未定义的变量: %s", n.Name)   // 语义检查在运行期
}
func (n *VarRef) String() string { return n.Name }
 
type BinaryExpr struct {
	Op    TokenType
	Left  Node
	Right Node
}
 
func (n *BinaryExpr) Eval(env *Env) (int, error) {
	l, err := n.Left.Eval(env)
	if err != nil {
		return 0, err
	}
	// 短路求值：&& 和 || 的右侧不一定执行
	if n.Op == TokAndAnd && l == 0 {
		return 0, nil
	}
	if n.Op == TokOrOr && l != 0 {
		return 1, nil
	}
	r, err := n.Right.Eval(env)
	if err != nil {
		return 0, err
	}
	switch n.Op {
	case TokPlus:
		return l + r, nil
	case TokMinus:
		return l - r, nil
	case TokStar:
		return l * r, nil
	case TokSlash:
		if r == 0 {
			return 0, fmt.Errorf("除零错误")
		}
		return l / r, nil
	case TokLt:
		return boolToInt(l < r), nil
	case TokGt:
		return boolToInt(l > r), nil
	case TokLe:
		return boolToInt(l <= r), nil
	case TokGe:
		return boolToInt(l >= r), nil
	case TokEq:
		return boolToInt(l == r), nil
	case TokNe:
		return boolToInt(l != r), nil
	case TokAndAnd:
		return boolToInt(l != 0 && r != 0), nil
	case TokOrOr:
		return boolToInt(l != 0 || r != 0), nil
	}
	return 0, fmt.Errorf("未知运算符")
}
 
func boolToInt(b bool) int {
	if b {
		return 1
	}
	return 0
}
 
type AssignExpr struct {
	Name  string
	Value Node
}
 
func (n *AssignExpr) Eval(env *Env) (int, error) {
	v, err := n.Value.Eval(env)
	if err != nil {
		return 0, err
	}
	env.Set(n.Name, v)
	return v, nil
}
func (n *AssignExpr) String() string { return n.Name + " = " + n.Value.String() }
 
type IfStmt struct {
	Cond Node
	Then Node
	Else Node
}
 
func (n *IfStmt) Eval(env *Env) (int, error) {
	c, err := n.Cond.Eval(env)
	if err != nil {
		return 0, err
	}
	if c != 0 {
		return n.Then.Eval(env)
	}
	if n.Else != nil {
		return n.Else.Eval(env)
	}
	return 0, nil
}
 
type BlockStmt struct{ Stmts []Node }
 
func (n *BlockStmt) Eval(env *Env) (int, error) {
	env = env.Enter() // 新作用域
	result := 0
	for _, s := range n.Stmts {
		v, err := s.Eval(env)
		if err != nil {
			return 0, err
		}
		result = v
	}
	return result, nil
}
 
type WhileStmt struct {
	Cond Node
	Body Node
}
 
func (n *WhileStmt) Eval(env *Env) (int, error) {
	result := 0
	for {
		c, err := n.Cond.Eval(env)
		if err != nil {
			return 0, err
		}
		if c == 0 {
			break
		}
		result, err = n.Body.Eval(env)
		if err != nil {
			return 0, err
		}
	}
	return result, nil
}
 
// ============ 运行时环境（符号表的运行期形式）============
 
type Env struct {
	vars   map[string]int
	parent *Env
}
 
func NewEnv() *Env { return &Env{vars: make(map[string]int)} }
 
func (e *Env) Enter() *Env {
	return &Env{vars: make(map[string]int), parent: e}
}
 
func (e *Env) Get(name string) (int, bool) {
	if v, ok := e.vars[name]; ok {
		return v, true
	}
	if e.parent != nil {
		return e.parent.Get(name)
	}
	return 0, false
}
 
func (e *Env) Set(name string, val int) { e.vars[name] = val }
 
// ============ 解析器 ============
 
type Parser struct {
	tokens []Token
	pos    int
}
 
func (p *Parser) peek() Token          { return p.tokens[p.pos] }
func (p *Parser) next() Token          { t := p.tokens[p.pos]; p.pos++; return t }
func (p *Parser) at(t TokenType) bool  { return p.peek().Type == t }
 
func (p *Parser) expect(t TokenType) (Token, error) {
	tok := p.peek()
	if tok.Type != t {
		return tok, fmt.Errorf("第 %d 行: 期望 %s，实际得到 %s",
			tok.Line, tokName(t), tokName(tok.Type))
	}
	p.next()
	return tok, nil
}
 
func (p *Parser) ParseProgram() (Node, error) {
	stmts := []Node{}
	for !p.at(TokEOF) {
		s, err := p.parseStmt()
		if err != nil {
			return nil, err
		}
		stmts = append(stmts, s)
	}
	return &BlockStmt{Stmts: stmts}, nil
}
 
func (p *Parser) parseStmt() (Node, error) {
	switch p.peek().Type {
	case TokLBrace:
		p.next()
		stmts := []Node{}
		for !p.at(TokRBrace) {
			s, err := p.parseStmt()
			if err != nil {
				return nil, err
			}
			stmts = append(stmts, s)
		}
		if _, err := p.expect(TokRBrace); err != nil {
			return nil, err
		}
		return &BlockStmt{Stmts: stmts}, nil
 
	case TokIf:
		p.next()
		if _, err := p.expect(TokLParen); err != nil {
			return nil, err
		}
		cond, err := p.parseExpr(0)
		if err != nil {
			return nil, err
		}
		if _, err := p.expect(TokRParen); err != nil {
			return nil, err
		}
		then, err := p.parseStmt()
		if err != nil {
			return nil, err
		}
		var elseNode Node
		if p.at(TokElse) {
			p.next()
			elseNode, err = p.parseStmt()
			if err != nil {
				return nil, err
			}
		}
		return &IfStmt{Cond: cond, Then: then, Else: elseNode}, nil
 
	case TokWhile:
		p.next()
		if _, err := p.expect(TokLParen); err != nil {
			return nil, err
		}
		cond, err := p.parseExpr(0)
		if err != nil {
			return nil, err
		}
		if _, err := p.expect(TokRParen); err != nil {
			return nil, err
		}
		body, err := p.parseStmt()
		if err != nil {
			return nil, err
		}
		return &WhileStmt{Cond: cond, Body: body}, nil
 
	default:
		expr, err := p.parseExpr(0)
		if err != nil {
			return nil, err
		}
		if _, err := p.expect(TokSemi); err != nil {
			return nil, err
		}
		return expr, nil
	}
}
 
// ★ 优先级爬升
func (p *Parser) parseExpr(minPrec int) (Node, error) {
	left, err := p.parseUnary()
	if err != nil {
		return nil, err
	}
 
	// 赋值：右结合，优先级最低
	if p.at(TokAssign) {
		p.next()
		vr, ok := left.(*VarRef)
		if !ok {
			return nil, fmt.Errorf("赋值左侧必须是变量")
		}
		rhs, err := p.parseExpr(1) // 右结合：传 1 而不是 2
		if err != nil {
			return nil, err
		}
		return &AssignExpr{Name: vr.Name, Value: rhs}, nil
	}
 
	for {
		tok := p.peek()
		prec, isBinary := precedence[tok.Type]
		if !isBinary || prec < minPrec {
			break
		}
		p.next()
		right, err := p.parseExpr(prec + 1) // 左结合
		if err != nil {
			return nil, err
		}
		left = &BinaryExpr{Op: tok.Type, Left: left, Right: right}
	}
	return left, nil
}
 
func (p *Parser) parseUnary() (Node, error) {
	switch p.peek().Type {
	case TokMinus, TokNot:
		op := p.next().Type
		operand, err := p.parseUnary()
		if err != nil {
			return nil, err
		}
		return &UnaryExpr{Op: op, Operand: operand}, nil
	}
	return p.parsePrimary()
}
 
func (p *Parser) parsePrimary() (Node, error) {
	tok := p.peek()
	switch tok.Type {
	case TokInt:
		p.next()
		v, _ := strconv.Atoi(tok.Value)
		return &IntLit{Value: v}, nil
	case TokIdent:
		p.next()
		return &VarRef{Name: tok.Value}, nil
	case TokLParen:
		p.next()
		e, err := p.parseExpr(0)
		if err != nil {
			return nil, err
		}
		if _, err := p.expect(TokRParen); err != nil {
			return nil, err
		}
		return e, nil
	}
	return nil, fmt.Errorf("第 %d 行: 意外的 token", tok.Line)
}
 
// ============ 演示 ============
 
func demoParser() {
	src := `
x = 10;
y = 0;
i = 1;
while (i <= x) {
    y = y + i;
    i = i + 1;
}
result = y * 2 - 100;
`
	tokens, err := Tokenize(src)
	if err != nil {
		fmt.Println("词法错误:", err)
		return
	}
	ast, err := NewParser(tokens).ParseProgram()
	if err != nil {
		fmt.Println("语法错误:", err)
		return
	}
 
	fmt.Println("=== AST ===")
	printAST(ast, 0)
 
	env := NewEnv()
	val, err := ast.Eval(env)
	if err != nil {
		fmt.Println("运行时错误:", err)
		return
	}
	fmt.Println("\n=== 执行结果 ===")
	fmt.Printf("result = %d\n", val) // 55*2-100 = 10
}
 
func printAST(n Node, depth int) {
	indent := ""
	for i := 0; i < depth; i++ {
		indent += "  "
	}
	switch v := n.(type) {
	case *BlockStmt:
		fmt.Printf("%sBlock\n", indent)
		for _, s := range v.Stmts {
			printAST(s, depth+1)
		}
	case *WhileStmt:
		fmt.Printf("%sWhile:\n%s  cond:\n", indent, indent)
		printAST(v.Cond, depth+2)
		fmt.Printf("%s  body:\n", indent)
		printAST(v.Body, depth+2)
	case *AssignExpr:
		fmt.Printf("%sAssign(%s):\n", indent, v.Name)
		printAST(v.Value, depth+1)
	case *BinaryExpr:
		fmt.Printf("%sBinary(%s):\n", indent, tokName(v.Op))
		printAST(v.Left, depth+1)
		printAST(v.Right, depth+1)
	default:
		fmt.Printf("%s%s\n", indent, n.String())
	}
}

运行输出：

=== AST ===
Block
  Assign(x):
    10
  Assign(y):
    0
  Assign(i):
    1
  While:
    cond:
      Binary(<=):
        i
        10
    body:
      Block
        Assign(y):
          Binary(+):
            y
            i
        Assign(i):
          Binary(+):
            i
            1
  Assign(result):
    Binary(-):
      Binary(*):
        y
        2
      100

=== 执行结果 ===
result = 10

注意观察：y * 2 - 100 被解析成 Binary(-, Binary(*, y, 2), 100) —— * 在更深的层级，说明它结合得更紧。这就是优先级爬升正确工作的证据。

动手二：DSL 规则引擎（带友好错误提示）

真实场景：公司的规则引擎，业务方要写这样的规则：

user.age > 18 AND user.city IN ["北京","上海"] AND score >= 60

语法设计

expression = or_expr
or_expr    = and_expr { "OR" and_expr }
and_expr   = not_expr { "AND" not_expr }
not_expr   = "NOT" not_expr | comparison
comparison = operand [ comp_op operand ]
comp_op    = ">" | ">=" | "<" | "<=" | "==" | "!=" | "IN" | "CONTAINS"
operand    = field_ref | literal | "(" expression ")"
field_ref  = ident { "." ident }
literal    = int | float | string | bool | array
array      = "[" [ literal { "," literal } ] "]"

四个设计决策及理由：

决策理由
优先级用 BNF 层级直接表达or→and→not→cmp 的层级直接编码了 NOT > 比较 > AND > OR，符合 SQL 惯例
用关键字 AND/OR/NOT 而非 &&/||/!业务方不是程序员；避免 & vs && 拼写错误；词法更简单
比较运算符是可选中缀允许 user.isVip（裸布尔字段），规则更自然
数组字面量支持 INcity IN [...] 是最高频模式，作为一等公民

带友好错误的实现（核心部分）

// ParseError 带上下文和修复建议
type ParseError struct {
	Line, Col  int
	Message    string
	Suggestion string
}
 
func (e *ParseError) Error() string {
	var sb strings.Builder
	fmt.Fprintf(&sb, "规则语法错误 (第 %d 行第 %d 列): %s\n", e.Line, e.Col, e.Message)
	if e.Suggestion != "" {
		sb.WriteString("\n💡 提示: " + e.Suggestion + "\n")
	}
	return sb.String()
}
 
type RuleParser struct {
	tokens []Token
	pos    int
}
 
var compOps = map[string]bool{
	">": true, ">=": true, "<": true, "<=": true,
	"==": true, "!=": true, "IN": true,
	"CONTAINS": true, "MATCHES": true,
}
 
var knownKeywords = []string{"AND", "OR", "NOT", "IN", "CONTAINS", "MATCHES", "true", "false"}
 
func (p *RuleParser) parseComparison() (Expr, error) {
	// 括号：递归下降处理嵌套
	if p.at(TokLParen) {
		p.next()
		inner, err := p.parseOr()
		if err != nil {
			return nil, err
		}
		if !p.at(TokRParen) {
			return nil, p.errorf("括号未闭合，期望 ')'")
		}
		p.next()
		return inner, nil
	}
 
	left, err := p.parseOperand()
	if err != nil {
		return nil, err
	}
 
	// 可选的比较运算符（没有就是裸布尔字段）
	if p.at(TokIdent) && compOps[p.peek().Value] {
		opTok := p.next()
		right, err := p.parseOperand()
		if err != nil {
			return nil, err
		}
		return &Compare{Left: left, Op: opTok.Value, Right: right}, nil
	}
	return left, nil
}
 
func (p *RuleParser) errorf(format string, args ...any) error {
	tok := p.peek()
	suggestion := ""
	if tok.Type == TokIdent {
		if s := suggestKeyword(tok.Value); s != "" {
			suggestion = fmt.Sprintf("你是不是想写 %q？", s)
		}
	}
	return &ParseError{
		Line: tok.Line, Col: tok.Col,
		Message:    fmt.Sprintf(format, args...),
		Suggestion: suggestion,
	}
}
 
// 编辑距离建议
func suggestKeyword(got string) string {
	upper := strings.ToUpper(got)
	best, bestDist := "", 1<<30
	for _, kw := range knownKeywords {
		d := levenshtein(upper, kw)
		if d < bestDist && d <= 2 {
			best, bestDist = kw, d
		}
	}
	return best
}
 
func levenshtein(a, b string) int {
	m, n := len(a), len(b)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := 0; i <= m; i++ {
		dp[i][0] = i
	}
	for j := 0; j <= n; j++ {
		dp[0][j] = j
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			cost := 1
			if a[i-1] == b[j-1] {
				cost = 0
			}
			dp[i][j] = min3(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+cost)
		}
	}
	return dp[m][n]
}
 
func min3(a, b, c int) int {
	m := a
	if b < m {
		m = b
	}
	if c < m {
		m = c
	}
	return m
}

效果：

输入:  user.age > 18 ADN user.city == "北京"

输出:  规则语法错误 (第 1 行第 15 列): 表达式结束后还有多余的内容 "ADN"

       💡 提示: 你是不是想写 "AND"？

扩展性验证

要加一个 STARTS_WITH 运算符，只需两处：

// 1. 加到 compOps
"STARTS_WITH": true,
 
// 2. 加到 compareValues
case "STARTS_WITH":
	s, _ := l.(string)
	prefix, _ := r.(string)
	return strings.HasPrefix(s, prefix), nil

词法层和语法层完全不用改——因为 STARTS_WITH 是 identifier，词法分析器已经能识别。

这就是”把运算符设计成关键字而非符号”的扩展性好处。

三个可改进点

  1. 类型检查应在解析期做（根据字段 schema），而不是运行期才发现 user.age > "abc"
  2. 优先级硬编码在函数层级，若支持算术运算应改用优先级爬升
  3. 性能：规则会被反复执行，应把 AST 编译成闭包或字节码，而不是每次解释执行

思考题 2 ·【应用层】

上面的规则引擎有个设计问题：user.age > 18 中，如果 user.age 字段不存在，会在运行时才报错。请设计一个”编译期检查”方案：给定字段 schema，在解析阶段就验证所有字段存在且类型正确。说明你的方案如何处理这三个情况：① 嵌套字段 user.profile.city；② 动态字段（schema 里没有但允许）；③ 字段类型与运算符不匹配。

参考答案

方案：Schema 驱动的语义分析

核心思路：把”验证”从运行期提前到解析期。 这正是编译器语义分析做的事——在运行前发现尽可能多的错误。

// ============ Schema 定义 ============
 
type FieldType int
 
const (
	TypeInt FieldType = iota
	TypeFloat
	TypeString
	TypeBool
	TypeArray
	TypeObject
)
 
type Schema struct {
	Fields map[string]*FieldDef
	// 是否允许 schema 之外的动态字段
	AllowDynamic bool
}
 
type FieldDef struct {
	Type     FieldType
	ElemType FieldType   // TypeArray 时的元素类型
	Children *Schema     // TypeObject 时的子 schema
}
 
// 判断某个运算符支持哪些类型
var opSupportedTypes = map[string][]FieldType{
	">":  {TypeInt, TypeFloat},
	">=": {TypeInt, TypeFloat},
	"<":  {TypeInt, TypeFloat},
	"<=": {TypeInt, TypeFloat},
	"==": {TypeInt, TypeFloat, TypeString, TypeBool},
	"!=": {TypeInt, TypeFloat, TypeString, TypeBool},
	"IN": {TypeInt, TypeFloat, TypeString},
	"CONTAINS":   {TypeString},
	"STARTS_WITH": {TypeString},
}
 
// ============ 类型推导 ============
 
// inferType 推导表达式的类型，同时做检查
func inferType(e Expr, schema *Schema) (FieldType, []error) {
	var errs []error
 
	switch v := e.(type) {
	case *Literal:
		return literalType(v.Value), nil
 
	case *FieldRef:
		ft, err := resolveField(schema, v.Path)
		if err != nil {
			return TypeInt, []error{fmt.Errorf("第 %d 列: %v", v.Col, err)}
		}
		return ft, nil
 
	case *Compare:
		lt, e1 := inferType(v.Left, schema)
		rt, e2 := inferType(v.Right, schema)
		errs = append(errs, e1...)
		errs = append(errs, e2...)
 
		// 检查运算符是否支持这两个类型
		supported := opSupportedTypes[v.Op]
		if !containsType(supported, lt) {
			errs = append(errs, fmt.Errorf(
				"运算符 %s 不支持左操作数类型 %s（字段 %s）",
				v.Op, typeName(lt), v.Left.String()))
		}
		// IN 的右侧必须是数组，且元素类型匹配
		if v.Op == "IN" {
			arr, ok := v.Right.(*ArrayLit)
			if !ok {
				errs = append(errs, fmt.Errorf("IN 的右侧必须是数组字面量"))
			} else {
				for _, elem := range arr.Elements {
					et, _ := inferType(elem, schema)
					if et != lt {
						errs = append(errs, fmt.Errorf(
							"IN 数组元素类型 %s 与左操作数类型 %s 不匹配",
							typeName(et), typeName(lt)))
					}
				}
			}
		} else if !typesCompatible(lt, rt) {
			errs = append(errs, fmt.Errorf(
				"类型不匹配: %s %s %s", typeName(lt), v.Op, typeName(rt)))
		}
		return TypeBool, errs
 
	case *Logical:
		lt, e1 := inferType(v.Left, schema)
		errs = append(errs, e1...)
		if lt != TypeBool {
			errs = append(errs, fmt.Errorf(
				"逻辑运算符 %s 的操作数必须是布尔类型，实际是 %s",
				v.Op, typeName(lt)))
		}
		if v.Right != nil {
			rt, e2 := inferType(v.Right, schema)
			errs = append(errs, e2...)
			if rt != TypeBool {
				errs = append(errs, fmt.Errorf(
					"逻辑运算符 %s 的操作数必须是布尔类型，实际是 %s",
					v.Op, typeName(rt)))
			}
		}
		return TypeBool, errs
	}
	return TypeInt, nil
}
 
// ============ 三个特殊情况的处理 ============
 
func resolveField(schema *Schema, path []string) (FieldType, error) {
	cur := schema
	var lastDef *FieldDef
 
	for i, p := range path {
		def, ok := cur.Fields[p]
		if !ok {
			// ★ 情况 ②：动态字段
			if cur.AllowDynamic && i == len(path)-1 {
				// 允许，但类型未知 —— 返回特殊的"动态类型"
				return TypeDynamic, nil
			}
			return TypeInt, fmt.Errorf("未定义的字段: %s%s",
				strings.Join(path[:i+1], "."),
				suggestField(p, cur))
		}
		lastDef = def
 
		// ★ 情况 ①：嵌套字段
		if i < len(path)-1 {
			if def.Type != TypeObject || def.Children == nil {
				return TypeInt, fmt.Errorf(
					"字段 %s 不是对象，无法访问子字段 .%s",
					strings.Join(path[:i+1], "."), path[i+1])
			}
			cur = def.Children   // 下钻到子 schema
		}
	}
 
	if lastDef == nil {
		return TypeInt, fmt.Errorf("空字段路径")
	}
	return lastDef.Type, nil
}
 
// 字段名的编辑距离建议
func suggestField(got string, schema *Schema) string {
	best, bestDist := "", 1<<30
	for name := range schema.Fields {
		d := levenshtein(strings.ToLower(got), strings.ToLower(name))
		if d < bestDist && d <= 2 {
			best, bestDist = name, d
		}
	}
	if best != "" {
		return fmt.Sprintf("，你是不是想写 %q？", best)
	}
	return ""
}

三个情况的具体处理

情况 ①：嵌套字段 user.profile.city

方案：Schema 递归下钻。

userSchema := &Schema{Fields: map[string]*FieldDef{
	"age":  {Type: TypeInt},
	"name": {Type: TypeString},
	"profile": {
		Type: TypeObject,
		Children: &Schema{Fields: map[string]*FieldDef{
			"city": {Type: TypeString},
			"vip":  {Type: TypeBool},
		}},
	},
}}

解析 user.profile.city 时：

  1. 在根 schema 找 user → 找到，类型是 Object
  2. 下钻到 user.Children，找 profile → 找到，类型是 Object
  3. 再下钻，找 city → 找到，类型是 String

关键点：中间层如果不是 Object，要报明确的错误：“字段 user.age 不是对象，无法访问子字段 .city”

这个设计的额外好处：schema 本身是递归结构，天然支持任意深度嵌套。而且下钻的过程就是一次”作用域链查找”——跟编译器查符号表的逻辑完全同构。

情况 ②：动态字段

方案：引入 TypeDynamic 特殊类型 + AllowDynamic 开关。

const TypeDynamic FieldType = 99  // 类型未知
 
// 类型兼容性检查时，dynamic 与任何类型都兼容
func typesCompatible(a, b FieldType) bool {
	if a == TypeDynamic || b == TypeDynamic {
		return true   // 放宽检查
	}
	return a == b || (isNumeric(a) && isNumeric(b))
}

权衡：

  • 允许动态字段 → 灵活，但失去类型检查的保护
  • 禁止 → 安全，但业务方抱怨”我的字段明明有”

我的建议：分层处理。

  • 核心字段（schema 里定义的）严格检查
  • 动态字段允许，但标记为”未验证”，在规则管理界面上显示警告
  • 运行时对动态字段做防御性处理（取不到值就返回 false，不 panic）

更进一步的方案：支持”部分动态”——schema 里声明”user 下的所有字段都是 string 类型”：

"user": {
	Type: TypeObject,
	Children: &Schema{
		AllowDynamic: true,
		DynamicType:  TypeString,   // 动态字段默认是 string
	},
}

这样既灵活又保留了一定检查能力。

情况 ③：类型与运算符不匹配

方案：运算符的类型表（白名单）。

var opSupportedTypes = map[string][]FieldType{
	">":  {TypeInt, TypeFloat},
	"CONTAINS": {TypeString},
	// ...
}

user.age > "abc" 会报：“运算符 > 不支持左操作数类型 int 与右操作数类型 string 不匹配”

关键的额外检查：IN 的数组元素类型

user.age IN ["北京", "上海"]   // ❌ int 字段配 string 数组

这个错误很容易漏检——因为 IN 的右侧是数组，如果只检查”右侧是数组”就通过了。必须逐个元素检查类型。

三个容易忽略的细节

细节 1 · 错误要一次全报，不要遇错即停

// ❌ 遇到第一个错误就返回
func check(e Expr) error { ... return err }
 
// ✅ 收集所有错误
func check(e Expr) []error { ... return errs }

业务方写规则时，往往有多个错误。一次全报出来能省好几轮修改。这就是上篇说的”错误恢复 + 多错误报告”。

细节 2 · 空值处理要有明确策略

user.profile.city == "北京"
// 如果 user 为 null 怎么办？profile 为 null 怎么办？

三种策略：

  1. 三值逻辑（SQL 的做法）：NULL == "北京" 结果是 UNKNOWN，不是 true 也不是 false
  2. 短路为 false：任何路径取不到值，整个表达式返回 false
  3. 报错

建议用策略 2（短路为 false）。理由：规则引擎的语义是”满足条件才执行动作”，取不到值就当不满足，最符合直觉，也不会因为数据缺失导致规则引擎崩溃。

但要在文档里明确写出来，否则业务方会困惑”为什么这条规则没触发”。

细节 3 · Schema 变更的兼容

字段 schema 会变（新增字段、改类型）。已经写好的规则怎么办？

方案：

  • 规则保存时，同时保存编译后的 AST + 当时的 schema 版本
  • schema 变更时，重新校验所有存量规则，把失效的规则标红
  • 提供”规则健康检查”页面，列出所有有问题的规则

这本质上是一个”数据库 migration”问题——schema 演进时要考虑存量数据的兼容性。规则即数据。

一句话总结

这个设计的核心思想跟编译器完全一致：把错误从运行期提前到编译期。

代价是需要维护 schema，收益是：

  1. 业务方写完规则立即看到错误，不用等到运行时
  2. 规则引擎运行时不需要做类型检查，性能更好
  3. 可以做静态分析（比如检测出矛盾的规则 age > 18 AND age < 10）

这个模式（schema 驱动 + 提前验证）可以推广到很多场景：配置校验、API 参数校验、数据管道的质量检查。凡是”用户输入会被反复执行”的场景，都应该考虑提前验证。

思考题 3 ·【创造层】

Go 用递归下降，GCC/Clang 用 LALR/递归下降混合。假设你要设计一门新语言，怎么选分析策略？如果语言要支持”用户自定义运算符优先级”（如 Haskell），你的选择会变吗？

参考答案

决策框架：五个因素

① 语法复杂度（有歧义吗？需要几层前瞻？）
② 错误提示质量要求
③ 编译速度要求
④ 可维护性（团队能维护吗？）
⑤ 扩展性（语言还要演进吗？）

① 语法复杂度

  • LL(k)：必须在看到前 k 个 token 后确定用哪条产生式。两产生式前 k 个 token 相同就冲突
  • LR(k)：可”看完整条产生式再决定归约”，能处理更多文法
  • 但 LL 可用”回溯”绕过大部分限制，代价是速度和错误提示

② 错误提示（最大差异点）

  • 递归下降：只知道”我猜的这条路走不通”
  • LR：状态机记录”当前所有可能的 token”，能给”expected one of X, Y, Z”

③ 编译速度

  • 递归下降：函数调用，分支预测友好，指令缓存局部性好 → 快
  • 表驱动 LR：每步查表，缓存不友好 → 慢 2~5 倍

④ 可维护性

  • 递归下降：代码就是语法的直接映射，每个产生式一个函数，任何人都能读
  • LR：状态表是生成的，几千个状态，人类无法阅读，改语法要重新生成，diff 无法审阅

这是 Go 选递归下降的关键理由——Go 团队极其在意编译器代码的可读性。

⑤ 扩展性

  • 递归下降：加新语法 = 加新函数，局部改动
  • LR：加新语法可能引入 shift-reduce 冲突，解决冲突可能要重构文法

我的选择（通用语言）

首选：手写递归下降 + 优先级爬升

理由：编译速度、可维护性、扩展性都最优；错误提示的劣势可通过”记录期望集合”缓解。

代价：文法必须避免左递归和歧义，语言设计受约束。

但我接受这个约束——而且我认为这是好事：如果你的语法连递归下降都处理不了，大概率它对人类来说也太复杂了。

这是 Go 的哲学：语言特性应该让编译器简单，也应该让人简单。这两个目标是一致的。

如果要支持自定义运算符，选择会大变

问题在哪

infixl 7 <*>     -- Haskell：自定义优先级和结合性
infixr 5 ++
infix  4 ==
// Scala：优先级由首字符决定，不可自定义
// (字母) < | ^ & = ! : + - * / % (其他)

对解析器的冲击：

  1. 优先级表是动态的——解析到一半才知道某运算符的优先级
  2. 优先级可能重定义——a + b * c 中 * 的优先级取决于上下文定义
  3. 不同作用域可能有不同定义

静态递归下降无法处理——因为 parseExpr(minPrec) 里的 minPrec 比较依赖一个解析时才能确定的表。

三种解法

解法 A · 解析成平坦序列，语义阶段再建树（Haskell）

-- 第一步：不管优先级，全部解析成列表
-- a + b * c  →  [a, +, b, *, c]
 
-- 第二步：语义分析时查优先级表，用算符优先分析法建树
--          →  a + (b * c)

把”优先级解析”推迟到语义阶段——又是”信息推迟到能获取的时候再处理”的模式。

解法 B · 限制自定义能力（Scala）

优先级完全由运算符首字符决定，不可自定义。这样优先级表仍静态，递归下降可用。代价是表达力受限。

解法 C · 放弃中缀运算符（Lisp）

(+ a (* b c))   ; 前缀，优先级由括号显式给出

语法分析极简单（就是括号匹配）。代价是读写体验。

Lisp 的 S 表达式之所以简单，正是因为这个选择——它的语法几乎是”无语法”。这也是 Lisp 宏系统强大的原因：语法树就是数据结构，可直接操作。

我的选择

解法 B（受限自定义）+ 解法 A（延迟解析）的混合：

  1. 默认运算符用静态优先级表（递归下降直接处理，保证 95% 场景的速度和错误提示）
  2. 自定义运算符的优先级由首字符决定（Scala 规则），不可任意指定
  3. 如果某作用域内确实重定义了优先级，回退到”平坦解析 + 延迟建树”

理由：这个混合方案让最常见的情况走快路径，同时保留了表达能力。这是”优化常见路径，为罕见情况保留退路”的经典思路。

更深的洞察：这三个解法对应三种语言哲学

解法语言哲学
A · 延迟解析Haskell表达力优先。语法可以复杂，但编译器要能处理，哪怕慢一点
B · 限制能力Scala实用性优先。牺牲一点表达力，换取编译器简单和错误提示好
C · 放弃中缀Lisp极简优先。语法简单到极致，把复杂度推给用户（括号）和宏系统

没有对错，只有取舍。

但要看到一个共同点：三种解法都接受了”在某个维度上做出牺牲”。它们没有试图”全都要”。

试图全都要的语言，最后往往会得到一个谁都用不好的系统。 这是语言设计（其实也是所有系统设计）最重要的一条教训。

给你自己的检验标准

设计任何系统时，问自己：

  1. 我的核心约束是什么？（编译速度？错误提示？表达力？）
  2. 为了这个约束，我愿意牺牲什么？
  3. 这个牺牲，用户能接受吗？

答不上来第 2 个，说明你还没真正做设计，只是在堆特性。

小结：这一节你应该带走的东西

  1. 编译的五个阶段，每一层都在丢弃信息：词法丢格式、语法丢括号、IR 丢变量名、代码生成丢类型。后面阶段拿不到的信息，就没法做相应优化——这是现代编译器往”保留更多信息”演进的原因。

  2. 理论约束塑造工程实践：

    • 正则无法计数 → 嵌套结构必须用栈 → 编程语言停在 2 型文法
    • 通用 CFG 分析是 O(n³) → LL/LR 只处理子集才做到 O(n)
    • 这解释了为什么编译要分阶段

  3. 递归下降 vs LR 的本质是信息量的差异：递归下降只知道”我猜错了”，LR 知道”所有可能的选项”。这直接决定了错误提示的质量。

  4. 优先级爬升是手写解析器的核心技巧：parseExpr(minPrec)，传 prec+1 得左结合，传 prec 得右结合。值得背下来。

  5. 纯粹的分层在真实系统里总被打破：C 的 typedef 问题、Go 泛型的 [ 歧义，都需要语义信息倒流回语法层。Go 的解法是改语言设计来避开歧义，这是”为了编译器简单而改变语言”的典范。

  6. Go 编译快的三个原因：包级符号表、手写递归下降、扁平 IR。这是明确的取舍——用优化质量换迭代速度。

下一节

06 · 动手：用 Go 写一个 C 编译器

理论讲完，接下来是本章最硬的一个项目：从零实现一个能编译 C 子集（指针、结构体、函数、控制流、递归）的编译器，直接生成可执行的机器码。

老陈的预告：这个项目做完，你会真正理解”高级语言”和”机器指令”之间那道鸿沟是怎么被填平的。而且你会发现一个惊人的事实——编译器 90% 的复杂度不在算法，而在处理各种边界情况和 ABI 细节。

反向链接