《2022年编译原理阶段测试题.docx》由会员分享，可在线阅读，更多相关《2022年编译原理阶段测试题.docx（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆第一阶段测试卷考试科目 : 编译原理第 1 章至第 4 章（总分 100 分）时间： 90 分钟学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一、 挑选与填充 （30）1. 一个正就语言只能对应 ？A. 一个正就文法 B. 一个最小有限状态自动机C. 一个自然语言 D. 一个上下文有关文法2. 对于编译程序而言,输入数据是源程序,输出数据是_；3. 给出在字母表0,1上的“ 全部以00 结尾的符号串的集合” 的语言的正就表达式：_ ；4. 一个句型中最左的（）称为该句型的句柄；终结符号A. 简洁短语
2、B. 短语 C. 非终结符号 D. 5. Micro 语言只有三种语句： （）、输入语句和输出语句；A. GOTO语句 B.赋值语句 C. 条件语句 D.循环语句6. 描述高级语言语法的常用方法有_和 BNF 范式；二、给出与正规式R（ ab）*（a|b *）ab 等价的 NFA；（16）三、简述 DFA 与 NFA 有何区分；（14）四、判定以下文法是否具有二义性：GP: PPaP|PbP|cP|Pe|f 18 五、对于下面的文法 GZ,构造句子 i*i+i*i 的最左和最右推导及相应的语法树；（22） 1 Z:=E 2 E:=T+E 3 E:=T 4 T:=F*T 5 T:=F 6 F:=
3、E 7 F:=i 附：参考答案：一、 挑选与填充 （30）1.一个正就语言只能对应 B ？第 1 页,共 10 页A. 一个正就文法 B. 一个最小有限状态自动机名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆C. 一个自然语言 D. 一个上下文有关文法2. 对于编译程序而言,输入数据是源程序,输出数据是_目标程序 _；3. 给出在字母表 0,1 上的“ 全部以 00 结尾的符号串的集合” 的语言的正就表达式：_0|1*00_；4. 一个句型中最左的（ A ）称为该句型的句柄；A. 简洁短语 B. 短语 C. 非终结符号 D.
4、 终结符号5. Micro 语言只有三种语句： （B ）、输入语句和输出语句；A.GOTO语句 B. 赋值语句 C. 条件语句 D. 循环语句6. 描述高级语言语法的常用方法有_语法图 _和 BNF 范式；二、给出与正规式R（ ab）*（a|b *）ab 等价的 NFA；（16）三、简述 DFA 与 NFA 有何区分；（14）解： DFA与 NFA的区分主要有两点：1 是 NFA可以如干个开头状态,而DFA仅只一个开头状态；2 是 DFA的映象 M是从 K 到 K,而 NFA的映象 M是从 K 到 K的子集, 即映象 M将产生一个状态集合（可能为空集）,而不是单个状态；18 第 2 页,共 1
5、0 页四、判定以下文法是否具有二义性：GP: PPaP|PbP|cP|Pe|f名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆解：由于文法存在句型 fbfbf ,此句型有两棵不同的语法树,所以文法具有二义性；五、对于下面的文法 GZ,构造句子 i*i+i*i 的最左和最右推导及相应的语法树；（22）1 Z:=E 2 E:=T+E 3 E:=T 4 T:=F*T 5 T:=F 6 F:=E 7 F:=i 解：最左：Z=E=T=F*T=E*T=T+E*T=F*T+E*T=i*T+E*T=i*F+E*T=i*i+E*T =i*i+T
6、*T=i*i+F*T=i*i+i*T=i*i+i*F=i*i+i*i 最右： Z=E=T=F*T=F*F=F*i=E*i=T+E*i=T+T*i=T+F*i=T*i*i=F*T+i*i =F*F+i*i=F*i+i*i=i*i+i*i 其次阶段测试卷名师归纳总结 - - - - - - -第 3 页,共 10 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆考试科目 : 编译原理第 4 章至第 7 章（总分 100 分）时间： 90 分钟学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一、挑选与填充 （30）1. 有限状态自动机能识别 ；A. 上下
7、文无关文法 B. 上下文有关文法 C. 正就文法 D. 短语文法2在语法分析处理中, FIRST 集合、 FOLLOW集合、 SELECT集合都是 ；A. 非终极符集 B终极符集 C字母表 D. 状态集3在自底向上的语法分析方法中,分析的关键是 ；A. 查找句柄 B. 查找句型 C. 排除递归 D. 排除公共前缀4_是这样一种动作文法,即动作符只显现于产生式的末尾；5文法要满意两个条件：_ 和_ 才可以使用自顶向下的语法分析方法；6. 文法 GE: E E+T|T, T T*P|P, PE|I, 就句型 P+T+i 的短语有（）；A. i, P+T B. P, P+T, i, P+T+i C.
8、 P+T+i D. P, P+T, i 二、如有文法 GS为： S-Ac|aB A-df B-be,请写出语言 LGS 的全部元素；（12）三、文法 GS为：（18）SV VT | ViT TF| T+FFV* | 试给出句型 ViFi 的短语,简洁 直接 短语 ,句柄；四、写出表达式 ab*c/abd 的逆波兰表示和三元式序列； （15）五、下面的文法是不是 LL1 文法？如是,请构造相应的 LL1 分析表；（25）S aD D STe | T bH | H H d | 附：参考答案：一、 挑选与填充 （30）1.有限状态自动机能识别（C ）第 4 页,共 10 页名师归纳总结 - - -
9、- - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆A. 上下文无关文法 B. 上下文有关文法 C. 正就文法 D. 短语文法2在语法分析处理中, FIRST 集合、 FOLLOW集合、 SELECT集合都是 B ；A. 非终极符集 B终极符集 C字母表 D. 状态集3在自底向上的语法分析方法中,分析的关键是 A ；A. 查找句柄 B. 查找句型 C. 排除递归 D. 排除公共前缀4_尾动作文法 _是这样一种动作文法,即动作符只显现于产生式的末尾；5文法要满意两个条件：_没有左递归 _和_没有公共前缀 _才可以使用自顶向下的语法分析方法；6. 文法 GE:
10、 E E+T|T, T T*P|P, PE|I, 就句型 P+T+i 的短语有（B ）；A. i, P+T B. P, P+T, i, P+T+i C. P+T+i D. P, P+T, i 二、如有文法 GS为： S-Ac|aB A-df B-be,请写出语言 LGS 的全部元素；（12）解：由于 S=Ac=dfc S=aB=abe 所以 LGS=a b c d e f 三、文法 GS为：（18）SV VT | ViT TF| T+FFV* | 试给出句型 ViFi 的短语,简洁 直接 短语 ,句柄；解: 句型 ViFi 的语法树如下 : F 是句型 ViFi 相对于 T 的短语、简洁短语、
11、句柄（ 是句型 ViFi 相对于 F 的短语、简洁短语（ 是句型 ViFi 相对于 T 的短语ViF 是句型 ViFi 相对于 V 的短语名师归纳总结 - - - - - - -第 5 页,共 10 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆ViFi 是句型 ViFi 相对于 V 的短语 ViFi 是句型 ViFi 相对于 S 的短语四、写出表达式 ab*c/abd 的逆波兰表示和三元式序列； （15）解：逆波兰表示：abc*ab/d三元式序列：1 * ,b,c 2 , a, 1 3 , a, b 4 / ,2, 3 5 , 4,d 五、下面的文法是不是 L
12、L1 文法？如是,请构造相应的 LL1 分析表；（25）S aD D STe | T bH | H H d | 解: PredictS aD=firstaD=a PredictD STe=firstSTe=a PredictD =followD=#,b,d,e PredictT bH=firstbH=b PredictT H=firstH followT=d,e PredictH d=firstd=d PridictH =followH=e 所以该文法是LL1 文法, LL1 分析表如下表 : b d # a e S 1 3 3 3 D 2 3 T 5 4 5 H 7 6 第三阶段测试卷考试科
13、目 : 编译原理第 8 章至第 10 章（总分 100 分）时间： 90 分钟学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一、挑选与填充 （30）1. 四元式之间的联系是通过 来实现的；符号表 D程序变量第 6 页,共 10 页A指示器 B暂时变量 C名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆2. 优化可生成 的目标代码；A. 运行时间较短 B. 运行时间短但占用内存空间大C. 占用储备空间较小 D. 运行时间短且占用储备空间小3. 以下 优化方法不是针对循环优化进行的；A. 强度减弱 B删除归纳变量
14、 C删除余外运算 D代码外提4. 在目标代码生成阶段,符号表用于 ；A目标代码生成 B语义检查 C语法检查 D地址安排5语法分析是依据语言的 _规章进行的,中间代码产生是依据语言的 _规进行的；6优化可分为局部优化、_和全局优化三种；二、写出表达式 A*B/C-D+E/F 的逆波兰中间代码；15 三、什么是活动记录？它主要由哪些内容构成？15 四、试写出算术表达式 a+b*c-c*b+a-e/b*c+d 优化后的四元式序列； 15 五、文法 GM 及其 LR 分析表如下,请给出对串 dada#的分析过程；30 GM: 1 S VdB 2 V e3 V 4 B a 5 B Bda 6 B ACT
15、ION GOTO 状态d e a # S B V 0 r3 S3 1 2 1 acc 2 S4 3 r2 4 r6 S5 r6 6 5 r4 r4 6 S7 r1 7 S8 8 r5 r5 附：参考答案：一、挑选与填充（30）1. 四元式之间的联系是通过 B 来实现的；第 7 页,共 10 页名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆A指示器 B暂时变量 C符号表 D程序变量2. 优化可生成 D 的目标代码；A. 运行时间较短 B. 运行时间短但占用内存空间大C. 占用储备空间较小 D. 运行时间短且占用储备空间小3.
16、以下 C 优化方法不是针对循环优化进行的；A. 强度减弱 B删除归纳变量 C删除余外运算 D代码外提4. 在目标代码生成阶段,符号表用于 D ；A目标代码生成 B语义检查 C语法检查 D地址安排5语法分析是依据语言的 _语法 _规章进行的, 中间代码产生是依据语言的 _语义 _规进行的；6优化可分为局部优化、_循环优化 _和全局优化三种；二、写出表达式 A*B/C-D+E/F 的逆波兰中间代码；15 解：ABC/D-*EF/+ 三、什么是活动记录？它主要由哪些内容构成？15 解：一个过程的一次执行所需信息的治理,是通过称为活动记录的连续储备块来实现的；活动记录的主要内容有：1 暂时变量域 存放
17、目标程序暂时变量的值；2 局部数据域 存放过程本次执行时的局部数据、简洁变量及数组内情向量等；3 机器状态域 储存在调用过程前有关机器状态的信息,包括各寄存器的当前值及返回地址等；4 存取链 为拜访其它活动记录中所存放的非局部数据所供应的链地址；5 掌握链 指向主调过程的活动记录；6 实参 存放主调过程为被调用过程所供应的实参信息；7 返回值 为主调过程存放被调过程的返回值四、试写出算术表达式 a+b*c-c*b+a-e/b*c+d 优化后的四元式序列；15 解：该表达式的四元式序列为：1 *, b, c, T1 ）2 +, a, T1, T2 3 *, c, b, T3 4 +, T3, a
18、, T4 5 -, T4, e, T5 6 *, b, c, T6 7 +, T6, d, T7 8 /, T5, T7, T8 9 -, T2, T8, T9 可以对该表达式进行删除公共子表达式的优化；优化后的四元式序列为：名师归纳总结 - - - - - - -第 8 页,共 10 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆1 *, b, c, T1 ）dada#的分析过程；30 2+, a, T1, T2 3-, T2, e, T5 4+, T1, d, T7 5/, T5, T7, T8 6-, T2, T8, T9 五、文法 GM 及其 LR 分析
19、表如下,请给出对串V GM: 1 S VdB2 V e3 V 4 B a GOTO 5 B Bda 6 B 状态d e ACTION # a S B 0 r3 S3 1 2 1 acc 6 2 S4 3 r2 4 r6 S5 r6 5 r4 r4 6 S7 r1 7 S8 8 r5 r5 解：状态栈符号栈输入流动作第 9 页,共 10 页S0 # dada# r3 S0S2 #V dada# S4 S0S2S4 #Vd ada# S5 S0S2S4S5 #Vda da# r4 S0S2S4S6 #VdB da# S7 S0S2S4S6S7 #VdBd a# S8 S0S2S4S6S7S8 #VdBda # r5 S0S2S4S6 #VdB # r1 S0S1 #S # acc 名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆名师归纳总结 - - - - - - -第 10 页,共 10 页