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

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

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

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

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 句子abba合法。

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

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

Z::=Ab|b

A::=Aa|a

S::=aA|b A::=aA|b

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

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

V={S,A,a,b} Vn={S,A} 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 0 0 A 1 ε Z 4、

q0 1 0 0,1 q2 q1

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

0 1 0 4 3 1 1 1 1 ε 0 1 0 8 6 0 1 7 2 5 0 3.4 将图3.36的NFA M确定化

a 0 a,b a 1

图3.36 状态图

解： q0={0} q1={0,1} q2={1} DFA:

a {0,1} {0,1} {0} b {1} {1} Φ

a a q0 b q2 3.5 将图3.37的DFA化简。

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

图3.37 DFA状态图

a {1} {1,3,0,5} b {2,4} {3,5,2,4} a b

{0,1} {2,4} {3,5} q0={0,1}

{1} {0,1} {3,5} q1={2,4}

q2={3,5}

{2,4} {3,5} {2,4} 化简后的DFA：

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

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

过程S N INPUTSYM=’a’ Y INPUTSYM=下一个符号 b q1 b q2 a

N INPUTSYM=’(’ Y INPUTSYM=下一个符号 错误 过程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=下一个符号 错误 错误 表达式 出口

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)分析表： <声明语句> <类型> <变量表> <变量表1> ； int <声明语句>→<类型><变量表>； <类型>→int float <声明语句>→<类型><变量表>； <类型>→float char <声明语句>→<类型><变量表>； <类型>→char ID <变量表>→ID<变量表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 4 #；<变量表> x，y，z；# NEXTSYM 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 1 2 3 4 5 ACTION ； S4 R2 R3 R1 a S3 R2 R3 S3 R1 # ACCEPT R2 R3 R1 S 1 GOTO T 2 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 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[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 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 1 2 3 4 5 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 ACTION a S5 b S2 S3 R1 c R1 # ACCEPT R1 A 1 GOTO B 4

4 5 6 7 8 9 S6 R4 R3 R5 R1 S2 R2 S9 R2 S8 R1 R1 R2 7 该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 S4 R4 S9 b R4 S5 R3 S8 # 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 S 1 A 2 6 B 3 7 1 2 3 4 5 6 7 8 9 LR(1)分析表： 状态 0 1 2 3 4 5 6 7 8 9 ACCEPT R1 R2 分析表无重定义，说明该文法是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＋ ，*:+ E→·EE* ，*:+ E→·a ，*:+ 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[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 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 1 2 3 4 5 6 7 8 9

（2）构造LR(1)分析表 状态 0 1 2 3 ACTION ＋ S5 * S6 a S2 S4 R3 S4 # ACCEPT R3 GOTO E 1 3 7

4 5 6 7 8 9 R3 S8 R1 R2 R3 S9 R1 R2 R1 R2 S4 R1 R2 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:#:*:+ E→EE·* ，a:#:*:+ E→E·E＋ ，*:+ E→E·E* ，*:+ E→·EE＋ ，*:+ E→·EE* ，*:+ E→·a ，*:+ E→EE＋· ，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 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 1 2 3 4 5 （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 状态栈 0 符号栈 # 输入串 aa*a+# ACTION GOTO S2

2 3 4 5 6 7 8 9 10 11 02 01 014 013 0136 01 014 013 0135 01 #a #E #Ea #EE #EE* #E #Ea #EE #EE+ #E a*a+# a*a+# *a+# *a+# a+# a+# +# +# # # 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 9 10 11 状态栈 0 02 01 012 013 0135 01 012 013 0134 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 S2 R3 S5 R2 S2 R3 S4 R1 1 3 1 3 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，# 转换函数 GO[0，S]＝1 GO[0，a]＝2

S→·bBd，# S→·aBe，# S→·bAe，# 1 2 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· ，# S→bBd· ，# S→bAe· ，# 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 R2 R4 3 4 5 6 7 8 9 10 11 12 13 构造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

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