编译原理习题 2003.4

目录 chap 1 基本知识 chap 3 词法分析 chap 4 语法分析 chap 5 语法制导翻译 chap 6 运行时刻环境

第一章 练习 1.1 文法 S  ( L ) | a L  L , S | S (a) 指出文法的终结符号, 非终结符号, 开始符号. 文法的四个组成部分: 终结符号 VT : 语言不可再分的基本符号 非终结符号VN : 语法范畴(语法概念) 开始符号 S : 最终感兴趣的语法范畴 产生式 P : 定义语法范畴的一种书写形式 终结符号: ( , ) a 非终结符号: S L 开始符号: S 元语言符号:  表示“定义为” | 表示“或”

(b) 给出句子的分析树 分析树: (推导树) 表示一个句型的推导  (a, (a,a)) S ( L ) L , S S ( L ) a S a

最左推导 : 推导中任何一步 都是对中的最左非终结 短语 (c) 给出句子的最左推导 给出每次推导后得到的句型的短语, 直接短语 最左推导 : 推导中任何一步 都是对中的最左非终结 lm 符号进行替换的推导. 短语  是文法的句型(S * )  S * A且A +  则是关于A的句型的短语. 直接短语  S * A且A  则是关于A的句型的直接短语. 句柄: 一个句型的最左直接短语称为句柄.

