北京电影学院《编译原理》2025-2026学年期末试卷

北京电影学院《编译原理》2025-2026学年期末试卷

一、单项选择题（总共10题，每题3分，每题只有一个正确答案，请将正确答案填写在每题后面的括号内）1.编译程序的执行部分是（）。A.词法分析器B.语法分析器C.语义分析器D.目标代码生成器2.正规式M1和M2等价是指（）。A.M1和M2的状态数相等B.M1和M2的有向边条数相等C.M1和M2所识别的字符串集合相等D.M1和M2状态数和有向边条数相等3.文法G所描述的语言是（）的集合。A.文法G的字汇表V中所有符号组成的符号串B.文法G的字汇表V的闭包V中的所有符号串C.由文法的识别符号推出的所有符号串D.由文法的识别符号推出的所有终结符号串4.一个句型中的最左（）称为该句型的句柄。A.短语B.简单短语C.素短语D.终结符号5.算符优先分析法每次都是对（）进行归约。A.最左直接短语B.简单短语C.素短语D.最左素短语6.若项目集Ik含有A→α•，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α•”动作的一定是（）。A.LALR文法B.LR(0)文法C.LR(1)文法D.SLR(1)文法7.同心集合并有可能产生新的（）冲突。A.归约B.“移进”/“移进”C.“移进”/“归约”D.“归约”/“归约”8.代码优化的目的是（）。A.节省时间B.节省空间C.提高目标代码的质量D.便于进行目标代码生成9.表达式a(b+c)-d的后缀式是（）。A.abcd+-B.abc+d-C.abc+d-D.-+abcd10.过程调用时参数传递的方式不包括（）。A.值传递B.引用传递C.地址传递D.返回值传递二多项选择题（总共5题，每题4分，每题有两个或两个以上正确答案，请将正确答案填写在每题后面的括号内，多选、少选、错选均不得分）1.编译程序的组成部分包括（）。A.词法分析器B.语法分析器C.语义分析器D.中间代码生成器E.目标代码生成器2.下列关于正规式的说法正确的有（）。A.正规式可以表示空串B.正规式可以表示无穷集合C.两个正规式的连接结果仍是正规式D.正规式的闭包运算结果仍是正规式E.正规式的并运算结果仍是正规式3.下列关于文法的说法正确的有（）。A.文法的开始符号可以是终结符号B.文法的产生式是有限的C.文法可以描述无穷集合D.文法的非终结符号可以出现在产生式的左部E.文法的终结符号可以出现在产生式的左部4.下列关于语法分析的说法正确的有（）。A.自顶向下的语法分析方法不能处理左递归文法B.自底向上的语法分析方法不能处理右递归文法C.算符优先分析法是一种自底向上的语法分析方法D.LR分析法是一种自顶向下的语法分析方法E.递归下降分析法是一种自顶向下的语法分析方法5.下列关于代码优化的说法正确的有（）。A.局部优化是指在基本块内进行的优化B.循环优化是指对循环中的代码进行的优化C.全局优化是指在整个程序范围内进行的优化D.代码优化可以提高程序的执行效率E.代码优化可以减少程序占用的存储空间三、判断题（总共10题，每题2分，请在每题后面的括号内打“√”或“×”）1.编译程序是将高级语言程序翻译成机器语言程序。（）2.正规式只能描述有限集合。（）3.文法的二义性是指对于同一个句子有两棵不同的语法树。（）4.最左推导和最右推导的结果一定相同。（）5.算符优先分析法比LR分析法效率高。（）6.一个LR(1)文法一定是SLR(1)文法。（）7.代码优化一定会提高目标代码的质量。（）8.表达式的前缀式和后缀式的运算顺序是相同的。（）9.过程调用时参数传递的方式只有值传递和引用传递。（）10.编译程序的各个阶段都需要对源程序进行一遍扫描。（）四、综合应用题（总共2题，每题20分）1.已知文法G[S]：S→aSb|bSa|ε（1）请构造该文法的识别活前缀的DFA。（2）该文法是LR(0)文法吗？请说明理由。2.对于表达式a+(bc-d)/e，请分别给出其语法树、三地址代码序列（假设采用四元式表示）。五、设计题（总共1题，每题30分）请设计一个简单的词法分析器，能够识别以下单词：标识符：以字母开头，由字母、数字组成常量：整数常量运算符：+、-、、/、=界符：,、;要求：（1）给出词法分析器的状态转换图。（2）说明状态转换图中每个状态的含义。（3）编写一个简单的程序实现该词法分析器，输入一个字符串后，输出该字符串中识别出的单词。请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请在下方空白区域作答：请