还剩7页未读,继续阅读
文本内容:
试卷
(一)
一、选择
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充分必要条件
二、多项选择
1.PL/0语言的目标程序解释执行时用到的数据对象有AC A目标代码CODE B符号表TABLEC数据栈SD关键字表WORD
2.PL/0语言编译时产生或使用的数据对象有 ABD A目标代码CODEB符号表TABLEC数据栈SD关键字表WORD
(1)给出下列PL/0示意程序中当程序执行到X过程调用Z过程后(即执行Z过程体时)的栈式存储分配布局和用Display显示表时Z过程最新活动记录的内容
(2)说明Display表和DL(老SP)RATOP及全局Display的作用PL/0示意程序为 consta=80; varbc; procedureX; vard; procedureZ; vareg; begin*Z* c:=b*a; end;*Z* begin*X* callZ; end;*X* procedureY; varf; begin*Y* callX; end;*y* begin*main* callY; end.*main*解
(1)当程序执行到X过程调用Z过程后(即执行Z过程体时)的栈式存储分配布局和用Display显示表时Z过程最新活动记录的内容如下图解
(2)Display表和DL(老SP)RATOP及全局Display的作用分别说明如下·Display表的作用是对嵌套过程语言实现对非局部变量的引用而设置的,它依次存放着包围它的外过程的最新活动记录的基地址SP值,由于,嵌套层次为i+1过程中的非局部变量可能在i,i-1,…,0层,所以,对非局部变量的引用是通过它的display表元素d[i],d[i-1],…,d
[0]而获得包围它的外过程的最新活动记录的基地址SP值,再加上变量在该过程(第i层)的偏移量如若非局部变量a是在第i层,那么引用a时,首先从当前栈顶过程的display表中元素d[i]中取出存放的第i层最新活动记录基地址SP值,然后加上a所在过程(第i层)的偏移量,就得到a的存放地址 如Z过程的display表内容为d
(2)Z的SPd
(1)X的SPd
(0)Main的SP·DL(老SP)也称动态链或控制链,指向调用该过程前正在运行过程的数据段基地址,用以过程执行结束释放数据空间时,恢复调用该过程前运行栈的状态·RA返回地址,记录调用该过程时目标程序的断点,即调用过程指令的下一条指令的地址,用以过程执行结束后返回调用过程时的下一条指令继续执行·TOP栈顶指针TOP指出了当前栈中最新分配的单元·全局Display是存放本过程display表的起始地址,其作用是把display地址作为连接数据之一,如过程P1调用过程P2时,这时先从P1的全局Display找到P1的display表起始地址,然后从P1的display表中自底向上地抄录I2个单元(I2为P2的层数)再添上进入P2后新建立的P2的SP值,就构成了P2的display表问答第6题5分给出问答第5题PL/0示意程序编译到Y过程体时TABLE表的内容解PL/0示意程序编译到Y过程体时TABLE表的内容如下表解TABLE表的内容namekindlevelvaladrsizemainabcXYfprocedureconstantvariablevariableprocedureprocedurevariable..
00001.
800.dxdx+1过程X的入口过程Y的入口dx
5...44由于Y和X是并列过程,当编译到Y过程时X过程体已经编译结束,X所定义的标识符不会再被使用,所以X定义的标识符d、Z及Z定义的e、g都被Y过程定义的标识符覆盖问答第7题10分某语言的拓广文法G′为0S′→T 1T→aBd|ε 2B→Tb|ε 证明G不是LR0文法而是SLR1文法,请给出SLR1分析表解在项目集I0中有移进项目T→·aBd和归约项目T→· 存在移进-归约冲突,所以G不是LR0文法若产生式排序为 0S→T1T→aBd2T→ε 3B→Tb 4B→εG的LR0项目集族及识别活前缀的DFA如下图所示 识别G′活前缀的DFA由产生式知FollowT={#b} FollowB={d}在I0中 FollowT∩{a}={#,b}∩{a}= 在I2中FollowB∩{a}={d}∩{a}= FollowT∩{a}={#,b}∩{a}= FollowB∩FollowT={d}∩{#,b}= 所以在I0,I2,中的移进-归约和归约-归约冲突可以由Follow集解决,所以G是SLR1文法构造的SLR1分析表如下表SLR1分析表nameACTIONGOTOabd#TB0S2r2 r21 1 acc 2S2r2r4r2433 S5 4 S6 5 r1 r1 6 r3 问答第8题5分给出文法G[S]的LR1项目集规范族中I0项目集的全体项目 G[S]为S→BD|D B→aD|b D→B I0: 解:I0问答第9题5分文法G[M]及其LR分析表如下,请给出对串dbba#的分析过程G[M]:1M→VbA 2V→d 3V→ε 4A→a 5A→Aba 6A→ε ACTIONGOTObda#MAV0r3S3 1 21 acc 2S4 3r2 4r6 S5r6 6 5r4 r4 6S7 r1 7 S8 8r5 r5 解对输入串dbba#的分析过程步骤状态栈文法符号栈剩余输入符号动作12345678900302024024602467024678024601##d#V#Vb#VbA#VbAb#VbAba#VbA#Mdbba#bba#bba#ba#ba#a####移进用V→d归约移进用A→ε归约移进移进用A→Aba归约用M→VbA归约接受问答第10题(5分)文法G[E]为E→E+T|T T→T*F|F F→E|i 试给出句型E+F*i的短语,简单直接短语句柄和最左素短语解短语有:E+F*i,E+F,E+F,F,i 简单直接短语有:F,i 句柄是:F 最左素短语是:E+F 问答第11题(6分)按指定类型给出下列语言的文法1L1={anbmc|n≥0m0}用正规文法2L2={a0n1nbdm|n0,m0}用二型文法1解描述L1语言的正规文法如下 S→aS|A A→bA|bB B→c2解描述L2语言的二型文法如下 S→AB A→aT T→0T1|01 B→bD D→dD|d 问答第12题(6分)试对ifadthens:=eelses:=f的四元式序列给出第四区段应回填的指令地址,并指出真假出口链和链头及回填的次序 应回填的值回填的次序 1ifabgoto 真链头E.true=2goto 真出口链 3ifadgoto 4goto 假链头E.false=5s:=e 假出口链 6goto 7s:=f
8... 解 应回填的值回填的次序 1ifabgoto31真链头E.true=32goto74真出口链33ifadgoto52 4goto73假链头E.false=45s:=e 假出口链426goto85 7s:=f
8... 。