编译原理试卷核心考点：从正规表达式到LL(1)与四元式

简介：常州工学院编译原理课程试卷配套资料，面向正在备考或复习编译原理的高校学生与任课教师，可用于阶段测验、期末复习和自测对照。内容围绕正规表达式与有限自动机、逆波兰表示、文法二义性及文法所描述语言、LL(1)文法判定、First/Follow集计算、预测分析表构造和if-then-else语句四元式翻译等核心考点展开，覆盖词法分析、语法分析、语义分析与中间代码生成等教学重点。包内共1个doc文件，约55KB，以试卷文档形式集中呈现题目，便于打印或电子端查阅。已有393人浏览学习，适合希望按题型梳理知识脉络、检验掌握程度并查漏补缺的读者。试卷中的DFA构造、表达式转换、二义性证明、LL(1)分析与四元式序列等题目，可帮助读者对照课程要求定位薄弱环节，理解编译各阶段的典型解题思路，适合作为复习阶段的专项练习材料。

1. 编译原理试卷为什么值得认真对待：它其实是一张给编译器做的体检表

编译原理试卷大概是计算机专业课里最容易被误读的一类资料。翻开第一页，正规表达式、DFA、First 集、LL(1)、四元式一路排下来，看着像另一门语言写的天书，很多人扫两眼就合上了，觉得这门课是“背了也白背”。换个角度想，这张卷子问的问题其实都挺朴素：编译器凭什么知道你写的if该走哪条路？凭什么敢把A+B*(C-D)算对？为什么有的语法规则写成那样就“有歧义”，机器会犯迷糊？把一份编译原理试卷当成体检表，每道题对应的都是编译器身体里的一个器官：认字、断句、算账、排流程。看懂这张表，以后遇到“语法错误”“表达式求值异常”“配置文件写错”这类报错，脑子里就会多出一层画面。

2. 正规表达式与有限自动机：编译器怎么学会认字

编译器做的第一件事，是把一长串字符切成一个个有意义的“词”——if、变量名、数字、加号。这一步叫词法分析，而它手里的两件工具就是正规表达式和有限自动机。前者是人类写规则用的，后者是机器跑规则用的，两者本质上说的是同一件事，只是表达方式不同。

2.1 正规表达式到底在描述什么

正规表达式不是“匹配字符串的技巧”，而是一种描述字符串集合的形式化写法。它只有三种基本操作：连接（把两段拼起来）、选择（这个或那个）、闭包（重复零次或多次）。所有复杂的规则，都是这三种操作叠出来的。

打个比方，正规表达式像身份证号码的格式规定：前六位是地区码，中间八位是生日，最后一位是校验位。规定本身不指向任何一个具体的人，它描述的是“所有合法身份证号”这个集合。正规表达式也一样，(0|1)*01(0|1)*描述的不是某一个串，而是“所有含有 01 子串的二进制串”这一整个集合。

理解了这一点，就能明白为什么试卷第一题会同时给出字母表和自然语言描述：字母表限定你能用哪些字符，自然语言描述限定结构，你的任务是把这个结构翻译成由连接、选择、闭包组成的表达式。翻译过程中最容易翻车的地方，是边界情况——最短的串算不算、空串算不算、长度为 1 的串算不算。这些细节不写清楚，表达式就会悄悄漏掉一类字符串。

2.2 DFA 是一台没有记忆的检票闸机

确定有限自动机（DFA）听起来唬人，其实就是一台没有记忆的检票闸机。它只有有限的几个“站位”，每读入一个字符，就按照固定规则从当前站位走到下一个站位，走完全部字符后，如果停在“允许通过”的站位，这个串就被接受。

关键在于“没有记忆”这四个字：它不记得自己一路上读过什么，只知道自己现在站在哪个站位。正因为不记忆，它才能用极少的资源高速运行，这也是词法分析器普遍采用它的原因。地铁闸机不需要记得你今天刷了几次卡，它只需要判断“当前这张卡是否有效”。

把正规表达式变成 DFA，中间通常先经过一个带“空跳”的 NFA，再做子集构造，最后做状态化简。这条流水线在教材里画得很长，但核心思想只有一句：把“我可能同时在好几个站位”合并成“我现在确定在哪个站位”。

2.3 为什么非要化简成最简 DFA

试卷里常写“构造与之等价的最简 DFA”，很多人的疑问是：能跑不就行了吗，为什么还要求最简？

原因很实际。DFA 最终要变成代码里的状态表，状态数直接对应表的大小和判断分支的多少。两个状态如果对后续所有输入的反应完全一样，它们就是等价的，合并之后行为一点不变，但表小了一圈。状态化简就是反复找这种“行为一致”的状态对，合并到不能再合并。

