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

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

1、试卷（三）：一、选择1.下面说法正确的是：AA一个正规文法也一定是二型文法B一个二型文法也一定能有一个等价的正规文法2.文法G[A]：A→bA→ABB→AbB→a是(　A　)：A二型文法B正规文法3.下面说法正确的是(　B　)：Alex是一个词法分析器Byacc是一个语法分析器的生成器4.一个LR（1）文法合并同心集后,如果不是LALR(1)文法必定存在(　B　)：A移进--归约冲突B归约--归约冲突5PL/0语言编译程序使用递归子程序法进行语法分析，他的文法必须满足(A　　)：ALL（1）文法BSLR(1)文法二、问答题问答第1题（6分）试对repeatx:=buntilb>aor(

2、bagoto(　)(　)真出口链(　)(3)goto(　)(　)(4)ifbagoto(8)(6)真出口链(6,2)(3)goto(4)(1)(4)ifb

3、链头E.false=7(5)goto(1)(4)假出口链(7,5)(6)ifb=dgoto(8)(5)(7)goto(1)(3)问答第2题(10分)某语言的拓广文法G′为：　　(0)S′→S　　(1)S→Db

4、B　　(2)D→d

5、ε　　(3)B→Ba

6、ε证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。解：拓广文法G'，增加产生式S'→S在项目集I0中：有移进项目D→·d归约项目D→·和B→·存在移进-归约和归约-归约冲突，所以G不是LR(0)文法。若产生式排序为：(0)S'→S(1)S→Db(2)S→B(3)D→d(4)D→ε(5)B→Ba(6)B→εG′的LR

7、(0)项目集族及识别活前缀的DFA如下图：识别G′活前缀的DFA由产生式知：Follow(S)={#}Follow(D)={b}Follow(B)={a,#}在I0中:Follow(D)∩{d}={b}∩{d}=Follow(B)∩{d}={a,#}∩{d}=Follow(D)∩Follow(B)={b}∩{a,#}=在I3中:Follow(S)∩{a}={#}∩{a}=所以在I0，I3中的移进-归约和归约-归约冲突可以由Follow集解决,所以G是SLR(1)文法,构造的SLR(1)分析表如下表。SLR(1)分析表问答第3题(5分)给出文法G[S]的LR(1)项目集规范族中I0项目集

8、的全体项目。　　G[S]为：S→S;V

9、V　　　　　　V→VaA

10、A　　　　　　A→b(S)

11、εI0:解：I0:问答第4题(5分)文法G[M]及其LR分析表如下，请给出对串dada#的分析过程。　　G[M]:1)S→VdB　　　　2)V→e　　　　　3)V→ε　　　　4)B→a　　　　　5)B→Bda　　　6)B→ε解：对串dada#的分析过程如下表对输入串dada#的分析过程步骤状态栈文法符号栈剩余输入符号动作用V→ε归约移进移进用B→a归约移进移进1234567890020240245024602467024601##V#Vd#Vda#VdB#VdBd#VdBda#VdB#Sdad

12、a#dada#ada#da#da#a####用B→Bda归约用S→VdB归约接受问答第5题(7分)(1)给出下列PL/0示意程序中当程序执行到D过程调用A过程后（即执行A过程体时）的栈式存储分配布局和用Display显示表时A过程最新活动记录的内容。　　(2)说明Display表和全局Display的作用。PL/0示意程序为：　　　varx;　　procedureA;　　　vard;　　　begin(*A*)　　　　write(x);　　　end(*A*);　　procedureB;　　　constn=7;　　　vare,g;　　　procedureD;　　　　varj,k;　　　　b

13、egin(*D*)　　　　　read(j,k);　　　　　x:=x+j*n;　　　　　callA;　　　　end;(*D*)　　　begin(*B*)　　　　callD;　　　end;(*B*)　　begin(*main*)　　　read(x);　　　callB;　　end.(*main*)解：（1）PL/0示意程序中当程序执行到D过程调用A过程后（即执行A过程体时）的栈式存储分配布局和用Display显示表时栈中过程最新活动记录的内容如下图。