编译原理(第2版)陈意云+张昱编著课后答案【稻谷书店】

资源描述

《编译原理(第2版)陈意云+张昱编著课后答案【稻谷书店】》由会员分享，可在线阅读，更多相关《编译原理(第2版)陈意云+张昱编著课后答案【稻谷书店】（106页珍藏版）》请在金锄头文库上搜索。

1、编译原理习题2003.41专业课目录chap 1 基本知识chap 3 词法分析chap 4 语法分析chap 5 语法制导翻译chap 6 运行时刻环境chap 7 中间代码生成chap 8 代码生成2专业课第一章练习1.1 文法 S ( L ) | a L L , S | S(a) 指出文法的终结符号, 非终结符号, 开始符号.文法的四个组成部分: 终结符号 VT : 语言不可再分的基本符号非终结符号VN : 语法范畴(语法概念) 开始符号 S : 最终感兴趣的语法范畴产生式 P : 定义语法范畴的一种书写形式终结符号: ( , ) a 非终结符号: S L开始符号: S元语言符号:

2、表示“定义为” | 表示“或”3专业课(b) 给出句子的分析树分析树: (推导树) 表示一个句型的推导 (a, (a,a) S ( L ) L , S S ( L ) a S a4专业课(c) 给出句子的最左推导给出每次推导后得到的句型的短语, 直接短语最左推导 : 推导中任何一步都是对中的最左非终结 lm 符号进行替换的推导.短语是文法的句型(S * ) S * A且A + 则是关于A的句型的短语. 直接短语是文法的句型(S * ) S * A且A 则是关于A的句型的直接短语. 句柄: 一个句型的最左直接短语称为句柄.5专业课 S ( L ) ( L, S ) ( S, S ) (

3、 a, S ) ( a, ( L )短语 ( L ) L, S S a a ( L, S ) S,S a, S a, ( L ) ( S, S ) (a, S) ( a, ( L ) ( L )直接 ( L ) L, S S a a 短语 ( L ) ( a, ( L, S ) ( a, ( S, S) ( a, (a, S) ( a, (a, a)短语 a a a a a, ( L, S ) a, ( S, S) a, (a, S) a, (a, a) ( a, ( L, S ) ( a, ( S, S) ( a, (a, S) ( a, (a, a) L, S S a a (L, S) S

4、, S a, S a, a ( S, S) ( a, S) ( a, a)直接 a a a a短语 L, S S a a a 6专业课(d) 构造各个句子的最右推导. 最右推导(规范推导)(e) 这个文法产生的语言是什么? a (a) (a,a) (a,a),a) . a和数据元素为a的广义表全体7专业课1.2 考虑文法 S aSbS | bSaS |(a) 试说明此文法是二义性的.(定义1.5) 如果一文法的句子存在两棵分析树, 则该句子是二义性的 . 如果一文法包含二义性的句子,则这个文法是二义性的. 可以从句子abab有两个不同的最左推导来说明. S aSbS abS abaSbS ab

5、abS abab lm lm lm lm lm S aSbS abSaSbS abaSbS ababS abab lm lm lm lm lm 句子abab有两个不同的最左推导, 该句子是二义性的 . 所以此文法是二义性的.8专业课(b) 对于句子abab构造两个相应的最右推导. S aSbS aSb abSaSb abSab abab rm rm rm rm rm S aSbS aSbaSbS aSbaSb aSbab abab rm rm rm rm rm (c)对于句子abab构造两个相应的分析树. S S a S b S a S b S b S aS a S b S (d) 此文法产生

6、的语言是什么? 由相同个数的a和b组成的字符串.9专业课1.3 考虑文法 bexpr bexpr or bterm | bterm bterm bterm and bfactor | bfactor bfactor not bfactor | ( bfactor ) | true | false(a) 请指出此文法的终结符号, 非终结符号和开始符号. 终结符号: or, and, not, (, ), true, false 非终结符号: bexpr, bterm, bfactor 开始符号: bexpr10专业课(b) 试对于句子 not ( true or false) 构造一棵分析树.

7、bexpr bterm bfactor not bfactor ( bexpr ) bexpr or bterm bterm bfactor bfactor false true11专业课(c) 试说明此文法产生的语言是全体布尔表达式.12专业课练习:长度为n的字符串, 分别有多少个前缀, 后缀, 子串, 真前缀, 子序列 ?前缀: n+1后缀: n+1子串: 1+ n+(n-1)+.+1 = 1+n(n+1)/2真前缀: n子序列: 1+Cn1+Cn2+Cn3+.+Cnn = 2n13专业课 E E + T T * F i给出句型E+T*i的短语, 直接短语和句柄 E E + T F T *

8、 F 给出句型F+T*F的短语, 直接短语和句柄短语: i, T*i, E+T*i直接短语: i句柄: i短语: F, T*F, F+T*F直接短语: F, T*F句柄: F14专业课第三章练习3.3 试描述下列正规表达式所表示的语言:(a) 0 ( 0 | 1)* 0(b) ( ( | 0 ) 1* ) *由0和1组成且以0开始和结束的符号串全体.(c) ( 0 | 1 )* 0 ( 0 | 1) ( 0 | 1)由0和1组成的符号串全体.由0和1组成且以000,001,010或011结束的符号串全体.长度大于等于3且倒数第3个字符为0的01符号串全体.15专业课(d) 0*10*10*1

9、0*(e) ( 00 | 11)* ( ( 01 | 10 ) ( 00 | 11)* ( 01 | 10 ) ( 00 | 11)* )*有且只有3个1的0、1字符串全体.带有偶数个0和偶数个1的由0和1组成的符号串全体.带有偶数个a和偶数个b的符号串全体.( (aa|bb) | (ab|ba) (aa|bb)* (ab|ba) )*16专业课3.4 对于下列语言分别写出它们的正规表达式:(a) 英文字母组成的所有符号串, 要求符号串中顺序包含五个元音字母. 令letter=非元音的英文字母 letter* (a|A) letter* (e|E) letter* (i|I) letter*

10、 (o|O) letter* (u|U) letter* (b) 英文字母组成的所有符号串, 要求符号串中的字母依照字典序排列. ( a | A)* ( b | B)* ( c | C)*. ( z | Z)*17专业课 (c)没有重复出现的数字的数字符号串全体.(d) 最多有一个重复出现的数字的数字符号串全体令 ri = i | , i=0,1,2,.,9 R0|R1|R2|.|R9记为 Ri i(0,1,2.,9)P(0,1,2.,9)表示0,1,2.,9的全排列 ri0ri1.ri9 i0i1. i9P(0,1,2.,9) i ri0ri1.ri9i(0,1,2.,9) i0i1. i

11、9P(0,1,2.,9)18专业课(e) 带有偶数个0和奇数个1的由0和1组成的符号串全体. E为带有偶数个0和1的由0和1组成的符号串全体.即 ( 00 | 11)* ( ( 01 | 10 ) ( 00 | 11)* ( 01 | 10 ) ( 00 | 11)* )* E 1 E | E 0 E 1 E 0 E(f) 不包含子串011的由0和1组成的符号串全体. (g) 不包含子序列011的由0和1组成的符号串全体1*0*10* |1*( 0* | (10)* )*19专业课练习:1. 令A,B和C是任意正规式,证明以下关系成立: A|A=A (A*)*=A* A*=|AA* (AB)*

12、 A =A(BA)* (A|B)*=(A*B*)*=(A*|B*)* A=b|aA当且仅当A=a*b20专业课3.6 给出接受下列在字母表0，1上的DFA。（a）所有以00结束的符号串的集合；AstartB0C010NFA等价于A1startBC00011DFA(1|0)*0021专业课（b）所有具有三个0的符号串的集合。1*01*01*01*AstartB0C01DFA11B0122专业课3.7 构造等价于下列正规表达式的有限自动机.(a) 10|(0|11)0*100011AstartD1BEC1NFA 0 1A D BCD D EBC E DE / / 1010AstartBC0DEDF

13、A123专业课(b) (0|1)* |(11)*0|111AstartCBEDNFA 0 1ABDE ABDE ABCDEABCDE ABDE ABCDE11Astart0BDFA01Astart最小化DFA024专业课3.8 给定右线性文法G: S 0S | 1S | 1A | 0B A 1C | B 0C | 1 C 0C | 1C | 0 | 1 试求一个等价的左线性文法G. 000,11SstartB1ACf状态转移图100,10,1左线性文法G: f A1 | B0 | C1 | C0 A S1 B S0 C A1 | B0 | C1 | C0 S S0 | S1 | 图中状态C和f

14、可合并, 得到左线性文法G: C A1 | B0 | C1 | C0 A S1 B S0 S S0 | S1 | 25专业课3.9-3.11(d) (a|b)*abb(a|b)* 1start2a4ba3bbba由正规表达式构造NFA1start12a14b13bbaaba124a134bba由NFA得到DFAABCDEFB C D E F A B C D E ABaDbCbabaab最小化DFA26专业课3.13 对于下列正规表达式构造最小状态的DFA.(b) (a|b)*a(a|b)(a|b)a1start2a43babNFAbaAstartBabHGaCDaaaEFabaaabbbb最小

15、化DFA27专业课4.4 考虑文法 R R | R | RR | R* | (R) | a | b(a)试说明此文法生成在符号a和b之上的所有正规表达式.(b)试说明此文法是二义性的.(c)试构造一个等价的无二义性文法.(b) 句子a|aa的两种最左推导. 句子aa*的两种最左推导. RR Ra R * a R R * R R a a(c)消除二义性 R R | S | S S ST | T T U* | U U (R) | a | b28专业课4.5 dangling-else文法: stmt if expr then stmt | matched-stmt matched-stmt if

16、expr then matched-stmt else stmt | other 试说明此文法是二义性的。句子 if e1 then if e2 then s1 else if e3 then s2 else s3 if e1 then if e2 then s1 else if e3 then s2 else s3 S MSif E then MS else S e1 if E then MS else S MS e2 other if E then S other s1 e3 MS s3 other s2 Sif E then S e1 MSif E then MS else S e2 o

17、ther MS s1 if E then MS else S e3 other MS s2 other s329专业课4.3 对于下面的每一个语言设计一个文法。试问其中哪些语言是正规的？(a) 使得在每一个0后至少立即跟随一个1的由0和1组成的符号串的全体。(b) 具有相同数目的0和1的由0和1组成的符号串的全体。(c) 具有不同数目的0和1的由0和1组成的符号串的全体。S 1S | 01S | (1|01)*S 0S1S | 1S0S | 非正规语言S SAS S 0S1S | 1S0S | A B | C 非正规语言B 1B | 1C 0C | 0S A | BA 0 | 0A | A0

18、| 10A | 01A| A10 | A01| 1A0 | 0A1B 0 | 0B | B0 | 10B | 01B| B10 | B01| 1B0| 0B130专业课(d) 所有形如xy而xy的由0和1组成的符号串。S 0E | 1E | LBRE 00E | 01E | 10E | 11E | B I I1B | OO1B | IO1C | OI1CC IO1C | OI1C | I1 O OI1O1I IO1I1I I I1O1O OO1L I 1LLO 0LI1R R1O1R R0LR 所有形如xy而x=y的由0和1组成的符号串。S 0S0| 1S1| 31专业课4.5 (a) 给出一

21、bfactor) =not, (, true, false First(bexpr) = or, First(bterm) = and, Follow(bexpr) = $, ) Follow(bexpr) = $, ) Follow(bterm) = or, $, ) Follow(bterm) = or, $, ) Follow(bfactor) = or, and, $, )34专业课(1) bexpr bterm bexpr (2) bexpr or bterm bexpr (3) bexpr (4) bterm bfactor bterm(5) bterm and bfactor b

22、term (6) bterm (7) bfactor not bfactor(8) bfactor (bexpr) (9) bfactor true (10) bfactor falseFirst(bexpr) = First(bterm) = First(bfactor) =not, (, true, falseFirst(bexpr) = or, First(bterm) = and, Follow(bexpr) = $, )Follow(bexpr) = $, )Follow(bterm) = or, $, ) Follow(bterm) = or, $, )Follow(bfactor

23、) = or, and, $, ) or and not true false ( ) $bexpr (1) (1) (1) (1) synch synch bexpr (2) (3) (3) bterm synch (4) (4) (4) (4) synch synch bterm (6) (5) (6) (6)bfactor synch synch (7) (9) (10) (8) synch synch 35专业课4.11试说明没有一个左递归文法可以是LL(1)的。 (1) 直接左递归文法中存在产生式: A A1 | A2 |.| Am | 1 | 2 |.| n, 其中 1 2 . n

24、均不以A开头 First(Ai) First( j) = First( j) 若 j *, First(A i) Follow(A) = First( i) , 不是LL(1)文法. (2) 间接左递归文法中存在产生式集合: A B1 1 | 1 | 2 |.| n B1 B2 2 . Bm A First(B1 1) = First(A m . 1) First( j) First(B1 1) , j=1,.,n First( j) First(B1 1) , j=1,.,n 若 j *, First(B1 1) Follow(A) = First( m . 1) , 不是LL(1)文法.3

25、6专业课4.12试说明没有一个LL(1)文法可以是二义性的。若有一个LL(1)文法是二义性的, 则存在句子w 有两种不同的最左推导: S * A 1 * w S * A 2 * w 对于文法中的产生式 A 1 | 2 , 其中1 , 2 First(1) First(2) = First(w) 与LL(1)文法矛盾.37专业课4.15 文法 S (L) | a L L, S | S的算符优先关系由表4.20给出。建立与表相应的算符优先函数并用算符优先分析法分析句子(a, (a, a)及(a, (a,a), (a,a)。算符优先关系表 a ( ) , $a ( = ) , $ 算符优先函数 a

26、 ( ) , $f 2 0 2 2 0g 3 3 0 1 0句子(a, (a, a)的分析过程栈输入动作$ (a,(a,a)$ $( shift$( a,(a,a)$ (a shift $(a ,(a,a)$ a, reduce$(S ,(a,a)$ (, shift $(S, (a,a)$ ,( shift $(S,( a,a)$ (a shift $(S,(a ,a)$ a, reduce$(S,(S ,a)$ (, shift$(S,(S, a)$ ,a shift$(S,(S,a )$ a) reduce$(S,(S,S )$ ,) reduce$(S,(L )$ (=) shif

27、t$(S,(L) )$ ) reduce$(S,S )$ ,) reduce$(L )$ (=) shift$(L) $ )$ reduce$S $ accept 38专业课4.16 试为下列各文法建立算符优先关系表。(a) S a S b S | b S a S | a b $a = b = $ acc设G是一个运算符文法, R和S是G中任何两个终结符, 定义:(1) R=S当且仅当G中存在产生式 .RS. 或 .RS.(2) RS当且仅当G中存在产生式 .R., 其中 + S. 或 + S.(3) RS当且仅当G中存在产生式 . S., 其中 + .R 或 + .R最左终结符: S.或 S

28、., S是的最左终结符 ., 则的最左终结符是的最左终结符对于文法中 R.的产生式, R 的最左终结符.39专业课(b) bexpr bexpr or bterm | bterm bterm bterm and bfactor | bfactor bfactor not bfactor | (bexpr) | true | false or and not ( ) true false $or ( = true false $ acc 最左终结符最右终结符bexpr or, and, not, (, true, false or, and, not, ), true, falsebterm

29、and, not, (, true, false and, not, ), true, falsebfactor not, (, true, false not, ), true, false40专业课4.18 给出文法LR(0)项目集族及相应的识别活前缀的自动机的状态转移图. S S C cC S CC C d I0: S .S S .CC C . cC C .dI1: S S.I2: S C.C C .cC C .dI3: C c.C C .cC C .dI4: C d.I5: S CC.I6: C cC.I0I1SCI2cI3CI5dI4cdCI6cdstart41专业课4.19 利用图

30、4.31画出文法4.27的识别活前缀的自动机的状态转移图. (P.200)I0: S .S S .iSeS S .iS S .aI1: S S.I2: S i.Ses S i.S S .iSeS S .iS S .a0I3: S a.I4: S iS.eS S iS.I5: S iSe.S S .iSeS S .iS S .aI6: S iSeS.iI0I1SaI3iI2SI4istarteI5SI6aa42专业课4.21 考虑文法 S A S | b A S A | a(1) 构造文法的LR(0)项目集规范族及相应的DFA.(2) 如果把每一个LR(0)项目看成一个状态, 并从每个形如B.X

31、的状态出发画一条标记为X的弧到状态BX., 且从从每个形如B.A的状态出发画一条标记为的弧到所有形如A.的状态.这样就得到了一个NFA. 说明这个NFA和(1)的DFA是等价的.(3) 构造文法的SLR分析表.(4) 对于输入串bab, 给出SLR分析器的动作.(5) 构造文法的LR(1)分析表和LALR分析表.43专业课I0: S .S S .AS S .b A .SA A .aI1:(I0,S) S S. A S.A A .SA A .a S .AS S .bI2: (I0,A) (I2,A) (I6,A) S A.S S .AS S .b A .SA A .aI3: (I0,b) (I1

32、,b) (I2,b) (I5,b) (I6,b) (I7,b) S b.I4: (I0,a) (I1,a) (I2,a) (I5,a) (I6,a) (I7,a) A a.I5: (I1,S) (I5,S) (I7,S) A S.A A .SA A .a S .AS S .bI6: (I1,A) (I5,A) (I7,A) A SA. S A.S S .AS S .b A .SA A .aI7 : (I2,S) (I6,S) S AS. A S.A A .SA A .a S .AS S .b44专业课First(S) = First(S) = First(A) = b, aFollow(S)

33、= $Follow(S) = a, b, $Follow(A) = a, bSLR分析表STATE ACTION GOTO a b $ S A0 s4 s3 1 21 s4 s3 acc 5 62 s4 s3 7 2 3 r3 r3 r34 r5 r5 5 s4 s3 5 66 s4/r4 s3/r4 7 27 s4/r2 s3/r2 r2 5 6SLR分析表存在移入-归约冲突.为消除二义性，假设a的优先级高于b，则遇到a时移入，遇到b时归约。输入串bab, SLR分析器的动作:栈输入动作0 bab$ shift30b3 ab$ reduce S b0S1 ab$ shift40S1a4

34、b$ reduce A a0S1A6 b$ shift-reduce collision 输入串bab, SLR分析器的动作:栈输入动作0 bab$ shift30b3 ab$ reduce S b0S1 ab$ shift40S1a4 b$ reduce A a0S1A6 b$ reduce A SA0A2 b$ shift30A2b3 $ reduce S b0A2S7 $ reduce S AS0S1 $ accept45专业课LR(1)项目集规范族I0: S .S, $ S .AS, $/a/b S .b, $/a/b A .SA, a/b A .a, a/bI1:(I0,S) S

35、 S., $ A S.A, a/b A .SA, a/b A .a, a/b S .AS, a/b S .b, a/bI2: (I0,A) (I2,A) S A.S, $/a/b S .AS, $/a/b S .b, $/a/b A .SA, a/b A .a, a/bI3: (I0,b) (I2,b) S b., $/a/bI4: (I0,a) (I1,a) (I2,a) (I5,a) (I6,a) (I8,a) (I9,a) (I10,a) A a., a/bI5: (I1,S) (I5,S) (I8,S) (I10,S) A S.A, a/b A .SA, a/b A .a, a/b S

36、 .AS, a/b S .b, a/bI6: (I1,A) (I5,A) (I8,A) (I10,A) A SA., a/b S A.S, a/b S .AS, a/b S .b, a/b A .SA, a/b A .a, a/bI7 : (I1,b) (I5,b) (I6,b) (I8,b) (I9,b) (I10,b) S b., a/bI8 : (I2,S) S AS., $/a/b A S.A, a/b A .SA, a/b A .a, a/b S .AS, a/b S .b, a/bI9: (I6,A) (I9,A) S A.S, a/b S .AS, a/b S .b, a/b A

37、 .SA, a/b A .a, a/bI10: (I6,S) (I9,S) S AS., a/b A S.A, a/b A .SA, a/b A .a, a/b S .AS, a/b S .b, a/b46专业课STATE ACTION GOTO a b $ S A0 s4 s3 1 21 s4 s7 acc 5 62 s4 s3 8 2 3 r3 r3 r34 r5 r5 5 s4 s7 5 66 s4/r4 s7/r4 10 97 r3 r38 s4/r2 s7/r2 r2 5 69 s4 s7 10 910 s4/r2 s7/r2 5 6 LR(1)分析表该文法的LR(1)分析表中存在移

38、入-归约冲突，文法具有二义性。为消除二义性，假设a的优先级高于b，则遇到a时移入，遇到b时归约。s4r4r247专业课该文法不是LR(1)文法.具有二义性.对于句子abab,存在两颗不同的分析树.SASaASSA bbaSASaSAbbaAS48专业课4.22 构造文法 S a S S b | a S S S | c 的LR(0)项目集规范族及识别活前缀的自动机.I0: S .S S .aSSb S .aSSS S .cI1: S S.I2: S a.SSb S a.SSS S .aSSb S .aSSS S .cI3: S c.I4: S aS.Sb S aS.SS S .aSSb S .a

39、SSS S .cI5: S aSS.b S aSS.S S .aSSb S .aSSS S .cI6: S aSSb.I7: S aSSS.I0I1ScI3aI2SI4startSI5bI6acaaccSI749专业课4.25 证明下面文法是SLR(1)文法, 并构造其SLR分析表. E E + T (1) F F* (5) E T (2) F a (6) T T F (3) F b (7) T F (4)I0: E .E E .E+T E .T T .TF T .F F .F* F .a F .bI1: E E. E E.+TI2: E T. T T.F F .F* F .a F .bI3:

40、 T F. F F.*I4: F a.I5: F b.I6: E E+.T T .TF T .F F .F* F .a F .bI7: T TF. F F.*I8: F F*.I9: E E+T. T T.F F .F* F .a F .b action goto + * a b $ E T F0 s4 s5 1 2 31 s6 acc2 r2 s4 s5 r2 73 r4 s8 r4 r4 r4 4 r6 r6 r6 r6 r6 5 r7 r7 r7 r7 r7 6 s4 s5 9 37 r3 s8 r3 r3 r3 8 r5 r5 r5 r5 r5 9 r1 s4 s5 r1 7 Foll

41、ow(E) = +, $Follow(T) = +, $, a, bFollow(E) = +, $, *, a, b50专业课4.26 证明每一个LL(1)文法都是LR(1)文法.51专业课4.27 证明下面文法是LL(1)的但不是SLR(1)文法. S A a A b | B b B a A B First(AaAb)=aFirst(BbBa)=bFirst(AaAb) First(BbBa) = 文法是LL(1)的.构造SLR(1)项目集:I0: S .S S .AaAb S .BbBa A . B .Follow(A) = Follow(B) = a, b存在归约-归约冲突,该文法不是

42、SLR(1)文法.52专业课4.28 证明任何一个LR(1)文法都是无二义文法.53专业课4.29 证明任何SLR(1)文法都是LR(1)文法.假设文法G是SLR(1)文法, 则对于文法的状态i:对于A.X, XVT, , XFollow(B), i中没有项目B.对于A.和B ., Follow(A) Follow(B) = 构造G的LR(1)项目集, 若G是LR(1)文法, 则项目集i必须满足条件:(1)对于A.X, a, XVT, , XFollow(B), i中没有项目B., X. (显然成立)(2)没有A., a和B .,a的两个项目.由closure(I)的构造A.B,a, B.,

43、First(a)可得知, 项目A.的向前搜索符号Follow(A)对于一个项目集中的不同归约项目A2.搜索符A, B3.,搜索符A搜索符A 搜索符A = 不存在归约-归约冲突, 所以条件(2)成立.54专业课4.31 为下面的文法构造它的LR(1)项目集规范族,并判断它是否为LR(1)文法? 若是,构造它的分析表. S E S S S E (1) E E + T | T E E + T (2) E T (3) T ( E ) | a T ( E ) (4) T a (5)I0: S .S $ S .E $ E .E+T $/+ E .T $/+ T .(E) $/+ T .a $/+I1: S

44、 S. $ I2: S E. $ E E.+T $/+I3: E T. $/+I4: T (.E) $/+ E .E+T )/+ E .T )/+ T .(E) )/+ T .a )/+I5: T a. $/+I6: E E+.T $/+ T .(E) $/+ T .a $/+I7: T (E.) $/+ E E.+T )/+I8: E T. )/+I9: T (.E) )/+ E .E+T )/+ E .T )/+ T .(E) )/+ T .a )/+I10:T a. )/+I11:E E+T. $/+I12: T (E). $/+ I13:E E+.T )/+ T .(E) )/+ T

45、.a )/+I14: T (E.) )/+ E E.+T )/+I15: E E+T. )/+I16: T (E). )/+LR(1)项目集规范族:55专业课 action goto + ( ) a $ S E T0 s4 s5 1 2 31 acc2 s6 r13 r3 r3 4 s9 s10 7 85 r5 r56 s4 s5 117 s13 s12 8 r3 r39 s9 s5 14 8 10 r5 r511 r2 r2 12 r4 r413 s9 s10 1514s13 s16 15r2 r216r4 r4LR(1) 分析表:56专业课LALR(1)分析表: action goto +