提示：判断两个状态能不能合并，看的不是它们“长得像不像”，而是从这两个状态出发，读入任何字符串，接受与否的结果是否永远一致。这个判断要一直推到不再产生新的区分才停。

2.4 拿试卷上的两道题走一遍

第一小题：字母表 {0,1} 上，不以 0 开头、且以 11 结尾的所有字符串。拆成两个条件看——“不以 0 开头”等于“第一个字符必须是 1”，“以 11 结尾”等于“最后两个字符是 11”。正规表达式可以写成11 | 1(0|1)*11，前面那一项专门兜住最短的串11，这是最容易漏掉的边界。

对应的 DFA 只需要四个有效状态：起点、结尾是单个 1、结尾是 11（接受态）、结尾是 0。

# 识别 {0,1} 上"不以 0 开头、且以 11 结尾"的字符串 # start: 还没读到字符 / s1: 结尾是单个 1 / s11: 结尾是 11（接受态）/ s0: 结尾是 0 dfa = { ("start", "1"): "s1", ("start", "0"): "dead", # 首字符是 0，直接判死 ("s1", "1"): "s11", ("s1", "0"): "s0", ("s11", "1"): "s11", # 已经以 11 结尾，再读 1 仍然以 11 结尾 ("s11", "0"): "s0", ("s0", "1"): "s1", ("s0", "0"): "s0", } accept = {"s11"} def match(s: str) -> bool: state = "start" for ch in s: state = dfa.get((state, ch), "dead") # 没定义的转移一律进死状态 if state == "dead": return False return state in accept for s in ["11", "1", "111", "1011", "011", "1101"]: print(s, match(s)) # 结果依次为 True False True True False False

这段代码把状态转移表直接写成字典，accept是接受态集合，match逐字符推进。之所以把“首字符是 0”单独设为死状态，是因为一旦第一个字符错了，后面读什么都救不回来。注意s11读入 1 之后仍停在s11——111的结尾依然是 11，这一点初学者经常写错成回到s1。

第二小题简单些：含 01 子串，表达式是(0|1)*01(0|1)*，DFA 只要三个状态——还没见到 0、上一个字符是 0、已经出现过 01。一旦进入第三个状态，后面读什么都停在那儿。

3. 逆波兰表示与四元式：表达式和语句被翻译成了什么样

词法分析把字符切成词之后，编译器要处理结构问题：这个表达式先算哪一步？那句if-else在机器眼里长什么样？这两个问题的答案，分别就是逆波兰表示和四元式序列。它们都属于“中间表示”，往上承接源代码，往下对接目标代码。

3.1 逆波兰表示：运算符排到操作数后面

平时写的A+B叫中缀表示，运算符夹在两个操作数中间。好处是人读着顺，坏处是必须靠括号和优先级来消除歧义。逆波兰表示（后缀表达式）把运算符挪到操作数后面，写成A B +，从此不需要括号，也不需要记优先级，从左往右扫一遍就能算完。

打个比方，中缀表达式像一份写着“先切菜再热锅”的菜谱，你得记住各种先后规则；后缀表达式像后厨已经按出菜顺序摆好的备菜盘，厨师只需要按顺序动手，不用思考。这也是为什么早期计算器和栈式虚拟机偏爱后缀形式：机器不擅长处理优先级，但非常擅长按顺序干活。

代价是可读性。A B C D - * +这串东西，人得在脑子里搭个栈才能看懂，所以后缀形式几乎不会直接给人看，它是给机器看的中间形态。

3.2 A+B*(C-D)+E/(C-D) 是怎么变过去的

转换的核心是一个栈和一个规则：遇到操作数直接输出，遇到运算符时先把栈里优先级不低于它的运算符全部弹出输出，再把自己压进去；遇到左括号压栈，遇到右括号就一直弹到左括号为止。

# 中缀转后缀（逆波兰）的调度场算法，最小实现 prec = {"+": 1, "-": 1, "*": 2, "/": 2} def to_rpn(tokens): out, ops = [], [] for t in tokens: if t.isalpha(): # 操作数：直接进结果 out.append(t) elif t == "(": ops.append(t) elif t == ")": while ops and ops[-1] != "(": out.append(ops.pop()) ops.pop() # 弹出并丢弃左括号 else: # 运算符 while ops and ops[-1] != "(" and prec[ops[-1]] >= prec[t]: out.append(ops.pop()) # 优先级高的先走 ops.append(t) while ops: # 收尾：栈里剩下的全部吐出 out.append(ops.pop()) return out print(to_rpn(list("A+B*(C-D)+E/(C-D)"))) # ['A','B','C','D','-','*','+','E','C','D','-','/','+']

