大学编译原理课程复习试题及答案

大学编译原理课程复习试题及答案一、单项选择题（每题2分，共20分）1.词法分析阶段的主要任务是（）A.识别单词并生成单词符号流B.检查语法错误并生成语法树C.分析语义并生成中间代码D.优化目标代码并生成可执行文件2.以下关于上下文无关文法的描述中，正确的是（）A.所有产生式的左部必须是单个非终结符B.终结符可以出现在产生式左部C.非终结符不能出现在产生式右部D.文法符号包括终结符和开始符号两类3.若文法G存在某个句子有两个不同的语法树，则G是（）A.二义性文法B.正则文法C.LL(1)文法D.LR(0)文法4.构造LL(1)分析表时，需要计算的两个关键集合是（）A.FIRST集和LAST集B.FIRST集和FOLLOW集C.FOLLOW集和CLOSED集D.CLOSURE集和GOTO集5.以下属于自底向上语法分析方法的是（）A.递归下降分析B.预测分析C.LR分析D.LL(1)分析6.语法制导翻译中，属性文法的语义规则通常与（）关联A.终结符B.非终结符C.产生式D.语法树节点7.中间代码的主要形式不包括（）A.四元式B.三元式C.逆波兰式D.机器指令8.基本块内的优化主要指（）A.循环优化B.全局优化C.局部优化D.过程间优化9.以下关于代码生成的描述，错误的是（）A.需要考虑目标机器的寄存器分配B.应生成高效的目标代码C.中间代码到目标代码的转换是一一对应的D.需处理操作数的地址计算10.正则表达式a(b|c)*d对应的NFA状态数最少为（）A.3B.4C.5D.6二、填空题（每空1分，共20分）1.编译程序的工作过程通常分为词法分析、语法分析、（）、（）、代码优化和目标代码生成六个阶段。2.词法分析器的输入是（），输出是（）。3.上下文无关文法G的四元组表示为（），其中V_N是非终结符集合，V_T是终结符集合，S是开始符号，P是（）。4.对于产生式A→α，若α能推导出ε，则FIRST(α)应包含（）；FOLLOW(A)表示所有可能出现在（）之后的终结符集合。5.LR分析器的核心部件是（），其状态转移由（）函数和（）函数决定。6.常用的中间代码形式包括（）、（）、抽象语法树和符号表。7.四元式的一般形式是（），其中op表示操作符，arg1和arg2是操作数，result是结果。8.循环优化的主要技术有（）、（）和（）。9.代码生成阶段需要考虑的关键问题包括（）分配和（）选择。10.有限自动机分为（）和（）两类，其中（）可以通过确定化转换为（）。三、判断题（每题1分，共10分。正确打√，错误打×）1.词法分析阶段可以检测到所有语法错误。（）2.每个正则文法都可以转换为等价的正则表达式。（）3.若文法G是LL(1)文法，则其必然是无二义性的。（）4.LR分析是一种自顶向下的语法分析方法。（）5.语法制导翻译仅能处理综合属性，无法处理继承属性。（）6.三元式与四元式的主要区别在于是否保留对中间结果的引用。（）7.基本块是程序中一个顺序执行的语句序列，只有一个入口和一个出口。（）8.循环不变计算是指在循环体中值保持不变的表达式。（）9.目标代码生成时，应优先使用寄存器存储频繁访问的变量。（）10.NFA的状态转移函数是多值的，而DFA的状态转移函数是单值的。（）四、简答题（每题6分，共30分）1.简述词法分析与语法分析的区别与联系。2.说明如何判断一个文法是否为LL(1)文法。3.比较自顶向下分析与自底向上分析的主要特点。4.解释语法制导翻译中“综合属性”和“继承属性”的区别，并举例说明。5.简述代码优化的分类及各阶段优化的目标。五、综合题（共20分）1.（8分）给定正则表达式r=a(a|b)*c，要求：（1）构造对应的NFA（用状态转移图表示）；（2）将该NFA确定化为DFA（列出状态转换表）；（3）指出该DFA的接受状态。2.（6分）给定文法G[S]：S→aABeA→b|bCC→d|εB→d|ε（1）计算各非终结符的FIRST集和FOLLOW集；（2）判断该文法是否为LL(1)文法，说明理由。3.（6分）对语句“x=(a+b)*c(de)”，要求：（1）生成对应的四元式序列；（2）画出对应的抽象语法树（用二叉树形式表示）。答案及解析一、单项选择题1.A（词法分析的核心任务是识别单词并转换为符号流）2.A（上下文无关文法产生式左部必须是单个非终结符）3.A（二义性文法的定义是存在句子有多个语法树）4.B（LL(1)分析需要FIRST和FOLLOW集确定分析表）5.C（LR分析属于自底向上方法，其他为自顶向下）6.C（语义规则与产生式关联，用于计算属性）7.D（机器指令属于目标代码，非中间代码）8.C（基本块优化是局部优化的主要形式）9.C（中间代码到目标代码的转换需考虑机器特性，非一一对应）10.B（最简NFA状态数为4：初始→a→(b|c)*→d→接受）二、填空题1.语义分析；中间代码生成2.源程序字符串；单词符号流（或二元组序列）3.G=(V_N,V_T,P,S)；产生式集合4.ε；A的句型中A5.分析表；ACTION；GOTO6.四元式；逆波兰式（或三元式、抽象语法树）7.(op,arg1,arg2,result)8.代码外提；强度削弱；删除归纳变量9.寄存器；指令选择10.确定有限自动机（DFA）；非确定有限自动机（NFA）；NFA；DFA三、判断题1.×（词法分析仅检测词法错误，语法错误由语法分析检测）2.√（正则文法与正则表达式等价）3.√（LL(1)文法要求无左递归和公共左因子，必然无二义）4.×（LR分析是自底向上）5.×（语法制导翻译可处理继承属性，需用属性文法）6.√（三元式通过位置引用中间结果，四元式独立存储）7.√（基本块的定义）8.√（循环不变计算的定义）9.√（寄存器访问速度快，优先使用）10.√（NFA允许状态转移多值，DFA单值）四、简答题1.区别：词法分析处理字符流，识别单词；语法分析处理单词流，验证结构。联系：词法分析为语法分析提供输入（单词符号流），语法分析发现的词法错误需反馈给词法分析。2.判断步骤：（1）消除左递归；（2）提取公共左因子；（3）对每个非终结符A的产生式A→α|β，检查FIRST(α)∩FIRST(β)=∅；若α或β能推导出ε，检查FIRST(α)∩FOLLOW(A)=∅且FIRST(β)∩FOLLOW(A)=∅。若所有产生式满足，则为LL(1)文法。3.自顶向下：从开始符号出发，试图推导出输入串，需解决左递归和回溯问题（如递归下降、LL分析）；自底向上：从输入串出发，逐步归约到开始符号（如LR分析），无需处理左递归，分析能力更强。4.综合属性：由子节点属性计算父节点属性（自底向上传递），如表达式值；继承属性：由父节点或兄弟节点属性计算子节点属性（自顶向下传递），如变量作用域信息。例：表达式文法E→E1+T，E的综合属性值=E1.value+T.value（综合属性）；若T需要知道运算优先级（由E的继承属性传递），则为继承属性。5.分类：（1）局部优化（基本块内）：删除公共子表达式、复写传播；（2）循环优化（循环内）：代码外提、强度削弱；（3）全局优化（程序全局）：全局公共子表达式删除、常量传播。目标：提高代码执行效率，减少运行时间和空间占用。五、综合题1.（1）NFA构造：状态0（初始）→a→状态1；状态1→ε→状态2（分支起点）；状态2→b→状态2，状态2→a→状态2（表示(a|b)*）；状态2→ε→状态3；状态3→c→状态4（接受状态）。（2）DFA确定化：ε-闭包计算：初始状态S0=ε-closure({0})={0}输入a：move(S0,a)={1}，ε-closure({1})={1,2}→S1输入b/c：S0无b/c转移，无定义S1输入a：move({1,2},a)={2}，ε-closure({2})={2}→S2S1输入b：move({1,2},b)={2}，ε-closure({2})=S2S1输入c：move({1,2},c)={3}，ε-closure({3})={3}→S3S2输入a：move({2},a)={2}→ε-closure=S2S2输入b：move({2},b)={2}→ε-closure=S2S2输入c：move({2},c)={3}→ε-closure=S3S3输入c：无转移；输入a/b：无转移状态转换表：状态|a|b|cS0|S1||-S1|S2|S2|S3S2|S2|S2|S3S3|||-（3）接受状态：S3（包含原NFA的接受状态4的ε闭包）2.（1）FIRST集：FIRST(S)={a}（S→aABe）FIRST(A)={b}（A→b|bC）FIRST(C)={d,ε}（C→d|ε）FIRST(B)={d,ε}（B→d|ε）FOLLOW集：FOLLOW(S)={#}（开始符号）FOLLOW(A)：由S→aABe，A后是B，故FOLLOW(A)⊇FIRST(B)-{ε}∪FOLLOW(S)（当B→ε时）→{d}∪{#}={d,#}FOLLOW(C)：A→bC，C在A产生式末尾，故FOLLOW(C)=FOLLOW(A)={d,#}FOLLOW(B)：由S→aABe，B后是e，故FOLLOW(B)={e}（2）判断LL(1)：检查A的产生式A→b|bC：FIRST(b)={b}，FIRST(bC)={b}，交集为{b}≠∅，不