《2022年武汉大学编译原理试卷借鉴 .pdf》由会员分享，可在线阅读，更多相关《2022年武汉大学编译原理试卷借鉴 .pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、武汉大学20042005 学年度第二 学期 编译原理 试卷（A）学号 _ 姓名 _ 院（系）_ 分数 _ 注意：请将答案全部写在答题纸上，并请写明题目的序号。一、(10 分)对于文法GS：S 1A|0B|A 0S|1AA B 1S|0BB (3 分)请写出三个关于GS 的句子；(4 分)符号串11A0S 是否为G S 的句型？试证明你的结论。(3 分)试画出001B 关于 G S 的语法树。二、(10 分)请构造一个文法，使其产生这样的表达式E：表达式中只含有双目运算符+、*，且+的优先级高于*，+采用右结合，*采用左结合，运算对象只有标识符i，可以用括号改变运算符优先级。要求给出该文法的形式
2、化描述。三、(20 分)设有语言L=|0,1+，且 不以 0 开头，但以00 结尾。(5 分)试写出描述L 的正规表达式；(15 分)构造识别L 的 DFA（要求给出详细过程，并画出构造过程中的NDFA、DFA 的状态转换图，以及DFA 的形式化描述)。四、(25 分)给定文法GS：S AB A aB|bS|c B AS|d (6 分)请给出每一个产生式右部的First 集；(3 分)请给出每一个非终结符号的Follow 集；(8 分)请构造该文法的LL(1)分析表；(8 分)什么是LL(1)文法？该文法是LL(1)文法吗？为什么？五、(20 分)给定文法GS：S SaA|a A AbS|b
3、(8 分)请构造该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA。(4 分)请构造该文法的LR(0)分析表。(4 分)什么是LR(0)文法？该文法是LR(0)文法吗？为什么？(4 分)什么是SLR(1)文法？该文法是SLR(1)文法吗？为什么？六、(10)给定下列语句：if a+bc then x:=a*(b-c)+(b*c-d)/e (5 分)写出其等价的逆波兰表示；(5 分)写出其等价的四元式序列。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 5 页 -七、(5 分)已知下列C 语言程序：int*f()int a=100;return&a;main()int*i
4、=f();char a=“compiler”;printf(“the result is%dn”,*i);程序运行结果为：the result is 26157,请解释为什么程序运行的结果不是期望的“the result is 100”？第一题1.1 三个 0 和 1 数量相等的串1.2 S=1A=11AA=11A 0S 1.3 第二题构造文法如下:GE=(+,*,(,),i,E,F,T,P,E)，其中 P 为：EE*F|F FT+F|T T(E)|i第三题（1）正规表达式：1(0|1)*00（2）第一步：将正规表达式转换为NDFA 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共
5、 5 页 -第二步：将NDFA 确定化为DFA：造表法确定化（3 分）确定化后DFA M 的状态转换表(2 分)状态 输入I 0 I 1 t 0 1 S A,D,B q 0 q 1 A,D,B D,B,C D,B 重新命名q 1 q 2 q 3 D,B,C D,B,C,Z D,B q 2 q 4 q 3 D,B D,B,C D,B q 3 q 2 q 3 D,B,C,Z D,B,C,Z D,B q 4 q 4 q 3 DFA 的状态转换图（3 分）第三步：给出DFA 的形式化描述DFA M=（q 0,q 1,q 2,q 3,q 4,0,1,t,q 0,q 4 ）t 的定义见M 的状态转换表。第
6、四题（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 分）V N V T a b c d#S S?AB S?AB S?AB 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 5 页 -A A?aB A?bS A?C B B?AS B?AS B?AS B?d（4）对于文法G 的每一个非终结符U 的产生式U?1|2|n，如果 SEL
7、ECT(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 分GS :S S S SaA S a A AbS A b 该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA：该文法的LR(0)分析表：状态ACTION GOTO a b#S A 0 S 2 1 1 S 3 acc 2 r 3 r 3 r 3 3 S 5 4 4 r 2 r 2/S 6 r 2 5 r
8、5 r 5 r 5 6 S 2 7 7 r 4/S 3 r 4 r 4 LR(0)文法：该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA 中没有冲突状态。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 5 页 -该文法不是LR(0)文法因为存在冲突状态：I 4 和 I 7 SLR(1)文法：该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA 中有冲突状态，冲突可用 FOLLOW 集解决。该文法不是SLR(1)文法。因为 FOLLOW(S)=a,b,#，所以无法解决冲突第六题（1）(1)ab+c(23)jumpf(8)xabc-*bc*d-e/+:=(23).（2）第七题C 语言采用栈式存储分配方法作为其运行环境；f()返回的是指向其活动记录某一位置的指针；f()返回后，其活动记录被释放，并且，其对应的存储空间被数组a 占用，再次引用该指针时，其结果由于对回收的活动记录所占用的内存空间的再分配，其所指的值发生了改变。释放在前，引用在后的现象称:Dangling Reference。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 5 页 -