2022年陕师大编译原理考试题 .pdf

《2022年陕师大编译原理考试题 .pdf》由会员分享，可在线阅读，更多相关《2022年陕师大编译原理考试题 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 编译原理试题及答案一、对于文法GS ：S 1A | 0B | A 0S | 1AA B 1S | 0BB (3 分 ) 请写出三个关于GS 的句子； (4 分 ) 符号串11A0S 是否为G S 的句型？试证明你的结论。 (3 分 ) 试画出001B 关于 G S 的语法树。二、请构造一个文法，使其产生这样的表达式E ：表达式中只含有双目运算符+ 、 * ，且 + 的优先级高于* ， + 采用右结合，* 采用左结合，运算对象只有标识符i ，可以用括号改变运算符优先级。要求给出该文法的形式化描述。三、设有语言L= | 0,1 + ，且不以0 开头，但以00 结尾 。试写出描述L 的正规表达式

2、；构造识别L 的 DFA （要求给出详细过程，并画出构造过程中的NDFA 、 DFA 的状态转换图，以及DFA 的形式化描述) 。四、给定文法GS ：S AB A aB | bS | c B AS | d (6 分 ) 请给出每一个产生式右部的First 集； (3 分 ) 请给出每一个非终结符号的Follow 集； (8 分 ) 请构造该文法的LL(1) 分析表； (8 分 ) 什么是LL(1) 文法？该文法是LL(1) 文法吗？为什么？五、给定文法GS ：S SaA|a A AbS|b 请构造该文法的以LR(0) 项目集为状态的识别规范句型活前缀的DFA 。请构造该文法的LR(0) 分析表

3、。什么是LR(0) 文法？该文法是LR(0) 文法吗？为什么？什么是SLR(1) 文法？该文法是SLR(1) 文法吗？为什么？六、给定下列语句：if a+bc then x := a*(b-c) + (b*c-d)/e 写出其等价的逆波兰表示；写出其等价的四元式序列。七、已知下列C 语言程序：int * f() int a = 100; return &a; main() int * i = f(); char a = “compiler”; printf( “the result is %dn”, *i); 程序运行结果为：the result is 26157, 请解释为什么程序运行的结果

4、不是期望的“the result is 100 ”？名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 2 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 ）第一步：将正规表达式转换为ND

5、FA 第二步：将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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页

6、 - - - - - - - - - 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 的状态转换表。第四题（ 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

7、, b, c, d （ 3 ） LL(1) 分析表（8 分）V N V T a b c d # S S ? AB S ? AB S ? AB A A ? aB A ? bS A ? C B B ? AS B ? AS B ? AS B ? d （ 4 ）对于文法G 的每一个非终结符U 的产生式U ? 1 | 2 | | n ，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - 4 如果 SELECT(U ? i ) ? SELECT

8、(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

9、 S 5 4 4 r 2 r 2 /S 6 r 2 5 r 5 r 5 r 5 6 S 2 7 7 r 4 /S 3 r 4 r 4 LR(0) 文法：该文法的以LR(0) 项目集为状态的识别规范句型活前缀的DFA 中没有冲突状态。该文法不是LR(0) 文法因为存在冲突状态：I 4 和 I 7 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 5 SLR(1) 文法：该文法的以LR(0) 项目集为状态的识别规范句型活前缀的DFA

10、中有冲突状态，冲突可用 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 页 - - - - - - - - -