简介这份常州工学院编译原理试卷Adoc格式55KB共1个文件面向计算机专业学生及备考者用于检验和巩固编译原理核心知识。试卷覆盖正规表达式与有限自动机、逆波兰表示、文法二义性、LL(1)文法与预测分析表、语句四元式序列等模块题型包含构造最简DFA、证明文法二义性、计算First与Follow集、构造预测分析表以及将if-then-else语句翻译为四元式序列能帮助读者系统梳理词法分析、语法分析、语义分析与代码生成各阶段要点。目前已有391人学习下载适合作为期末复习、考研自测或课堂练习的参考材料便于对照查漏补缺、熟悉典型题型与解题思路。1. 从一张期末卷看编译原理到底考什么编译原理这门课很多人复习到后期会有一种玄学感明明每个概念都背了一上考场看到“构造最简DFA”“证明文法是LL(1)的”还是发懵。这张试卷给了一个很清晰的信号——它不考你背定义考的是你能不能把一套形式化工具跑通。整张卷子五道大题覆盖了词法分析、语法分析、语义分析与中间代码生成三大模块分值分布是30分、10分、20分、25分、15分合计100分。其中正规表达式与DFA占30分是单题分值最高的部分LL(1)文法的First/Follow集、预测分析表占25分是第二重头。换句话说这张卷子的及格线基本由“自动机”和“自顶向下分析”两块决定。如果你正在准备这门课的期末或者考研专业课下面按考点模块拆开的答题思路可以直接拿去对着练。2. 正规表达式与最简DFA两道30分大题的完整推导2.1 不以0开头但以11结尾的字符串从语言描述到正规式题目要求在字母表{0,1}上写出所有不以0开头但以11结尾的字符串的正规表达式并构造等价的最简DFA18分。这类题的标准解法是“先拆结构再拼正规式最后走子集构造最小化”。先分析语言结构。不以0开头意味着首字符必须是1。以11结尾意味着最后两个字符固定是1、1。中间部分可以是任意由0和1组成的串。所以正规表达式可以写成1(0|1)*11这里有个容易翻车的地方如果中间部分允许为空那么字符串“111”是否合法首字符1中间为空结尾11合起来是111确实不以0开头且以11结尾合法。所以闭包用*而不是是对的。接下来构造NFA再转DFA。按Thompson构造法先画出1(0|1)*11的NFA状态数会比较多。更高效的做法是直接按语言特征设计DFA。我们需要的状态可以这样定义q0初始状态还没读到任何字符q1已读到首字符1且当前不以“11”结尾q2已读到首字符1且当前恰好以“1”结尾可能是结尾11的第一个1q3已读到首字符1且当前以“11”结尾接受状态q4死状态读到0开头的情况转移关系如下表当前状态读入0读入1说明q0q4q1首字符不能是0q1q1q2读1后可能形成结尾11的第一个1q2q1q3再读1则到达接受态q3q1q3已接受继续读0回到q1读1保持q3q4q4q4死状态检查最小化q0和q4显然不等价q0读1到q1q4读1到q4。q1、q2、q3是否可区分q3是接受态q1和q2是非接受态所以q3单独一组。q1读0到q1q2读0到q1行为相同q1读1到q2q2读1到q3而q2和q3不等价所以q1和q2可区分。最终五个状态都是必要的最简DFA就是上面这张表。提示画DFA时一定要标清楚初始状态和接受状态转移箭头上写清输入符号。很多同学丢分不是不会是图画得不规范阅卷老师找不到接受态。2.2 包含01子串的字符串12分题的快速解法第二小题要求在{0,1}上写出包含01子串的所有字符串的正规表达式12分。这题比第一题简单但有个常见错误把“包含01”理解成“以01开头”或“以01结尾”。包含01子串意味着字符串中任意位置出现连续的0和1即可。正规表达式可以写成(0|1)*01(0|1)*这个表达式的含义是01前面可以有任意串01后面也可以有任意串。验证几个边界情况字符串“01”本身前面为空后面为空合法字符串“001”前面是0后面为空合法字符串“010”前面为空后面是0合法字符串“1”不包含01不匹配正确。对应的最简DFA只需要三个状态S0初始状态还没看到0S1已经看到了一个0正在等待后面的1S2已经看到了01子串接受状态转移表当前状态读入0读入1S0S1S0S1S1S2S2S2S2S2是接受态读入任何字符都停留在S2因为一旦包含01后续怎么加都还是包含01。S0读0到S1读1留在S0因为还没出现0。S1读0留在S1多个0连续读1到S2形成01。三个状态两两可区分S2接受S0和S1非接受S0读0到S1S1读0到S1但S0读1到S0S1读1到S2S0和S2不等价所以S0和S1可区分。最简DFA就是这三个状态。这类12分题阅卷通常按“正规式正确给6分DFA正确给6分”来分配。正规式写错DFA画得再对也拿不到前半部分的分所以先确保正规式无误再画图。3. 文法二义性与语言描述20分证明题的答题模板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要求证明该文法有二义性并描述它所描述的语言共20分。证明二义性的标准做法是找到一个句子它能对应两棵不同的语法分析树或两个不同的最左推导。观察这个文法N可以推导出SE或E。S可以推导出SD或DD是单个数字。E是偶数0、2、4、6、8、10。考虑句子“10”。它可以这样推导路径一N ⇒ E ⇒ 10路径二N ⇒ SE ⇒ DE ⇒ 1D ⇒ 10这里S⇒D⇒1E⇒0两条推导路径产生同一个句子“10”但语法树结构不同。路径一中10是一个终结符E直接产生路径二中10被拆成S产生的1和E产生的0。这就证明了文法存在二义性。注意证明二义性不需要穷举所有句子找到一个反例即可。但一定要把两棵语法树或两个推导过程写清楚只写“因为有两种推导”而不展示具体步骤阅卷时会被扣分。3.2 文法描述的语言从产生式反推字符串集合描述语言需要从文法的产生式出发分析它能生成什么样的字符串。N产生SE或E。E产生偶数0、2、4、6、8、10。S产生SD或DD产生单个数字0-9。所以S产生的是一个或多个数字组成的数字串因为S⇒SD⇒DD⇒...每次可以追加一个数字。因此N产生的字符串是一个数字串后面跟一个偶数或者单独一个偶数。数字串可以是一位或多位。用自然语言描述就是所有以偶数结尾的数字串或者单独的偶数。更形式化地说语言L(G) { w | w是十进制数字串且w的最后一位是偶数或者w本身就是偶数 }。这里有个细节E产生10而10本身是两位数字。如果N⇒E⇒10那么10既是一个偶数也可以被看作数字串“1”后跟偶数“0”。这正是二义性的来源。描述语言时要把这个重叠说清楚否则容易漏掉情况。3.3 二义性文法的处理思路考试中遇到二义性文法除了证明和描述语言有时还会问“如何消除二义性”。标准思路是引入优先级和结合性规则或者重写文法。比如这个文法可以通过限制S的产生式来消除二义性让数字串的解析唯一。但本卷只要求证明和描述不需要给出消除方案。如果题目多问一句“该文法能否用于编译”答案是不能直接用于自顶向下分析因为二义性会导致预测分析表出现多重入口。4. LL(1)文法与预测分析表25分计算题的逐步拆解4.1 First集和Follow集的计算题目给出的文法GE → TE E → E | ε T → FT T → T | ε F → PF F → *F | ε P → (E) | ^ | a | b要求计算每个非终结符的First集和Follow集证明文法是LL(1)的构造预测分析表共25分。先算First集。规则是如果X是终结符First(X){X}如果X→ε则ε∈First(X)如果X→Y1Y2...Yk把First(Y1)中非ε的符号加入First(X)如果Y1能推出ε继续看Y2以此类推。逐个计算First(P) { (, ^, a, b }First(F) { *, ε }First(F) First(PF) First(P) { (, ^, a, b }First(T) First(T) ∪ {ε}而First(T)First(FT)First(F){ (, ^, a, b }所以First(T) { (, ^, a, b, ε }First(T) { (, ^, a, b }First(E) { , ε }First(E) First(TE) First(T) { (, ^, a, b }再算Follow集。规则是Follow(S)包含$如果A→αBβ把First(β)中非ε的符号加入Follow(B)如果A→αB或A→αBβ且β能推出ε把Follow(A)加入Follow(B)。Follow(E) { $, ) }E是开始符号$加入P→(E)中E后面是)所以)加入Follow(E) Follow(E) { $, ) }Follow(T) First(E)中非ε的符号 ∪ Follow(E) { } ∪ { $, ) } { , $, ) }Follow(T) Follow(T) { , $, ) }Follow(F) First(T)中非ε的符号 ∪ Follow(T) { (, ^, a, b } ∪ { , $, ) } { (, ^, a, b, , $, ) }Follow(F) Follow(F) { (, ^, a, b, , $, ) }Follow(P) First(F)中非ε的符号 ∪ Follow(F) { * } ∪ { (, ^, a, b, , $, ) } { *, (, ^, a, b, , $, ) }提示Follow集计算最容易漏掉“β能推出ε时要把Follow(A)加进来”这一步。比如T→ε时Follow(T)要包含Follow(T)很多同学只看了First(T)就停了。4.2 证明LL(1)文法检查冲突LL(1)文法的条件是对于每个非终结符A的任意两个不同产生式A→α和A→β满足First(α)∩First(β)∅如果α能推出ε则First(β)∩Follow(A)∅。检查EE→E | ε。First(E){}First(ε){ε}交集为空。由于ε∈First(ε)需要检查First(E)∩Follow(E){}∩{$,)}∅。满足。检查TT→T | ε。First(T){ (, ^, a, b }First(ε){ε}交集为空。First(T)∩Follow(T){ (, ^, a, b }∩{,$,)}∅。满足。检查FF→*F | ε。First(F){}First(ε){ε}交集为空。First(F)∩Follow(F){}∩{ (, ^, a, b, , $, ) }∅。满足。检查PP→(E) | ^ | a | b。四个产生式的First集分别是{( }、{^}、{a}、{b}两两不相交。满足。所有非终结符都满足LL(1)条件所以文法G是LL(1)文法。4.3 构造预测分析表预测分析表的行是非终结符列是终结符加上$。对于每个产生式A→α如果a∈First(α)把A→α填入M[A,a]如果ε∈First(α)对于每个b∈Follow(A)把A→α填入M[A,b]。逐行填写非终结符()*^ab$EE→TEE→TEE→TEE→TEEE→εE→EE→εTT→FTT→FTT→FTT→FTTT→TT→εT→εT→TT→TT→TT→εFF→PFF→PFF→PFF→PFFF→εF→εF→εF→*FF→εF→εF→εF→εPP→(E)P→^P→aP→b这张表是LL(1)分析器的核心。构造时要注意E在遇到)和$时填E→ε因为Follow(E){$,)}T在遇到、)、$时填T→ε因为Follow(T){,$,)}F在遇到(、)、、^、a、b、$时都填F→ε因为Follow(F)包含了这些符号。注意预测分析表里每个单元格最多只能有一个产生式。如果某个单元格出现两个产生式说明文法不是LL(1)的。这张表填完后可以自查一遍确认没有冲突。5. 逆波兰表示与四元式序列10分和15分的送分题怎么拿稳5.1 逆波兰表示栈操作的经典应用题目要求写出表达式AB*(C-D)E/(C-D)的逆波兰表示10分。逆波兰表示就是后缀表达式运算符写在操作数后面。转换规则是遇到操作数直接输出遇到运算符则与栈顶运算符比较优先级优先级不高于栈顶则弹出栈顶输出直到栈顶优先级更低或栈为空再压入当前运算符。括号内的运算符优先级提升遇到右括号则弹出直到左括号。逐步转换读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 - / 提示逆波兰表示中操作数和运算符之间用空格分隔不要写成ABCD-*ECD-/ 这种连在一起的格式阅卷时容易看错。5.2 四元式序列if-then-else的翻译题目要求把语句if x0 y0 then z:xy else begin x:x2; y:y3 end;翻译成四元式序列15分。四元式的一般形式是(op, arg1, arg2, result)。条件语句的翻译需要生成条件跳转和无条件跳转。先分析语句结构条件部分是x0 y0这里“y0”前面缺少逻辑运算符按编译原理常见题型理解应该是x0 and y0或者x0 or y0。从语义上看if x0 y0 then更可能是x0 and y0的简写。我们按and处理。四元式序列如下(, x, 0, t1) // t1 x 0 (, y, 0, t2) // t2 y 0 (and, t1, t2, t3) // t3 t1 and t2 (j, t3, _, 5) // 如果t3为假跳转到第5条 (, x, y, t4) // t4 x y (:, t4, _, z) // z t4 (j, _, _, 10) // 无条件跳转到第10条 (, x, 2, t5) // 第8条t5 x 2 (:, t5, _, x) // x t5 (, y, 3, t6) // t6 y 3 (:, t6, _, y) // y t6这里第4条四元式(j, t3, _, 5)表示如果t3为假则跳转到第5条四元式。第5到第7条是then分支第8到第10条是else分支。第7条(j, _, _, 10)表示then分支执行完后跳过else分支。注意四元式的编号从1开始还是从100开始不同教材有不同约定。本卷没有指定按从1开始编号即可。跳转目标要写清楚是第几条四元式不要写“跳到else”这种模糊描述。5.3 中间代码生成的常见失分点四元式翻译题最容易丢分的地方有三个一是条件跳转的方向搞反j和j≠分不清二是then分支结束后忘记加无条件跳转导致else分支被顺序执行三是临时变量命名混乱t1、t2重复使用。建议在草稿纸上先把控制流图画出来再逐条写四元式写完后按编号走一遍确认跳转逻辑正确。6. 易错点与失分点五类高频翻车现场6.1 正规表达式闭包用错错在哪把1(0|1)*11写成1(0|1)11认为中间部分不能为空。 为什么错没有验证字符串“111”是否合法。首字符1中间为空结尾11确实满足“不以0开头且以11结尾”。 怎么答对写完正规式后用最短字符串、最长字符串、边界字符串各验证一遍。空串、单字符、双字符都要试。6.2 DFA最小化时状态合并错误错在哪把不等价的状态合并了比如把接受态和非接受态合并。 为什么错最小化算法的第一步就是按“接受态/非接受态”分组接受态和非接受态永远不可能等价。 怎么答对先分组再在组内按转移关系细分。每次细分后重新检查直到不能再分。画最小化DFA时每个状态都要有明确的转移。6.3 Follow集漏算ε产生式的影响错在哪计算Follow(T)时只看了First(T)忘了T→ε时要把Follow(T)加进来。 为什么错Follow集的定义是“可能出现在非终结符后面的终结符”当产生式右部某个非终结符能推出ε时它后面的符号就变成了再后面的符号。 怎么答对对每个产生式A→αBβ先看First(β)如果β能推出ε再把Follow(A)加入Follow(B)。养成逐条产生式检查的习惯。6.4 预测分析表填错ε产生式的位置错在哪把E→ε填在了First(E)对应的列而不是Follow(E)对应的列。 为什么错ε产生式的填写规则是“对于每个b∈Follow(A)把A→ε填入M[A,b]”不是填在First集里。 怎么答对先算清楚每个非终结符的Follow集填表时对照Follow集逐列检查。填完后看每个单元格是否只有一个产生式。6.5 四元式跳转目标编号错误错在哪then分支的(j, _, _, 10)写成了(j, _, _, 8)导致跳转到else分支中间。 为什么错没有数清楚四元式的条数或者写的时候漏了一条。 怎么答对写完所有四元式后从第一条开始逐条编号确认每个跳转目标都指向正确的四元式。最好在草稿纸上先列出所有四元式再统一编号。7. 考场答题节奏与押题思路这张卷子的答题节奏很关键。30分的正规表达式与DFA题建议分配40分钟正规式5分钟NFA 10分钟子集构造15分钟最小化10分钟。20分的文法二义性题15分钟找反例5分钟画语法树5分钟描述语言5分钟。25分的LL(1)题35分钟First/Follow集15分钟证明LL(1) 5分钟预测分析表15分钟。10分的逆波兰表示10分钟。15分的四元式20分钟。合计120分钟正好是标准考试时长。押题方向上这张卷子释放了几个信号。第一正规表达式与DFA是必考大题而且往往要求“最简DFA”说明最小化算法必须熟练掌握。第二LL(1)文法的First/Follow集和预测分析表是计算量最大的题平时练习时要限时训练否则考场上容易算错。第三四元式翻译题通常考if-then-else或while循环这两种控制结构的翻译模板要背熟。第四文法二义性证明题找反例的技巧是优先看那些“既能整体推导又能拆分推导”的句子比如本题中的“10”。我自己的血泪经验是每次做DFA最小化我都会在草稿纸上先画初始DFA再用不同颜色的笔标出分组最后才画最简图。这个习惯让我在考场上少丢了很多冤枉分。从那以后我每次做自动机题都强制走一遍“验证正规式→画NFA→子集构造→最小化→验证”的流程一步都不跳。希望帮到你。本文还有配套的精品资源点击获取