结果就是A B C D - * + E C D - / +。这里有两个细节值得留意：一是prec里的数字只是相对大小，用什么数值无所谓，关键体现*/高于+-；二是循环条件用了>=而不是>，这保证了同级运算符按从左到右的顺序处理，也就是左结合。如果把>=改成>，减法这类不满足结合律的运算就会算错。

注意：C-D 在表达式里出现了两次，转成后缀后也是两段独立的C D -，编译器不会自动帮你合并公共子表达式，那属于后续的优化阶段。

3.3 四元式：把一句 if-else 拆成流水账

逆波兰只解决表达式，遇到if-else这种带跳转的语句就无能为力了。这时需要四元式：每条指令由四个字段构成——运算符、第一个操作数、第二个操作数、结果。形如(+, x, y, t1)表示把 x 加 y 的结果存进临时变量 t1。

四元式的好处是结构极其规整，每条都是定长四元组，便于存进数组、也便于后续做优化和生成目标代码。它像流水账：不写“如果……那么……否则……”，只写“判断、跳转、赋值、再跳转”，一行一行往下走。

把if x>0 ∧ y>0 then z:=x+y else begin x:=x+2; y:=y+3 end翻译成四元式，关键在于布尔表达式的短路求值——x>0一旦为假，y>0根本不用算。

注意第 2 条和第 4 条里的jf（jump if false）。很多教材的写法是先算出一个and的临时变量再统一跳转，那种写法虽然直观，却丢掉了短路语义——y>0在x>0为假时本来不该被求值。如果 y 是一个有副作用的函数调用，两种写法得到的结果会不一样。这种差别在考试里可能只扣几分，在真实项目里就是血泪经验。

3.4 逆波兰和四元式不是同一层的东西

这两者经常被混为一谈，因为它们都被叫作“中间表示”。区别在于覆盖范围：

简单说，逆波兰只回答“这个式子怎么算”，四元式还要回答“这句话执行完该去哪儿”。后者才是完整的中间代码。

4. 文法二义性与 LL(1)：同一句话为什么能长出两副骨架

前面两步处理的都是“词”和“表达式”，到了语法分析，编译器要面对完整的句子结构。这里有两个看似矛盾的要求：一方面，一门语言的语法规则不能有歧义；另一方面，规则还得足够简单，让机器看一眼就能决定走哪条路。二义性和 LL(1) 分别对应这两件事。

4.1 二义性：一句话两种断句

“咬死了猎人的狗”这句话，可以理解成“狗咬死了猎人”，也可以理解成“猎人养的那条狗被咬死了”。同一串字，两种语法结构，这就是二义性。

文法的二义性完全是同一回事：同一个句子，存在两棵不同的语法分析树。注意，二义性是文法（也就是你写的那套规则）的属性，不是句子的属性。句子本身没有歧义，是那套规则给了它两条生成路径。

这一点特别重要，因为它决定了解法。证明一个文法有二义性，只需要找出一个句子，给出它的两棵不同分析树，就足够了——不需要穷举，不需要证明所有句子都有问题。反过来，证明一个文法没有二义性则困难得多，通常要靠构造性论证。

4.2 一个“偶数在开头或结尾”的文法为什么会有两条路

试卷第三题给的文法，核心结构是：N → SE | ES，其中S生成一串数字，E生成一个偶数，D生成一个数字。N的两种候选式，一种让偶数在末尾，一种让偶数在开头。

要证明二义，挑最短的句子就行：22。它可以走N → SE，让S生成2、E生成2；也可以走N → ES，让E生成2、S生成2。两条路都合法，生成同一串字符，于是同一串字符有了两棵分析树。

如果要做得更严谨，可以指出：只要一个串的首位和末位都是偶数，它就能被这两条路径同时覆盖。这也解释了为什么这个文法的设计者故意把SE和ES并排放——它天生就留了个重叠区。

至于这个文法描述的语言，说人话就是“长度至少为 2、首位或末位是偶数的数字串”。注意S不能推出空串，所以单个数字2不在其中，这类边界在答题时经常被忽略。

4.3 First 和 Follow：一个管开头，一个管后面

到了 LL(1) 部分，First 集和 Follow 集是绕不开的两个概念。它们都是符号集合，都要反复迭代到不再变化，所以很容易混。

First 集回答的是“从这个符号出发，第一个字符可能是谁”。Follow 集回答的是“这个符号后面，可能紧跟着谁”。前者用于挑候选式，后者用于处理空产生式。打个比方，First 是“这道菜的第一口可能是什么味道”，Follow 是“吃完这道菜，下一道可能是什么”。