S  ( L )  ( L, S )  ( S, S )  ( 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, S a, S a, a ( S, S) ( a, S) ( a, a) 直接 a a a a 短语 L, S S a a a

(d) 构造各个句子的最右推导. 最右推导(规范推导) (e) 这个文法产生的语言是什么? a (a) (a,a) ((a,a),a) ...... a和数据元素为a的广义表全体

如果一文法的句子存在两棵分析树, 则该句子是二义性的 . 如果一文法包含二义性的句子,则这个文法是二义性的. 1.2 考虑文法 S  aSbS | bSaS | (a) 试说明此文法是二义性的. (定义1.5) 如果一文法的句子存在两棵分析树, 则该句子是二义性的 . 如果一文法包含二义性的句子,则这个文法是二义性的. 可以从句子abab有两个不同的最左推导来说明. S aSbS  abS  abaSbS  ababS  abab lm lm lm lm lm S aSbS  abSaSbS  abaSbS  ababS  abab lm lm lm lm lm 句子abab有两个不同的最左推导, 该句子是二义性的 . 所以此文法是二义性的.

(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 a　S   a S b S     (d) 此文法产生的语言是什么? 由相同个数的a和b组成的字符串.

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 开始符号: bexpr

(b) 试对于句子 not ( true or false) 构造一棵分析树. bexpr bterm bfactor not bfactor ( bexpr ) bexpr or bterm bterm bfactor bfactor false true

(c) 试说明此文法产生的语言是全体布尔表达式.

练习: 长度为n的字符串, 分别有多少个 前缀, 后缀, 子串, 真前缀, 子序列 ? 前缀: n+1 后缀: n+1 子串: 1+ n+(n-1)+...+1 = 1+n(n+1)/2 真前缀: n 子序列: 1+Cn1+Cn2+Cn3+...+Cnn = 2n

给出句型E+T*i的短语, 直接短语和句柄 短语: i, T*i, E+T*i 直接短语: i 句柄: i 给出句型F+T*F的短语, 短语: F, T*F, F+T*F 直接短语: F, T*F 句柄: F

长度大于等于3且倒数第3个字符为0的01符号串全体. 第三章 练习 3.3 试描述下列正规表达式所表示的语言: (a) 0 ( 0 | 1)* 0 由0和1组成且以0开始和结束的符号串全体. (b) ( (  | 0 ) 1* ) * 由0和1组成的符号串全体. (c) ( 0 | 1 )* 0 ( 0 | 1) ( 0 | 1) 由0和1组成且以000,001,010或011结束的符号串全体. 长度大于等于3且倒数第3个字符为0的01符号串全体.

(d) 0*10*10*10* 有且只有3个1的0、1字符串全体. (e) ( 00 | 11)* ( ( 01 | 10 ) ( 00 | 11)* ( 01 | 10 ) ( 00 | 11)* )* 带有偶数个0和偶数个1的由0和1组成的符号串全体. 带有偶数个a和偶数个b的符号串全体. ( (aa|bb) | (ab|ba) (aa|bb)* (ab|ba) )*

3.4 对于下列语言分别写出它们的正规表达式: (a) 英文字母组成的所有符号串, 要求符号串中顺序包含 五个元音字母. 令letter={非元音的英文字母} letter* (a|A) letter* (e|E) letter* (i|I) letter* (o|O) letter* (u|U) letter* (b) 英文字母组成的所有符号串, 要求符号串中的字母依 照字典序排列. ( a | A)* ( b | B)* ( c | C)*...... ( z | Z)*

 i  ri0ri1...ri9 (c)没有重复出现的数字的数字符号串全体. 令 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... i9P(0,1,2...,9) (d) 最多有一个重复出现的数字的数字符号串全体  i  ri0ri1...ri9 i(0,1,2...,9) i0i1... i9P(0,1,2...,9)

(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组成的符号串全体. 1*( 0* | (10)* )* (g) 不包含子序列011的由0和1组成的符号串全体 1*0*10* |

练习: 1. 令A,B和C是任意正规式,证明以下关系成立: A|A=A (A*)*=A* A*=|AA* (AB)* A =A(BA)* (A|B)*=(A*B*)*=(A*|B*)* A=b|aA当且仅当A=a*b

3.6 给出接受下列在字母表{0，1}上的DFA。 （a）所有以00结束的符号串的集合； (1|0)*00 等价于 A 1 start B C DFA A start B C 1 NFA

（b）所有具有三个0的符号串的集合。 1*01*01*01* A start B C 1 DFA

3.7 构造等价于下列正规表达式的有限自动机. (a) 10|(0|11)0*1 0 1 A D BC D D E BC E D E / / 1 A start D B E C NFA 1 A start BC D E DFA

(b) ((0|1)* |(11))* 0|1 1 A start C B E  D NFA 0 1 ABDE ABDE ABCDE ABCDE ABDE ABCDE 1 A' start 最小化DFA 1 A' start B' DFA

3.8 给定右线性文法G: S  0S | 1S | 1A | 0B A  1C |１ B  0C | 1 C  0C | 1C | 0 | 1 试求一个等价的左线性文法G’. 左线性文法G’: f  A1 | B0 | C1 | C0 A  S1 B  S0 C  A1 | B0 | C1 | C0 S  S0 | S1 |  图中状态C和f可合并, 得到左线性文法G’: 0,1 1 S start B A C f 状态转移图

3.9-3.11 (d) (a|b)*abb(a|b)* 1 start 2 a 4 b 3 由正规表达式构造NFA A B a D b C 最小化DFA B  C   D    E     F      A B C D E 1 start 12 a 14 b 13 124 134 由NFA得到DFA A B C D E F

3.13 对于下列正规表达式构造最小状态的DFA. (b) (a|b)*a(a|b)(a|b) a 1 start 2 4 3 b NFA A start B a b H G C D E F 最小化DFA

4.4 考虑文法 R R ‘|’ R | RR | R* | (R) | a | b (a)试说明此文法生成在符号a和b之上的所有正规表达式. (b)试说明此文法是二义性的. (c)试构造一个等价的无二义性文法. (c)消除二义性 R  R ‘|’ S | S S  ST | T T  U* | U U (R) | a | b (b) 句子a|aa的两种最左推导. 句子aa*的两种最左推导. R R R a R * a R * R R a a

stmt  if expr then stmt | matched-stmt 4.5 dangling-else文法: stmt  if expr then stmt | matched-stmt matched-stmt  if 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 if E then S e1 MS if E then MS else S e2 other MS s1 if E then MS else S e3 other MS s2 other s3 S MS if 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 消除悬空else二义性的例子

4.3 对于下面的每一个语言设计一个文法。试问其中哪些语言是正规的？ (a) 使得在每一个0后至少立即跟随一个1的由0和1组成的符号串的全体。 S  1S | 01S |  (1|01)* (b) 具有相同数目的0和1的由0和1组成的符号串的全体。 S  0S1S | 1S0S |  非正规语言 (c) 具有不同数目的0和1的由0和1组成的符号串的全体。 S'  SAS S  0S1S | 1S0S |  A  B | C 非正规语言 B  1B | 1 C  0C | 0 S  A | B A  0 | 0A | A0 | 10A | 01A| A10 | A01| 1A0 | 0A1 B  0 | 0B | B0 | 10B | 01B| B10 | B01| 1B0| 0B1

(d) 所有形如xy而xy的由0和1组成的符号串。 S  0E | 1E | LBR E  00E | 01E | 10E | 11E |  B  I I1B | OO1B | IO1C | OI1C C  IO1C | OI1C |  I1 O OI1 O1I  IO1 I1I  I I1 O1O OO1 L I  1L LO  0L I1R  R1 O1R  R0 LR   所有形如xy而x=y的由0和1组成的符号串。 S  0S0| 1S1| 

4.5 (a) 给出一个上下文无关产生式的集合， 使它与A  B*a (C|D) 生成同样的 符号串集合。 A  B’ a E B’  B B’ |  E  C | D (b) 是否可以把E  T | E+T写为： E  T {+T} 是否可以把E  T | E+T | E-T写为： E  T {(+|-T)} E  T {+T} 等价于 E  T T’ T’ +TT’ |

4.7对于文法S  aSbS | bSaS | 构造一个带有回溯的递归下降分析器. 问能否构造一个预测分析器. procedure match(t:token); begin ifkahead = t then end; procedure S; if match

4.9 对于文法 bexpr  bexpr or bterm | bterm bterm  bterm and bfactor | bfactor bfactor not bfactor | (bexpr) | true | false 构造一个预测分析器。 1. 消除左递归 bexpr  bterm bexpr’ bexpr’  or bterm bexpr’ |  bterm  bfactor bterm’ bterm’  and bfactor bterm’ |  2. First(bexpr) = First(bterm) = First(bfactor) ={not, (, true, false} First(bexpr’) = {or, } First(bterm’) = {and, } Follow(bexpr) = { $, )} Follow(bexpr’) = { $, )} Follow(bterm) = {or, $, ) } Follow(bterm’) = {or, $, )} Follow(bfactor) = {or, and, $, )}

