《2022年广工编译原理试卷A .pdf》由会员分享，可在线阅读，更多相关《2022年广工编译原理试卷A .pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、学习必备欢迎下载编译原理试卷A 一、选择题（每空2 分，共 20 分）1.一个正规语言只能对应(B)？A 一个正规文法；B 一个最小有限状态自动机；2.文法 GA ：A A aB B Ab B a是(B)：A 正规文法B 二型文法3.下面说法正确的是(A)：A 一个 SLR（1）文法一定也是LALR （1）文法B 一个 LR（1）文法一定也是LALR （1）文法4.一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL （1）文法的 (A)：A 必要条件B 充分必要条件5. （D ）不是 NFA 的成分。A 由穷字母表B 初始状态集合C 终止状态集合D 有限状态集合6 （ C ）不是编译
2、程序的组成部分A 词法分析程序B 代码生成程序C 设备管理程序D 语法分析程序7有文法G=(S,a,SSaS, S,S),该文法是（ B ） 。A. LL(1)文法 B. 二义性文法 C 算符优先文法 D SLR(1)文法8 给定文法 AbA|cc ，则符号串 ccbcbcbcbccbccbcc bbbcc 中，是该文法句子的是（ D ）A B C D 9 表达式 A*(B-C*(C/D)的逆波兰表示为（ B ）A. ABC-CD/* B. ABCCD/*-* C. ABC-*CD/* D. 前三个选项都不对10 LR(1) 文法都是（ A ）A 无二义性且无左递归 B 可能有二义性但无左递归
3、C 无二义性但可能有无左递归 D 可以既有二义性又有左递归二、问答题第 1 题(10 分)将文法 GS 改写为等价的G S ，使 G S 不含左递归和左公共因子。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 6 页学习必备欢迎下载GS： SbSAe | bAAAb | d 答： 文法 GS 改写为等价的不含左递归和左公共因子的GS为：SbB BSAe | AAd A A bA | 第 2 题（ 10 分）给出与正规式R（ ab）*（ a|b*）ba 等价的 NFA 。答：与正规式 R（ab）*（a|b*）ba 等价的 NFA如下图第
4、3 题（ 10 分） 将下图的NFA 确定化为DFA。答： 用子集法确定化如下表用子集法对所给图的确定化IIaIb状态X,1,2 1,2 .1,2,3 1,2,Y1,2 .1,2 .1,2,Y 1,2 .1,2,3 1,2,3 1,2,3 1,2,3X 1 2 3精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 6 页学习必备欢迎下载确定化后如下图第 4 题（ 10 分）给出文法 GS的 LR(1) 项目集规范族中I0项目集的全体项目。GS 为：S BD|DB aD|bD B 答：解:I0第 5 题(10 分)文法 GM 及其 LR 分析
5、表如下，请给出对串dbba#的分析过程。GM: 1) M VbA 2) V d 3) V 4) A a 5) A Aba 6) A nameACTIONGOTO精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 6 页学习必备欢迎下载b da#MAV0r3 S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5答：对串 dbba#的分析过程如下表对输入串dbba#的分析过程步骤状态栈文法符号栈剩余输入符号动作1 2 3 4 5 6 7 8 90 03 02 024 0246 02467 024678 0246 01
6、# #d #V #Vb #VbA #VbAb #VbAba #VbA #Mdbba# bba# bba# ba# ba# a# # # #移进用 V d归约移进用 A 归约移进移进用 A Aba 归约用 M VbA 归约接受第 6 题(20 分)某语言的拓广文法G 为： (0) S T (1) T aBd|(2) B Tb| 证明 G 不是 LR(0)文法而是SLR(1) 文法，请给出SLR(1)分析表。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 6 页学习必备欢迎下载答：拓广文法G，增加产生式S T 在项目集I0中：有移进项目T
7、aBd 和归约项目T 存在移进 -归约冲突，所以G 不是 LR(0) 文法。若产生式排序为：(0) ST(1) T aBd(2) T (3) B Tb (4) B G的 LR(0) 项目集族及识别活前缀的DFA如下图所示：识别 G 活前缀的 DFA由产生式知：Follow(T)=#,b Follow(B)= d 在 I0中：Follow(T) a=# ，b a=在 I2中：Follow(B) a= d a=精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 6 页学习必备欢迎下载Follow(T) a=# ，b a=Follow(B) Fo
8、llow(T) = d# ， b=所以在 I0，I2，中的移进 - 归约和归约 - 归约冲突可以由 Follow 集解决，所以 G是 SLR(1)文法。构造的 SLR(1)分析表如下表。SLR(1)分析表nameACTIONGOTOabd#TB0S2r2r211acc2S2r2r4r2433S54S65r1r16r3第 7 题（ 10 分） 对产生 C 语言中的条件表达式的文法GE ：EE?E:E 写出相应的翻译文法。答: E1 E? BackPatch($1.TC,NXQ); $.FC=$1.FC; E2E1E2:$.place=$2.place; $.temp=NXQ; GEN(j,0,0,0); BackPatch($1,FC,NXQ); E2E2E:$.place=$2.place; BackPatch($1,temp,NXQ); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 6 页