46、 ( ) a $ S E T 0 s4 9 s5 10 1 2 3 8 1 acc 2 s6 13 r1 3 8 r3 r3 r3 4 9 s4 9 s5 10 7 14 3 8 5 10 r5 r5 r5 6 13 s4 9 s5 10 11 15 7 14 s6 13 s12 1611 15 r2 r2 r212 16 r4 r4 r4LALR(1)分析表不存在冲突, 所以该文法是LALR(1)文法.57专业课证明文法G: ad bd ae be c c是LR(1)文法, 但不是LALR(1)文法.58专业课5.1 对于输入的表达式(4*7+1)*2, 根据表5.1的语法制导定义建立一棵带

47、注释的分析树. L E.val=58 n T.val=58 T.val=29 * F.val=2 F.val=29 digit.lexval=2 ( E.val=29 ) E.val=28 + T.val=1 T.val=28 F.val=1T.val=4 * F.val=7 digit.lexval=1F.val=4 digit.lexval=7digit.lexval=4（lex表示是从词法分析来的）59专业课5.2 试根据 (a) 表5.3中的语法制导定义，和 (b) 图5.17的翻译模式来建立表达式(a)+(b)的分析树和语法树.(a) E T ( E nptr ) E + T T

48、( E ) ( E ) T nptr T nptr id ididentry to aidentry to a+60专业课(b) E T R ( E nptr ) T R ( E ) + T i R s T nptr R ( E ) id Tnptr R id identry to aidentry to a+61专业课5.4 E E+T | T T num.num | num(a) 给出一个语法制导定义以确定每个子表达式的类型. 5.7(b) 扩充(a)中的语法制导定义把表达式翻译成前缀形式, 并且决定类型.(a) E E1+T if ( E1.type=real or T.type=re

49、al ) then E.type=real else E.type=integer E T E.type = T.type; T num.num T.type = real; T num T.type = integer;62专业课(b) S E S.type = E.type; S.code = E.code; E E1+T if ( E1.t ype = real and T.type = integer ) then begin E.type = real; E.code = + | E1 .code | inttoreal(T.code) end else if ( E1.t ype

50、= integer and T.type = real ) then begin E.type = real; E.code = + | inttoreal(E1 .code) | T.code end else begin E.type = E1.t ype; E.code = + | E1 .code | T.code end E T E.type = T.type ; E.code = T.code T num.num T.type = real; T.code = (num.num).lexval T num T.type = integer; T.code = num.lexval6