(1) bexpr  bterm bexpr’ (2) bexpr’  or bterm bexpr’ (3) bexpr’   (4) bterm  bfactor bterm’ (5) bterm’  and bfactor bterm’ (6) bterm’   (7) bfactor not bfactor (8) bfactor  (bexpr) (9) bfactor  true (10) bfactor  false First(bexpr) = First(bterm) = First(bfactor) ={not, (, true, false} First(bexpr’) = {or, } First(bterm’) = {and, } Follow(bexpr) = { $, )} Follow(bexpr’) = { $, )} Follow(bterm) = {or, $, ) } Follow(bterm’) = {or, $, )} Follow(bfactor) = {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

4.11试说明没有一个左递归文法可以是LL(1)的。 (1) 直接左递归文法中存在产生式: A  A1 | A2 |...| Am |  1 |  2 |...|  n, 其中 1  2 ...  n均不以A开头 First(Ai)  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)  ,

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)文法矛盾.

句子(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 ))$ (=) shift $(S,(L) )$ )<) reduce $(S,S )$ ,<) reduce $(L )$ (=) shift $(L) $ )<$ reduce $S $ accept 4.15 文法 S  (L) | a L  L, S | S 的算符优先关系由表4.20给出。建立与 表相应的算符优先函数并用算符优先分 析法分析句子(a, (a, a))及(a, ((a,a), (a,a)))。 算符优先关系表 a ( ) , $ a < < < ( < < = < ) < < < , < < < < $ < < 算符优先函数 a ( ) , $ f 2 0 2 2 0 g 3 3 0 1 0

4.16 试为下列各文法建立算符优先关系表。 (a) S  a S b S | b S a S |  设G是一个运算符文法, R和S是G中任何 两个终结符, 定义: (1) R=S当且仅当G中存在产生式 <U>  ...RS... 或<U>  ...R<V>S... (2) R<S当且仅当G中存在产生式 <U>  ...R<W>..., 其中 <W> + S... 或<W> + < V>S... (3) R>S当且仅当G中存在产生式 <U>  ... <W> S..., 其中 <W> + ...R 或<W> + ...R<V> a b $ a < > < > = > b < > = < > > $ < < acc 最左终结符: <U>  S...或<U>  <V>S..., S是的最左终结符 <U>  <V>..., 则<V>的最左终结符是<U>的最左终结符 对于文法中<U>  R<W>...的产生式, R< <W>的最左终结符.

