欢迎来到天天文库
浏览记录
ID:41696843
大小:145.35 KB
页数:9页
时间:2019-08-30
《杭电编译原理试卷二及答案》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、试卷(二):_、选择1.下面说法正确的是:BA一个正规式只能対应一个确定的有限状态自动机;B一个正规语言可能对应多个正规文法;2.算符优先分析与规范归约相比的优点是:AA归约速度快B対文法限制少3.—个LR(1)文法合并同心集后若不是LALR(1)文法:BA则可能存在移进/归约冲突B则可能存在归约/归约冲突C则可能存在移进/归约冲突和归约/归约冲突4•下面说法正确的是:AALex是一个词法分析器的生成器BYacc是一个语法分析器二、问答题问答第1题(5分)将文法G[S]改写为等价的G[S],使G[S]不含左递归和左公共因子。G[SJ:S->SAe
2、AeA—dAbA
3、dA
4、
5、d解:文法G[S]改写为等价的不含左递归和左公共因子的G[S]为:S->AeS*S'->AeSf
6、eA—dA‘A1->AB
7、eBfbA
8、e问答第2题(10分)判断下面文法是否为LL(1)文法,若是,请构造相应的LL(1)分析表。S—>aDD—STc
9、eT->bH
10、HH->d
11、s首先计算文法的FIRST集和FOLLOW集如下表。文法的FIRST集和FOLLOW集FOLLOW集非终结符FIRST集{a}{a,£}{#,b,d,e}{#,b,d,e}{b,dte}仙£}由于select(D—>STe)Oselect(D—>c)={a}0{#,bselect(T—>bH)Cl
12、select(T—>H)={b}D{e}=0select(H—>d)Aselect(H—w)={d}C{e}=0所以该文法是LL(1)文法,LL(1)分析表如下表。LL(1)分析表aebS-aDD—STe—£TiHibH->H问答第3题(5分)给出与正规式R=((ab)*
13、b)*(a
14、(ba)*)a等价的NFA。解:与正规式1<=((ab)*
15、b)*(a
16、(ba)*)a等价的NFA如下图问答第4题解:根据所给的PL/0示意程序完成下列要求。(1)(4分)给出当程序执行到A过程体的write(c)语句时的栈式存储分配布局和用Display显示表时A过程最新活动记录的内容
17、;(2)(2分)说明在过程D中,当执行c:=b*a;语句吋,变量c和b的存取位置是如何确定的(请填在下面的相应括号内)。c的存取位置=()b的存取位置=()PL/0示意程序为:varc;procedureM;procedureA;begin(*A*)writc(c);end(*A*)procedureZ;vara,b;procedureDbegin(*D*)c:=b*a;callA;end;(*D*)begin(*Z*)callD;end:(*Z*)begin(*M*)callZ;end;(*M*)begin(*main*)callM;end.(*main*)解:(1)
18、当程序执行到A过程体的write(c)语句时的栈式存储分配布局和用Display显示表时A过程最新活动记录的内容如下图当程序执行到A过程时栈式存储分配布局和栈中过程最新活动记录的内容(2)在过程D'p,当执行c:=b*a;语句时,变量c和b的存取位置可如下确定:由于D过程的display表内容为:(3)D的SP(2)Z的SP(1)M的SP(0)Main的SP所以c的存取位置=(d(0)屮Main的SP+c在Main屮的偏移量)b的存取位置=(d(2)中Z的SP+b在Z中的偏移量)问答第5题(6分)试对while(a>banda19、出第四区段应回填的指令地址,并指出真假链和链头及回填的次序。回填的次序应回填的值⑴ifa>bgoto()()真链头E.true=⑵goto()()真出口链()⑶ifabgoto(3)(1)真链头E.true=5⑵goto(5)(3)真出口链(5,3)⑶ifa20、7)⑺s:=a⑻goto(1)(6)问答第6题(10分)某语言的文法G为:E->aTd21、eT—Eb22、a证明G不是LR(0)文法而是SLR(l)文法,请给出该文法的SLR(l)分析表。解:拓广文法G,增加产生式S,tE在项目集10中:有移进项目E->aTd和归约项目存在移进■归约冲突,所以G不是LR(0)文法。若产生式排序为:(0)SJE(1)E->aTd(1)E->£⑶T->Eb⑷T->a血:S*B-**aTdL■G,的LR(O)项目集族及识别活前缀的DFA如下图:*JL:K-M-UT-*■■T-bma-■-M-TtT-*・•■+■T-*
19、出第四区段应回填的指令地址,并指出真假链和链头及回填的次序。回填的次序应回填的值⑴ifa>bgoto()()真链头E.true=⑵goto()()真出口链()⑶ifabgoto(3)(1)真链头E.true=5⑵goto(5)(3)真出口链(5,3)⑶ifa20、7)⑺s:=a⑻goto(1)(6)问答第6题(10分)某语言的文法G为:E->aTd21、eT—Eb22、a证明G不是LR(0)文法而是SLR(l)文法,请给出该文法的SLR(l)分析表。解:拓广文法G,增加产生式S,tE在项目集10中:有移进项目E->aTd和归约项目存在移进■归约冲突,所以G不是LR(0)文法。若产生式排序为:(0)SJE(1)E->aTd(1)E->£⑶T->Eb⑷T->a血:S*B-**aTdL■G,的LR(O)项目集族及识别活前缀的DFA如下图:*JL:K-M-UT-*■■T-bma-■-M-TtT-*・•■+■T-*
20、7)⑺s:=a⑻goto(1)(6)问答第6题(10分)某语言的文法G为:E->aTd
21、eT—Eb
22、a证明G不是LR(0)文法而是SLR(l)文法,请给出该文法的SLR(l)分析表。解:拓广文法G,增加产生式S,tE在项目集10中:有移进项目E->aTd和归约项目存在移进■归约冲突,所以G不是LR(0)文法。若产生式排序为:(0)SJE(1)E->aTd(1)E->£⑶T->Eb⑷T->a血:S*B-**aTdL■G,的LR(O)项目集族及识别活前缀的DFA如下图:*JL:K-M-UT-*■■T-bma-■-M-TtT-*・•■+■T-*
此文档下载收益归作者所有