杭电编译原理试卷一及答案.doc

上传人:豆**** 文档编号:17240266 上传时间:2022-05-22 格式:DOC 页数:10 大小:231.50KB
返回 下载 相关 举报
杭电编译原理试卷一及答案.doc_第1页
第1页 / 共10页
杭电编译原理试卷一及答案.doc_第2页
第2页 / 共10页
点击查看更多>>
资源描述

《杭电编译原理试卷一及答案.doc》由会员分享,可在线阅读,更多相关《杭电编译原理试卷一及答案.doc(10页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、【精品文档】如有侵权,请联系网站删除,仅供学习与交流杭电编译原理试卷一及答案.精品文档. 试卷(一)一、 选择1.一个正规语言只能对应( B)?A 一个正规文法;B 一个最小有限状态自动机;2.文法GA:A AaB BAb Ba是( B):A 正规文法;B 二型文法;3.下面说法正确的是( A):A 一个SLR(1)文法一定也是LALR(1)文法;B 一个LR(1)文法一定也是LALR(1)文法4.一个上下文无关文法消除了左递归,提取了左公共因子后是满足LL(1)文法的( A):A 必要条件B 充分必要条件二、多项选择1.PL/0语言的目标程序解释执行时用到的数据对象有(AC):A 目标代码C

2、ODEB 符号表TABLEC 数据栈SD 关键字表WORD2.PL/0语言编译时产生或使用的数据对象有(ABD):A 目标代码CODEB 符号表TABLEC 数据栈SD 关键字表WORD三、问答题问答第1题(5分)将文法GS 改写为 等价的GS,使GS不含左递归和左公共因子。GS: SbSAe | bA AAb | dSbBBSAe | AAd AA bA | 问答第2题(10分) 判断下面文法是否为LL(1)文法,若是,请构造相应的LL(1)分析表。SaHHaMd | dMAb | AaM | e首先计算文法的 FIRST集和FOLLOW集如下表非终结符 FIRST集 FOLLOW集 S a

3、. # . H a ,d. # . M a ,e , d ,b A a ,e. b. 由于select(HaMd)select(Hd)=ad = select(MAb)select(M)=a ,ed ,b = select(AaM)select(Ae)= a e = 所以该文法是LL(1)文法,LL(1)分析表如下表。 LL(1)分析表 a d b e # S aH. H aMd d. M Ab. Ab A aM. e. 问答第3题给出与正规式R(ab)*(a|b*)ba等价的NFA。问答第4题将下图的NFA确定化为DFA。 用子集法对所给图的确定化I Ia Ib 状态 X,1,21,2.1,

4、2,31,2,Y 1,2.1,2.1,2,Y1,2. 1,2,31,2,31,2,31,2,3 X123 确定化后如下图问答第5题(7分)(1)给出下列PL/0示意程序中当程序执行到X过程调用Z过程后(即执行Z过程 体时)的栈式存储分配布局和用Display显示表时Z过程最新活动记录的内容。(2)说明Display表和DL(老SP),RA,TOP及全局Display的作用。 PL/0示意程序为:const a=80;var b,c;procedure X;var d;procedure Z;var e,g;begin (* Z *)c:=b*a;end ;(* Z *)begin (* X *

5、)call Z;end ;(* X *)procedure Y;var f;begin (* Y *)call X;end ;(* y *)begin (* main *)call Y;end. (* main *)解:(1)当程序执行到X过程调用Z过程后(即执行Z过程 体时)的栈式存储分配布局和用Display显示表时Z过程最新活动记录的内容如下图。解:(2)Display表和DL(老SP),RA,TOP及全局Display的作用分别说明如下:Display表的作用是对嵌套过程语言实现对非局部变量的引用而设置的,它依次存放着包围它的外过程的最新活动记录的基地址SP值,由于,嵌套层 次为i+1

6、过程中的非局部变量可能在i,i-1,0层,所以,对非局部变量的引用是通过它的display表元素di,di- 1,d0而获得包围它的外过程的最新活动记录的基地址SP值,再加上变量在该过程(第i层)的偏移量。如若非局部变量a是在第i层,那么引用a 时,首先从当前栈顶过程的display表中元素di中取出存放的第i层最新活动记录基地址SP值,然后加上a所在过程(第i层)的偏移量,就得到a 的存放地址。如Z过程的display表内容为:d(2) Z的SP d(1) X的SP d(0) Main的SP DL(老SP): 也称动态链或控制链,指向调用该过程前正在运行过程的数据段基地址,用以过程执行结束释

7、放数据空间时,恢复调用该过程前运行栈的状态。RA:返回地址,记录调用该过程时目标程序的断点,即调用过程指令的下一条指令的地址,用以过程执行结束后返回调用过程时的下一条指令继续执行。TOP:栈顶指针TOP指出了当前栈中最新分配的单元。全局Display是存放本过程display表的起始地址,其作用是把display地址作为连接数据之一,如过程P1调用过程P2时,这时先从 P1的全局Display找到P1的display表起始地址,然后从P1的display表中自底向上地抄录I2个单元(I2为P2的层数)再添上进入 P2后新建立的P2的SP值,就构成了P2的display表。问答第6题(5分)给出

8、问答第5题PL/0示意程序编译到Y过程体时TABLE表的内容。解:PL/0示意程序编译到Y过程体时TABLE表的内容如下表。解:TABLE表的内容name kind level val adr size mainabcXYf procedureconstantvariablevariableprocedureprocedurevariable .00001 .80 0.dxdx+1过程X的入口过程Y的入口dx 5.44 由于Y和X是并列过程,当编译到Y过程时X过程体已经编译结束,X所定义的标识符不会再被使用,所以X定义的标识符d 、Z及Z定义的e、g都被Y过程定义的标识符覆盖。问答第7题(10

9、分)某语言的拓广文法G为:(0) ST (1) T aBd| (2) B Tb|证明G不是LR(0)文法而是SLR(1)文法,请给出SLR(1)分析表。解:在项目集I0中:有移进项目T 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)=#,bFollow(B)= d在I0中:Follow(T) a=# ,b a=在I2中:Follow(B) a= d a=Follow(T) a=#