(b) bexpr  bexpr or bterm | bterm bterm  bterm and bfactor | bfactor bfactor not bfactor | (bexpr) | true | false 最左终结符 最右终结符 bexpr or, and, not, (, true, false or, and, not, ), true, false bterm and, not, (, true, false and, not, ), true, false bfactor not, (, true, false not, ), true, false or and not ( ) true false $ or > < < < > < < and > > < < > < < not > > < < > < < ( < < < < = < < ) > > > > true > > > > false > > > > $ < < < < acc

4.18 给出文法LR(0)项目集族及相应的识别活前缀的自动机的状态转移图. S’  S C  cC S  CC C  d I0: S’  .S S  .CC C  . cC C  .d I1: S’  S. I2: S  C.C C  .cC I3: C  c.C I4: C  d. I5: S  CC. I6: C  cC. I0 I1 S C I2 c I3 I5 d I4 I6 start

4.19 利用图4.31画出文法4.27的识别活前缀的自动机的状态转移图. (P.200) I0: S’  .S S  .iSeS S  .iS S  .a I1: S’  S. I2: S  i.Ses S  i.S S  .a0 I3: S  a. I4: S  iS.eS S  iS. I5: S  iSe.S S  .iSeS S  .iS S  .a I6: S  iSeS. i I0 I1 S a I3 I2 I4 start e I5 I6

4.21 考虑文法 S  A S | b A  S A | a (1) 构造文法的LR(0)项目集规范族及相应的DFA. (2) 如果把每一个LR(0)项目看成一个状态, 并从每个形如B.X的状态出发画一条标记为X的弧到状态BX., 且从从每个形如B.A的状态出发画一条标记为的弧到所有形如A.的状态.这样就得到了一个NFA. 说明这个NFA和(1)的DFA是等价的. (3) 构造文法的SLR分析表. (4) 对于输入串bab, 给出SLR分析器的动作. (5) 构造文法的LR(1)分析表和LALR分析表.

I0: S’  .S S  .AS S  .b A  .SA A  .a I1:(I0,S) S’  S. A  S.A I2: (I0,A) (I2,A) (I6,A) S  A.S I3: (I0,b) (I1,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  .b I6: (I1,A) (I5,A) (I7,A) A  SA. S  A.S I7 : (I2,S) (I6,S) S  AS.

First(S’) = First(S) = First(A) = {b, a} Follow(S’) = {$} Follow(S) = {a, b, $} Follow(A) = {a, b} SLR分析表 输入串bab, SLR分析器的动作: 栈 输入 动作 0 bab$ shift3 0b3 ab$ reduce S  b 0S1 ab$ shift4 0S1a4 b$ reduce A a 0S1A6 b$ shift-reduce collision STATE ACTION GOTO a b $ S A 0 s4 s3 1 2 1 s4 s3 acc 5 6 2 s4 s3 7 2 3 r3 r3 r3 4 r5 r5 5 s4 s3 5 6 6 s4/r4 s3/r4 7 2 7 s4/r2 s3/r2 r2 5 6 输入串bab, SLR分析器的动作: 栈 输入 动作 0 bab$ shift3 0b3 ab$ reduce S  b 0S1 ab$ shift4 0S1a4 b$ reduce A a 0S1A6 b$ reduce A SA 0A2 b$ shift3 0A2b3 $ reduce S  b 0A2S7 $ reduce S AS 0S1 $ accept SLR分析表存在移入-归约冲突.为消除二义性，假设a的优先级高于b，则遇到a时移入，遇到b时归约。

LR(1)项目集规范族 I0: S’  .S, $ S  .AS, $/a/b S  .b, $/a/b A  .SA, a/b A  .a, a/b I1:(I0,S) S’  S., $ A  S.A, a/b S  .AS, a/b S  .b, a/b I2: (I0,A) (I2,A) S  A.S, $/a/b I3: (I0,b) (I2,b) S  b., $/a/b I4: (I0,a) (I1,a) (I2,a) (I5,a) (I6,a) (I8,a) (I9,a) (I10,a) A  a., a/b I5: (I1,S) (I5,S) (I8,S) (I10,S) A  S.A, a/b A  .SA, a/b A  .a, a/b S  .AS, a/b S  .b, a/b I6: (I1,A) (I5,A) (I8,A) (I10,A) A  SA., a/b S  A.S, a/b I7 : (I1,b) (I5,b) (I6,b) (I8,b) (I9,b) (I10,b) S  b., a/b I8 : (I2,S) S  AS., $/a/b I9: (I6,A) (I9,A) S  A.S, a/b S  .AS, a/b S  .b, a/b A  .SA, a/b A  .a, a/b I10: (I6,S) (I9,S) S  AS., a/b A  S.A, a/b

LR(1)分析表 STATE ACTION GOTO a b $ S A 0 s4 s3 1 2 1 s4 s7 acc 5 6 2 s4 s3 8 2 3 r3 r3 r3 4 r5 r5 5 s4 s7 5 6 6 s4/r4 s7/r4 10 9 7 r3 r3 8 s4/r2 s7/r2 r2 5 6 9 s4 s7 10 9 10 s4/r2 s7/r2 5 6 r4 s4 r2 该文法的LR(1)分析表中存在移入-归约冲突，文法具有二义性。 为消除二义性，假设a的优先级高于b，则遇到a时移入，遇到b时归约。

该文法不是LR(1)文法.具有二义性.对于句子abab,存在两颗不同的分析树. S S A S A S a A S S A b S A b A S a a b a b

4.22 构造文法 S  a S S b | a S S S | c 的LR(0)项目集规范族及识别活前缀的自动机. I0: S’  .S S  .aSSb S  .aSSS S  .c I1: S’  S. I2: S  a.SSb S  a.SSS I3: S  c. I4: S  aS.Sb S  aS.SS I5: S  aSS.b S  aSS.S I6: S  aSSb. I7: S  aSSS. I0 I1 S c I3 a I2 I4 start I5 b I6 I7

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) Follow(E) = {+, $} Follow(T) = {+, $, a, b} Follow(E) = {+, $, *, a, b} I0: E’  .E E  .E+T E  .T T  .TF T  .F F  .F* F  .a F  .b I1: E’  E. E  E.+T I2: E  T. T  T.F I3: T  F. F  F.* I4: F  a. I5: F  b. I6: E  E+.T I7: T  TF. I8: F  F*. I9: E  E+T. action goto + * a b $ E T F 0 s4 s5 1 2 3 1 s6 acc 2 r2 s4 s5 r2 7 3 r4 s8 r4 r4 r4 4 r6 r6 r6 r6 r6 5 r7 r7 r7 r7 r7 6 s4 s5 9 3 7 r3 s8 r3 r3 r3 8 r5 r5 r5 r5 r5 9 r1 s4 s5 r1 7

