【软考备考】编译原理详解：文法、自动机与表达式转换——纸老虎三兄弟（附 10 道练习）

程序设计语言与编译原理，是上午题里弃考率最高的模块：文法产生式像天书、自动机图看着眼晕、前后缀表达式一转换就乱。

真相是：这块每年 2~4 分的题目，套路比任何模块都死——自动机题就是"走迷宫"，表达式题就是"画二叉树"，文法题就是"套规则硬推"。零数学门槛，全是手工活。

一、编译与解释：先分清两种翻译官

• 编译程序：把源程序一次性整体翻译成目标代码（机器语言），之后运行目标代码。像翻译公司译整本书；

• 解释程序：逐句翻译、逐句执行，不产生目标代码。像同声传译。

编译的六个阶段（顺序要记）：

词法分析 → 语法分析 → 语义分析 → 中间代码生成 → 代码优化 → 目标代码生成

前三个阶段是考点，各管一类错误：

• 词法分析：把字符流切成一个个合法"单词"（记号）。3.5.2这种不合法数字、乱拼的关键字，归它管；

• 语法分析：按文法规则把单词组装成结构（语法树）。括号不匹配、语句结构残缺，归它管；

• 语义分析：检查含义合不合理。类型不匹配（把字符串赋给整型变量）、变量未声明，归它管。

二、文法：语言的"生产规则"

文法就是一组替换规则（产生式）。两类符号：

• 终结符（小写）：最终出现在句子里的字符，不可再分解；

• 非终结符（大写）：中间符号，可以被产生式右部替换。

推导= 从开始符号 S 出发，不断把非终结符替换成产生式右部，直到串里全是终结符。能推出来的串，就属于这个文法描述的语言。

例：文法 G：S→aA，A→bS | b。它能产生哪些串？

S → aA → ab （A 取 b） → ab S → aA → abS → abaA → abab （A 取 bS 再展开） → abab 再循环一轮 → ababab ……

规律一目了然：(ab)ⁿ。考场上给你四个候选串问哪个推不出来，就挨个试推——推不出来就是答案，不需要任何理论。

三、有限自动机：就是走迷宫

自动机图就两个记号：单箭头指入的是初态，双圆圈是终态。识别规则一句话：

从初态出发，按输入串逐字符走边；串走完的那一刻，停在终态上，就接受；否则拒绝。

做题方法就是笨办法：每个候选串都在图上走一遍。比如初态 A，A 读 0 到 B，B 读 1 到 C（C 是终态）——串01从 A 出发：读 0 到 B，读 1 到 C，串尽人终，接受。其余10、00、11走一遍，要么无路可走，要么停在非终态，都拒绝。

DFA（确定的）和 NFA（不确定的）区别一句话：DFA 每个状态对同一个输入只有一条出路，NFA 可能有多条或 ε 空转移。软考识别题大多是 DFA，走迷宫即可。

四、表达式：画棵树，三种遍历给三种答案

三种记法：中缀a+b（运算符在中间）、前缀+ab、后缀ab+（逆波兰式，编译器最爱，因为算它不用括号不用管优先级）。

转换神器：表达式树。建树规则：优先级高的运算先算、做子树；最后算的运算做根。

例：a + b*c——先算b*c（乘号做子树的根），+最后算做总根：

+ / \ a * / \ b c

然后三种遍历对应三种记法：

前序遍历（根左右）：+ a * b c → 前缀 +a*bc 中序遍历（左根右）：a + b * c → 中缀 a+b*c 后序遍历（左右根）：a b c * + → 后缀 abc*+

后缀表达式求值用栈：遇操作数入栈；遇运算符，弹出栈顶两个计算，结果压回栈。

例：3 4 + 5 *：

3 入栈 [3] 4 入栈 [3, 4] 遇 + ：弹 4、3，算 3+4=7，压栈 [7] 5 入栈 [7, 5] 遇 * ：弹 5、7，算 7×5=35，压栈 [35] → 结果 35

五、传值与传址：函数调用的最后一考

• 传值调用：形参是实参的副本，函数里怎么改，实参纹丝不动；

• 传址调用（引用调用）：形参是实参的别名，函数里改的就是实参本身。

f(x){ x=x+1; }，a=5调用f(a)：传值则 a 还是 5；传址则 a 变 6。软考喜欢给一段小程序问输出，本质就考这一句。

六、10 道练习题

基础题（1~5）

1.编译程序与解释程序的区别在于（ ）。

