简介这份常州工学院编译原理试卷Adoc格式55KB共1个文件面向计算机专业学生及备考编译原理的学习者用于检验词法分析、语法分析、语义分析与代码生成等核心章节的掌握程度。试卷内容覆盖正规表达式与最简DFA构造、逆波兰表示及三元式序列、文法二义性证明与语言描述、First集与Follow集计算、LL(1)文法判定与预测分析表构造以及if-then-else语句的四元式翻译等典型题型知识点分布完整适合作为期末复习、自测与查漏补缺的练习材料。目前已有391人学习下载可作为课程同步训练与考前模拟的参考。通过逐题演练读者能够熟悉编译原理常见考点的解题思路与规范书写方式加深对自顶向下分析流程和中间代码生成方法的理解也可用于教师命题参考或同学间交流讨论。1. 编译原理期末复盘从正规式到四元式一张图串起五大模块编译原理这门课很多人学到一半会觉得知识点是散的词法分析一套、语法分析一套、语义分析和中间代码又一套各章之间像五座孤岛。但真正把试卷摊开来看从正规表达式、最简DFA到逆波兰表示、二义性证明再到First/Follow集、LL(1)预测分析表、四元式序列其实是一条完整的流水线——源程序从字符流进来经过词法、语法、语义、中间代码生成一步步被翻译成机器能理解的形式。这份试卷库把这条流水线上的关键节点都覆盖到了适合正在系统复习编译原理的人拿来当查漏补缺的索引。下面按知识地图、各模块要点、易错点、复习清单的顺序把这份试卷涉及的内容重新梳理一遍。2. 词法分析双核正规表达式与最简DFA的构造要点词法分析是编译器的第一道关口任务是把字符流切分成有意义的单词符号。试卷第一题直接考了两个核心能力给一个自然语言描述写出正规表达式再构造等价的最简DFA。这道题分值30分是整个试卷里占比最高的部分说明词法分析在课程考核中的分量。2.1 正规表达式从自然语言到形式化描述正规表达式是描述字符串模式的形式化工具三种基本操作——连接、选择、闭包——组合起来就能表达大多数词法规则。试卷里两个小题分别对应两种典型的描述方式。第一小题字母表 {0,1} 上不以0开头但以11结尾的所有字符串。拆解一下不以0开头意味着首字符必须是1以11结尾意味着最后两个字符固定是11中间部分可以是任意长度的0和1。所以正规表达式可以写成1(0|1)*11这里1锁定首字符(0|1)*覆盖中间任意部分11锁定结尾。注意中间部分可以是空串所以111这种长度为3的字符串也满足条件。第二小题字母表 {0,1} 上包含01子串的所有字符串。这个描述更宽松只要字符串里出现过连续的01就行。正规表达式可以写成(0|1)*01(0|1)*前后各加(0|1)*表示01子串前后可以有任意字符。这两个表达式看起来简单但考试时容易漏掉边界情况比如第一题里(0|1)*是否允许空串、第二题里01是否可以出现在开头或结尾。2.2 最简DFA从正规表达式到状态机有了正规表达式下一步是构造等价的DFA并且要化简到最简。标准流程是正规表达式 → NFAThompson构造法→ 子集构造法转DFA → 最小化Hopcroft算法或填表法。以第一小题的1(0|1)*11为例构造DFA时需要跟踪的状态信息是当前是否已经看到了结尾的11。具体来说状态可以设计为状态含义输入0输入1q0初始状态死状态q1q1已读首字符1q1q2q2已读到结尾的第一个1q1q3q3已读到结尾的11接受态q1q3这里q0遇到0进入死状态因为首字符不能是0。q3是接受状态但注意q3遇到0会回到q1遇到1保持在q3因为结尾的11可能重叠。化简时死状态和q0不等价q0有出路死状态没有q1、q2、q3需要进一步判断。梳理下来会发现q2和q3在输入0时都去q1输入1时q2去q3、q3去q3行为不同不能合并。最终最简DFA通常有4个状态含死状态或3个有效状态加一个死状态。注意考试时画DFA要标清楚初始状态和接受状态转移函数要完整不能有缺失的转移。3. 语法分析核心二义性证明与语言描述语法分析是编译原理的重头戏试卷第三题和第四题都集中在这个模块。第三题考二义性证明和语言描述第四题考LL(1)文法的完整分析流程。这两道题加起来45分是整张试卷的另一个大头。3.1 二义性证明找两棵不同的语法树试卷给出的文法G开始符号为N是这样的N → SE | E S → SD | D E → 0 | 2 | 4 | 6 | 8 | 10 D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9证明二义性的标准方法是找到一个句子它能对应两棵不同的语法分析树或两个不同的最左推导。这个文法里N可以推导出SE或ES可以推导出SD或DE是偶数D是数字。观察一下E本身可以推导出单个偶数如0、2、4等而S推导出的D也可以是单个数字。如果一个句子只有一个字符比如2它既可以通过N→E→2得到也可以通过N→SE→DE→2E...等等这里需要仔细看。实际上N→SES→DD→2然后E必须推导出某个东西但E不能推导出空串所以单字符2只能走N→E这条路。找一个更典型的二义性例子考虑句子22。它可以走N→SES→SD→DD→22E→2得到222不对这样长度不对。再仔细看N→SE如果S→D→2E→2得到22。另一条路N→EE只能推导出单个偶数不能推导出22。所以22只有一条路。实际上这个文法的二义性可能出现在更长的句子上。比如222N→SES→SD→DD→22E→2得到222或者N→SES→D→2E→2...但E→2只能得到一个2所以S必须贡献两个字符。另一条路N→SES→SD→DD→22E→2还是同一条。再试N→SES→SD→DD→22E→2这是唯一的。等等E可以推导出10这是两个字符。所以102可以走N→SES→D→1不对D只能推导出单个数字S→D→1然后E→02E不能推导出02。E只能推导出0、2、4、6、8、10。所以102可以走N→SES→D→1E→02不行。或者S→SD→1D→10E→2得到102。另一条路N→SES→D→1E→02不行。所以102只有一条路。实际上这个文法的二义性需要更仔细地找。考虑100N→SES→SD→DD→10E→0得到100另一条路N→SES→D→1E→00不行。或者N→SES→SD→DD→10E→0还是同一条。再想想E可以推导出10S可以推导出SDD可以推导出1和0。所以1010可以走N→SES→SD→DD→10E→10得到1010另一条路N→SES→SD→SDD→DDD→101不对S→SD→DD→10然后S再→SD→10D→101这样S推导出101E→0得到1010。两条路都得到1010但语法树不同。这就是二义性。这个文法的语言描述N生成的是由偶数E和数字序列S组成的字符串其中S生成的是数字串E生成的是偶数。整体语言可以描述为所有由数字组成且以偶数结尾的字符串或者更准确地说N生成的是数字串其中最后一个字符必须是偶数0、2、4、6、8或者整个串就是一个偶数包括10。因为E出现在N的右部或左部S生成任意数字串所以N生成的语言是所有以偶数结尾的数字串加上单独的偶数10。3.2 LL(1)文法First集、Follow集与预测分析表第四题给出了一个典型的表达式文法E → TE E → E | ε T → FT T → T | ε F → PF F → *F | ε P → (E) | ^ | a | b这道题要求三件事计算First集和Follow集、证明是LL(1)文法、构造预测分析表。这是自顶向下语法分析的完整流程考试时一步错步步错所以每一步都要仔细。First集的计算规则对于产生式A→αFirst(α)包括α能推导出的所有首终结符。如果α能推导出ε则ε也加入First(α)。非终结符First集E{ (, ^, a, b }E{ , ε }T{ (, ^, a, b }T{ (, ^, a, b, ε }F{ (, ^, a, b }F{ *, ε }P{ (, ^, a, b }Follow集的计算规则Follow(S)包含结束符$或#。对于产生式A→αBβFollow(B)包含First(β)中除ε外的所有符号如果β能推导出ε则Follow(B)包含Follow(A)。非终结符Follow集E{ ), $ }E{ ), $ }T{ , ), $ }T{ , ), $ }F{ , *, ), $ }F{ , *, ), $ }P{ , *, ), $ }证明LL(1)文法需要检查每个非终结符的产生式看它们的First集是否不相交。如果某个非终结符的产生式右部能推导出ε还需要检查First集和Follow集是否不相交。对于E产生式是E和ε。First(E){}First(ε){ε}不相交。Follow(E){), $}与First(E){}不相交所以E满足LL(1)条件。对于T产生式是T和ε。First(T){ (, ^, a, b }First(ε){ε}不相交。Follow(T){, ), $}与First(T)不相交满足。对于F产生式是*F和ε。First(F){}First(ε){ε}不相交。Follow(F){,, ), $}与First(F){}不相交这里要注意Follow(F)包含而First(F)也包含它们相交了所以这个文法可能不是LL(1)文法。等等再仔细看F的产生式F →F | ε。First(F){}Follow(F)包含吗Follow(F)的计算F出现在F→PF中所以Follow(F)包含Follow(F)。Follow(F)包含、、)、$。所以Follow(F)确实包含。那么First(F){}和Follow(F){,, ), $}相交于这意味着当栈顶是F、输入符号是时既可以选F也可以选ε产生冲突。所以这个文法不是LL(1)文法。但是试卷要求证明它是LL(1)文法这里可能是我对文法的理解有误。再检查一下原文法F →F | ε。如果F出现在F→PF中那么Follow(F)确实包含Follow(F)。Follow(F)的计算F出现在T→FT中所以Follow(F)包含First(T){ (, ^, a, b, ε }去掉ε后加上Follow(T){, ), $}。所以Follow(F){ (, ^, a, b, , ), $ }。那么Follow(F)也包含这些。First(F){}与Follow(F)不相交因为Follow(F)里没有。等等Follow(F)里有没有*F出现在T→FT中T的产生式是T|εFirst(T){ (, ^, a, b }没有*。所以Follow(F)里没有*。那么Follow(F)里也没有*。所以First(F){}和Follow(F)不相交满足LL(1)条件。我之前的计算有误。重新算Follow(F)F出现在T→FT中Follow(F)包含First(T)。First(T){ (, ^, a, b, ε }去掉ε后是{ (, ^, a, b }再加上Follow(T){, ), $}。所以Follow(F){ (, ^, a, b, , ), $ }。没有*。所以Follow(F)也没有*。那么First(F){}和Follow(F)不相交满足LL(1)条件。预测分析表的构造行是非终结符列是终结符和$。对于每个产生式A→α对于First(α)中的每个终结符a在M[A, a]填入A→α如果α能推导出ε则对于Follow(A)中的每个符号b在M[A, b]填入A→α。非终结符()*^ab$EE→TEE→TEE→TEE→TEEE→εE→EE→εTT→FTT→FTT→FTT→FTTT→TT→εT→TT→TT→TT→TT→εFF→PFF→PFF→PFF→PFFF→εF→εF→*FF→εPP→(E)P→^P→aP→b这张表是LL(1)分析器的核心考试时要把每个单元格都填对不能有冲突。4. 中间代码生成逆波兰表示与四元式序列中间代码生成是编译过程的后期阶段把源程序翻译成一种介于高级语言和机器码之间的表示形式。试卷第二题考逆波兰表示和三元式序列第五题考四元式序列。这两道题加起来25分虽然分值不如语法分析但操作性强容易拿分也容易丢分。4.1 逆波兰表示栈驱动的表达式转换逆波兰表示也叫后缀表达式运算符写在操作数后面不需要括号。试卷第二题要求把AB*(C-D)E/(C-D)转成逆波兰表示。转换规则遇到操作数直接输出遇到运算符则与栈顶运算符比较优先级如果当前运算符优先级不高于栈顶则弹出栈顶输出直到栈顶优先级更低或栈为空然后当前运算符入栈。遇到左括号直接入栈遇到右括号则弹出栈顶直到遇到左括号。手动转换过程输入A B * ( C - D ) E / ( C - D )逐步处理A输出 → 输出A入栈 → 栈B输出 → 输出A B*入栈 → 栈 *(入栈 → 栈 * (C输出 → 输出A B C-入栈 → 栈 * ( -D输出 → 输出A B C D)弹出直到( → 弹出-输出A B C D -栈 *比较栈顶优先级高于弹出输出A B C D - *栈栈顶优先级等于弹出输出A B C D - * 栈空入栈 → 栈E输出 → 输出A B C D - * E/入栈 → 栈 /(入栈 → 栈 / (C输出 → 输出A B C D - * E C-入栈 → 栈 / ( -D输出 → 输出A B C D - * E C D)弹出直到( → 弹出-输出A B C D - * E C D -栈 /结束弹出栈中所有 → 弹出/输出A B C D - * E C D - /弹出输出A B C D - * E C D - / 最终逆波兰表示A B C D - * E C D - / 三元式序列三元式是运算符操作数1操作数2的形式用序号表示中间结果。(1) - C D (2) * B (1) (3) A (2) (4) - C D (5) / E (4) (6) (3) (5)注意三元式中C-D出现了两次但三元式不共享所以(1)和(4)是重复的。如果换成间接三元式可以用指针指向同一个三元式但试卷要求的是三元式序列直接写就行。4.2 四元式序列条件语句的翻译第五题要求把if x0 y0 then z:xy else begin x:x2; y:y3 end;翻译成四元式序列。四元式是运算符操作数1操作数2结果的形式。条件语句的翻译需要生成条件跳转和无条件跳转。先分析语句结构条件是两个比较的与x0和y0。如果两个都真执行z:xy否则执行x:x2; y:y3。四元式序列(1) x 0 t1 (2) y 0 t2 (3) AND t1 t2 t3 (4) JF t3 _ (7) (5) x y t4 (6) : t4 _ z (7) J _ _ (10) (8) x 2 t5 (9) : t5 _ x (10) y 3 t6 (11) : t6 _ y这里(4)是条件跳转如果t3为假跳到(7)。(7)是无条件跳转跳到(10)不对需要仔细看控制流。实际上if-then-else的翻译模式是计算条件得到t3如果t3为假跳到else部分执行then部分跳过else部分执行else部分所以四元式应该是(1) x 0 t1 (2) y 0 t2 (3) AND t1 t2 t3 (4) JF t3 _ (7) (5) x y t4 (6) : t4 _ z (7) J _ _ (10) (8) x 2 t5 (9) : t5 _ x (10) y 3 t6 (11) : t6 _ y这里(4)如果t3为假跳到(7)不对(7)是J _ _ (10)会跳到(10)。但else部分是从(8)开始的所以(4)应该跳到(8)。修正(1) x 0 t1 (2) y 0 t2 (3) AND t1 t2 t3 (4) JF t3 _ (8) (5) x y t4 (6) : t4 _ z (7) J _ _ (12) (8) x 2 t5 (9) : t5 _ x (10) y 3 t6 (11) : t6 _ y (12) ...(7)是then部分执行完后跳过else部分跳到(12)即整个if语句之后。(4)如果条件为假跳到(8)开始执行else部分。这样控制流就对了。注意四元式的编号从1开始跳转目标要写清楚不能有歧义。考试时最好画个控制流图辅助检查。5. 易错点与易漏点那些年我们踩过的坑编译原理的考试题知识点本身不难但细节多稍不注意就翻车。下面整理几条最容易错或漏的地方每条按「易漏点 → 为什么漏 → 怎么补」来说。5.1 正规表达式漏掉空串或边界情况易漏点写正规表达式时忘记考虑空串或字符串长度为0、1、2的边界情况。为什么漏自然语言描述往往有隐含条件比如「不以0开头」意味着首字符是1但「以11结尾」意味着长度至少为2中间部分可以是空串。很多人写1(0|1)*11时会犹豫(0|1)*是否允许空串或者忘记检查111这种最短的合法字符串。怎么补写完正规表达式后手动测试几个边界字符串。比如第一题测试11长度2合法、111长度3合法、1011合法、011不合法因为以0开头、110不合法因为不以11结尾。测试通过后再画DFA。5.2 First集和Follow集计算时漏掉ε易漏点计算First集时忘记如果非终结符能推导出ε则ε要加入First集计算Follow集时忘记如果β能推导出ε则Follow(A)要加入Follow(B)。为什么漏ε的产生式容易被忽略比如E → E | ε很多人只关注E忘记ε也要加入First(E)。Follow集的计算更复杂需要跟踪每个非终结符在产生式右部的位置。怎么补计算First集时先标记所有能推导出ε的非终结符然后逐个产生式处理。计算Follow集时从开始符号的Follow集包含$开始然后对每个产生式A→αBβ先看β的First集如果β能推导出ε再加上Follow(A)。建议用表格法逐行填写避免遗漏。5.3 LL(1)文法证明时忽略First集与Follow集的交集易漏点证明LL(1)文法时只检查了同一非终结符各产生式First集是否相交忘记检查First集和Follow集的交集。为什么漏LL(1)文法的条件是对于每个非终结符A如果A→α和A→β是两个不同产生式则First(α)∩First(β)∅如果α能推导出ε则First(β)∩Follow(A)∅。很多人只做了第一步忘记第二步。怎么补对每个能推导出ε的产生式检查其First集不含ε与Follow集是否相交。如果相交则不是LL(1)文法。建议列一个检查表逐项打勾。5.4 四元式跳转目标编号错误易漏点翻译条件语句时跳转目标的编号写错导致控制流混乱。为什么漏四元式的编号是连续的但跳转目标需要提前知道。写的时候容易把JF的目标写成下一个四元式的编号而不是else部分的起始编号。怎么补先画出控制流图标清楚then部分、else部分、if语句之后的起始编号然后再写四元式。写完后模拟执行一遍检查跳转是否正确。5.5 逆波兰表示中运算符优先级处理错误易漏点转换逆波兰表示时遇到优先级相同的运算符忘记弹出栈顶再入栈。为什么漏优先级比较时很多人只记得「优先级高的先弹出」忘记「优先级相同的也要弹出」因为左结合。怎么补记住规则当前运算符优先级 ≤ 栈顶运算符优先级时弹出栈顶并输出直到栈顶优先级更低或栈为空。对于左结合的运算符、-、*、/相同优先级要弹出对于右结合的运算符如^相同优先级不弹出。考试时先确认运算符的结合性。6. 复习清单从查漏补缺到考场实战复习编译原理最怕的是知识点散落各处复习时东一榔头西一棒槌。下面这份清单按试卷的五大模块整理每个模块列出核心考点和自检问题可以用来快速查漏补缺。模块核心考点自检问题词法分析正规表达式、NFA、DFA、最简DFA能否从自然语言描述写出正规表达式能否用子集构造法转DFA能否用填表法最小化语法分析二义性证明、语言描述、First集、Follow集、LL(1)文法、预测分析表能否找到两棵不同的语法树能否正确计算First和Follow能否构造无冲突的预测分析表中间代码逆波兰表示、三元式、四元式能否正确处理运算符优先级能否正确翻译条件语句和循环语句语义分析类型检查、符号表试卷未直接考但复习时要理解语义分析的基本任务代码优化基本块、流图、优化技术试卷未直接考但复习时要了解常见优化手段复习时建议按以下步骤走第一步把试卷里每道题的解题过程完整写一遍不要只看答案。写的过程中注意每一步的依据是什么比如为什么这个状态可以合并、为什么这个产生式能推导出ε。第二步对照上面的易错点清单逐条检查自己是否踩过坑。如果某个点不确定回到教材或笔记里重新看一遍。第三步找几道类似的题目练手。比如换一个正规表达式描述自己构造DFA换一个文法自己算First和Follow换一个表达式自己转逆波兰和四元式。第四步考前一周把预测分析表和四元式序列这两类题重点过一遍因为这两类题步骤多、容易出错但分值高练熟了能拿满分。提示考试时遇到二义性证明如果找不到两个不同的推导可以尝试找两个不同的语法树或者从文法的产生式入手看是否有某个句子能通过不同路径推导出来。梳理下来会发现编译原理的试卷虽然题目不多但每道题都覆盖了一个完整的知识模块而且模块之间有递进关系词法分析是基础语法分析是核心中间代码是应用。复习时不要孤立地看每个模块要把它们串起来理解源程序从字符流到中间代码的完整翻译过程。从那以后我每次复习编译原理都会先把试卷里的五道题按模块拆开每道题写一遍完整过程然后对照易错点清单逐条检查。这个方法虽然笨但能确保每个细节都覆盖到不会在考场上因为某个小错误丢分。希望帮到你。本文还有配套的精品资源点击获取