4.26 证明每一个LL(1)文法都是LR(1)文法.

4.27 证明下面文法是LL(1)的但不是SLR(1)文法. S  A a A b | B b B a A   B   I0: S’  .S S  .AaAb S  .BbBa A  . B  . Follow(A) = Follow(B) = {a, b} 存在归约-归约冲突, 该文法不是SLR(1)文法. First(AaAb)={a} First(BbBa)={b} First(AaAb)  First(BbBa) =  文法是LL(1)的.

4.28 证明任何一个LR(1)文法都是无二义文法.

4.29 证明任何SLR(1)文法都是LR(1)文法. 假设文法G是SLR(1)文法, 则 对于文法的状态i: 对于A.X, XVT, , XFollow(B), i中没有项目B. 对于A.和B ., Follow(A)  Follow(B) =  构造G的LR(1)项目集, 若G是LR(1)文法, 则项目集i必须满足条件: (1)对于[A.X, a], XVT, , XFollow(B), i中没有项目[B., X]. (显然成立) (2)没有[A., a]和[B .,a]的两个项目. 由closure(I)的构造{[A.B,a], [B., First(a)]}可得知, 项目A.的向前搜索符号Follow(A) 对于一个项目集中的不同归约项目[A2.搜索符A,], [ B3.,搜索符A] 搜索符A 搜索符A =  不存在归约-归约冲突, 所以条件(2)成立.

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) LR(1)项目集规范族: I0: S’  .S $ S  .E $ E  .E+T $/+ E  .T $/+ T  .(E) $/+ T  .a $/+ I1: S’  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  .a )/+ I14: T  (E.) )/+ E  E.+T )/+ I15: E  E+T. )/+ I16: T  (E). )/+

LR(1) 分析表: action goto + ( ) a $ S E T 0 s4 s5 1 2 3 1 acc 2 s6 r1 3 r3 r3 4 s9 s10 7 8 5 r5 r5 6 s4 s5 11 7 s13 s12 8 r3 r3 9 s9 s5 14 8 10 r5 r5 11 r2 r2 12 r4 r4 13 s9 s10 15 14s13 s16 15r2 r2 16r4 r4