51、3专业课 E T E.type = T.type ; E.code = T.code T num.num T.type = real; T.code = (num.num).lexval T num T.type = integer; T.code = num.lexval64专业课 S t c E t c E t c + T t c E t c + T t c num.num T t c num num 65专业课5.5 S L.L | L L L B | B B 0 | 1 (a) 试用各有关综合属性决定S.val.引入L的属性b记录2的L的位数次幂值S L1.L2 S.val = L1.

52、val +L2.val / L2.b;S L S.val = L.val;L L1 B L.val = L1.val *2 + B.val; L.b = L.b*2;L B L.val = B.val; L.b = 2;B 0 B.val = 0;B 1 B.val = 1;66专业课 S val L v . L b v L v B v L b v B v B v 0 L b v B v 1 1 B v 0 167专业课(b) 试用一个语法制导定义来决定S.val, 在这个定义中B仅有综合属性c,给出由B生成的位对于最后的数值的分担额.引入B的继承属性i, 综合属性cS L1.L2 L1.i

53、 = 20; L2 .i = 2-1; S.val = L1.val +L2.valS L L.i = 20; S.val = L.val;L L1 B if L.i = 20 then begin L1.i = L.i *2 ; B.i = L.i end else begin L1.i = L.i ; L.s = L1.s/2; B.i = L1.s end L.val = L1.val +B.c L B B.i = L.i ; L.s= L.i/2; L.val = B.cB 0 B.c = B.i*0B 1 B.c = B.i*168专业课 S val i L v . i L s vi

