华南农业大学编译原理题库_第1页
华南农业大学编译原理题库_第2页
华南农业大学编译原理题库_第3页
华南农业大学编译原理题库_第4页
华南农业大学编译原理题库_第5页
已阅读5页,还剩18页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持华南农业大学期末考试题库(含参考答案)本题共6小题,每小题5分,共30分考试科目: 编译原理考试时间: 120 分钟题号-一一二二二-三四五总分得分评阅人学号姓名年级专业得分O1、写出下面右线性正规文法所对应的正规式。2、给出下面语言集合的上下文无关文法。文法所对应20正规式为:A f aDLi= arbm | rm 1 a(b|aa)*b2、文法: S f aS | D为正规集L2=anbm ck | rDf, aDabk1构造一右线性正规文法(2010)S f aS | aA3、按照编译过程的-5个阶段得到编译程序的逻辑结构框图如

2、下:B f cB | c2文档收集于互联网,如有不妥请联系删除文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持4、简述编译过程的5个阶段及各阶段的主要功能。(多年必考)编译过程即编译程序的工作过程,是指从输入源程序开始到输出目标程序为 5止“含有优化部分的编译程序的执行效率而言,一这以划分为五个工作阶 这句话是错的析优化不是编译程序必须的进个部分和含有优识的出译程序的 6单简述语算导翻译技术的基的语法规则,把单词符号串但得成各目标法单 位语法制通翻译技术间基本产想是即对文法语法每个产生式都含义并个语义n 7、动作或语优先分析方对执行语行分价变过程以和产运用该产生式进行推导 I标或归

3、约成,就执行相应变语义动定机从而完成预语商指令工作。算符优先分析方法是一种移进-归约的语法分析方法,这种分析方法首先要山 、根据说明翻译程序与编译程序优先同系优然后借助与种解释程序的异在移进(2011) I -归约程程是将译比较相邻序(符)间的成另译种语确程句型目可归约串对源语言和 目标语素短语)另并进行归约译程序是译种高级范归约的源程序转换只适用于言程序, 序的是NfA还是DFA,并用正规式来描述它所识别的语分编译程序与解释程序都是将高级语言翻译成低级语言,但编译程序要先编译生 成目标代码、再执行目标代码,解释程序边转换边执行,不生成目标代码。是DFA(1分),对应的正规式为 &来描述它所识