action goto + ( ) a $ S E T 0 s4 9 s5 10 1 2 3 8 1 acc 2 s6 13 r1 LALR(1)分析表: action goto + ( ) 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 16 11 15 r2 r2 r2 12 16 r4 r4 r4 LALR(1)分析表不存在冲突, 所以该文法是LALR(1)文法.

<S>  a<A>d <S> b<B>d 证明文法G[<S>]: <S>  a<A>d <S> b<B>d <S>  a<B>e < S>  b<A>e <A >  c < B> c 是LR(1)文法, 但不是LALR(1)文法.

5.1 对于输入的表达式(4*7+1)*2, 根据表5.1的语法制导定义建立 一棵带注释的分析树. 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=1 T.val=4 * F.val=7 digit.lexval=1 F.val=4 digit.lexval=7 digit.lexval=4（lex表示是从词法分析来的）

来建立表达式((a)+(b))的分析树和语法树. (a) E T ( E nptr ) E + T T ( E ) ( E ) T nptr T nptr id id + id entry to a id entry to a

(b) + id id entry to a entry to a E T R ( E nptr )  ( E ) + T i R s T nptr R ( E )  id  Tnptr R id  + id id entry to a entry to a

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=real ) 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;}

E.code = ‘+’ || E1 .code || inttoreal(T.code) (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 = integer and T.type = real ) then begin E.type = real; E.code = ‘+’ || inttoreal(E1 .code) || T.code else begin E.type = E1.t ype; E.code = ‘+’ || E1 .code || T.code } 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.lexval}

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.lexval}

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

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.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;}

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 1

(b) 试用一个语法制导定义来决定S.val, 在这个定义中B仅有综合 属性c,给出由B生成的位对于最后的数值的分担额. 引入B的继承属性i, 综合属性c S  L1.L2 { L1.i = 20; L2 .i = 2-1; S.val = L1.val +L2.val} S  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 L.val = L1.val +B.c } L  B { B.i = L.i ; L.s= L.i/2; L.val = B.c} B  0 { B.c = B.i*0} B  1 { B.c = B.i*1}

S val i L v . i L s v i L v i B c i L s v i B c i B c 0 i L s v i B c 1 1 i B c 0 1

5.6 重写例5.3中语法制导定义的基础文法, 使类型信息只需用综合属性来传递. D  T L L  L1 , id | id T  int T  real D L id L id , T int 改写为: 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.type T  int T.type = int T  real T.type = real

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 t Tt it F t num + Tt it F t num.num 

(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 then begin F1.it = real; F1.ic = ‘+’ || F.ic || inttoreal(T.c); end else if F.it = integer and T.t = real then begin F1.ic = ‘+’ || inttoreal(F.ic) || T.c; else begin F1.it = F.it; F1.ic = ‘+’ || F.ic || T.c; F.t = F1.it;F.c = F1.ic;} F   { F.t = F.it; F.c = F.ic;} T  num.num {T.t = real; T.c= num.num.lexval; } T  num {T.t = integer; T.c = num.lexval; }

E t c T t c it icF t c num + T t c it icF t c num.num 

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(id.entry, L.type} L  : T {L.type= T.type} T  integer {T.type= 0} T  real {T.type= 1} 用整数0表示整型, 1表示实型.

(b) procedure D; var Ltype:integer; begin match(id); Ltype:=L(); addtype(id.entry, Ltype) end; function L():integer; if lookahead = ‘,’ then match(‘,’); match(id); Ltype:= L(); end else if lookahead = ‘:’ then match(‘:’); Ltype:=T(); return Ltype funtion T():integer; begin if lookahead = ‘integer’ then match(‘integer’); return 0 end else if lookahead = ‘real’ then match(‘real’); return 1

5.10 下面的文法是表5.7中基础文法的无二义形式. S  L L  LB | B B  B sub F | F F  {L} | 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

(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.ps}

5.12 从5.10(b)中消除左递归. L  L1 B | B 转化为: L  B L' L'  B L' L'   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 {L'1.ps = L'.ps} {L'1.iht = max(B.ht, L'.iht } L'1 {L'.ht = L'1.ht } L'   {L'.ht = L'.iht } ps L ht ps B ht ps iht L' ht ps B ht ps iht L' ht 