54、 L v i B c i L s v i B ci B c 0 i L s v i B c 1 1 i B c 0 169专业课5.6 重写例5.3中语法制导定义的基础文法, 使类型信息只需用综合属性来传递. D T LL L1 , id | idT intT real改写为:D L id addtype(id.entry, L.type)L L1 id, L.type = L1 .type; addtype(id.entry, L1.type)L T L.type = T.typeT int T.type = intT real T.type = real D L id L id ,T in

55、t70专业课5.7 试从5.4(a)和 (b)中的语法制导定义中消除左递归.(a) E T F F.it = T.t; E.t = F.t F +TF1 F1.t = F.it and T.t; F.t = F1 .t F F.t = F.it T num.num T.t = false; T num T.t = true; E tTt it F tnum + Tt it F t num.num 71专业课(b) E T F F.it = T.t; E.t = F.t; F.ic = T.c; E.c = F.c F +TF1 if F.it = real and T.t = integer

57、.num.lexval; T num T.t = integer; T.c = num.lexval; 72专业课 E t c T t c it icF t c num + T t c it icF t c num.num 73专业课5.9 假设说明是由下列文法产生的: D L id L , id L1 | : T T integer | real(a) 建立一个翻译模式, 把每一个标识符的类型加入到符号表中.(b)从(a)中的翻译模式构造一个与翻译程序. (a) D L id addtype(id.entry, L.type L , id L1 L.type= L1.type addtype

58、(id.entry, L.type L : T L.type= T.type T integer T.type= 0 T real T.type= 1 用整数0表示整型, 1表示实型.74专业课(b) procedure D; var Ltype:integer; begin match(id); Ltype:=L(); addtype(id.entry, Ltype) end; function L():integer; var Ltype:integer; begin if lookahead = , then begin match(,); match(id); Ltype:= L();

59、 end else if lookahead = : then begin match(:); Ltype:=T(); end; return Ltypeend;funtion T():integer;begin if lookahead = integer then begin match(integer); return 0 end else if lookahead = real then begin match(real); return 1 endend75专业课5.10 下面的文法是表5.7中基础文法的无二义形式. S L L LB | B B B sub F | F F L |

60、text(a) 用上面的文法修改表5.7中的语法制导定义. S L L.ps=10; S.ht = L.ht L L1B L1.ps = L.ps; B.ps = L.ps; L.ht = max(L1.ht,B.ht ) L B B.ps = L.ps; L.ht = B.ht B B1 sub F B1.ps = B.ps; F.ps = shrink(B.ps); B.ht = disp(B1.ht, F.ht) B F F.ps = B.ps; B.ht = F.ht F L L.ps = F.ps; F.ht = L.ht F text F.ht = text.h * F.ps 76

61、专业课(b) 把(a)中的语法制导定义转化为翻译模式. S L.ps=10 L S.ht = L.ht L L1.ps = L.ps L1 B.ps = L.ps B L.ht = max(L1.ht,B.ht ) L B.ps = L.ps B L.ht = B.ht B B1.ps = B.ps B1 sub F.ps = shrink(B.ps) F B.ht = disp(B1.ht, F.ht) B F.ps = B.ps F B.ht = F.ht F L.ps = F.ps L F.ht = L.ht F text F.ht = text.h * F.ps77专业课5.12 从5

62、.10(b)中消除左递归.L B.ps = L.ps B L.ps = L.ps; L.iht = B.ht L L.ht = L.ht L B.ps = L.ps B L1.ps = L.ps L1.iht = max(B.ht, L.iht L1 L.ht = L1.ht L L.ht = L.iht L L1 B | B 转化为: L B L L B L L ps L htps B ht ps iht L ht ps B ht ps iht L ht 78专业课B B1 sub F | F转化为: B F B B sub F B B B F.ps = B.ps F B.ps = B.ps

63、; B.iht = F.ht B B.ht = B.ht B sub F.ps = shrink(B.ps) F B1.ps = B.ps B1.iht = disp(B1.ht, F.ht) B1 B.ht = B1.iht B B.ht = B.iht ps B htps F ht ps iht B ht sub ps F ht ps iht B ht 79专业课5.14 证明: 在一个LL(1)文法的任何位置加上可区别的标记非终结符号, 结果得到一个LR(1)文法.设文法G是LL(1)文法, 则G中的每一个非终结符号A的任何两个不同的产生式A | , 下列条件成立:1. FIRST( )

64、 FIRST() = ;2. 若* , 那么FIRST( ) FOLLOW(A) = ;不妨设=Y1.Yn,在产生式A| 的任何位置加上可区别的标记非终结符号,得到 A , =M1Y1 M2Y2. MnYn Mn+1 M1 M2 . . Mn+1 则:1. FIRST() = FIRST() , FIRST( ) FIRST() = ;2. 若* , * 也成立, FIRST( ) FOLLOW(A) = ;因此, 得到的文法仍然是LL(1)文法.80专业课5.14 考虑对LR(1)文法 L L b | a 的下面的修改: L M L b | a M (a)问在输入符号串abbb的分析树中,

65、自底向上分析程序以怎样的顺序使用产生式.(b)说明这一经过修改的文法不是LR(1)文法 .(a)符号串abbb的最右推导为: rm rm rm rm rm L MLb MMLbb MMMLbbb MMMabbb MMabbb LMLb LMLb LMLb L a M rm rm Mabbb abbb M M (b)构造该文法的LR(1)项目集: I0: L .L, $ L .M L b, $ L .a, $ M ., a在状态I0中, 对于符号a存在移入-归约冲突, 所以不是LR(1)文法.81专业课5.17(a)把表5.10中的语法制导定义转化为翻译模式.S L BL B B1 M B2B

66、 B1 sub N B2B textM N B.ps=L.sS.ht=B.htL.s=10B1.ps=B.psM.i=B.psB2.ps=M.sM.ht=max(B1.ht, B2.ht)B1.ps=B.psN.i=B.psB2.ps=N.sM.ht=disp(B1.ht, B2.ht)B.ht=text.h*B.psM.s=M.iN.s=shrink(N.i)82专业课5.17 (b)修改翻译模式, 使继承属性ps的值出现在分开的栈中. 在处理过程中消除标记非终结符号M.增加栈ps_val,栈顶指针ps_topS L B S.ht = B.ht; ps_stack.pop; ps_stack

67、.destroy;L ps_stack.create; ps_stack.push(10)BB1B2 B.ht =max(B1 .ht , B2 .ht )B B1 sub N B2 B.ht =disp(B1 .ht , B2 .ht ); ps_stack.popB text B.ht = text.h * ps_stack.top( )N ps_stack. Push( shrink(ps_stack.top( )83专业课6.2 program main(input, output); procedure p(x, y, z); begin y := y + 1; z := z + x

68、; end; begin a := 2; b := 3; p(a+b, a, a); print aend. (a) call-by-value 2(b) call-by-reference p(5, a, a) 8(c) copy-restore p(5, 2, 2) y := y + 1; 3 z := z + x; 7 3 or 7(d) call-by-name a:= a+1; a:= a+ a + b; 984专业课6.4 (1) program param(input, output);(2) procedure b ( function h(n:integer) : integ

69、er);(3) var m : integer;(4) begin m := 3; writeln(h(2); end b ;(5) procedure c;(6) var m : integer;(7) function f(n:integer) : integer;(8) begin f := m + n end;(9) procedure r;(10) var m : integer;(11) begin m := 7; b(f) end;(12) begin m:=0; r end;(13) begin(14) c(15) end. 活动树:Param | c | r | b | f8

70、5专业课(a) 词法环境Paramcaccesslinkmraccesslinkmbaccesslinkmfaccesslinkm(b) 传递环境Paramcaccesslinkmraccesslinkmbaccesslinkmfaccesslinkm(c) 活动环境Paramcaccesslinkmraccesslinkmbaccesslinkmfaccesslinkm 输出: 2 输出: 9 输出: 586专业课7.2 翻译算术表达式-(a+b)*(c+d)+(a+b+c)为(a) 四元式(b) 三元式(c) 间接三元式t1 := a + bt2 := - t1t3 := c + dt4

71、:= t2 * t3t5 := t1 + ct6 := t4 + t587专业课7.3 把下列C语言程序的可执行语句翻译为： main() int i; int a10; while (i=10) ai = 0; (a) 一棵语法树(b) 后缀式(c) 三地址代码 while = assigni 10 ai 0后缀式： i 10 = ai 0 assign while(c) L0: if i=10 goto L1 goto L2 L1: ai:=0 goto L0 L2:88专业课7.4 修改图7.4中计算说明语句中的名字的类型及相对地址的翻译模式，以允许在形如D id : T 的说明中可以

72、用一串名字表来代替单个名字。D id , D1 enter(id.name, D1.type, offset); offset := offset + D1.width; D.type := D1.type; D.width := D1.width; D id : T enter(id.name, T.type, offset); offset := offset + T.width; D.type := T.type; D.width := T.width; 89专业课7.8 将下列赋值语句译成三地址代码。 Ai, j := Bi, j + CAk, l + Di + jlow1=2; lo

73、w2= 4; n1=10; n2=20; w = 4(low1 * n2) + low2)*w = (2*20)+4)*4 = 176t1 := i * 20t1 := t1 + jt2 := A - 176t3 := 4 * t1t4 := i*20t4 := t4 + jt5 := B - 176t6 := 4 * t4t7 := t5t6t8 := k * 20t8 := t8 + lt9 := A - 176t10 := t8 * 4t11 := t9t10t12 := C - 4t13 := 4 * t11t14 := t12t13t15:= i + jt16 := D - 4t17

74、 := 4 * t15t18 := t16t17t19 := t7 + t14t20 := t19 + t18t2t3 := t2090专业课7.9 Pascal语言中，语句 for v := initial to final do stmt 与下列代码序列有相同含义： begin t1 := initial; t2 := final; if t1= t2 then begin v := t1; stmt while v t2 do begin v := succ(v); stmt end end 91专业课(a) 试考虑下述Pascal程序 program forloop ( input,

75、 output); var i, initial, final : integer; begin read ( initial, final); for i := initial to final do writeln(i) end.对于initial = MAXINT - 5和final = MAXINT ，问此程序将做些什么？其中MAXINT为目标机器允许的最大整数。输出从MAXINT -5 到MAXINT 之间的六个整数(b) 试构造一个程序翻译Pascal的for 语句为三地址代码的语法制导定义。92专业课begin t1 := initial; t2 := final; if

76、t1= t2 then begin v := t1; stmt while v t2 do begin v := succ(v); stmt end endend begin t1 := initial; t2 := final; if t1= t2 then begin v := t1; goto L2 L1: v:= succ(v); L2: stmt if v t2 then goto L1 endend F for v := E1 to E2 do S等价于:F1 for v := E1 to E2F F1 do S93专业课F1 for v := E1 to E2 check v.t

77、ype is the required type; checi E1.type and E2.type have the same type as v.type; F1.nextlist := nextquad; emit(if E1.value E2.value goto_); emit(v.value := E1.value); emit( gotonextquad+2); F1.L1:=nextquad; emit(v.value := succ(v.value); F1.var := v.value F1.final := E2.value; F F1 do S emit(ifF1.v

78、ar F1.final goto F1.L1); F.nextlist := F1.nextlist; 94专业课 F nextlist F1 nextlist do S var final L1 for v := E1 to E21234595专业课中间代码序列: . E1的中间代码 . E2的中间代码100: if E1.value E2.value goto_101: v.value := E1.value102: goto 104103: v.value := succ(v.value)104: . S的中间代码 if F1.var F1.final goto 103F.nextlis

79、t: begin t1 := initial; t2 := final; if t1= t2 then begin v := t1; goto L2 L1: v:= succ(v); L2: stmt if v t2 then goto L1 endend 96专业课8.1 生成下列C语句的目标代码, 假定所有变量均为静态分配, 并有三个寄存器是可用的.(a) x = 1 MOV #1, x(b) x = y MOV y, R0 MOV R0, x(c) x = x + 1 MOV x, R0 ADD #1, R0 MOV R0, x(d) x = a + b * c MOV c, R0 MU

80、L b, R0 ADD a, R0 MOV R0, x(e) x = a / ( b + c ) - d * ( e + f) MOV c, R0 ADD b, R0 MOV a, R1 DIV R0, R1 MOV f, R0 ADD e, R0 MUL d, R0 SUB R0, R1 MOV R1, x97专业课8.2 生成下列C语句的目标代码, 假定所有变量在栈中分配。(a) x = 1 MOV #1, x(R3)(b) x = y MOV y(R3), R0 MOV R0, x(R3)(c) x = x + 1 MOV x(R3), R0 ADD #1, R0 MOV R0, x(R

81、3)(d) x = a + b * c MOV c(R3), R0 MUL b(R3), R0 ADD a(R3), R0 MOV R0, x(R3)(e) x = a / ( b + c ) - d * ( e + f) MOV c(R3), R0 ADD b(R3), R0 MOV a(R3), R1 DIV R0, R1 MOV f(R3), R0 ADD e(R3), R0 MUL d(R3), R0 SUB R0, R1 MOV R1, x(R3)98专业课8.3 生成下列C语句的目标代码，假定所有变量均为静态分配，并有三个寄存器是可用的。(a) x = ai + 1 MOV i,

82、R0 MOV a(R0), R1 ADD #1, R1 MOV R1, x(b) ai = bci MOV i, R0 MOV c(R0), R1 MOV b(R1), R2 MOV R2, a(R0)(c) aij = bik * ckj (设a: n*m b: n*r c: r*m) MOV i, R0 MUL r, R0 ADD k, R0 MOV b(R0), R1 ; bik 在R1中 MOV k, R0 MUL m, R0 ADD j, R0 MOV c(R0), R2 ; ckj 在R2中 MUL R1, R2 MOV i, R0 MUL m, R0 ADD j, R0 MOV

83、R2, a(R0)99专业课(d) ai = ai + bj MOV j, R0 MOV b(R0), R1 MOV i, R0 MOV a(R0), R2 ADD R1, R2 MOV R2, a(R0) (e) ai += bj MOV j, R0 MOV b(R0), R1 MOV i, R0 MOV a(R0), R2 ADD R1, R2 MOV R2, a(R0) 100专业课8.4 采用8.5节算法重新生成下列C语句的目标代码, 假定所有变量均为静态分配, 并有三个寄存器是可用的.101专业课8.5 为下列C语言程序生成目标代码: main() int i; int a10; w

84、hile (i=10) ai = 0; 假定main代码段入口地址为100100: MOV i, R0108: SUB 10, R0116: CJ 132124: GOTO 160132: MOV i, R0140: MOV 0, a(R0)152: GOTO 100160: HALT102专业课8.6 为下列赋值语句生成目标代码.(a) x := a + b * c MOV b, R0 MUL c, R0 ADD a, R0 MOV R0, x(b) x := (a*- b)+(c-(d+e) + 1 * 2 - 3 a - 4 c + 5 b d e计算次序: 12435MOV d, R0

85、ADD e, R0MOV c, R1SUB R0, R1MOV 0, R0SUB B, R0MUL a, R0ADD R0, R1MOV R1, x103专业课(c) x := (a/b-c)/d MOV a, R0 DIV b, R0 SUB c, R0 DIV d, R0 MOV R0, x(d) x := a+(b+c/d*e)/(f*g-h*i) MOV h, R0 MUL i, R0 MOV f, R1 MUL g, R1 SUB R0, R1 MOV c, R0 DIV d, R0 MUL e, R0 ADD b, R0 DIV R0, R1 ADD a, R1 MOV R1, x

86、104专业课(e) ai, j := bi, j - cak, l * di+j := - t11 a * t10 t7 t3 c t6b + t2,t13 a +t5 t9 *t1,t12 j * t4 l d + t8 i m k j计算次序: at13 t11 t3 t2 t1 t10 t7 t6 t5 t4 t9 t8MOV i, R0ADD j, R0 ; t8MOV d(R0), R1 ;t9MOV m, R0MUL k, R0 ; t4ADD l, R0 ; t5MOV a(R0), R2 ; t6MOV c(R2), R0 ; t7MUL R0, R1 ; t10MOV i, R0MUL m, R0 ;t1ADD j, R0 ; t3MOV b(R0), R2; t3SUB R1, R2 ; t11MOV R2, a(R0)105专业课8.7 为下列基本块构造dag.d := b * ce := a + bb := b * ca := e - d - a + e * d, ba0 b0 c0106专业课

展开阅读全文

编译原理(第2版)陈意云+张昱编著课后答案【稻谷书店】

最新文档