编译原理及实现课后习题答案

2.1 设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+和A*. x0=(aaa)0=ε | x0|=0 xx=aaaaaa |xx|=6 x5=aaaaaaaaaaaaaaa | x5|=15 A+ =A1∪A2∪ …. ∪A n∪…={a,aa,aaa,aaaa,aaaaa…}

A* = A0 ∪A1 ∪ A2 ∪ …. ∪ A n ∪…={ε,a,aa,aaa,aaaa,aaaaa…}

2.2 令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3

xy=abcb |xy|=4 xyz=abcbaab |xyz|=7 (xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12 2.3

设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。 S => SS* => Sa* => SS+a* => Sa+a* => aa+a*

S S S * S a S a + a 2.4 已知文法G[Z]：Z∷=U0∣V1 、 U∷=Z1∣1 、 V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。

Z=>U0=>Z10=>U010=>1010

Z=>U0=>Z10=>V110=>0110 Z=>V1=>Z01=>U001=>1001 Z=>V1=>Z01=>V101=>0101

2.5 已知文法G[S]： S∷=AB A∷=aA︱ε B∷=bBc︱bc , 写出该文法描述的语言。

A∷=aA︱ε描述的语言: {an|n>=0} B∷=bBc︱bc描述的语言：{bncn|n>=1} L(G[S])={anbmcm|n>=0,m>=1}

2.6 已知文法E∷=T∣E+T∣E-T 、 T∷=F∣T*F∣T/F 、 F∷=(E)∣i，写出该文法的开始符号、终结符号集合VT、非终结符号集合VN。

开始符号：E

Vt={+, - , * , / ,（ , ）, i} Vn={E , F , T}

2.7 对2.6题的文法，写出句型T+T*F+i的短语、简单短语以及句柄。 短语：T+T*F+i T+T*F i i T T*F 简单短语：i T*F T 句柄：T

2.8 设有文法G[S]：S∷=S*S|S+S|(S)|a，该文法是二义性文法吗？

E E E T + T + T * F T F i

S S * S S S + S S + S a a S * S a a a a

根据所给文法推导出句子a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。

2.9 写一文法，使其语言是奇正整数集合。 A::=1|3|5|7|9|NA N::=0|1|2|3|4|5|6|7|8|9

2.10给出语言{anbm|n,m≥1}的文法。 G[S]: S::=AB A::=aA|a B::=bB|b

3.1 有正则文法G[Z]：Z::=Ua|Vb，U::=Zb|b，V::=Za|a ，画出该文法的状态图，并检查句子abba是否合法。

解：该文法的状态图如下：

S a b U b a V b a Z

句子abba合法。

3.2 状态图如图3.35所示，S为开始状态，Z为终止状态。写出相应的正则文法以及V，Vn和Vt。

S b a b Z A a 图3-35状态图

解： 左线性文法G[Z]: 右线性文法G’[S]:

Z::=Ab|b S::=aA|b

A::=Aa|a A::=aA|b

V={Z,A,a,b} V={S,A,a,b} Vn={Z,A} Vn={S,A} Vt={a,b} Vt={a,b}

3.3 构造下列正则表达式相应的NFA： 1(1|0)*|0

1(1010*|1(010)*1)*0 解：正则表达式：1(1|0)*|0 1、

S 2、

1(1|0)*|0 Z 0 S 1(1|0)* 3、

Z

S 1 4、

0 0 A 1 ε Z q0 1 正则表达式：1(1010*|1(010)*1)*0

0 0,1 q2 q1

0 1 1 1 3 ε 0 8 6 0 1 0 1 4 5 7 0 3.4

将图3.36的NFA M确定化

1 1 0 2 a a 图3.36 状态图 解： q0={0} a {0,1} b {1} 0 a,b 1

q1={0,1} q2={1} DFA:

{0,1} {0} {1} Φ a a q0 b q2 3.5

将图3.37的DFA化简。

q1 a b 0 a 1 a 解： 划分 {0,1} {2,3,4,5} 划分 {0,1} {2,4} {3,5} b a a b 2 4 b b b b a 3 a 5

图3.37 DFA状态图

a {1} {1,0,3,5} a {1} {0,1} {3,5} q2={3,5}

b {2,4} {3,5,2,4} b {2,4} {3,5} {2,4} q0={0,1} q1={2,4} 化简后的DFA：

b a q0 a

4.1 对下面文法，设计递归下降分析程序。 S→aAS|(A) , A→Ab|c

解：首先将左递归去掉，将规则A→Ab|c 改成 A→c{b} 非终结符号S的分析程序如下：

b q1 b q2 a

过程S N INPUTSYM=’a’ Y INPUTSYM=下一个符号 INPUTSYM=’(’ Y INPUTSYM=下一个符号 N 错误 过程A 过程A N INPUTSYM=’)’ Y INPUTSYM=下一个符号 错误 过程S 出口 非终结符号A的分析程序如下：

过程A INPUTSYM=’c’ Y INPUTSYM=下一个符号 N 错误 INPUTSYM=下一个符号 INPUTSYM=’b’ Y N 出口

4.2 设有文法G[Z]： Z∷=(A) , A∷=a|Bb , B∷=Aab

若采用递归下降分析方法，对此文法来说，在分析过程中，能否避免回溯？为什么？

解：若采用递归下降分析方法，对此文法来说，在分析过程中不能避免回朔。因为规则A

∷=a|Bb和规则B∷=Aab构成了间接左递归，不满足实现没有回溯的递归下降分析方法的条件（1）（书P67），且规则 A: := a|Bb，FIRST(a)={a}，FIRST(Bb)={a}，即此规则候选式的首符号集有相交，不满足实现没有回溯的递归下降分析方法的条件（2）（书P67），在分析过程中，将造成回溯。 改写文法可避免回溯：

将规则B∷=Aab代入规则A∷=a|Bb得：A∷=a|Aabb，再转换成：A∷=a{abb}，可避免回溯。

4.3 若有文法如下，设计递归下降分析程序。 <语句>→<语句><赋值语句>|ε <赋值语句>→ID=<表达式>

<表达式>→<项>|<表达式>＋<项>|<表达式>－<项> <项>→<因子>|<项>*<因子>|<项>/<因子> <因子>→ID|NUM|(<表达式>)

解：首先，去掉左递归

<语句>→<语句><赋值语句>|ε改为： <语句>→{<赋值语句>} <表达式>→<项> | <表达式> + <项> | <表达式> - <项> 改为： <表达式>→<项>{（+ | -）<项>}

<项>→<因子> | <项> * <因子> | <项> / <因子> 改为： <项>→<因子>{（* | /）<因子>}

则文法变为：

<语句>→{<赋值语句>} <赋值语句>→ID=<表达式> <表达式>→<项>{（+ | -）<项>} <项>→<因子>{（* | /）<因子>} <因子>→ID|NUM|(<表达式>) 非终结符号 <语句> 的分析程序如下： <语句>→{<赋值语句>} 语句 FIRST(<赋值语句>)={ID} N INPUTSYM=’ID’ Y 赋值语句 出口

非终结符号 <赋值语句> 的分析程序如下：

<赋值语句>→ ID=<表达式>

赋值语句 N INPUTSYM=’ID’ INPUTSYM=下一个符号 N INPUTSYM=’=’ Y INPUTSYM=下一个符号 错误 错误 表达式 出口

非终结符号 <表达式> 的分析程序如下：

<表达式>→<项>{（+ | -）<项>} 表达式 项 INPUTSYM=下一个符号 Y INPUTSYM=’+’ N Y INPUTSYM=’-’ N 出口

非终结符号 <项> 的分析程序如下：

<项>→<因子>{（* | /）<因子>} 项 因子 INPUTSYM=下一个符号 Y INPUTSYM=’*’ N Y INPUTSYM=’/’ N 出口

非终结符号 <因子> 的分析程序如下：

<因子>→ID|NUM|(<表达式>) 复值语句的分析程序

因子 N INPUTSYM=’ID’ Y INPUTSYM=下一个符号 N 错误 出口 INPUTSYM=’(’ Y INPUTSYM=下一个符号 Y N 错误 INPUTSYM=’)’

4.4 有文法G[A]：A::=aABe|ε，B::=Bb|b （1）求每个非终结符号的FOLLOW集。 （2）该文法是LL(1)文法吗？ （3）构造LL(1)分析表。 解：

（1） FOLLOW(A)=First(B)∪{#}={b,#}

FOLLOW(B)={e,b}

（2） 该文法中的规则B::=Bb|b为左递归，因此该文法不是LL(1)文法 （3） 先消除文法的左递归（转成右递归），文法变为：A::=aABe|ε，B::=bB’，B’=bB’|ε，

该文法的LL(1)分析表为： A B B’ a e b a e b POP POP ， PUSH(B’b) POP ， PUSH(B’b) POP, NEXTSYM # POP POP ， PUSH(eBAa) POP, NEXTSYM POP POP, NEXTSYM INPUTSYM=’NUM’ Y N 表达式

# A B B’ a A→aABe e B’→ε b A→ε B→bB’ B’→bB’ ACCEPT # A→ε 更常用且简单的LL(1)分析表：

4.5 若有文法A→(A)A|ε

（1）为非终结符A构造FIRST集合和FOLLOW集合。 （2）说明该文法是LL(1)的文法。 解：

（1）FIRST(A)＝｛(, ε｝ FOLLOW(A)＝｛)，#｝ （2）

该文法不含左递归；

FIRST（(A)A）={(}，FIRST（ε）={ε}，FIRST（(A)A）∩FIRST（ε）=Φ， 且FOLLOW(A)＝｛)，#｝，FIRST（(A)A）∩ FOLLOW(A) =Φ， 因此，该文法满足LL(1)文法的条件，是LL(1)文法。

4.6 利用分析表4-1，识别以下算术表达式，请写出分析过程。 （1）i+i*i+i （2）i*(i+i+i) 解：

（1）i+i*i+i 步骤 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 分析栈 #E #E’T #E’T’F #E’T’i #E’T’ #E’ #E’T+ #E’T #E’T’F #E’T’i #E’T’ #E’T’F* #E’T’F #E’T’i #E’T’ #E’ #E’T+ #E’T 余留输入串 i+i*i+i# i+i*i+i# i+i*i+i# i+i*i+i# +i*i+i# +i*i+i# +i*i+i# i*i+i# i*i+i# i*i+i# *i+i# *i+i# i+i# i+i# +i# +i# +i# i# 分析表元素 POP,PUSH(E’T) POP,PUSH(T’F) POP,PUSH(i) POP,NEXTSYM POP POP,NEXTSYM POP,PUSH(T’F) POP,PUSH(i) POP,NEXTSYM POP,NEXTSYM POP,PUSH(i) POP,NEXTSYM POP POP,NEXTSYM POP,PUSH(T’F) 所用产生式 E→TE’ T→FT’ F→i T’→ε T→FT’ F→i F→i T’→ε T→FT’ POP,PUSH(E’T+) E’→+TE’ POP,PUSH(T’F*) T’→*FT’ POP,PUSH(E’T+) E’→+TE’

19 20 21 22 23 （2）i*(i+i+i) 步骤 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #E’T’F #E’T’i #E’T’ #E’ # 分析栈 #E #E’T #E’T’F #E’T’i #E’T’ #E’T’F* #E’T’F #E’T’ )E( #E’T’ )E #E’T’ ) E’T #E’T’ ) E’ T’F #E’T’ ) E’ T’i #E’T’ ) E’ T’ #E’T’ ) E’ #E’T’ ) E’T+ #E’T’ ) E’T #E’T’ ) E’T’F #E’T’ ) E’T’i #E’T’ ) E’T’ #E’T’ ) E’ #E’T’ ) E’ T+ #E’T’ ) E’ T #E’T’ ) E’ T’F #E’T’ ) E’ T’i #E’T’ ) E’ T’ #E’T’ ) E’ #E’T’ ) #E’T’ #E’ # i# i# # # # 余留输入串 i*(i+i+i)# i*(i+i+i)# i*(i+i+i)# i*(i+i+i)# *(i+i+i)# *(i+i+i)# (i+i+i)# (i+i+i)# i+i+i)# i+i+i)# i+i+i)# i+i+i)# +i+i)# +i+i)# +i+i)# i+i)# i+i)# i+i)# +i)# +i)# +i)# i)# i)# i)# )# )# )# # # # POP,PUSH(i) POP,NEXTSYM POP POP ACCEPT 分析表元素 POP,PUSH(E’T) POP,PUSH(T’F) POP,PUSH(i) POP,NEXTSYM POP,NEXTSYM POP, PUSH()E() POP,NEXTSYM POP,PUSH(E’T) POP,PUSH(T’F) POP,PUSH(i) POP,NEXTSYM POP POP,NEXTSYM POP,PUSH(T’F) POP,PUSH(i) POP,NEXTSYM POP POP,NEXTSYM POP,PUSH(T’F) POP,PUSH(i) POP,NEXTSYM POP POP POP,NEXTSYM POP POP ACCEPT F→i T’→ε E’→ε 所用产生式 E→TE’ T→FT’ F→i F→(E) E→TE’ T→FT’ F→i T’→ε T→FT’ F→i T’→ε T→FT’ F→i T’→ε E’→ε T’→ε E’→ε POP,PUSH(T’F*) T’→*FT’ POP,PUSH(E’T+) E’→+TE’ POP,PUSH(E’T+) E’→+TE’

4.7 考虑下面简化了的C声明文法： <声明语句>→<类型><变量表>； <类型>→int|float|char

<变量表>→ID,<变量表>|ID

（1） 在该文法中提取左因子。

（2） （3） （4） （5） 解： （1）

为所得的文法的非终结符构造FIRST集合和FOLLOW集合。 说明所得的文法是LL(1)文法。 为所得的文法构造LL(1)分析表。 假设有输入串为“char x，y，z；”，写出相对应的LL(1)分析过程。

规则<变量表>→ID,<变量表>|ID提取公因子如下：<变量表>→ID（,<变量表>|ε） 增加新的非终结符<变量表1>，规则变为：

<变量表>→ID<变量表1> <变量表1>→，<变量表>|ε

C声明文法改变为：

<声明语句>→<类型><变量表>；

<类型>→int|float|char <变量表>→ID<变量表1> <变量表1>→，<变量表>|ε

（2） FIRST(<声明语句>)＝FIRST(<类型>)＝｛int，float，char｝

FIRST(<变量表>)＝｛ID｝ FIRST(<变量表1>)＝｛，，ε｝

FOLLOW(<声明语句>)＝｛#｝

FOLLOW(<类型>)＝FIRST(<变量表>)＝｛ID｝ FOLLOW(<变量表>)＝FOLLOW(<变量表1>)＝｛；｝

（3） 所得文法无左递归，且

FIRST（int）∩FIRST（float）∩FIRST（char）＝Φ FIRST（，<变量表>）∩FIRST（ε）＝Φ

FIRST（，<变量表>）∩FOLLOW(<变量表1>)＝Φ 因此，所得文法为LL(1)文法。

（4） 所得的文法构造LL(1)分析表如下所示： <声明语句> ； int POP ， PUSH(；<变量表><类型>) POP ， PUSH(int) float POP ， PUSH(；<变量表><类型>) POP ， PUSH(float) char POP ， PUSH(；<变量表><类型>) POP ， PUSH(char) ID ， # <类型> <变量表> POP ， PUSH(<变量表1>ID) <变量表1> POP POP ， PUSH(<变量

表>，) ； POP, NEXTSYM int POP, NEXTSYM float char ID POP, NEXTSYM POP, NEXTSYM POP, NEXTSYM ， POP, NEXTSYM # ACCEPT ， # 更常用且简单的LL(1)分析表： <声明语句> <类型> <变量表> ； int <声明语句>→<类型><变量表>； <类型>→int float <声明语句>→<类型><变量表>； <类型>→float char <声明语句>→<类型><变量表>； <类型>→char ID <变量表>→ID<变量表1> <变量表1> <变量表1>→ε <变量表1>→,<变量表> （5） 输入串“char x，y，z；”相对应的LL(1)分析过程如下： 步骤 1 分析栈 #<声明语句> 余留输入串 分析表元素 所用产生式 <声明语句>→<类型><变量表>； <类型>→char char x，y，z；# POP ， PUSH(；<变量表><类型>) char x，y，z；# POP ， PUSH(char) 2 3 #；<变量表><类型> #；<变量表> char x，y，z；# POP, char NEXTSYM

4 #；<变量表> x，y，z；# POP ， PUSH(<变量表1>ID) POP, NEXTSYM POP ， PUSH(<变表>，) POP, NEXTSYM POP ， PUSH(<变量表1>ID) POP, NEXTSYM POP ， PUSH(<变表>，) POP, NEXTSYM POP ， PUSH(<变量表1>ID) POP, NEXTSYM POP POP, NEXTSYM ACCEPT 量量<变量表>→ID<变量表1> <变量表1>→，<变量表> <变量表>→ID<变量表1> <变量表1>→，<变量表> <变量表>→ID<变量表1> <变量表1>→ε 5 6 #；<变量表1>x x，y，z；# #；<变量表1> ，y，z；# 7 8 #；<变量表>， #；<变量表> ，y，z；# y，z；# 9 10 #；<变量表1>y y，z；# #；<变量表1> ，z；# 11 12 #；<变量表>， #；<变量表> ，z；# z；# 13 14 15 16

#；<变量表1>z z；# #；<变量表1> #； # ；# ；# #

5.1 考虑以下的文法： S→S;T|T T→a

（1） 为这个文法构造LR(0)的项目集规范族。

（2） 这个文法是不是LR(0)文法？如果是，则构造LR(0)分析表。 （3） 对输入串“a;a”进行分析。 解：

（1）拓广文法G[S’]： 0：S’→S 1：S→S;T 2：S→T 3：T→a

构造LR(0)项目集规范族 状态 0 项目集 S’→·S S→·S;T S→·T T→·a S’→S· S→S·;T S→T· T→a· S→S;·T T→·a S→S;T· 转换函数 GO[0，S]＝1 GO[0，S]＝1 GO[0，T]＝2 GO[0，a]＝3 ACCEPT GO[1，;]＝4 R2 R3 GO[4，T]＝5 GO[4，a]＝3 R1 1 2 3 4 5

（2）该文法不存在“归约－归约”和“归约－移进”冲突，因此是LR(0)文法。LR(0)分析表如下： 状态 0 ACTION ； a S3 # S 1 GOTO T 2

1 2 3 4 5 S4 R2 R3 R1 R2 R3 S3 R1 ACCEPT R2 R3 R1 5

（3）对输入串“a;a”进行分析如下： 步骤 0 1 3 4 5 6 7 8 状态栈 0 03 02 01 014 0143 0145 01 符号栈 # #a #T #S #S; #S;a #S;T #S 输入符号栈 ACTION a;a# ;a# ;a# ;a# a# # # # S3 R3 R2 S4 S3 R3 R1 ACCEPT GOTO 2 1 5 1

5.2 证明下面文法是SLR(1)文法，但不是LR(0)文法。 S→A

A→Ab|bBa B→aAc|a|aAb 解：文法G[S]： 0：S→A 1：A→Ab 2：A→bBa 3：B→aAc 4：B→a 5：B→aAb

构造LR(0)项目集规范族： 状态 0 项目集 S→·A A→·Ab A→·bBa S→A· A→A·b A→b·Ba B→·aAc B→·a B→·aAb A→Ab· A→bB·a 转换函数 GO[0，A]＝1 GO[0，A]＝1 GO[0，b]＝2 ACCEPT GO[1，b]＝3 GO[2，B]＝4 GO[2，a]＝5 GO[2，a]＝5 GO[2，a]＝5 R1 GO[4，a]＝6 1 2 3 4

5 B→a·Ac B→a· B→a·Ab A→·Ab A→·bBa A→bBa· B→aA·c B→aA·b A→A·b B→aAc· B→aAb· A→Ab· GO[5，A]＝7 R4 GO[5，A]＝7 GO[5，A]＝7 GO[5，b]＝2 R2 GO[7，c]＝8 GO[7，b]＝9 GO[7，b]＝9 R3 R5 R1 6 7 8 9 状态5存在“归约－移进”冲突，状态9存在“归约－归约”冲突，因此该文法不是LR(0)文法。 状态5：

FOLLOW(B)＝｛a｝，因此，FOLLOW(B)∩｛b｝＝Φ 状态9：

FOLLOW(B)＝｛a｝，FOLLOW(A)＝｛#，b，c｝，因此FOLLOW(B)∩FOLLOW(A)＝Φ 状态5和状态9的冲突均可用SLR(1)方法解决，构造SLR(1)分析表如下： 状态 0 1 2 3 4 5 6 7 8 9 ACTION a S5 S6 R4 R3 R5 R1 b S2 S3 R1 S2 R2 S9 c R1 R2 S8 R1 R1 # ACCEPT R1 R2 A 1 7 GOTO B 4 该SLR(1)分析表无重定义，因此该文法是SLR(1)文法，不是LR(0)文法。

5.3 证明下面文法是LR(1)文法，但不是SLR(1)文法。 S→AaAb|BbBa A→ε B→ε

解：拓广文法G[S’]： 0：S’→S 1：S→AaAb 2：S→BbBa 3：A→ε 4：B→ε

构造LR(0)项目集规范族： 状态 0 项目集 S’→·S S→·AaAb S→·BbBa A→· B→· S’→S· S→A·aAb S→B·bBa S→Aa·Ab A→· S→Bb·Ba B→· S→AaA·b S→BbB·a S→AaAb· S→BbBa· 转换函数 GO[0，S]＝1 GO[0，A]＝2 GO[0，B]＝3 R3 R4 ACCEPT GO[2，a]＝4 GO[3，b]＝5 GO[4，A]＝6 R3 GO[5，B]＝7 R4 GO[6，b]＝8 GO[7，a]＝9 R1 R2 1 2 3 4 5 6 7 8 9 状态0存在“归约－归约”冲突，且FOLLOW(A) ＝｛a,b｝，FOLLOW(B)＝｛a,b｝，即FOLLOW(A)∩FOLLOW(B)＝｛a,b｝≠Φ，所以该文法不是SLR(1)文法。

构造LR(1)项目集规范族： 状态 0 项目集 S’→·S，# S→·AaAb，# S→·BbBa，# A→·，a B→·，b S’→S·，# S→A·aAb，# S→B·bBa，# S→Aa·Ab，# A→·，b S→Bb·Ba，# B→·，a S→AaA·b，# S→BbB·a，# S→AaAb·，# S→BbBa·，# ACTION a R3 b R4 # S 1 转换函数 GO[0，S]＝1 GO[0，A]＝2 GO[0，B]＝3 R3 R4 ACCEPT GO[2，a]＝4 GO[3，b]＝5 GO[4，A]＝6 R3 GO[5，B]＝7 R4 GO[6，b]＝8 GO[7，a]＝9 R1 R2 GOTO A 2 B 3 1 2 3 4 5 6 7 8 9 LR(1)分析表： 状态 0

1 2 3 4 5 6 7 8 9 S4 R4 S9 S5 R3 S8 ACCEPT R1 R2 6 7 分析表无重定义，说明该文法是LR(1)文法，不是SLR(1)文法。

5.4 考虑以下的文法： E→EE＋ E→EE* E→a

（1）为这个文法构造LR(1)项目集规范族。 （2）构造LR(1)分析表。

（3）为这个文法构造LALR(1)项目集规范族。 （4）构造LALR(1)分析表。

（5）对输入符号串“aa*a+”进行LR(1)和LALR(1)分析。 解：

（1）拓广文法G[S]： 0：S→E 1：E→EE＋ 2：E→EE* 3：E→a

构造LR(1)项目集规范族： 状态 0 项目集 S→·E ，# E→·EE＋ ，a:# E→·EE* ，a:# E→·a ，a:# S→E· ，# E→E·E＋ ，a:# E→E·E* ，a:# E→·EE＋ ，*:+ E→·EE* ，*:+ E→·a ，*:+ E→a· ，a:# E→EE·＋ ，a:# E→EE·* ，a:# E→E·E＋ ，*:+ E→E·E* ，*:+ E→·EE＋ ，*:+ 转换函数 GO[0，E]＝1 GO[0，E]＝1 GO[0，E]＝1 GO[0，a]＝2 ACCEPT GO[1，E]＝3 GO[1，E]＝3 GO[1，E]＝3 GO[1，E]＝3 GO[1，a]＝4 R3 GO[3，＋]＝5 GO[3，*]＝6 GO[3，E]＝7 GO[3，E]＝7 GO[3，E]＝7 1 2 3

E→·EE* ，*:+ E→·a ，*:+ 4 5 6 7 E→a· ，*:+ E→EE＋· ，a:# E→EE*· ，a:# E→EE·＋ ，*:+ E→EE·* ，*:+ E→E·E＋ ，*:+ E→E·E* ，*:+ E→·EE＋ ，*:+ E→·EE* ，*:+ E→·a ，*:+ E→EE＋· ，*:+ E→EE*· ，*:+ GO[3，E]＝7 GO[3，a]＝4 R3 R1 R2 GO[7，+]＝8 GO[7，*]＝9 GO[7，E]＝7 GO[7，E]＝7 GO[7，E]＝7 GO[7，E]＝7 GO[7，a]＝4 R1 R2 8 9

（2）构造LR(1)分析表 状态 0 1 2 3 4 5 6 7 8 9 ACTION ＋ S5 R3 S8 R1 R2 * S6 R3 S9 R1 R2 a S2 S4 R3 S4 R1 R2 S4 # ACCEPT R3 R1 R2 GOTO E 1 3 7 7

（3）构造LALR(1)项目集规范族: 状态 0 项目集 S→·E ，# E→·EE＋ ，a:# E→·EE* ，a:# E→·a ，a:# S→E· ，# E→E·E＋ ，a:# E→E·E* ，a:# E→·EE＋ ，*:+ E→·EE* ，*:+ E→·a ，*:+ E→a· ，a:#:*:+ E→EE·＋ ，a:#:*:+ 转换函数 GO[0，E]＝1 GO[0，E]＝1 GO[0，E]＝1 GO[0，a]＝2 ACCEPT GO[1，E]＝3 GO[1，E]＝3 GO[1，E]＝3 GO[1，E]＝3 GO[1，a]＝2 R3 GO[3，＋]＝4 1 2 3

E→EE·* ，a:#:*:+ E→E·E＋ ，*:+ E→E·E* ，*:+ E→·EE＋ ，*:+ E→·EE* ，*:+ E→·a ，*:+ 4 5 E→EE＋· ，a:#:*:+ E→EE*· ，a:#:*:+ GO[3，*]＝5 GO[3，E]＝3 GO[3，E]＝3 GO[3，E]＝3 GO[3，E]＝3 GO[3，a]＝2 R1 R2

（4）构造LALR(1)分析表。 状态 0 1 2 3 4 5 ACTION ＋ R3 S4 R1 R2 * R3 S5 R1 R2 a S2 S2 R3 S2 R1 R2 # ACCEPT R3 R1 R2 GOTO E 1 3 3 （5）对输入符号串“aa*a+”进行LR(1)分析: 步骤 1 2 3 4 5 6 7 8 9 10 11 状态栈 0 02 01 014 013 0136 01 014 013 0135 01 符号栈 # #a #E #Ea #EE #EE* #E #Ea #EE #EE+ #E 输入串 aa*a+# a*a+# a*a+# *a+# *a+# a+# a+# +# +# # # ACTION GOTO S2 R3 S4 R3 S6 R2 S4 R3 S5 R1 1 3 1 3 1 ACCEPT

对输入符号串“aa*a+”进行LALR(1)分析: 步骤 1 2 3 4 5 6 7 8 状态栈 0 02 01 012 013 0135 01 012 符号栈 # #a #E #Ea #EE #EE* #E #Ea 输入串 aa*a+# a*a+# a*a+# *a+# *a+# a+# a+# +# ACTION GOTO S2 R3 S2 R3 S5 R2 S2 R3 1 3 1 3

9 10 11 013 0134 01 #EE #EE+ #E +# # # S4 R1 1 ACCEPT

5.5 说明以下的文法是LR(1)文法，但不是LALR(1)文法。 S→aAd|bBd|aBe|bAe A→c B→c 解：

拓广文法： 0：S’→S 1：S→aAd 2：S→bBd 3：S→aBe 4：S→bAe 5：A→c 6：B→c

构造LR(1)项目集规范族 状态 0 项目集 S’→·S，# S→·aAd，# S→·bBd，# S→·aBe，# S→·bAe，# S’→S· ，# S→a·Ad，# S→a·Be，# A→·c，d B→·c，e S→b·Bd，# S→b·Ae，# A→·c，e B→·c，d S→aA·d，# S→aB·e，# A→c· ，d B→c· ，e S→bB·d，# S→bA·e，# A→c· ，e B→c· ，d S→aAd· ，# S→aBe· ，# 转换函数 GO[0，S]＝1 GO[0，a]＝2 GO[0，b]＝3 GO[0，a]＝2 GO[0，b]＝3 ACCEPT GO[2，A]＝4 GO[2，B]＝5 GO[2，c]＝6 GO[2，c]＝6 GO[3，B]＝7 GO[3，A]＝8 GO[3，c]＝9 GO[3，c]＝9 GO[4，d]＝10 GO[5，e]＝11 R5 R6 GO[7，d]＝12 GO[8，e]＝13 R5 R6 R1 R3 1 2 3 4 5 6 7 8 9 10 11

12 13 S→bBd· ，# S→bAe· ，# R2 R4

构造LR(1)分析表： 状态 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ACTION a S2 b S3 c S6 S9 d S10 R5 S12 R6 e S11 R6 S13 R5 # ACCEPT R1 R3 R2 R4 S 1 GOTO A 4 8 B 5 7

同核项目集合并，构造LALR(1)项目集规范族： 状态 0 项目集 S’→·S，# S→·aAd，# S→·bBd，# S→·aBe，# S→·bAe，# S’→S· ，# S→a·Ad，# S→a·Be，# A→·c，d B→·c，e S→b·Bd，# S→b·Ae，# A→·c，e B→·c，d S→aA·d，# S→aB·e，# A→c· ，d:e B→c· ，d:e S→bB·d，# S→bA·e，# 转换函数 GO[0，S]＝1 GO[0，a]＝2 GO[0，b]＝3 GO[0，a]＝2 GO[0，b]＝3 ACCEPT GO[2，A]＝4 GO[2，B]＝5 GO[2，c]＝6 GO[2，c]＝6 GO[3，B]＝7 GO[3，A]＝8 GO[3，c]＝6 GO[3，c]＝6 GO[4，d]＝9 GO[5，e]＝10 R5 R6 GO[7，d]＝11 GO[8，e]＝12 1 2 3 4 5 6 7 8

9 10 11 12 S→aAd· ，# S→aBe· ，# S→bBd· ，# S→bAe· ，# R1 R3 R2 R4

构造LALR(1)分析表： 状态 0 1 2 3 4 5 6 7 8 9 10 11 12 ACTION a S2 b S3 c S6 S9 d S10 S12 e S11 S13 # ACCEPT R1 R3 R2 R4 S 1 GOTO A 4 8 B 5 7 R5/R6 R5/R6 从LR(1)分析表可以看出，分析表无重定义，因此该文法是LR(1)文法。 从LALR(1)分析表可以看出，分析表ACTION[6,d]和ACTION[6,e]存在重定义，因此该文法不是LALR(1)文法。

7.1 给出编译下面程序的有序符号表。 main() {

int m,n[5]; real x;

char name; } 解： 名字 m n x 类型 int int real 维数 0 1 0 0 main keyword 0 name char 7.2 按“质数除余法”，给出编译上题程序的散列符号表。 解：正整数H＝ASC函数（字符串），质数＝5，散列符号表如下所示： 名字 m main n name x 正整数 109 421 110 417 120 H%5 4 1 0 2 0 位置 0 1 2 3 4 名字域 n main name m 属性域 x 7.3 给出编译到下面程序a、b、c处的栈式符号表。 real x,y;

char str;………………………………a int fun1(int ind) {

int x; ……………………………b x=m2(ind+1); }

main() {

char y; …………………………c

x=2;y=5; printf(\ } 解：

a： Top str y x 0

b：

Top x ind fun1 str y 4 x 0 c：

Top y main fun1 str y 5 x 0

10.1 对下列基本块应用DAG进行优化： (=，3， ，B) (+，A，C，D) (*，A，C，E) (+，D，E，F) (*，B，F，G) (+，A，C，H) (*，A，C，I) (+，H，I，J) (*，B，5，K) (+，K，J，L) (=，L， ，M)

解：构造DAG如下：

G n7 * B n1 3 n8 15 D,H n4 + n2 A K n6 + E,I n5 * n3 C L,M n9 + F,J

按照上图的DAG结点顺序，优化后生成的程序如下： (=，3， ，B) (+，A，C，D) (=，D， ，H) (*，A，C，E) (=，E， ，I)

(+，D，E，F) (=，F， ，J) (*，3，F，G) (=，15， ，K) (+，15，J，L) (=，L， ，M)

10.2 对下面程序段画出程序流图，并进行循环优化。 I=1; J=10; K=5; L1:X=K*I; Y=J*I; Z=X*Y; I=I+1

IF I<100 GOTO L1; 解：程序流图如下： B1：I=1; J=10; K=5; B2：X=K*I; Y=J*I; Z=X*Y; I=I+1; IF I<100 GOTO B2; 从程序流图可知，要优化的循环是基本块B2。对循环B2中代码分别实行代码外提、强度删弱和删除归纳变量优化如下：

（1） 代码外提：循环中无不变运算、 （2） 强度删弱：由于循环中有 X=K*I; Y=J*I;

其中，K，J在循环中值不发生改变，I每次增加1。因此，对X，Y可进行强度删弱，将乘法运算（*）改为加法运算（＋）。强度删弱后程序流图如下图所示：

Y

B1：I=1; J=10; K=5; B2’：X=K*I; Y=J*I; B2：Z=X*Y; X=X＋K; Y=Y＋J; I=I+1; IF I<100 GOTO B2; （3） 删除基本归纳变量：循环中I是基本归纳变量，X、Y是与I同族的归纳变量，且有

如下线性关系：

X=K*I; Y=J*I;

于是，条件I<100可用X

本文来源：https://www.bwwdw.com/article/0qxw.html