杭电编译原理试卷二及答案

《杭电编译原理试卷二及答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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>banda

19、出第四区段应回填的指令地址，并指出真假链和链头及回填的次序。回填的次序应回填的值⑴ifa>bgoto()()真链头E.true=⑵goto()()真出口链()⑶ifabgoto(3)(1)真链头E.true=5⑵goto(5)(3)真出口链(5,3)⑶ifa

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-*