# 用一个结构相似的迷你文法演示 First 集的不动点计算（非原题） grammar = { "E": [["T", "E'"]], "E'": [["+", "T", "E'"], []], # 空列表代表 ε 产生式 "T": [["F", "T'"]], "T'": [["*", "F", "T'"], []], "F": [["(", "E", ")"], ["a"]], } first = {A: set() for A in grammar} changed = True while changed: # 反复传播，直到没有任何集合再变大 changed = False for A, prods in grammar.items(): for prod in prods: if not prod: # 空产生式：First 直接含 ε if "ε" not in first[A]: first[A].add("ε"); changed = True continue for sym in prod: # 是终结符就取自己，是非终结符就取它的 First 去掉 ε add = first[sym] - {"ε"} if sym in grammar else {sym} if not add <= first[A]: first[A] |= add; changed = True # 该符号推不出 ε，后面的符号就没资格当首字符，停 if sym not in grammar or "ε" not in first[sym]: break else: first[A].add("ε") # 整个候选式都能推空 for A in ["E", "E'", "T", "T'", "F"]: print(A, sorted(first[A]))

这段代码做了两件事：一是逐个候选式扫描，把首符号能产生的东西并进来；二是用while changed循环到集合不再变化，因为一个符号的 First 可能依赖另一个符号的 First，而依赖关系可能有环。break那一句是关键——如果当前符号推不出空串，它后面那些符号永远轮不到当首字符，继续扫下去是浪费时间。

Follow 的规则稍微绕一点：先把开始符号的 Follow 里塞进结束符$，然后对每条产生式A → αBβ，把 First(β) 去掉 ε 加进 Follow(B)；如果 β 能推出空串，或者 B 就在产生式末尾，再把 Follow(A) 整体加进 Follow(B)。这里有个常见错法：把 ε 也加进 Follow，实际上 Follow 里不该出现 ε。

4.4 LL(1) 和预测分析表：看一眼就决定走哪条

LL(1) 这个名字拆开看就懂了：第一个 L 是从左到右扫描输入，第二个 L 是最左推导，括号里的 1 是向前看一个符号。合起来就是——从左往右读，每次只看下一个字符，就能唯一决定用哪条产生式。

判定条件也就两条：对同一个非终结符的任意两条候选式 α 和 β，First(α) 和 First(β) 不能有交集；如果 β 能推出空串，那么 First(α) 和 Follow(该非终结符) 也不能有交集。翻译成人话就是：不许出现“看同一个字符，两条规则都说得通”的情况。

满足条件之后，就能把规则填进预测分析表：行是非终结符，列是终结符，格子里写“用哪条产生式”。分析时维护一个栈，栈顶是非终结符就去查表，查到什么就展开什么。整个过程没有回溯，也没有猜测，像自动售货机——投进去什么，就掉出来什么。

反过来说，左递归和左公因子是 LL(1) 的两大杀手。左递归会让分析器无限展开下去，左公因子会让两条候选式的 First 撞车。遇到这两种情况，得先做消除左递归、提取左公因子，才有资格谈 LL(1)。

5. 常见误区拆解：正规表达式、文法与中间表示到底谁管谁

上面几章分别讲了词法、语法、中间代码三块，概念一多，边界就开始模糊。下面这五组是初学者最容易搞混的，每组按“混在哪儿、为什么混、怎么区分”说清楚。

5.1 正规表达式和文法：都能描述语言，但能力差一截

易混点：两者都是“写一套规则来描述一批字符串”，课本上也都是用箭头、竖线、括号来写。

为什么混：正规表达式里的|和文法里的候选式长得像，正规表达式的*和文法里的递归也长得像，初学时会觉得它们只是写法不同。

怎么区分：问一个问题——这套规则能不能数嵌套？正规表达式描述不了“n 个左括号配 n 个右括号”这种结构，因为它的“记忆”只有有限个状态；文法可以，因为文法允许递归地调用自己。所以词法层（标识符、数字、关键字）用正规表达式，语法层（括号配对、if 嵌套、函数调用）必须用文法。这条分界线在编译器的模块划分里是硬性的。

5.2 逆波兰表示和四元式：都叫中间表示，管的范围不一样

易混点：两者都出现在“中间代码”这一章，都是把源代码换个形式写出来。

为什么混：教材常把它们放在同一节讲，加上都能用来表示A+B，看起来像是两种可互换的写法。

