编译原理习题含历年专业考试题

《编译原理习题含历年专业考试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理第一章---第六章补充例1文法G[P]及相应翻译方案为：P→bQb{print:”1”｝Q→cR{print:”2”｝Q→a{print:”3”｝R→Qad(print:”4”｝（1)该文法是不是算符优先文法，请构造算符优先关系表证实之。(2)输入串为bcccaadadadb时，该翻译方案的输出是什么。(1）文法G[P]的每个非终结符的FIRSTVT集和LASTVT集如下：FIRSTVT(P)={b}；FIRSTVT(Q)={a,c}；FIRSTVT(R)={a,c}；LASTVT(P)={b}；LASTVT(Q)={a,c}；LASTVT(R)={d)。构造优

2、先关系表：由表3.19可看出：终结符对（c,a)存在着两种优先关系＜和＞，故文法G不是一个算符优先文法。P→bQb{print:”1”｝Q→cR{print:”2”｝Q→a{print:”3”｝R→Qad(print:”4”｝P→bQb{print:”1”｝Q→cR{print:”2”｝Q→a{print:”3”｝R→Qad(print:”4”｝(2)对输入串bcccaadadadb,画出其语法树，。采用修剪语法树的办法，按句柄方式自下而上归约语法树，每当一个产生式得到匹配（归约）时执行相应的语义动作。因此，第一个句柄匹配的产生式为Q→a,执行相应的语义动作：打印3;第

3、二个句柄匹配的产生式为R→Qad,执行相应的语义动作：打印4；……。由此得到最终的翻译结果为：34242421。1.语法分析之所以采用上下文无关文法是因为它的描述能力最强。　　　　　　　　（　）2.欲构造行之有效的自上而下分析器，则必须消除左递归。　　　　（　　）3.文法(SaS

4、bcS

5、ε)描述的语言是（a

6、bc）*()4.在自下而上的语法分析中，语法树与分析树一定相同。（）5.二义文法不是上下文无关文法.（）6.每一个算符优先文法，必定能找到一组优先函数与之对应。7.语法分析时必须先消除文法中的左递归。（　）8.规范归约和规范推导是互逆的两个过程。（　）9.一个文

7、法所有句型的集合形成该文法所能接受的语言。（）10.LL(1)文法一定不含左递归和二义性。（　）已知文法G[S]：S→dABA→aA

8、aB→Bb

9、ε（1）试问G[S]是否为正规文法，为什么？（2）G[S]所产生的语言是什么？（3）G[S]能否改写为等价的正规文法?答：(1)因为S→dAB不符合正规文法产生式A→aB或A→a,a∈VT*,A,B∈VN的格式，故G[S]不是正规文法。(2)G[S]产生的语言为：L={danbm

10、n≥1,m≥0}(3)可以得到G[S]对应的正规文法G’[S]:S→dAA→aA

11、aB

12、aB→bB

13、ε给出文法G1：S→aSb

14、PP→bPc

15、bQc

16、Q→Qa

17、a（1)它是Chomsky哪一型文法？（2）它生成的语言是什么？根据Chomsky的定义，对任何形如A→β的产生式，有A∈VN，β∈(VT∪VN)*时为2型文法。而文法G1恰好满足这一要求，故为Chomsky2型文法。(2)由文法Gl可以看出：S推出串的形式是aiPbi(i≥0),P推出串的形式是bjQcj(j≥1),Q推出串的形式是ak(k≥1).因此，文法G1生成的语言是L=｛aibjakcjbi

18、i≥0,j≥l,k≥1}。已知文法G[S]:S→S*aP

19、aP

20、*aPP→+aP

21、+a（1）将文法G[S]改写为LL(1）文法G‘［S］。（2）写出文法G'[S

22、]的预测分析表。文法G[M]是否LL(1)的，说明理由。G[M]：M→TBT→Ba

23、εB→Db

24、eT

25、εD→d

26、ε设有文法G[S]：S→SAS

27、bA→bSb

28、b试构造一个与其等价的算符文法。经分析可知G[S］产生的句子为奇数个b,其正规式为b(bb)*,由此得到NFA,令S对应状态X,A对应状态Y,B对应状态1，我们得到改写的文法G‘[S]为：G’［S］：S→bA

29、bA→bBB→bA

30、b对文法G‘[S]求FIRSTOP集与LASTOP集如下：FIRSTOP(S)={b}；FIRSTOP(A)={b}；FIRSTOP(B)={b}；LASTOP(S)={b}；LASTOP

31、(A)={b}；LASTOP(B)={b}。由于文法G’[S]只存在形如P→...aR...的产生式，则：由S→bA得b