资源描述：
《2021年广工编译原理试卷A》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、学习必备欢迎下载编译原理试卷A一、挑选题（每空2分，共20分）1.一个正规语言只能对应〔B〕？A一个正规文法；B一个最小有限状态自动机；2.文法G[A]：A→εA→aBB→AbB→是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）不是编译程序的组成部分A词法分析程序
2、B代码生成程序C设备治理程序D语法分析程序7．有文法G=〔{S},{a},{S→SaS,S→ε},S〕,该文法是（B）；A.LL〔1〕文法B.二义性文法C算符优先文法DSLR〔1〕文法8给定文法A→bA
3、cc，就符号串①cc②bcbc③bcbcc④bccbcc⑤bbbcc中，是该文法句子的是（D）A①B③④⑤C②④D①⑤9表达式A*〔B-C*〔C/D〕〕的逆波兰表示为（B）A.ABC-CD/**B.ABCCD/*-*C.ABC-*CD/*D.前三个选项都不对10LR〔1〕文法都是（A）A无二义性且无左递归B可能有二义性但无左递归C无二义性但可能有无左递归D可以既有
4、二义性又有左递归二、问答题学习必备欢迎下载第1题〔10分〕将文法G[S]改写为等价的G′[S，]使G′[S不]含左递归和左公共因子；学习必备欢迎下载G[S]：S→bSAe
5、bAA→Ab
6、d答：文法G[S]改写为等价的不含左递归和左公共因子的G'[S]为：S→bBB→SAe
7、AA→dA'A'→bA'
8、ε第2题（10分）给出与正规式R＝（ab）*（a
9、b*）ba等价的NFA；**答：与正规式R＝（ab）（a
10、b）ba等价的NFA如下图第3题（10分）将下图的NFA确定化为DFA；答：用子集法确定化如下表用子集法对所给图的确定化IIaIb状态{X,1,2}{1,2}
11、..{1,2,3}X{1,2}..{1,2}..{1,2,3}1{1,2,3}{1,2,Y}{1,2,3}2{1,2,Y}{1,2}..{1,2,3}3学习必备欢迎下载确定化后如下图第4题（10分）给出文法G[S]的LR〔1〕项目集规范族中I0项目集的全体项目；G[S]为：S→BD
12、DB→aD
13、bD→B答：解:I0第5题〔10分〕文法G[M]及其LR分析表如下，请给出对串dbba#的分析过程；G[M]:1〕M→VbA2〕V→d3〕V→ε4〕A→a5〕A→Aba6〕A→εnameACTIONGOTO学习必备欢迎下载答：对串dbba#的分析过程如下表bda#MAV0r
14、3S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5对输入串dbba#的分析过程步骤状态栈文法符号栈剩余输入符号动作10#dbba#移进203#dbba#用V→d归约302#Vbba#移进4024#Vbba#用A→ε归约50246#VbAba#移进602467#VbAba#移进7024678#VbAba#用A→Aba归约80246#VbA#用M→VbA归约901#M#接受第6题〔20分〕某语言的拓广文法G′为：〔0〕S〔1〕T′→T→aBd
15、ε〔2〕B→Tb
16、ε证明G不是LR〔0〕文法而是SLR〔1〕文法，请给出SLR〔1〕分析表；学
17、习必备欢迎下载答：拓广文法G'，增加产生式S'→T在项目集I0中：有移进项目T→·aBd和归约项目T→·存在移进-归约冲突，所以G不是LR〔0〕文法；如产生式排序为：(0)S'→T(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}=学习必备欢迎下载Follow〔T〕∩{a}={#，b}∩{a}=Follow〔
18、B〕∩Follow〔T〕={d}∩{#，b}=所以在I0，I2，中的移进-归约和归约-归约冲突可以由是SLR〔1〕文法；构造的SLR〔1〕分析表如下表；Follow集解决，所以GSLR〔1〕分析表ACTIONGOTOnameabd#TB0S2r2r211acc2S2r2r4r2433S54S65r1r16r3第7题（10分）对产生C语言中的条件表达式的文法G[E]：E→E.E:E写出相应的翻译文法；答:E1→E.{BackPatch〔$1.TC,NXQ〕;$$.FC=$1.FC;}E2→E1E2:{$$.place=$2.place;$$.temp=NXQ;GEN
19、〔j,0,