B  B1 sub F | F 转化为: B  F B' B'  sub F B' B'   B  {F.ps = B.ps} F {B'.ps = B.ps; B'.iht = F.ht} B' {B.ht = B'.ht} B'  sub {F.ps = shrink(B'.ps)} F {B'1.ps = B'.ps} {B'1.iht = disp(B1.ht, F.ht)} B'1 {B'.ht = B'1.iht} B'   {B'.ht = B'.iht} ps B ht ps F ht ps iht B' ht sub ps F ht ps iht B' ht 

5.14 证明: 在一个LL(1)文法的任何位置加上可区别的标记 非终结符号, 结果得到一个LR(1)文法. 设文法G是LL(1)文法, 则G中的每一个非终结符号A的任何两个 不同的产生式A | , 下列条件成立: 1. FIRST( ) 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)文法.

5.14 考虑对LR(1)文法 L L b | a 的下面的修改: L  M L b | a M   (a)问在输入符号串abbb的分析树中, 自底向上分析程序以怎样的 顺序使用产生式. (b)说明这一经过修改的文法不是LR(1)文法 . (a)符号串abbb的最右推导为: rm rm rm rm rm L  MLb  MMLbb  MMMLbbb  MMMabbb  MMabbb LMLb LMLb LMLb 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)文法.

