《编译原理陈志刚编译原理试卷》由会员分享，可在线阅读，更多相关《编译原理陈志刚编译原理试卷（9页珍藏版）》请在金锄头文库上搜索。
1、编译原理编译原理软件工程软件工程 20052005 级期终考卷级期终考卷学号：学号：姓名：姓名： 说明说明:1.本考卷中大写字母本考卷中大写字母VN ，其他符号，其他符号VT； 2、试卷中一、二两题请作在考卷上、试卷中一、二两题请作在考卷上一、一、 概念题（概念题（15 分）分）1、编译过程一般分为几个阶段？各阶段的输入输出分别为什么？、编译过程一般分为几个阶段？各阶段的输入输出分别为什么？ 2、对下列状态转换图，写出状态、对下列状态转换图，写出状态 0 的处理过程：的处理过程：012字母其他数字其中：状态其中：状态 2 的过程为的过程为 proc2.3、文法、文法 G 为：为：SaABAaB
2、 |则判断则判断 G 为为 LL（1）文法的条件是：）文法的条件是： 二、判断题（二、判断题（10 分。注：每答对一题得分。注：每答对一题得+2 分；答错一题得分；答错一题得-2 分；不答者得分；不答者得 0 分）分） 1、设、设为为a，b，则，则 a，ba， 都是都是上的正规式。上的正规式。（ ）2 2、对于上下文无关文法、对于上下文无关文法 GSGS，若，若 S SAB 则则 A A一定是一条产生式规则，一定是一条产生式规则，其中其中 ,（VTVN）* *（ ）3、对于逆波兰后缀式，无论从哪头开始分析均可得到唯一正确的分解。、对于逆波兰后缀式，无论从哪头开始分析均可得到唯一正确的分解。 （
3、 ） 4、LRLR（0 0）分析法是一种规范归约法。）分析法是一种规范归约法。 （ ）5、算符优先分析法只能用来分析算符优先文法。、算符优先分析法只能用来分析算符优先文法。 （ ）三、三、 （1010 分）设文法分）设文法 G3 为：为：SAaBcAAa|aBb求句型求句型 AaBc 的最左素语。的最左素语。字母四、四、 （2020 分）设文法分）设文法 GSGS为为 S SaAcBaAcB 问：问：1 1、该文法是否为算符文法，为什么？、该文法是否为算符文法，为什么？A AAb|bAb|b 2 2、构造算符优先关系表。、构造算符优先关系表。B Bd d 3 3、该文法是否可改造为、该文法是否
4、可改造为 LLLL（1 1）文法，为什么？）文法，为什么？五、五、 （本题（本题 2020 分）设文法分）设文法 G G 为：为： E EeAf|eBgeAf|eBgA AaA|aaA|aB BBb|aBb|a 对于输入串对于输入串 eaaafeaaaf，采用，采用 LRLR（0 0） 、LLLL（1 1） 、SLRSLR（1 1）等方法中合适的一种进行分析。）等方法中合适的一种进行分析。六、六、 （2525 分）有作控制用的布尔表达式文法分）有作控制用的布尔表达式文法 GEGE及其语义动作如下：及其语义动作如下： 1 1、 构造构造 SLRSLR（1 1）分析表（若不是）分析表（若不是 SL
5、R(1)SLR(1)）的，则说明理由）的，则说明理由） 2、 分析布尔式分析布尔式 abbc#，则最左素短语为 AaBc。四、 （20 分）1、该文法是算符文法。因为其任一产生式的右部都不含相继（并列）的非终结符，即不含如下形式QR的产生式右部。 （4分）2、FIRST(S)=a, LAST(S)=c,FIRST(A)=b, LAST(A)=b,FIRST(B)=d, LAST(B)=d。 （3分）构造算符优先关系表如下： （5分）abcd#abc#=3、该文法可以改造为 LL（1）文法。 （8 分）原因： 消除左递归：SaAcBAbAAbA|Bd； FIRST(A)=a, FOLLOW(A)
6、=c,FIRST(A)=b, , FOLLOW(A)=c,FIRST(B)=d, FOLLOW(B)=#,FIRST(S)=a, FOLLOW(S)=#,对于每个非终结符的各个产生式的 FIRST 集两两不相交； 对于 A ，FIRST（A）FOLLOW（A）=。 综上所述，原文法可以改造成 LL（1）文法。五、 （20 分）原文法不是 LL（1）文法，故不能直接使用 LL（1）分析法进行分析。步骤如下：1、拓广文法：EE EeAfEeBg AaAAa BBbBa （2 分）2、项目集规范族：（6 分）E.E E.eAf E.eBgEE.Ee.Af A.aA A.a Ee.Bg B.Bb B.
7、aEeA.fAa.A Aa. A.aA A.a BB.bEeAf.AaA.Aa.A Aa. A.aA A.aEeBg.BBb.EeB.g BB.b0Ee123A4aB5f6A7a8g9b10Aa由此项目集规范族可判断，原文法非 LR（0）文法，故不能直接使用LR（0）分析法进行分析。因此，使用 SLR（1）分析法分析原文法。3、构造 SLR（1）分析表如下： FOLLOW(A)=f；FOLLOW(B)=b,g；FOLLOW(E)=#。ACTIONGOTO状态abefg#ABE0S211acc2S4353S64S8r7r5r775S10S96r27r48S8r579r310r6r6（6 分）4、
8、分析输入串 eaaaf 如下：步骤状态符号输入串动作10#eaaaf#预备202#eaaaf#移进3024#eaaaf#移进40248#eaaaf#移进502488#eaaaf#移进602487#eaaAf#归约70247#eaAf#归约8023#aAf#归约90236#aAf#移进1001#E#归约11acc接受（6 分）六、 （25 分）1、步骤：（1）拓广文法：EE Ei(1)i(2)EAE(1) ABBi （2 分）（2）项目集规范族：E.E E.i(1)i(2) E.AE(1) A.B B.iEE.Ei.(1)i(2) Bi.EA.E(1) E.i(1)i(2) E.AE(1) A.
9、B B.iEi(1).i(2)EAE.(1) Ei(1)i.(2)AB.AB.01E2 iA3B45A67EiB248i（6 分）（3）SLR（1）分析表如下：FOLLOW(E)=#；FOLLOW(A)=i；FOLLOW(B)= 。ACTIONGOTO状态i#EAB0S21341acc2S6r43S27344S55r36S87r28r1（6 分）2、分析输入串 abc 如下：步骤状态栈符号输入串动作四元式10#abc#预备202#ibc#移进304#Bbc#归约B.TC=1,B.FC=2; Gen(Jnz,a,_,0); Gen(J,_,_,3);4045#Bbc#移进503#Abc#归约A.
10、TC=B.TC=1; BackPatch(2,3);6032#Aic#移进70326#AiC#移进803268#Aii#移进9037#AE#归约E.TC=3,E.FC=4; Gen(J,b,c,0); Gen(J,_,_,0);1001#E#归约E.FC=4; E.TC=MERG(1,3);11acc接受（6 分）整理：真出口为 3；假出口为 4。 （2 分）3、四元式： 1、 （Jnz,a,_,5） 2、(J,_,_,3) 3、(J,b,c,5) 4、(J,_,_,8) 5、(*,m,n,T1) 6、(:=,T1,_,I) 7、(J,_,_,10) 8、(+,m,n,T2) 9、(:=,T2,_,I) 10、 （3 分）1、Gen(Jnz,a,_,0) 2、Gen(J,_,_,3) 3、Gen(J,b,c,1) 4、Gen(J,_,_,0)