10、,b a=Follow(B) Follow(T) = d# ,b=所以在I0,I2,中的移进-归约和归约-归约冲突可以由Follow集解决,所以G是SLR(1)文法。构造的SLR(1)分析表如下表。SLR(1)分析表name ACTION GOTO a b d # T B 0 S2 r2 r2 1 1 acc 2 S2 r2 r4 r2 4 3 3 S5 4 S6 5 r1 r1 6 r3 问答第8题(5分)给出文法GS的LR(1)项目集规范族中I0项目集的全体项目。GS为: S BD|D B aD|b D BI0:解:I0问答第9题(5分)文法GM及其LR分析表如下,请给出对串dbba#的分

11、析过程。GM: 1) M VbA 2) V d3) V 4) A a5) A Aba 6) A ACTION GOTO b d a # M A 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 解:对输入串dbba#的分析过程步骤 状态栈 文法符号栈 剩余输入符号 动作 123456789 00302024024602467024678024601 #d#V#Vb#VbA#VbAb#VbAba#VbA#M dbba#bba#bba#ba#ba#a# 移进用V d归约移进用A 归约移进移进用A Aba

12、归约用M VbA 归约接受 问答第10题(5分)文法GE为: EE+T|TTT*F|FF(E)|i试给出句型(E+F)*i的短语,简单(直接)短语,句柄和最左素短语。解:短语有: (E+F)*i ,(E+F) ,E+F ,F ,i简单(直接)短语有: F ,i句柄是: F最左素短语是: E+F问答第11题(6分)按指定类型给出下列语言的文法。(1)L1= anbm c| n0,m0 用正规文法。(2) L2= a0n1n bdm | n0,m 0 用二型文法。(1) 解:描述L1语言的正规文法如下:S aS|AA bA|bBB c(2) 解:描述L2语言的二型文法如下:S ABA aTT 0T

13、1|01B bDD dD|d问答第12题(6分)试对 if (ad) then s:=e else s:=f 的四元式序列给出第四区段应回填的指令地址,并指出真假出口链和链头及回填的次序。 应回填的值 回填的次序 (1) if ad goto ( ) ( ) (4) goto ( ) ( ) 假链头 E.false= (5) s:=e 假出口链( ) (6) goto ( ) ( ) (7) s:=f (8) . 解: 应回填的值 回填的次序 (1) if ad goto ( 5 ) ( 2 ) (4) goto ( 7 ) ( 3 ) 假链头 E.false= 4 (5) s:=e 假出口链( 4,2 ) (6) goto ( 8 ) ( 5 ) (7) s:=f (8) .

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 小学资料

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