A. 编译程序产生目标代码后再执行，解释程序逐句翻译执行、不产生目标代码 B. 解释程序执行速度更快 C. 编译程序不产生任何代码 D. 两者没有本质区别

2.词法分析阶段的主要任务是（ ）。

A. 检查括号是否匹配 B. 将字符流识别为一个个单词（记号） C. 进行类型检查 D. 生成目标代码

3.某确定有限自动机初态为 A，A 读入 0 转到 B，B 读入 1 转到 C，C 为终态，则下列串中被该自动机接受的是（ ）。

A. 10 B. 00 C. 01 D. 11

4.中缀表达式 a+b 的后缀表达式是（ ）。

A. +ab B. ab+ C. ba+ D. a+b

5.函数f(x){ x=x+1; }，主程序中a=5，以传值方式调用f(a)后，a 的值为（ ）。

A. 6 B. 不确定 C. 编译错误 D. 5

进阶题（6~10，带坑）

6.编译时发现某语句中出现了3.5.2这样不合法的数字形式，该错误应由（ ）阶段发现。

A. 词法分析 B. 语法分析 C. 语义分析 D. 目标代码生成

7.中缀表达式 a+b*c 的后缀表达式为（ ）。

A. ab+c* B. +abc C. abc+* D. abc*+

8.后缀表达式3 4 + 5 *的值为（ ）。

A. 23 B. 60 C. 35 D. 17

9.函数f(x){ x=x+1; }，主程序中a=5，以传址（引用）方式调用f(a)后，a 的值为（ ）。

A. 5 B. 6 C. 不变 D. 编译错误

10.文法 G：S→aA，A→bS|b，下列串中不能由该文法推导出的是（ ）。

A. ab B. abab C. ababab D. aabb

七、答案与详解

1. A编译 = 整体翻译出目标代码再运行；解释 = 逐句翻译逐句执行，不落目标代码。Java/C 是编译路线，传统 Python/Basic 是解释路线。

2. B词法分析管"切单词"：字符流 → 记号流。括号匹配是语法分析（C 的结构问题），类型检查是语义分析。

3. C走迷宫：A—0→B—1→C（终态），串01走完正好停在终态，接受。其余三个要么第一步就没路（A 读 1 无转移），要么停在非终态。

4. B后缀 = 运算符跟在两个操作数后面：ab+。

5. D传值调用，形参 x 是副本，x+1 改的是副本，实参 a 纹丝不动，仍为5。

6. A3.5.2是"造不出来的单词"——词法分析阶段就无法把它识别成合法记号，错误暴露在第一关。注意和"括号不匹配"（语法）、"类型不符"（语义）区分，三者正好对应三个阶段。

7. D画树：先算b*c（子树），+做根；后序遍历 →abc*+。选 A 的是按"先加后乘"的错误顺序建的树——先算的做子树、后算的做根，顺序一错全错。

8. C栈模拟：3、4 入栈，遇 + 弹出算得 7 压回；5 入栈，遇 * 弹出算 7×5 =35。选 B（60）的是把3 4+当成了3×4…… 按步骤走栈就不会错。

9. B传址调用，形参是实参的别名，x+1 直接改在 a 身上 → a =6。和第 5 题对照记忆：传值 5、传址 6，这一对是软考的固定节目。

10. D试推：该文法从 S 出发只能生成(ab)ⁿ形式的串（ab、abab、ababab……）。aabb中出现了aa——S 第一个产生式 S→aA 决定了 a 后面只能跟 A，而 A 只能产生 b 开头的内容，两个 a 永远不可能相邻。

八、五句话带走

1. 编译出目标代码，解释逐句执行；编译六阶段顺序：词法→语法→语义→中间码→优化→目标码；

2. 错误归口：造不出的单词归词法，结构残缺归语法，类型不对归语义；

3. 文法题 = 试推：能推出来的就是合法串；

4. 自动机题 = 走迷宫：初态出发逐字符走，串尽人终即接受；

5. 表达式题 = 画树：先算的做子树、后算的做根；前序前缀、中序中缀、后序后缀；后缀求值用栈：数入栈，运算符弹二算一。

下一篇预告：上午题的压轴模块——数据结构：二叉树的三个遍历（前中后序怎么互相还原）、完全二叉树的编号规律、堆为什么是"顶最大"却"整体无序"。这块正是你算法系列博客的"体"——分治、动规是招式，数据结构是内功。