4、别的语言。 (2011)11、有文法及其语A10、判断下图FA是i A还是gFA,并O1*01*(01*01*)* (4B是NFA,因为A状态输入0可以转换到A或B两状态。*(0|1)*S T pri nt(TQJyT T 1*E T.h= T 1.h +E.h T E T.h=E.h E (T)E.h= T.hE a E.h= 1 采用移进归约的分析方法,当分析器的输入为(a)*(a*a) 时,画出其语法树(可以带注释、也可以不带注释),并求输出的结果。12 (20语法空心圆柱体入表面积计算公式如时输出的结果为:S=米丿2*3.1416*(R+r)*(R-r)+ 2*3.1416*(R+r)

5、*h用LR语法制导翻译技术生成相应的三地址代码,然后运用 行局部优化,试写出能生成最优目标代码的优化后的三地址代码序列DAG对其进13、试14、可以采用合并已知量、删除公共子表达式、删除无用赋值、交换语句 式求表等优化方法优得到三地址代码序列缀式和三地址代码。(2011)(1) T仁R+r(2) T2=6.2832*T1(3) T3=T2*h S=T5+T3T2=B*T1T3=A+T2T5=B/T4T6=T3+T5B1B2B3考虑如1式的三地址语句序列鬥2*)-三地址代码;T仁-CL1: read T4=-CA=0;一 B=1;L2: A=A+B;if B C goto L3;B=B+1;go

6、to 2文档收集于互联网,如有不妥请联系删除goto L1;L3: write A;多余的语句,删去文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持(1) .将该代码序列划分成基本块,并给每个基本块一个序号;(2) .画出该代码序列的流图,每个基本块用(1)的序号表示;(3) .若有循环,列出构成循环的节点(基本块)。(10分)(1) .如图分成四个基本块 B1、B2、B3 B4(2) .流图:(3) .构成循环的15、有翻译模式S S14文档收集于互联网,如有不妥请联系删除S a S.h=O S( T)S.h= T.h+1T T 1, S T.h= T 1.h +S.h T S

7、T.h= S.h 采用移进归约的分析方法,当分析器的输入为(a,(a) 时,画出其语法树(可 以带注释、也可以不带注释),并求输出的结果。(2011)语法树:输出结果是:2得分、构造识别下列语言的最小 DFA (共20分):求出NFA 得C 4分,确定化了得6分,最小DFA的求出NFA得4分,确定化了得6分,最小DFA的 3状态错1漏一个的二进分串孤锚漏一条扣0.5分。0得构造识别下列语言的最小 DFA (共15分):(2011)4、正规式(0|1)*( 00 | 11 )( 0|1)* ;( 5 分)5、 含有、奇数个1或奇数个0的二进制串;(5分)6、能被2整除的二进制串。(5分)A 10

8、C1构造下列正规式相应的DFA (用状态转换图表示)(15) (2008)(7)1(0 | 1)*1得分7、将下图NFA确定化。(10分)(2013)首先将DFA的状态集划分成终态集和非终态集由于A,B,C,Doo=B,C,C,,、法如下:I b,| 耐B,C1=,D,T TeS | S9BA,B,C,D;D;、B,C;,所以再分划成A,B,0E、D所以再次分划成warn,的语法树母语所直不短语分素短语C是等价状态。0 分) 语法树得到最小白的胃如下:(5 分)( TB T eS0个T 右( S)10.有定义ETFP构造句型E+T*P P-i的语法树;并指出该句型的所有短语、直接短语、素短(2

9、 分)短语:(Sebe(a)、Sebe(a)、 Seb (a)、(1分)直接短语:S、b、a(1分)素短语:b、a(1分)句柄:SS b、aR表达式的文法如下:+T | E-T | T一算bT*F | T/F | F P F | P(E) | i11)语、句柄。(10分)所有的短语:E+T*P P-i、E+T*P P、i、T*P P、语法分析树:只接短(#ssn a的 下、 p告-另口八FAD/lE -th. 步(2)分别写出上一步DFA各状态所识别的活前/c 厶入 t t 处 口. i=b串、分析动作)。(1).(6分)拓广文法并给产生式编号:缀;彳:j过程状态栈、/I IS,t s ST

10、aSe、符号栈F输入文法的识别规范句型活前缀的Io: S t.SsDFA-Fi5: S t aSe日(2).文法的所有规范句型的活前缀就& | S | aa* t . |aACTS)N*ae |GOpa-ep s0S2a 1 , m 014 设有法aSbAib (2008)A BCc | gEB + tB bCDE | G1 :SABA aAb | abCDaB | caDdD| FB bBa |FIRSTFOLLOWAa,b,c,d,gfBb,a,c,d , f, gCa,c,dc,d,gDd,a,b,c,f,gEc,ga,c,d,f,gEgAf | c(1)计算该文法的每一个非终结符的FI

11、RST 集和 FOLLOW 集;(2)试判断该文法是否为 LL (1)文法。(10)是LL (1)文法。15、对表达式文法 G: ( 2008)E t E+T | TT t T*F | FF t (E) | I(1) 造各非终结符的 FIRSTVT和LASTVT集合;(2) 构造文法的算符优先关系表。(15)FIRSTVTLASTVTE*, +, (, i*, +,), iT*, (, i*,), iF(,i),i算符优先关系表+*I()#+*I()#16、 对下述文法:(10)(2008)St a |(T)Tt t , S | S构造一个翻译模式,统计输出配对的括号个数。引入S、T的综合属性

12、h来统计配对的括号个数,得到翻译模式如下:S t Spri nt(S.h)St a S.h=0 St( T)S.h= T.h+1Tt T 1, S T.h= T 1.h +S.h Tt S T.h= S.h 17、 有文法如下:(共15分)S t aBB t aDd|dD t Ab|A t aD | e(1) 计算文法的每个非终结符的FIRST集合和FOLLOW集合;(2) 计算文法的每个候选产生式的SELECT!合; 说明文法是LL (1)文法的理由,并给出其预测分析表;(4)给出符号串aaebd的预测分析过程(即最左推导过程)文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持(3

13、).(4分)如上所求结果,定义非终结符 B(或D或A)的两个规则的SELECT合无交集,所以文法是LL(1)文法,其预测分析表如下:abde#SS f aBBB f aDdB f dDD f Ab 1DfDfDf AbAA f aDAf e分析栈输入串所用规则#Saaebd#Baaaebd#Sf aB#Baebd#dDaaebd#Bf aDd#dDebd#dbAebd#Df Ab#dbeebd#Af e#dbbd#dd#结束.(3分)符号串aaebd的预测分析过程:符号串aaebd的最 左推导过程:S aB aaDd a aAbd aaebdii文档收集于互联网,如有不妥请联系删除文档来源为:

14、从网络收集整理.word版本可编辑.欢迎下载支持18、有文法如下:S f aAB(共 10 分)(2013)B f a | dA f bB | eA |&(1)计算文法的每个候选产生式的SELECT!合;(5分) 说明文法是LL (1)文法的理由,并给出其预测分析表。(5分)(1)SELECT(S f aAB)=a SELECT(B f a)=a SELECT(B f d )=dSELECTA f bB)=b SELECT(A f eA)=e SELECT(A f )=a , d(2)文法不含左递归,定义B的两条产生式的SELECT!没有交集,定义A的三条产生式的SELECT!两两不相交,所以

15、文法是LL (1)文法,预测分析表如下:abde#SS f aABBB f aB f dAA fA f bBA fAf eAL f id R19、有文法如下:(共 15 分)(2011)S f T L T f int |floatR f ,id R |&(1) 计算文法的每个候选产生式的SELECTS合;(5分)(2) 说明文法是LL (1)文法的理由,并给出其预测分析表;(6分)(3) 给出符号串int id,id的预测分析过程(包括分析栈、输入串、所用规则)。(4分)(1) SELECT(S f T L )=int,floatSELECT(T f int )=int SELECT(T f

16、float )=floatSELECT(L f id R )=id SELECT(R f ,id R )=,SELECT(R f )=$文法不含左递归,并且 SELECT(T f int )A SELECT(T f float )=OSELECT(R f ,id R ) n SELECT(R f )=所以文法是LL (1)文法,预测分析表如下:intfloatid$SS f T LS f T LTT f intT f floatLL f id RRR f ,id RR f(3)符号串 int id,id的预测分析过程:分析栈输入串所用规则$Sint id,id$S f TL$LTint id,

17、id$T f int$Li ntint id,id$int与int匹配$Lid,id$L f id R$Ridid,id$id与id匹配$R,id$R f ,id R$Rid,id$,与,匹配$ Ridid$id与id匹配$R$R f$分析结束得分20、有定义上进制串的文法如下:(共15分)S t LL t 0L1L t 01构造文法的识别规范句型活前缀的 DFA 分别写出上一步DFA各状态所识别的活前缀;rh.步说明该文法是SLR( 1)文法的理由,并给出SLR( 1)分析表; 给出符号串0011的LR移进-归约过程(包括状态栈、符号栈、输入串、 分析动作)。23文档收集于互联网,如有不妥请

18、联系删除(1)构造文法的识别规范句型活前缀的 DFA(叭2上一别写出上状态所识别的活前缀识别的活前分别是:|: 说明该文法蹙;slR:0*0l文法的理由01并给出0SLR( 1)分析表;(3). ( 4给出符号串面0DFA各各移态者归不含过突,包以文法是符号栈)、文法入串也是SLR(1)文法。析动作DOW(L)=1,#, SLR(1)分析表如下:LR(0)分析表如下acTOnGOTO012345符号L00S2acc对文法进行拓广并为产生式编号:(0) S T L (1)L T LB (2)L t B t 0(4)B t 1(1)(6 分)构造文法的识别活前缀的DFA图:S2 S4Io: S t

19、 .L -S5 L T丄Br2 L T. Br1 B t . 0r2r1串 a0e? 的 lr 分析r-,-1符号栈# #0 #00 #001 #0L #0L1#L犬态栈)L020220224023023501Iii: S t L .LtL.BBt. 0Bt. 1I5: L T LB.0亍过程(4 分): L T B .输入串0011#- 011# S2n# 4: B前仁0(4J分)DFA 各动作I0:祖 S: B T 0. I 4r| L1 耳 (6 分)丨1中羽犬态所识别的活前缀:I1: L I2: B I3: 0 | I5: LB含移进-归约冲突,1#1#r2 S5 r1 acc但FOL

20、LOW(S ) =$,与待移进 的符号集合0 , 1没有交集, 所以是 SLR(1)文法。FOLLOW(L)=FOLLOW(B)=0,1,$, SLR(1)分析表如下:状态ACTIONGOTO01$LB0S3S4121S3S4acc52r2r2r23r3r3r34r4r4r45r1r1r1(4分)符号串10的LR分析过程:状态栈符号栈输入串分析动作0$10$S404$10$r402$B0$r201$L0$S3013$L0$r3015$LB$r101$L$acc六、证明题(本题共2小题,每小题5分,共10分)1、证明正规式b(ab)*与(ba)*b是等价的。(5分)证明:因为两个正规式描述的正规集都是 b, bab, babab, bababab, babababab,所以等价。(用文字描述正规集也可以。) 或用等文的最小DFG一样来证些也可以,都是证明符号串(b)a(aA(b (Sa是,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论