编译原理试题及答案

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

1、编译原理试题及答案一、对于文法G[S]：　　S→1A

2、0B

3、ε　　A→0S

4、1AA　　B→1S

5、0BB　　⑴(3分)请写出三个关于G[S]的句子；　　⑵(4分)符号串11A0S是否为G[S]的句型？试证明你的结论。　　⑶(3分)试画出001B关于G[S]的语法树。二、请构造一个文法，使其产生这样的表达式E：表达式中只含有双目运算符+、*，且+的优先级高于*，+采用右结合，*采用左结合，运算对象只有标识符i，可以用括号改变运算符优先级。要求给出该文法的形式化描述。三、设有语言L={α

6、α∈{0,1}+，且α不以0

7、开头，但以00结尾}。　　⑴试写出描述L的正规表达式；　　⑵构造识别L的DFA（要求给出详细过程，并画出构造过程中的NDFA、DFA的状态转换图，以及DFA的形式化描述)。四、给定文法G[S]：　　S→AB　　A→aB

8、bS

9、c　　B→AS

10、d　　⑴(6分)请给出每一个产生式右部的First集；　　⑵(3分)请给出每一个非终结符号的Follow集；　　⑶(8分)请构造该文法的LL(1)分析表；　　⑷(8分)什么是LL(1)文法？该文法是LL(1)文法吗？为什么？五、给定文法G[S]：　　S→SaA

11、a　　A→A

12、bS

13、b　　⑴请构造该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA。　　⑵请构造该文法的LR(0)分析表。　　⑶什么是LR(0)文法？该文法是LR(0)文法吗？为什么？　　⑷什么是SLR(1)文法？该文法是SLR(1)文法吗？为什么？六、给定下列语句：　　ifa+b>c　　thenx:=a*(b-c)+(b*c-d)/e　　⑴写出其等价的逆波兰表示；　　⑵写出其等价的四元式序列。七、已知下列C语言程序：　　int*f()　　{　inta=100;return&a;　　}　　main()　　{　in

14、t*i=f();　　　　chara[]=“compiler”;printf(“theresultis%d”,*i);　　}　　程序运行结果为：theresultis26157,　　请解释为什么程序运行的结果不是期望的“theresultis100”？51.1三个0和1数量相等的串1.2S=>1A=>11AA=>11A0S1.3第二题构造文法如下:G[E]=({+,*,(,),i},{E,F,T},P,E)，其中P为：E→E*F

15、FF→T+F

16、TT→(E)

17、i第三题（1）正规表达式：1(0

18、1)*00（2）第

19、一步：将正规表达式转换为NDFA第二步：将NDFA确定化为DFA：造表法确定化（3分）确定化后DFAM的状态转换表(2分)状态输入I0I1 t01[S]—[A,D,B] q0—q1[A,D,B][D,B,C][D,B]重新命名q1q2q3[D,B,C][D,B,C,Z][D,B]q2q4q3[D,B][D,B,C][D,B] q3q2q3[D,B,C,Z][D,B,C,Z][D,B] q4q4q35DFA的状态转换图（3分）第三步：给出DFA的形式化描述DFAM=（{q0,q1,q2,q3,q4},{0,1},

20、t,q0,{q4}）t的定义见M的状态转换表。第四题（1）First(AB)={a,b,c}First(aB)={a}First(bS)={b}First(c)={c}First(AS)={a,b,c}First(d)={d}（2）Follow(S)={#,a,b,c,d}Follow(A)={a,b,c,d}Follow(B)={#,a,b,c,d}（3）LL(1)分析表（8分）VNVTabcd#SS?ABS?ABS?AB  AA?aBA?bSA?C  BB?ASB?ASB?ASB?d （4）对于文法G的每一

21、个非终结符U的产生式U?α1

22、α2

23、…

24、αn，5如果SELECT(U?αi)?SELECT(U?αj)=?（i≠j,i,j=1,2,…,n），则文法G是一个LL(1)文法。该文法是LL(1)文法。因为SELECT(A?aB)?SELECT(A?bS)?SELECT(A?C)=?SELECT(B?AS)?SELECT(B?d)=?第五题⑴拓广文法1分G[S′]:S′→S⑴S→SaA⑵S→a⑶A→AbS⑷A→b⑸该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA：⑵该文法的LR(0)分析表：状态ACTIO

25、NGOTOab#SA0S2  1 1S3 acc  2r3r3r3  3 S5  44r2r2/S6r2  5r5r5r5  6S2  7 7r4/S3r4r4  ⑶LR(0)文法：该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA中没有冲突状态。该文法不是LR(0)文法因为存在冲突状态：I4和I75⑷SLR(1)文法：该文法的以LR(0)项目集为状态的识别规范句型活前缀的D