(2025年)中北大学大数据学院编译原理期中考试试题及答案解析

(2025年)中北大学大数据学院编译原理期中考试试题及答案解析一、选择题（每题2分，共20分）1.编译过程中，词法分析的主要任务是（）。A.检查语法错误B.将源程序转换为符号表C.识别单词并提供-token序列D.提供中间代码2.若文法G的产生式为S→aSb|ε，则G属于（）。A.0型文法B.1型文法C.2型文法D.3型文法3.正则表达式(a|b)c与以下哪个字符串不匹配？（）A.accB.bcC.abbcD.c4.关于LL(1)文法，以下说法错误的是（）。A.要求文法无左递归B.要求任意两个产生式的SELECT集不相交C.可以处理所有上下文无关文法D.分析表通过First和Follow集构造5.构造DFA时，若状态集I的ε闭包包含状态S0、S1，且输入字符为a时，S0转移至S2，S1转移至S3，则I的a转移闭包为（）。A.ε-closure({S2,S3})B.{S2,S3}C.ε-closure(S2)∪ε-closure(S3)D.{S2}∪{S3}6.符号表在编译过程中的主要作用是（）。A.存储中间代码B.记录标识符的属性信息C.处理语法错误D.优化目标代码7.以下关于LR分析器的描述，正确的是（）。A.LR(0)分析器能处理所有上下文无关文法B.SLR(1)通过Follow集解决归约冲突C.LALR(1)分析表比LR(1)更小，但冲突更多D.LR分析属于自顶向下分析8.若文法G存在左公共因子，则可能导致（）。A.词法分析错误B.LL(1)分析表出现多重定义C.LR分析栈溢出D.语义分析无法推导属性9.中间代码“(+,a,b,t1);(,t1,c,t2)”对应的表达式是（）。A.a+bcB.(a+b)cC.a+(bc)D.ab+c10.错误处理中，“恐慌模式恢复”的主要做法是（）。A.跳过若干字符直到找到同步标记B.自动提供缺失的语法符号C.回退到最近的正确状态D.输出所有可能的错误位置二、填空题（每空2分，共20分）1.词法分析的输出是________序列。2.上下文无关文法（CFG）的产生式形式为________。3.正则表达式(a|b)aa对应的DFA最少有________个状态。4.LL(1)中的第一个“L”表示________，“1”表示________。5.计算Follow集时，若有产生式A→αBβ且β≠ε，则Follow(B)需包含________。6.LR分析器的核心部件是________，用于存储分析状态和符号。7.语义分析的主要任务是检查________和进行________。8.四元式的一般形式是________。三、简答题（每题5分，共20分）1.简述正则表达式与上下文无关文法（CFG）的表达能力差异。2.说明LL(1)文法需要满足的两个关键条件。3.对比自顶向下分析与自底向上分析的主要区别。4.举例说明如何通过消除左递归改造文法（给出具体文法及改造步骤）。四、分析题（共30分）1.（10分）将正则表达式r=(a|b)a(b|c)转换为NFA（用Thompson构造法），并通过子集法将其确定化为DFA（要求画出状态转移图）。2.（10分）给定文法G[S]：S→AA→aB|bB→Ac|ε（1）计算各非终结符的First集和Follow集；（2）判断G是否为LL(1)文法，说明理由。3.（10分）构造文法G[S]：S→EE→E+T|TT→TF|FF→(E)|id的LR(0)项目集族，并说明该文法是否为LR(0)文法（若存在冲突需指出类型）。五、综合题（10分）对表达式“id1+id2(id3id4)”，（1）构造其语法树；（2）提供对应的四元式序列（假设临时变量为t1、t2、t3等）。答案解析一、选择题1.C。词法分析的核心是将源程序字符流转换为有意义的单词（token）序列。2.C。产生式为A→α（α为终结符和非终结符的组合），符合2型文法（上下文无关文法）定义。3.A。(a|b)表示0个或多个a/b，后接c，因此“acc”需匹配(a|b)a后接c，但“acc”的第二个c无法被r匹配（r的结尾是(b|c)，但原正则式应为(a|b)a(b|c)，即结尾是b或c，所以“acc”的第二个c不匹配，正确不匹配项应为A）。4.C。LL(1)文法无法处理所有CFG，如存在左递归或回溯的文法需改造后可能成为LL(1)。5.A。DFA状态转移时，输入字符a的转移闭包是ε闭包中所有状态经a转移后的状态的ε闭包。6.B。符号表记录标识符的类型、作用域、地址等属性，供后续阶段使用。7.B。SLR(1)通过Follow集判断归约是否合法，解决归约-归约或移进-归约冲突。8.B。左公共因子会导致同一非终结符的多个产生式的First集相交，LL(1)分析表出现多重入口。9.B。第一个四元式计算a+b→t1，第二个四元式计算t1c→t2，对应(a+b)c。10.A。恐慌模式恢复跳过字符直到遇到同步标记（如分号、括号），快速恢复分析。二、填空题1.token2.A→α（A为非终结符，α为终结符或非终结符的序列）3.4（状态包括初始状态、读a/b循环、读第一个a、读第二个a）4.从左到右扫描输入；向前看1个字符5.First(β)（若β含ε则包含Follow(A)）6.分析栈（或状态栈、符号栈）7.静态语义（类型匹配等）；属性计算（如类型推导）8.（运算符，操作数1，操作数2，结果）三、简答题1.正则表达式仅能描述正则语言（如标识符、关键字），对应有限自动机；CFG能描述上下文无关语言（如嵌套结构、表达式），对应下推自动机。正则语言是上下文无关语言的子集，CFG表达能力更强。2.（1）文法无左递归；（2）对同一非终结符的任意两个产生式A→α|β，有SELECT(α)∩SELECT(β)=∅，其中SELECT(α)=First(α)（若α→ε则为Follow(A)）。3.自顶向下（如LL分析）从开始符号出发，通过推导匹配输入串；自底向上（如LR分析）从输入串出发，通过归约（逆推导）构造语法树。前者需处理左递归和左公共因子，后者能处理更多文法但实现复杂。4.例：原文法G[A]：A→Aab|c（左递归）。消除左递归步骤：引入新非终结符A’，将产生式改写为A→cA’；A’→abA’|ε。改造后文法无左递归，可用于LL分析。四、分析题1.（1）Thompson构造r的NFA：初始状态S0，终态S5。S0→ε→S1，S1→a→S2，S1→b→S3（处理(a|b)）；S2→ε→S4，S3→ε→S4（合并分支）；S4→ε→S1（处理闭包）；S4→ε→S6（跳出闭包）；S6→a→S7；S7→b→S8，S7→c→S9（处理(b|c)）；S8→ε→S5，S9→ε→S5。（2）子集法确定化：ε-closure(S0)={S0,S1,S4,S6}→状态A（初态）。A读a：转移状态为S2的ε闭包={S2,S4,S6}→状态B；读b：转移状态为S3的ε闭包={S3,S4,S6}→状态C；读其他字符无转移。B读a：S2→a→S2的ε闭包（同B）；读b：S2→ε→S4→ε→S6→a→S7→b→S8的ε闭包={S8,S5}→状态D（终态）；读c：S2→ε→S4→ε→S6→a→S7→c→S9的ε闭包={S9,S5}→状态E（终态）。类似推导其他状态，最终DFA状态包括A、B、C、D、E，转移图略。2.（1）First集：First(S)=First(A)={a,b}；First(A)={a,b}（A→aB|b）；First(B)=First(Ac)∪First(ε)={a,b,ε}（Ac的First为First(A)={a,b}，ε的First为{ε}）。Follow集：Follow(S)={}（假设输入结束符为）；Follow(A)=Follow(S)∪First(c)（S→A，A→aB；B→Ac→A后接c，故Follow(A)包含First(c)={c}）∪Follow(B)（B→ε时，A的Follow继承B的Follow）→Follow(A)={,c}；Follow(B)=Follow(A)（A→aB，B后无符号，故Follow(B)=Follow(A)={,c}）。（2）检查LL(1)条件：A的产生式：A→aB和A→b。SELECT(A→aB)=First(aB)={a}；SELECT(A→b)=First(b)={b}，交集为空。B的产生式：B→Ac和B→ε。SELECT(B→Ac)=First(Ac)=First(A)={a,b}；SELECT(B→ε)=Follow(B)={,c}。{a,b}∩{,c}=∅，无冲突。因此G是LL(1)文法。3.文法G[S]的LR(0)项目集族：项目包括：I0:S’→·S,S→·E,E→·E+T,E→·T,T→·TF,T→·F,F→·(E),F→·idI1:S’→S·（接受态），E→E·+TI2:E→T·，T→T·FI3:T→F·，F→(·E),E→·E+T,E→·T,T→·TF,T→·F,F→·(E),F→·id（由I0的F→·id转移id到I3）I4:F→(E·),E→E·+T（由I0的F→·(E)转移(到I4，E→·E+T等在I4的闭包）...（后续项目集需通过闭包和转移计算，最终发现存在移进-归约冲突：如I2中E→T·与T→T·F，当输入为时，需移进，但E→T·可能归约，