广工编译基础原理(精彩编辑题集必考大题.doc

《广工编译基础原理(精彩编辑题集必考大题.doc》由会员分享，可在线阅读，更多相关《广工编译基础原理(精彩编辑题集必考大题.doc（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.编译原理期末试题（二）1、 描述由正规式b*(abb*)*(a| e)定义的语言，并画出接受该语言的最简DFA。2、证明文法E E + id | id是SLR(1)文法。3、下面是表达式和赋值语句的文法，其中and的类型是bool bool bool，+的类型是int int int，=的类型是int int bool，:= 要求id 和E的类型都是int或者都是bool。为该文法写一个语法制导定义或翻译方案，它完成类型检查。S id := EE E and E | E + E | E = E |id6、 描述由正规式b*a(bb*a) *b*定义的语言，并画出接受该语言的最简DFA。7、下

2、面的文法产生代表正二进制数的0和1的串集：B B 0 | B 1 | 1下面的翻译方案计算这种正二进制数的十进制值：B B1 0B.val := B1.val 2 | B1 1B.val := B1.val 2 +1| 1 B.val := 1 请消除该基础文法的左递归，再重写一个翻译方案，它仍然计算这种正二进制数的十进制值。编译原理试卷二答案start1abb21、由正规式b*(abb*)*(a| e)定义的语言是字母表a, b上不含子串aa的所有串的集合。最简DFA如下：2、先给出接受该文法活前缀的DFA如下：E EE E + idE idI0E EE E+ idI1E idI2Eid+E

3、 E +idI3E E + idI4idI0和I3都只有移进项目，肯定不会引起冲突；I2和I4都无移进项目并仅含一个归约项目，也肯定不会引起冲突；在I1中，E的后继符号只有$，同第2个项目的展望符号“+”不一样，因此I1也肯定不会引起冲突。由此可以断定该文法是SLR(1)的。3、语法制导定义如下。S id := E S.type := if (id.type = bool and E.type = bool) or (id.type = int and E.type = int)then type_ok else type_error E E1 and E2 E.type := if E1.t

4、ype = bool and E2.type = bool then bool else type_error E E1 + E2 E.type := if E1.type = int and E2.type = int then int else type_error E E1 = E2 E.type := if E1.type = int and E2.type = int then bool else type_error E id E.type := lookup(id.entry) 6、正规式b*a(bb*a) *b*体现的特点是，每个a的左边都有若干b，除非a是第一个字母。该正规式

5、定义的语言是：至少含一个a，但不含子串aa的所有a和b的串集。最简DFA如下：start2abb10ab7、消除左递归后的文法：B 1 BB 0 B | 1 B | e相应的翻译方案如下：B 1 B.i := 1 BB.val := B.valB 0 B1.i := B.i 2 B1 B.val := B1.val| 1 B1.i := B.i 2 +1 B1 B.val := B1.val| e B.val := B.i编译原理期末试题（三）1、 从优化的范围的角度，优化可以分哪两类？对循环的优化可以有哪三种？ 答：从优化的范围的角度，优化可以分为局部优化和全局优化两类；对循环的优化有三种：

6、循环不变表达式外提、归纳变量删除与计算强度削减。2、写出表达式a=b*c+b*d对应的逆波兰式、四元式序列和三元式序列。 答：逆波兰式： abc*bd*+:= 四元式序列：三元式序列: OP ARG1 ARG2(1) (*， b， c， t1) (1) (* b， c )(2) (*， b， d， t2) (2) (* b， d )(3) (+， t1， t2，t3) (3) (+ (1)， (2)(4) (:=， t3， /， a)(4) (:= (3)， a)3、对于文法G(S): SbM(TMabL)答：1） 2） 短语: Ma)， (Ma)， b(Ma)b直接短语: Ma) 句柄: M

7、a)三、 设有字母表a，b上的正规式R=(ab|a)*。 解：（1）0123baa-+（2）将（1）所得的非确定有限自动机确定化ab-01131221+3ab-+013123+12312313+13123012aaba-+（3）对（2）得到的DFA化简，合并状态0和2 为状态2：12aab-+（4）令状态1和2分别对应非终结符B和AG: AaB|a|； BaB|bA|a|b|；可化简为：G: AaB|；BaB|bA|四、 设将文法G改写成等价的LL(1)文法，并构造预测分析表。 G：SS*aT|aT|*aT； T+aT|+a 解：消除左递归后的文法G: SaTS|*aTSS*aTS|T+aT|

8、+a 提取左公因子得文法G:SaTS|*aTSS*aTS|T+aTTT| Select(SaTS)=aSelect(S*aTS)=*Select(SaTS)Select(S*aTS)=Select(S*aTS)=*Select(S)=Follow(s)=#Select(S*aTS)Select(S)= Select(T+aT)=+Select(TT)=First(T) =+Select(T )=Follow(T)=*,#Select(TT)Select(T)= 所以该文法是LL(1)文法。预测分析表： *+a#S*aTSaTSS*aTST+aTT T 6设文法G 为： SA；ABA|；BaB|

9、b解：（1）拓广文法G：(0) SS (1) SA (2) ABA(3) A(4) BaB (5) Bb ； FIRST(A) = , a, b；FIRST(B) = a, b构造的DFA 如下:项目集规范族看出，不存在冲突动作。该文法是LR(1)文法。（2） LR(1)分析表如下： (3)输入串abab 的分析过程为：五、 给定文法GS： SaA|bQ； AaA|bB|b；BbD|aQ ；QaQ|bD|b；DbB|aA ；EaB|bF FbD|aE|b构造相应的最小的DFA 。 解：先构造其NFA： 用子集法将NFA确定化： abSAQAABZQQDZBZQDDZABDABBQD 将S、A、

10、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。因为3、4中含有z，所以它们为终态。ab012113224325416516625 令P0（0,1,2,5,6,3,4）用b进行分割： P1（0,5, 6,1,2,3,4）再用b进行分割： P2（0,5, 6,1,2,3,4）再用a、b 进行分割，仍不变。 再令为A，1，2为B，3，4为C，5，6为D。 最小化为右上图。编译原理期末试题（四）一、 简述编译程序的工作过程。（10）词法分析语法分析语义分析代码优化目标代码生成三、给出下面语言的相应文法：（15）L1=an bn | n1 L2=anbm+nam | n1，m0

11、G1： SAB AaAb | ab BbBa | G1： AaAb |ab 四、对下面的文法G： Sa | b | （T）TT，S | S(1) 消去文法的左递归，得到等价的文法G2；(2) 判断文法G2是否LL（1）文法，如果是，给出其预测分析表。（15）G2： Sa | b | （T） T ST T，S T | G2是LL（1）文法。ab（），#SSa Sb S（T）TT STT STT STTT T，S T 五、设有文法GA：ABCc | gDBBbCDE |CDaB | caDdD |EgAf | c(1) 计算该文法的每一个非终结符的FIRST集和FOLLOW集；(2) 试判断该文法

12、是否为LL（1）文法。（15）FIRSTFOLLOWABCDEA,b,c,d,gbA,c,dDC,gA,c,dC,d,gA,b,c,g是LL（1）文法。七、有定义二进制整数的文法如下：L LB | BB 0 | 1构造一个翻译模式，计算该二进制数的值（十进制的值）。（15）引入L、B的综合属性val，翻译模式为： S L print(L.val)L L1B L.val= L1.val*2+B.valL B L.val= B.valB 0 B.val=0B 1 B.val=1编译原理期末试题（五）三 有穷自动机M接受字母表S0,1上所有满足下述条件的串：每个1都有0直接跟在右边。构造一个最小的D

13、FA M及和M等价的正规式。【】【】四 证明正规式(ab)*a 与正规式a(ba)*等价 （用构造他们的最小的DFA方法）。【答案：】 五 写一个文法，使其语言是：L 1n0m1m0n | m,n0 【】【】五 文法G：S 1S0 | AA 0A1 | 六 对文法GS S aSb | PP bPc | bQcQ Qa | a(1) 它是否是算符优先文法？请构造算符优先关系表(2) 文法GS消除左递归、提取左公因子后是否是LL（1）文法？请证实。【】【】1.求出GS的FIRSTVT集和LASTVT集：FIERSTVT（S）=a,b LASTBVT（S）=b,c FIERSTVT(P)=b LAS

14、TBVT（P）=c FIERSTVT(Q)=a LASTBVT（Q）=a构造优先关系表为： a b c a b c 由于在优先关系中同时出现了aa以及bb，所以该文法不是算符优先文法。2. 消除左递归和提取左公因子后的文法为：S aSb | PP bPP Pc |QcQ aQQ aQ|求具有相同左部的两个产生式的Select集的交集：Select(SaSb)Select(SP) = aFirst(P) = ab = Select(PPc)Select(PQc) = First(P)First(Q)=ba= Select(QaQ)Select(Q) = aFollow(Q) = ac = 所以修

15、改后的文法是LL（1）文法。七 已知文法G为:（0） S S（1） S aAd（2） S bAc（3） S aec（4） S bed（5） A e 试构造它的LR（1）项目集、可归前缀图和LR（1）分析表。【】【答案：】ecAdI0:S S , # S aAd , # S bAc , # S aec , #S bed , #I2： Sa Ad , #Sa ec , # A e , d aI1：SS , #SI3: Sb Ac , # Sb ed , # A e , cbI6: SbAc,# AI7：Sbe d , #Ae , cI11：Sbed , #dI10：SbAc , # I4：SaA

16、d , #I5：Sae c , # Ae , deI8：SaAd , #I9：Saec , #c构造LR(1)分析表 如下： r4 11S10 6r2 10 r3 9 r1 8S11r5 7r5S9 5S8 4 6S7 3 4S5 2acc 1A#S3bedc1S gotoaS2 action 0状态八 已知源程序如下： prod:=0; i:=1; while i20 do beginprod:=prod+ai*bi;i:=i+1 end;试按语法制导翻译法将源程序翻译成四元式序列（设A是数组a的起始地址，B是数组b的起始地址；机器按字节编址，每个数组元素占四个字节）。【答案：】十一 对PL

17、/0语言的while语句 while 条件B DO 语句S 的编译程序，请在空缺处填空，完成该语句的编译算法：switch (SYM) case WHILESYM: CX1=CX ;GetSym(); CONDITION(SymSetAdd(DOSYM,FSYS),LEV,TX); CX2=CX ;GEN(JPC,0,0);if (SYM=DOSYM) GetSym() ;else Error(18);STATEMENT(FSYS,LEV,TX);GEN(JMP,0,CX1); CODECX2.A=CX ；break;编译原理期末试题（六）一、 回答下列问题：(30分)1什么是S-属性文法？什

18、么是L-属性文法？它们之间有什么关系？解答：S-属性文法是只含有综合属性的属性文法。 （2分）S-属性文法是L-属性文法的特例。 （2分）3划分程序的基本块时，确定基本块的入口语句的条件是什么？解答：（1）程序第一个语句，或（2）能由条件转移语句或无条件转移语句转移到的语句，或（3）紧跟在条件转移语句后面的语句。4(6分)运行时的DISPLAY表的内容是什么？它的作用是什么？答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层

19、、直接外层、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。二、设S=0，1上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。(8分)答：构造相应的正规式：(0|1)*1(0|1) (3分)NFA: (2分) 1 110432 e e e e 1 0 0确定化：(3分)I0,1,21,21,2,31,21,21,2,31,2,31,2,41,2,3,41,2,41,21,2,31,2,3,41,2,41,2,3,4 0 143210 0 1 0 0 0 1 1 1三、写一个文法

20、使其语言为L(G)= anbmambn | m,n1。(6分)答：文法G(S):S aSb | BB bBa | ba四、对于文法G(E): (8分)ET|E+TTF|T*FF(E)|iETF(E)E+TFiTT*F1. 写出句型(T*F+i)的最右推导并画出语法树。2. 写出上述句型的短语，直接短语、句柄和素短语。答：1. (4分)ETF(E) (E+T) (E+F) (E+i) (T+i) (T*F+i) 2. (4分)短语：(T*F+i), T*F+i, T*F, i直接短语：T*F, i句柄：T*F素短语：T*F, i六、设某语言的do-while语句的语法形式为 (9分) S do

21、S(1) While E其语义解释为：真假S(1)的代码E的代码针对自下而上的语法分析器，按如下要求构造该语句的翻译模式：(1) 写出适合语法制导翻译的产生式；(2) 写出每个产生式对应的语义动作。答：(1). 适合语法制导翻译的文法(3分) G(S): R do UR S(1) While SU E (2). (6分) R do R.QUAD:=NXQ UR S(1) While U.QUAD:=R.QUAD; BACKPATCH(S.CHAIN, NXQ) SU E BACKPATCH(E.TC, U.QUAD); S.CHAIN:=E.FC 答案二：(1) S do M1 S(1) Wh

22、ile M2 E M (3分)(2) M M.QUAD := NXQ (6分)S do M1 S(1) While M2 EBACKPATCH(S(1).CHAIN, M2.QUAD);BACKPATCH(E.TC, M1.QUAD); S.CHAIN:=E. FC七、(8分)将语句if (A0) then while C0 do C:=C+D翻译成四元式。(8分)答：100 (j， B， 0， 104)103 (j， -， -， 109)104 (j， C， 0， 106)105 (j， -， -， 109)106 (+， C， D， T1)107 (:=， T1， -， C)108 (j，

23、 -， -， 104)109 (控制结构3分，其他5分)八、(10分) 设有基本块如下：T1:=S+RT2:= 3T3:= 12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6(1)画出DAG图；(2)设A,B是出基本块后的活跃变量，请给出优化后的四元式序列。T1,T5, B3T24SR+/*_T3T4AT6,Bn4n5n1n2n3n6n8n7答：(1) DAG如右图：(6分)(2) 四元式序列：(4分)T1:=S+RT4:=S/RA:=T1-T4B:=T1*4九、(9分) 设已构造出文法G(S)：(1) S BB(2) B aB(3) B b的LR分析

24、表如下ACTIONGOTO状态ab#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。答：步骤状态符号输入串00#abab#103#abab#2034#abab#3038#aBab#402#Bab#5026#Bab#60267#Bab#70269#BaB#8025#BB#901#S#acc编译原理期末试题（八）1（10分）处于/* 和 */之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。2为语言L ambn | 0 m 2n（即a的

25、个数不超过b的个数的两倍）写一个LR（1）文法，不准超过6个产生式。（若超过6个产生式，不给分。若所写文法不是LR（1）文法，最多给5分。）3（10分）构造下面文法的LL（1）分析表。D TLT int | realL id RR , id R | e4（15分）就下面文法S ( L) | aL L , S | S 给出一个语法制导定义，它输出配对括号的个数。 给出一个翻译方案，它输出每个a的嵌套深度。如句子(a, (a, a) )，第一小题的输出是2，第二小题的输出是1 2 2。参考答案1124start52othersothers/*/2LR（1）文法LR（1）文法二义文法S AB | a

26、ABbS ABS AASb | eA aaAb | eA aaAb | ab | eA a | eB Bb | eB Bb | e3int realid,$DDTLDTLTTintTrealLLid RRR , id RR e4S S print(S.num)S (L)S.num := L.num +1S aS.num := 0L L1,SL.num := L1.num + S.num L SL.num := S.numS S.depth := 0 SS L.depth := S.depth +1 (L)S a print(S.depth)L L1.depth := L.depth L1, S

27、.depth := L.depth SL S.depth := L.depth S5t1 := initialt2 := finalif t1 t2 goto L1v := t1 L2:stmtif v = t2 goto L1v := v + 1goto L2 L1: 编译原理期末大题1. 设有如下文法G（S），试消除其左递归。G（S）：SAc|c ABb|b BSa|a解：SabcS|bcS|cS, SabcS|2. 试构造与下面G（S）等价的无左递归的文法。G（S）：SSa|Nb|c NSd|Ne|f解：SfNbS|cS, SaS|dNbS|, NeN|3. 设有文法G（S）：SaBc|

28、bABAaAb|bBb| 求各产生式的FIRST集，FOLLOW(A)和FOLLOW(B),以及各产生式的SELECT集。 构造LL(1)分析表，并分析符号串baabbb是否是。解：（1）FIRST(aBc)=a, FIRST(bAB)=b FIRST(aAb)=a, Ab: FIRST(Ab)=b, Bb: FIRST(b) = b, FIRST()= FOLLOW(A)=b, #, FOOLOW(B)=c, #SELECT(SaBc)=a, SELECT(SbAB) =b, SELECT(AaAb)=a, SELECT(Ab)=b, SELECT(Bb)=b, SELECT(B)=c, #

29、因此，所得的LL(1)分析表如表A-4所示。表A-4 LL(1)分析表输入VN输入符号abc#SSaBcSbABAAaAbAbBBbBB（2）分析符号串baabbb成功，baabbb是该文法的句子，如图A-16所示。图A-16 识别串baabbb的过程5.已知文法G(S)：Sa|(T)TT,S|S给出句子(a,a),a)的最左推导并画出语法树；给出句型(T,a,(T)所有的短语、直接短语、素短语、最左素短语、句柄和活前缀。解：（1）最左推导：S(T)(T,S)(S,S) (a,S)(a,(T)(a,(T,S)(a,(S,S)(a,(a, S)(a,(a,a)语法树：如图A-16所示。图A-16

30、 (a,(a,a)的语法树（2）句型(T, a, (T)的短语、直接短语、素短语、最左素短语、句柄、活前缀及语法树（图A-17）。短语：a | T,a | (T) | T , a , (T) | (T , a , (T)直接短语：a | (T)素短语：a | (T)最左素短语：a句柄：a活前缀： | ( | (T | (T , | (T , a 图A-17 (T,a,(T)的语法树4. 设文法（）为：求（）项目集族；构造识别文法（）的；构造文法（）的SLR（）的分析表；分析句子的识别过程。解：（1）、（2）LR(0)项目集族和识别活前缀的DFA，如图A-19所示。图A-19 LR(0) 项目集

31、族和DFA二、构造下列正则表达式的确定性的有限状态自动机。 （12%）aba(a|b)*a答： 三、证明下面文法是SLR(1)文法，并构造其SLR分析表。 （15%） + | | * | a | b答：分析表如下所示：状 态 T项 目 集输入符号下一状态0*1+12 2 3* 3a a4b b51*Accept*+62*/+#2*7* 7a a4b b53* /+/a/b#4* *84*a #65*b #76*+9 9 3* 3a a4b b57* /+/a/b#3* *88* #59*+/+#1* 7* 7a a4b b5四、写出下列表达式的三地址形式的中间表示。 （16%）（1） 5+6 (a + b);（2） A( B (C D);（3） for j:=1 to 10 do aj + j:=0;（4） if x y then x:=10 else x:= x + y;答： 100:t1:=a+b101:t2:=6*t1102:t3:=5+t2 100:if A goto 102101:goto T102:if B goto 104103:goto F 104:if C goto T105: