从零构建编译器：编译原理实战与考试重点解析

1. 编译器是什么为什么需要学习编译原理当你用Python写下print(Hello World)时计算机其实看不懂这行代码。编译器就像一位翻译官把人类能理解的高级语言转换成机器能执行的二进制指令。我在第一次实现编译器时发现这个过程就像教外星人做菜——需要把放少许盐精确转换成加入3.5克氯化钠。现代编译器的工作流程可以拆解为几个关键阶段前端处理词法分析→语法分析→语义分析把源代码解析成结构化数据中端优化对中间代码进行性能优化后端生成输出目标机器代码以计算斐波那契数列的函数为例def fib(n): if n 1: return n return fib(n-1) fib(n-2)编译器会先将其转化为抽象语法树AST然后生成类似下面的中间表示function fib(n): temp1 n 1 if temp1 goto L1 temp2 n - 1 temp3 fib(temp2) temp4 n - 2 temp5 fib(temp4) return temp3 temp5 L1: return n2. 词法分析从字符流到单词符号词法分析器就像文章的断句工具。当遇到if x 10:这样的代码时它会识别出关键字if标识符x运算符数字10冒号:我常用正则表达式定义词素模式比如// 匹配整数和标识符 const patterns [ [/^\d/, NUMBER], [/^[a-zA-Z_]\w*/, IDENTIFIER], [/^/, GE_OP] ];一个常见的踩坑点是最长匹配原则。比如应该被识别为单个运算符而不是和两个符号。测试时可以用这个案例验证int x10; // 应该识别为int,x,,10,;3. 语法分析构建程序结构树语法分析器根据文法规则检查代码结构。以简单的算术表达式为例E → E T | T T → T * F | F F → ( E ) | id当分析a b * c时会构建如下推导过程E → E T→ T T→ F T→ a T→ a T * F→ a F * F→ a b * c考试常考消除左递归的技巧。原始文法E → E T | T转换为右递归E → T E E → T E | ε4. 语义分析与中间代码生成语义分析器就像严格的语法老师检查类型是否匹配、变量是否声明等。比如这段代码x hello y 5 print(x y) # 类型错误中间代码生成阶段通常会使用三地址码这种形式容易优化且机器无关。例如t1 b * c t2 a t1我在项目中实现过语法制导翻译通过属性文法计算表达式类型产生式: E → E1 T 语义规则: E.type if E1.typeint T.typeint then int else if E1.typefloat || T.typefloat then float else error5. 代码优化与目标代码生成代码优化就像整理行李箱要去掉冗余物品无用代码并合理摆放指令调度。常见的优化技术包括常量折叠x 3*5→x 15公共子表达式消除a b * c d e b * c g优化为t b * c a t d e t g目标代码生成需要考虑机器特性。比如x86架构的寄存器有限需要精心设计寄存器分配策略。一个简单的启发式规则是优先分配在循环中频繁使用的变量。6. 实战用Python实现微型编译器下面演示一个超简版算术表达式编译器的工作流程# 词法分析 def tokenize(code): tokens [] while code: if code[0].isspace(): code code[1:] elif code[0].isdigit(): num while code and code[0].isdigit(): num code[0] code code[1:] tokens.append((NUM, int(num))) # 其他token识别... return tokens # 语法分析递归下降 def parse(tokens): def parse_expr(): left parse_term() while tokens and tokens[0][0] in (PLUS, MINUS): op tokens.pop(0) right parse_term() left (BINOP, op[0], left, right) return left # 其他parse函数... return parse_expr() # 代码生成 def generate(node): if node[0] NUM: return fmov eax, {node[1]} elif node[0] BINOP: left_code generate(node[2]) right_code generate(node[3]) return f {left_code} push eax {right_code} pop ebx {add if node[1]PLUS else sub} eax, ebx 7. 考试重点与常见题型解析根据山东大学近年考题高频考点包括概念题综合属性 vs 继承属性LL与LR分析的区别基本块划分原则计算题正则表达式→NFA→DFA的转换例题将(0|1)*01转换为NFA计算FIRST和FOLLOW集文法 S → aB | ε B → bC C → cS综合题给定代码段进行基本块划分应用3种以上优化技术如删除公共子表达式、强度削弱等我在监考时发现学生最容易在活变量分析和寄存器分配环节出错。建议通过这个例子练习1: x 1 2: y 2 3: z x y 4: if z 0 goto 6 5: x y 6: print(x)需要分析各点的活跃变量集合并模拟寄存器分配过程。