5.17(a)把表5.10中的语法制导定义转化为翻译模式. S  L B L   B  B1 M B2 sub N B  text M   N   {B.ps=L.s} {S.ht=B.ht} {L.s=10} {B1.ps=B.ps} {M.i=B.ps} {B2.ps=M.s} {M.ht=max(B1.ht, B2.ht)} {N.i=B.ps} {B2.ps=N.s} {M.ht=disp(B1.ht, B2.ht)} {B.ht=text.h*B.ps} {M.s=M.i} {N.s=shrink(N.i)

5.17 (b)修改翻译模式, 使继承属性ps的值出现在分开的栈中. 在处理过程中消除标记非终结符号M. 增加栈ps_val,栈顶指针ps_top S  L B {S.ht = B.ht; ps_stack.pop; ps_stack.destroy;} L   {ps_stack.create; ps_stack.push(10)} BB1B2 {B.ht =max(B1 .ht , B2 .ht )} B  B1 sub N B2 {B.ht =disp(B1 .ht , B2 .ht ); ps_stack.pop} B  text {B.ht = text.h * ps_stack.top( )} N   {ps_stack. Push( shrink(ps_stack.top( ))}

6.2 program main(input, output); procedure p(x, y, z); begin y := y + 1; z := z + x; end; a := 2; b := 3; p(a+b, a, a); print a end. (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; 9

6.4 (1) program param(input, output); (2) procedure b ( function h(n:integer) : integer); (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 f

(a) 词法环境 (b) 传递环境 (c) 活动环境 Param c accesslink m r b f Param c accesslink m r b f Param c accesslink m r b f 输出: 2 输出: 9 输出: 5

7.2 翻译算术表达式-(a+b)*(c+d)+(a+b+c)为 t1 := a + b t2 := - t1 t3 := c + d t4 := t2 * t3 t5 := t1 + c t6 := t4 + t5

7.3 把下列C语言程序的可执行语句翻译为： main() { int i; int a[10]; while (i<=10) a[i] = 0; } (a) 一棵语法树 (b) 后缀式 (c) 三地址代码 (c) L0: if i<=10 goto L1 goto L2 L1: a[i]:=0 goto L0 L2: while <= assign i 10 a[i] 0 后缀式： i 10 <= a[i] 0 assign while

7.4 修改图7.4中计算说明语句中的名字的类型及相对地址的翻译 模式， 以允许在形如D  id : T 的说明中可以用一串名字表来 代替单个名字。 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;}

7.8 将下列赋值语句译成三地址代码。 A[i, j] := B[i, j] + C[A[k, l]] + D[i + j] low1=2; low2= 4; n1=10; n2=20; w = 4 ((low1 * n2) + low2)*w = ((2*20)+4)*4 = 176 t1 := i * 20 t1 := t1 + j t2 := A - 176 t3 := 4 * t1 t4 := i*20 t4 := t4 + j t5 := B - 176 t6 := 4 * t4 t7 := t5[t6] t8 := k * 20 t8 := t8 + l t9 := A - 176 t10 := t8 * 4 t11 := t9[t10] t12 := C - 4 t13 := 4 * t11 t14 := t12[t13] t15:= i + j t16 := D - 4 t17 := 4 * t15 t18 := t16[t17] t19 := t7 + t14 t20 := t19 + t18 t2[t3] := t20

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); end

(a) 试考虑下述Pascal程序 program forloop ( input, 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 语句为三地址代码的语法制导 定义。

begin t1 := initial; t2 := final; if t1<= t2 then begin v := t1; stmt while v <> t2 do begin v := succ(v); end 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 end F  for v := E1 to E2 do S 等价于: F1  for v := E1 to E2 F  F1 do S

F1  for v := E1 to E2 { check v.type 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( ‘goto’nextquad+2); F1.L1:=nextquad; emit(v.value ‘:=’ succ(v.value)); F1.var := v.value F1.final := E2.value; } F  F1 do S { emit(‘if’F1.var ‘<>’F1.final goto F1.L1); F.nextlist := F1.nextlist;

F nextlist F1 nextlist do S var final L1 for v := E1 to E2 5 3 4 1 2

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 end 中间代码序列: … ... E1的中间代码 … ... E2的中间代码 100: if E1.value > E2.value goto_ 101: v.value := E1.value 102: goto 104 103: v.value := succ(v.value) 104: … ... S的中间代码 if F1.var <> F1.final goto 103 F.nextlist:

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 (d) x = a + b * c MOV c, R0 MUL b, R0 ADD a, R0 MOV R0, x (e) x = a / ( b + c ) - d * ( e + f) ADD b, R0 MOV a, R1 DIV R0, R1 MOV f, R0 ADD e, R0 MUL d, R0 SUB R0, R1 MOV R1, x

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 (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) 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)

8.3 生成下列C语句的目标代码，假定所有变量均为静态分配，并 有三个寄存器是可用的。 (c) a[i][j] = b[i][k] * c[k][j] (设a: n*m b: n*r c: r*m) MOV i, R0 MUL r, R0 ADD k, R0 MOV b(R0), R1 ; b[i][k] 在R1中 MOV k, R0 MUL m, R0 ADD j, R0 MOV c(R0), R2 ; c[k][j] 在R2中 MUL R1, R2 MOV R2, a(R0) (a) x = a[i] + 1 MOV i, R0 MOV a(R0), R1 ADD #1, R1 MOV R1, x (b) a[i] = b[c[i]] MOV c(R0), R1 MOV b(R1), R2 MOV R2, a(R0)

(d) a[i] = a[i] + b[j] MOV j, R0 MOV b(R0), R1 MOV i, R0 MOV a(R0), R2 ADD R1, R2 MOV R2, a(R0) (e) a[i] += b[j] MOV j, R0 MOV b(R0), R1 MOV i, R0 MOV a(R0), R2 ADD R1, R2 MOV R2, a(R0)

8.4 采用8.5节算法重新生成下列C语句的目标代码, 假定所有变量均为静态分配, 并有三个寄存器是可用的.

8.5 为下列C语言程序生成目标代码: main() { int i; int a[10]; while (i<=10) a[i] = 0; } 假定main代码段入口地址为100 100: MOV i, R0 108: SUB 10, R0 116: CJ< 132 124: GOTO 160 132: MOV i, R0 140: MOV 0, a(R0) 152: GOTO 100 160: HALT

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 计算次序: 12435 MOV d, R0 ADD e, R0 MOV c, R1 SUB R0, R1 MOV 0, R0 SUB B, R0 MUL a, R0 ADD R0, R1 MOV R1, x

(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

计算次序: a[t13] t11 t3 t2 t1 t10 t7 t6 t5 t4 t9 t8 (e) a[i, j] := b[i, j] - c[a[k, l]] * d[i+j] := [] - t11 a * t10 [] t7 [] t3 c [] t6 b + t2,t13 a +t5 [] t9 *t1,t12 j * t4 l d + t8 i m k j MOV i, R0 ADD j, R0 ; t8 MOV d(R0), R1 ;t9 MOV m, R0 MUL k, R0 ; t4 ADD l, R0 ; t5 MOV a(R0), R2 ; t6 MOV c(R2), R0 ; t7 MUL R0, R1 ; t10 MUL m, R0 ;t1 ADD j, R0 ; t3 MOV b(R0), R2; t3 SUB R1, R2 ; t11 MOV R2, a(R0)

8.7 为下列基本块构造dag. d := b * c e := a + b b := b * c a := e - d - a + e * d, b a0 b0 c0