怎么区分：看有没有跳转能力。逆波兰只是一串操作数和运算符，没有“跳到第几条”的概念，天生只能表示没有分支的表达式；四元式每条都带序号，可以写jf t1 → (8)这种跳转，因此能表示循环和分支。判断方法很直接：如果这段逻辑里有if、while、goto，逆波兰就表示不了，必须上四元式或三元式。

5.3 文法的二义性和语言的二义性：前者是写法问题，后者不存在

易混点：课本说“该文法有二义性”，听起来像是在说这门语言本身有毛病。

为什么混：二义性确实表现为“同一个句子两棵树”，很容易理解成句子的问题。

怎么区分：二义性是文法这种“描述方式”的属性。同一个语言可以有很多套文法，其中有的二义，有的不二义。经典例子是算术表达式：写成E → E+E | E*E | id有二义，改写成E → E+T | T、T → T*F | F之后就没有了，而两者描述的语言完全一样。所以遇到二义性，正确反应不是“这个语言有问题”，而是“换一套等价但更严格的写法”。顺带一提，有些语言确实无法用无二义的文法描述，那属于另一类问题。

5.4 First 集和 Follow 集：一个看前面，一个看后面

易混点：两个都是非终结符对应的符号集合，都要迭代到不动点，都在 LL(1) 判定里出现。

为什么混：计算过程相似，都要反复扫描产生式，公式也容易记串。

怎么区分：记住它们各自回答的问题。First(A) 是“从 A 出发，第一个字符可能是谁”，所以里面可以出现 ε——表示 A 可以什么都不生成。Follow(A) 是“A 的后面可能紧跟谁”，里面不该出现 ε，因为“后面跟着空”没有意义，取而代之的是结束符$。使用场景上，First 用来在多个候选式之间挑一个，Follow 用来判断“当某个非终结符能推出空串时，是不是该把它跳过去”。

5.5 无二义和 LL(1)：不冲突，但也不是一回事

易混点：两个词都跟“确定性”沾边，很容易被当成同义词。

为什么混：教材里两个概念前后脚出现，都会说“这样分析器就不会犯迷糊”。

怎么区分：无二义说的是“整句层面只有一棵分析树”，是一种全局性质；LL(1) 说的是“从左到右、只看一个符号就能立刻决定用哪条规则”，是一种更强的局部可判定性质。一个文法完全可能既无二义，又不满足 LL(1)——只要它含左递归，或者两条候选式的 First 有交集，就过不了 LL(1)，尽管它生成的每句话都只有唯一一棵树。反过来，满足 LL(1) 的文法一定无二义。所以判断顺序是：先消除左递归和左公因子，再谈能不能用 LL(1)。

6. 什么时候该用它、什么时候别硬啃：一份试卷库的适用边界

把这几章串起来看，一份编译原理试卷的价值不在于“押中多少题”，而在于它把编译器从认字到出码的每个环节都摆到了台面上。它的适用场景其实很明确。

适合用的时候，是把它当成阶段自测的尺子。学完词法，就只看正规表达式和最简 DFA 那部分，掐时间做完，重点检查边界串有没有漏；学完语法，就专攻二义性证明、First/Follow 计算和预测分析表构造，尤其是那种“先证明是 LL(1)、再建表”的连环题，它逼着你把每一步的判断依据写清楚；学完中间代码，就练逆波兰和四元式，重点体会短路求值这类细节。这种分块使用的方式，比从头到尾刷一遍有效得多，因为每个阶段你只需要面对一个认知目标。

不太适合用的时候有两种。第一种是把它当成唯一的学习材料。试卷的题目是抽样，覆盖的是最典型的知识点，像词法分析里的正则到 NFA 再到 DFA 的完整构造流程、语法分析里的 LR 系列方法，一份卷子未必都涉及。只刷卷子容易形成“题型记忆”，换个问法就卡住。第二种是直接背答案。文法和表达式这类题，答案往往依赖于你选的推导顺序或临时变量命名，背下来的答案换个输入就失效，真正要带走的是判断流程——先看什么、再看什么、哪一步容易出错。

我自己的习惯是每次做完一道文法题，都强制走一遍“这三步”：第一步，把文法抄一遍，标出所有候选式；第二步，找一个最短的边界串，看它到底有几条生成路径；第三步，才动笔算集合和建表。这个习惯是被坑出来的——有次算 First 集，因为漏看了一条空产生式，后面整张预测分析表全错，检查了半天才发现问题出在第一行。从那以后我每次做这类题都强制走一遍这三步，慢一点，但不会返工。这份资料里的题目按阶段分得挺清楚，如果你正准备系统过一遍编译原理，拿去当自测清单正合适，希望帮到你。

本文还有配套的精品资源，点击获取