搜索
1编译原理试题及答案高级版一、对于文法G[S]：S→1A|0B|εA→0S|1AAB→1S|0BB⑴(3分)请写出三个关于G[S]的句子；⑵(4分)符号串11A0S是否为G[S]的句型？试证明你的结论。⑶(3分)试画出001B关于G[S]的语法树。二、请构造一个文法，使其产生这样的表达式E：表达式中只含有双目运算符+、*，且+的优先级高于*，+采用右结合，*采用左结合，运算对象只有标识符i，可以用括号改变运算符优先级。要求给出该文法的形式化描述。三、设有语言L={α|α∈{0,1}+，且α不以0开头，但以00结尾}。⑴试写出描述L的正规表达式；⑵构造识别L的DFA（要求给出详细过程，并画出构造过程中的NDFA、DFA的状态转换图，以及DFA的形式化描述)。四、给定文法G[S]：S→ABA→aB|bS|cB→AS|d⑴(6分)请给出每一个产生式右部的First集；2⑵(3分)请给出每一个非终结符号的Follow集；⑶(8分)请构造该文法的LL(1)分析表；⑷(8分)什么是LL(1)文法？该文法是LL(1)文法吗？为什么？五、给定文法G[S]：S→SaA|aA→AbS|b⑴请构造该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA。⑵请构造该文法的LR(0)分析表。⑶什么是LR(0)文法？该文法是LR(0)文法吗？为什么？⑷什么是SLR(1)文法？该文法是SLR(1)文法吗？为什么？六、给定下列语句：ifa+bcthenx:=a*(b-c)+(b*c-d)/e⑴写出其等价的逆波兰表示；⑵写出其等价的四元式序列。七、已知下列C语言程序：int*f(){inta=100;return&a;}main()3{int*i=f();chara[]=“compiler”;printf(“theresultis%d\n”,*i);}程序运行结果为：theresultis26157,请解释为什么程序运行的结果不是期望的“theresultis100”？1.1三个0和1数量相等的串1.2S=1A=11AA=11A0S1.3第二题构造文法如下:G[E]=({+,*,(,),i},{E,F,T},P,E)，其中P为：E→E*F|FF→T+F|TT→(E)|i第三题（1）正规表达式：1(0|1)*00（2）第一步：将正规表达式转换为NDFA4第二步：将NDFA确定化为DFA：造表法确定化（3分）确定化后DFAM的状态转换表(2分)状态输入I0I1t01[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]q4q4q3DFA的状态转换图（3分）第三步：给出DFA的形式化描述5DFAM=（{q0,q1,q2,q3,q4},{0,1},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#6SS?ABS?ABS?ABAA?aBA?bSA?CBB?ASB?ASB?ASB?d（4）对于文法G的每一个非终结符U的产生式U?α1|α2|…|αn，如果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：7⑵该文法的LR(0)分析表：状态ACTIONGOTOab#SA0S211S3acc2r3r3r33S544r2r2/S6r25r5r5r56S277r4/S3r4r4⑶LR(0)文法：该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA中没有冲突状态。该文法不是LR(0)文法因为存在冲突状态：I4和I7⑷SLR(1)文法：该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA中有冲突状态，冲突可用FOLLOW集解决。该文法不是SLR(1)文法。8因为FOLLOW(S)={a,b,#}，所以无法解决冲突第六题（1）(1)ab+c(23)jumpf(8)xabc-*bc*d-e/+:=(23)...（2）第七题C语言采用栈式存储分配方法作为其运行环境；f()返回的是指向其活动记录某一位置的指针；f()返回后，其活动记录被释放，并且，其对应的存储空间被数组a占用，再次引用该指针时，其结果由于对回收的活动记录所占用的内存空间的再分配，其所指的值9发生了改变。释放在前，引用在后的现象称:DanglingReference。更多本课程的试题和答案