编译原理第七章例题

1．写出下列表达式的三地址形式的中间表示。

（1）5+6 ⨯ (a + b);（2）⌝A∨( B ∧ (C ∨ D));（3）for j:=1 to 10 do a[j + 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 F104: if C goto T105: goto 106106: if D goto T107: goto F⑶100: j:=1101: if j>10 goto NEXT102: i:=j+j103: a[i]:=0104: goto 101⑷100: if x>y goto 102101: goto 104102: x:=10103: goto 105104: x:=x+y105:2．将语句if A V B>0 then while C>0 do C:=C+D翻译成四元式。

答：100 (jnz，A，-，104)101 (j，-，-，102)102 (j>，B，0，104)103 (j，-，-，109)104 (j>，C，0，106)105 (j，-，-，109)106 (+，C，D，T1)107 (:=，T1，-，C)108 (j，-，-，104)1093．试将下述程序段翻译成三地址形式的中间代码表示。

while ( a+b<c OR a=b )while ( a<5 AND b<10 ){ a=a+1;b=b+1;}答：三地址代码如下：100: t:=a+b101: if t<c goto 105102: goto 103103: if a=b goto 105104: goto 112105: if a<5 goto 107106: goto 100107: if b<10 goto 109108: goto 100109: a:=a+1110: b:=b+1111: goto 105112:4．While a＞0 ∨b＜0doBeginX：＝X＋1；if a＞0 then a：＝a－1else b：＝b＋1End；翻译成四元式序列。

第七章习题解答7.1 给定文法：S→(A)A→ABBA→BB→bB→c①构造它的基本LR(0)项目集；②构造它的LR(0)项目集规范族；③构造识别该文法活前缀的DFA；④该文法是SLR文法吗？若是，构造它的SLR分析表。

7.2 给定文法：E→EE+E→EE*E→a①构造它的LR(0)项目集规范族；②它是SLR(1)文法吗？若是，构造它的SLR(1)分析表；③它是LR(1)文法吗？若是，构造它的LR(1)分析表；④它是LALR(1)文法吗？若是，构造它的LALR分析表。

7.3 给出一个非LR(0)文法。

7.4 给出一个SLR(1)文法，但它不是LR(0)文法，构造它的SLR分析表。

7.5 给出一个LR(1)文法，但它不是LALR(1)文法，构造它的规范LR(1)分析表。

7.6 给定二义性文法：① E→E+E② E→E*E③ E→(E)④ E→id用所述的无二义性规则和(或)另加一些无二义性规则，例如，给算符*、+施加某种结合规则。

①构造它的LR(0)项目集规范族及识别活前缀的DFA；②构造它的LR分析表。

习题参考答案7.1 解：文法的基本LR(0)项目集为S→.(A) S→(.A) S→(A.) S→(A).A→.ABB A→A.BB A→AB.B A→ABB.A→.B A→B. B→.b B→b.B→.c B→c.构造该文法的识别活前缀的DFSA如下图所示：I文法的识别活前缀的DFSA该文法的LR(0)项目集规范族={I0，I1，I2，I3，I4，I5，I6，I7，I8}因为在构造出来的识别活前缀的DFA中，每一个状态对应的项目集都不含有移进-归约、归约-归约冲突，所以该文法是LR(0)文法，当然也是SLR文法。

因为 FOLLOW(S)={#}FOLLOW(A)=FIRST{)}∪FIRST(BB)={)，b，c}FOLLOW(B)=FIRST(B)∪FOLLOW(A)={b，c，)}其对应的SLR(1)分析表如下表所示。

第1 题已知文法A→aAd|aAb|ε判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。

答案：文法：A→aAd|aAb|ε拓广文法为G′，增加产生式S′→A若产生式排序为：0 S' →A1 A →aAd2 A →aAb3 A →ε由产生式知：First (S' ) = {ε,a}First (A ) = {ε,a}Follow(S' ) = {#}Follow(A ) = {d,b,#}G′的LR(0)项目集族及识别活前缀的DFA 如下图所示在I0 中：A →.aAd 和A →.aAb 为移进项目，A →.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。

在I0、I2 中：Follow(A) ∩{a}= {d，b，#} ∩{a}=所以在I0、I2 中的移进-归约冲突可以由Follow 集解决，所以G 是SLR(1)文法。

构造的SLR(1)分析表如下：对输入串ab#的分析过程:第2 题若有定义二进制数的文法如下：S→L·L|LL→LB|BB→0|1(1) 试为该文法构造LR 分析表，并说明属哪类LR 分析表。

(2) 给出输入串101.110 的分析过程。

答案：文法：S→L.L|LL→LB|BB→0|1拓广文法为G′，增加产生式S′→S若产生式排序为：0 S' →S1 S →L.L2 S →L3 L →LB4 L →B5 B →06 B →1由产生式知：First (S' ) = {0,1}First (S ) = {0,1}First (L ) = {0,1}First (B ) = {0,1}Follow(S' ) = {#}Follow(S ) = {#}Follow(L ) = {.,0,1,#}Follow(B ) = {.,0,1,#}G′的LR(0)项目集族及识别活前缀的DFA 如下图所示：在I2 中：B →.0 和 B →.1 为移进项目，S →L.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。

1S → a | ∧ | ( T )T → T , S | S解：(1) 增加辅助产生式 S’→＃S＃求 FIRSTVT集FIRSTVT（S’）＝ {#}FIRSTVT（S）＝ {a ∧ ( }FIRSTVT (T) ＝ {,} ∪ FIRSTVT( S ) = { , a ∧ ( }求 LASTVT集LASTVT（S’）＝ { # }LASTVT（S）＝ { a ∧ )}LASTVT (T) ＝ { , a ∧ )}(2)算符优先关系表a ∧( ) , #a ·> ·> ·> ∧·> ·> ·> ( <·<·<·=·<·) ·> ·> ·>, <·<·<··> ·># <·<·<·=·因为任意两终结符之间至多只有一种优先关系成立，所以是算符优先文法(3)a ∧( ) ,F 1 1 1 11 1g 1 1 1 11 1f 2 2 1 3 2g 2 2 2 1 2f 3 3 1 3 3g 4 4 4 1 2f 3 3 1 3 3g 4 4 4 1 2(4)栈优先关系当前符号剩余输入串移进或规约＃<·( a,a)#移进＃( <· a,a)# 移进# (a ·> , a)# ＃(T <·, a)# ＃(T，<· a )# ＃(T,a ·> ) # ＃(T,T ·> ) # ＃(T =·) # ＃(T) ·> ＃＃T =·＃4.扩展后的文法S’→#S# S→S;G S→G G→G(T)G→H H→a H→(S)T→T+S T→S（1）FIRSTVT(S)={;}∪FIRSTVT(G) = {; , a , ( } FIRSTVT(G)={ ( }∪FIRSTVT(H) = {a , ( } FIRSTCT(H)={a , ( }FIRSTVT(T) = {+} ∪FIRSTVT(S) = {+ , ; , a , ( }LASTVT(S) = {;} ∪LASTVT(G) = { ; , a , )}LASTVT(G) = { )} ∪LASTVT(H) = { a , )}LASTVT(H) = {a, )}LASTVT(T) = {+ } ∪LASTVT(S) = {+ , ; , a , ) }构造算符优先关系表; ( ) a + # ；·> <··> <··> ·> ( <·<·＝·<·<·) ·> ·> ·> ·> ·> a ·> ·> ·> ·> ·> + <·<··> <··># <·<·<·＝·因为任意两终结符之间至多只有一种优先关系成立，所以是算符优先文法（2）句型a(T+S);H;(S)的短语有：a(T+S);H;(S) a(T+S);H a(T+S) a T+S (S) H直接短语有: a T+S H (S)句柄： a素短语：a T+S (S)最左素短语：a(3)分析a；（a＋a）栈优先关系当前符号剩余输入串移进或规约＃＃a ＃T ＃T；＃T；（<··><·<·<·a；；（a；（a＋a）＃（a＋a）＃（a＋a）＃a＋a）＃＋a）＃移进规约移进移进移进＃T；（T ＃T；（T ＋＃T；（T ＋a＃T；（T ＋T＃T；（T ＃T；（T）＃T；T ＃T <·<··>·>＝··>·>＝·＋a）））＃＃＃a）＃）＃＃＃＃移进移进规约规约移进规约规约接受分析a；（a＋a）栈优先关系当前符号剩余输入串移进或规约＃＃（＃（a ＃（T ＃（T＋<·<··><·<·(a＋＋aa＋a）＃＋a）＃a）＃移进移进规约移进移进＃（T＋T ＃（T＃（T）＃T ·>＝··>＝·））＃＃）＃＃＃＃规约移进规约接受（4）不能用最右推导推导出上面的两个句子。

第七章LR分析法1．已知文法A→aAd|aAb|ε判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。

解：增加一个非终结符S/后，产生原文法的增广文法有：S/→AA→aAd|aAb|ε下面构造它的LR(0)项目集规范族为：02对于I0来说有FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ所以在I0状态下面临输入符号为a时移进，为b,d,#时归约，为其他时报错。

对于I2来说有也有与I0完全相同的结论。

这就是说，以上的移进-归约冲突是可以解决的，因此该文法是SLR(1)文法。

其他SLR(1)分析表为：下面构造它的SLR(1)项目集规范族为：15S→a|^|(T)T→T,S|S(1)构造它的LR(0),LALR(1),LR(1)分析表。

(2)给出对输入符号串(a#和(a,a#的分析过程。

(3)说明(1)中三种分析表发现错误的时刻和输入串的出错位置有何区别。

解：(1)加入非终结符S/，方法的增广文法为：S/→SS→aS→^S→(T)T→T,ST→S下面构造它的LR(0)项目集规范族为：表7.15.1 文法的LR(0)分析表17．若包含条件语句的语句文法可缩写为：S→iSeS|iS|S;S|a其中：i代表if,e代表else,a代表某一语句。

若规定：(1)else与其左边最近的if结合(2);服从左结合试给出文法中i,e,; 的优先关系，然后构造出无二义性的LR分析表，并对输入串iiaea#给出分析过程。

解：加入S/→S产生式构造出增广文法如下：[0] S/→S[1] S→iSeS[2] S→iS[3] S→S;S[4] S→a由习惯可知，定义文法中i,e,;,a4个算符的优先关系为：a>e>i>;。

并且i与;的结合方向均为自左至右。

由上述状态项目集可见：a.状态I1存在移进-归约冲突，由于FOLLOW(S/)∩{;}={#}∩{;}=Φ,所以面临#号时应acc，面临;号时应移进。