编译原理作业答案

《编译原理》习题解答：

第一次作业：

P14 2、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间可能有何种关系？

答：被翻译的程序称为源程序；

翻译出来的程序称为目标程序或目标代码；

将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻译程序；

把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序；

解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读入源程序，即边解释边执行；

编译程序是将高级语言写的源程序翻译成目标语言的程序。

关系：汇编程序、解释程序和编译程序都是翻译程序，具体见P4 图 1.3。

P14 3、编译程序是由哪些部分组成？试述各部分的功能？ 答：编译程序主要由8个部分组成：（1）词法分析程序；（2）语法分析程序；（3）语义分析程序；（4）中间代码生成；（5）代码优化程序；（6）目标代码生成程序；（7）错误检查和处理程序；（8）信息表管理程序。具体功能见P7-9。

P14 4、语法分析和语义分析有什么不同？试举例说明。

答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：对变量 x：= y 符合语法规则就通过。语义分析是对语句意义进行检查，如赋值语句中x与y类型要一致，否则语法分析正确，语义分析则错误。

补充：为什么要对单词进行内部编码？其原则是什么？对标识符是如何进行内部编码的？ 答：内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。对于标识符编码，先判断出该单词是标识符，然后在类别编码中写入相关信息，以表示为标识符，再根据具体标识符的含义编码该单词的值。

１

第二次作业：

P38 1、设T1＝{11，010}，T2＝{0，01，1001}，计算：T2T1，T1*，T2+。 T2T1＝{011，0010，0111，01010，100111，1001010} T1*＝{ε，11，010，1111，11010，01011，010010??} T2+＝{0，01，1001，00，001，01001，010，0101??} P38-39 8、设有文法G[S]：

S∷＝aAb A∷＝BcA | B B∷＝idt |ε

试问下列符号串（1）aidtcBcAb （2）aidtccb（4）abidt是否为该文法的句型或句子。 （1）S?aAb?aBcAb?aidtcAb?aidtcBcAb 句型但不是句子；

（2）S?aAb?aBcAb?aidtcAb?aidtcBcAb?aidtccAb?aidtccBb?aidtccb；是句型也是句子；

（4）该文法的句子或句型的最后一个字符串一定是字符“b”；

２

第三次作业：

P39 11、试分别描述下列文法所产生的语言（文法开始符号为S）：

（1） S∷＝0S | 01 （2） S∷＝aaS | bc

（1） L(G)＝{0n1| n≥1}； {解题思路：将文法转换为正规表达式} （2） L(G)＝{a2nbc | n≥0}。

P39 12、试分别构造产生下列语言的文法： （1）{ abna | n=0，1，2，3??} （3）{ aban | n≥1}

（5）{ anbmcp | n，m，p≥0}

（1）G＝{VN，VT，P，S}，VN＝{S，A }，VT＝{a，b}，

P：S∷＝aAa A∷＝bA |ε

（3）G＝{VN，VT，P，S}，VN＝{S，A }，VT＝{a，b}，

P：S∷＝abA A∷＝aA | a

（5）①G＝{VN，VT，P，S}，VN＝{S，A ，B，C}，VT＝{a，b，c}，

P：S∷＝ABC A∷＝aA |ε B∷＝bB |ε C∷＝cC |ε

②G＝{VN，VT，P，S}，VN＝{S}，VT＝{a，b，c}，

P：S∷＝aS | bS | cS |ε

P39 15. 设文法G规则为：

S：：=AB B：：=a|Sb A：：=Aa|bB

对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。 （2）baabaab (3)bBABb 解（2） S

A B A a S b

b B A B

a b B a

a 句型baabaab的短语a, ba, baa, baab, baabaab，简单短语a，句柄 a

３

S （3）

A B b B S b A B 短语bB, AB, ABb，bBABb 简单短语bB, AB， 句柄bB

４

第四次作业

P41 24. 下面文法那些是短语结构文法，上下文有关文法，上下文无关文法，及正规文法？

1.S::=aB B::= cB B::=b C::=c 2.S::=aB B::=bC C::=c C::=ε

3.S::=aAb aA::=aB aA::=aaA B::=b A::=a 4.S::=aCd aC::=B aC::=aaA B::=b 5.S::=AB A::=a B::=bC B::=b C::=c 6. S::=AB A::=a B::=bC C::=c C::=ε

7. S::=aA S::= ε A::=aA A::=aB A::=a B::=b 8. S::=aA S::= ε A::=bAb A::=a 短语结构文法（0） 4 上下文有关文法（1） 3

上下文无关文法（2） 5 6 8 或者 2 5 6 7 正规文法（3） 1 2 7 或者 1

P42 29. 用扩充的BNF表示以下文法规则：

1． Z::=AB|AC|A

2． A::=BC|BCD|AXZ|AXY 3． S::=aABb|ab 4． A::=Aab|ε

解:

1．Z::=A（B|C|ε）::=A[B|C]

2．A::=BC（ε|D）|{X（Z|Y）}::= BC[D]|{X（Z|Y）} 3．A::=a((AB|ε)b) ::= a[AB]b 4．A::={ab|ε}::={ab}

５

8

第五次作业：

P74 4. 画出下列文法的状态图：

Z：：=Be B：：=Af A：：=e|Ae 并使用该状态图检查下列句子是否该文法的合法句子：f, eeff, eefe。

由状态图可知只有eefe是该文法的合法句子。

P74 5. 设右线性文法G=({S, A, B}, {a, b}, S, P)，其中P组成如下：

S：：=bA A：：=bB A：：=aA A：：=b B：：=a 画出该文法的状态转换图。

P74 6. 构造下述文法G[Z]的自动机，该自动机是确定的吗？它相应的语言是什么？ Z：：=A0 A：：=A0|Z1|0

解1：将左线性文法转换为右线性文法，由于在规则中出现了识别符号出现在规则右部的情形，因此不能直接使用书上的左右线性文法对应规则，可以引入非终结符号B，将左线性文法变为Z：：=A0 A：：=A0|B1|0 B：：=A0，具体为：

A := Z1 A := B1

A := A01 Z := A0 B := A0 将所得的新左线性文法转换成右线性文法： 此时利用书上规则，其对应的右线性文法为：A：：=0A|0B|0 Z：：=0A B：：=1A

解2：先画出该文法状态转换图：

６

NFA=（{S，A，Z}，{0，1}，M，{S}，{Z}）

其中M： M（S，0）={A} M（S，1）=? M（A，0）={A，Z} M（A，1）=? M（Z，0）=? M（Z，1）={A}

显然该文法的自动机是非确定的；它相应的语言为：{0，1}上所有满足以00开头以0结尾且每个1必有0直接跟在其后的字符串的集合；那么如何构造其相应的有穷自动机呢？ 先构造其转换系统： 0 ε S’ 0 0 S

A ε Z Z’

1

根据其转换系统可得状态转换集、状态子集转换矩阵如下表所示： I {S’, S} {A} {A, Z, Z’} I0 {A} {A, Z, Z’} {A, Z, Z’} I1 Ф Ф {A} S 0 1 2 0 1 1 Ф 2 Ф 2 1 则其相应的DFA为： 0

1 0 0 1 2

0

P74 8. 设 (NFA) M = ( {A, B}, {a, b}, M, {A}, {B} )，其中M定义如下：

M (A, a) = {A, B} M (A, b) = {B} M (B, a) = ? M (B, b) = {A, B}

请构造相应确定有穷自动机(DFA) M’。

解：构造一个如下的自动机(DFA) M’， (DFA) M’={K, {a, b}, M’, S, Z}

K的元素是[A] [B] [A, B]

由于M（A, a）={A, B}，故有M’（[A], a）=[A, B] 同样 M’（[A]，b）=[B]

M’（[B]，a）= ?

M’（[B]，b）=[A，B]

由于M（{A，B}，a）= M（A，a）U M（B，a）= {A，B}U ?= {A，B} 故 M’（[A，B]，a）= [A，B]

由于M（{A，B}，b）= M（A，b）U M（B，b）={B}U {A，B} = {A，B} 故 M’（[A，B]，b）= [A，B]

７

S=[A]，终态集Z={[A，B]，[B]}

重新定义：令0=[A] 1=[B] 2=[A, B]，则DFA如下所示：

可以进一步化简，把M’的状态分成终态组{1，2}和非终态组{0}

由于{1，2}a={1，2}b={2}?{1，2}，不能再划分。至此，整个划分含有两组{1，2}{0} 令状态1代表{1，2}，化简如图：

８

第六次作业：

P74 11（1）(0 | 11*0)*

解：先构造该正规式的转换系统：

(0 | 11*0)* S 0 ε 1 1 2 ε ε 1 0 4 ε Z Z S

0

ε ε

S 1 Z

11*0

由上述转换系统可得状态转换集K={S, 1, 2, 3, 4, Z}，状态子集转换矩阵如下表所示： I {S, 1, Z} {1, Z} {2, 3, 4} {3, 4}

0 0 1

1 1 0 3 1 02 1 1

0

I0 {1, Z} {1, Z} {1, Z} {1, Z} I1 {2, 3, 4} {2, 3, 4} {3, 4} {3, 4} K 0 1 2 3 3 0 1 1 2 1 2 1 3 1 3 由状态子集转换矩阵可知，状态0和1是等价的，而状态2和3是等价的，因此，合并等价状态之后只剩下2个状态，也即是最少状态的DFA。

1 1 a

1 0

0

P74 12. 将图3.24非确定有穷自动机NFA确定化和最少化。 a, b 1 0 a NFA状态转换图 图3.24

解：设(DFA)M = {K, VT, M, S, Z}，其中，K={[0], [0, 1], [1]}，VT ={a, b}，M：

９

1 1

M ([1], a) =[0] M ([1], b) =Ф M ([0, 1], a) =[0, 1] M ([0, 1], b) =[1] M ([0], a) =[0, 1] M ([0], b) =[1] S=[1]，Z={[0], [0, 1]}

令[0, 1]=2，则其相应的状态转换图为： b 现在对该DFA进行化简，先把状态分为两组： 1 0 终态组 {0, 2} 和非终态组 {1}，易于发现 {0, 2} a 不可以继续划分，因此化简后的状态转换图如下： a a b b 2

1 0, 2

a a

P74 18. 根据下面正规文法构造等价的正规表达式：

S::=cC | a ??① A::=cA | aB ??② B::=aB | c ??③

C::=aS | aA | bB | cC | a ??④ 解：由③式可得 B= aB + c → B=a*c

由②式可得 A= cA + aB → A= c*aa*c 由①式可得 S= cC + a

由④式可得 C= aS + aA + bB + cC + a → C= c*( aS + aA + bB + a) →

C= c*( aS + ac*aa*c + ba*c + a) → S= cc*( aS + ac*aa*c + ba*c + a) + a = cc*aS+ cc*( ac*aa*c + ba*c + a) + a = (cc*a)*( cc*( ac*aa*c + ba*c + a) + a) = (cc*a)*( cc*( ac*aa*c | ba*c | a) | a) 另一种答案是S= c(ac | c)*( ac*aa*c | ba*c | aa | a) | a

１０

（1）改写为LL（1）文法：

S∷＝bB{aB} A∷＝Sa B∷＝Ac （4）

FIRST(S)={ b }, FIRST(A)={b}, FIRST(B)={b},

FOLLOE(S)={a，＃}, FOLLOW(A)={ c}, FOLLOW(B)={a，＃}. S A B a b S∷＝bB{aB} A∷＝Sa B∷＝Ac c # P144 10. 证明下述文法不是简单优先文法： （1） S∷＝bEb

E∷＝E+T | T （2） S∷＝bEb

E∷＝F | F+T | T | i T∷＝i | (E) 证明：

(1)画语法树： S

╱ │ ╲ b E b ╱ │ ╲ E + T

可以得出b=E和b

T∷=i

右部两个产生式相同，故该文法不是简单优先文法.

P145 11. 构造下述文法的优先关系矩阵，它们是简单优先文法吗？ S∷＝M | U

M∷＝iEtMeM | a U∷＝iEtS | iEtMeU E∷＝b

解：

１６

S M U E i t e a b S M U E i t e a b S 0 0 0 0 0 0 0 0 0 S 0 1 1 0 0 0 0 0 0 M 0 0 0 0 0 0 1 0 0 M 0 0 0 0 1 0 0 1 0 U 0 0 0 0 0 0 0 0 0 U 0 0 0 0 1 0 0 0 0 = E 0 0 0 0 0 1 0 0 0 = E 0 0 0 0 0 0 0 0 1 B BL

i 0 0 0 1 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 t 1 1 0 0 0 0 0 0 0 t 0 0 0 0 0 0 0 0 0 e 0 1 1 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 b 0 0 0 0 0 0 0 0 0 b 0 0 0 0 0 0 0 0 0 S M U E i t e a b S M U E i t e a b S 0 0 0 0 0 0 0 0 0 S 0 1 1 0 M 0 0 0 0 0 0 1 0 0 M 0 0 0 0 1 0 0 1 0 U 0 0 0 0 0 0 0 0 0 U 0 0 0 0 1 0 0 0 0 B

L 2 = i 0 0 0 1 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 t 1 1 0 0 0 0 0 0 0 t 0 0 0 0 0 0 0 0 0 e 0 1 1 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 b 0 0 0 0 0 0 0 0 0 b 0 0 0 0 0 0 0 0 0 B S M U E i t e a b S M U E i t e a b S 0 0 0 0 0 0 0 0 0 S 0 1 1 0 0 0 0 0 0 M 0 0 0 0 0 0 0 0 0 M 0 1 0 0 0 0 0 1 0 U 0 0 0 0 0 0 0 0 0 U 1 0 1 0 0 0 0 0 0 B = i 0 0 0 0 0 0 0 0 1 i 0 0 0 0 0 0 0 0 0 t 0 1 1 0 1 0 0 1 0 t 0 0 0 0 0 0 0 0 0 e 0 0 0 0 1 0 0 1 0 e 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 b 0 0 0 0 0 0 0 0 0 b 0 0 0 0 0 0 0 0 0

S M U E i t e a b S M U E i t e a b S 1 1 1 0 0 0 0 1 0 S 1 1 1 0 0 0 0 1 0 M 0 1 0 0 0 0 0 1 0 M 0 1 0 0 0 0 0 1 0 U 1 1 1 0 0 0 0 0 0 U 1 1 1 0 0 0 0 1 0 B R2

= i 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 t 0 0 0 0 0 0 0 0 0 t 0 0 0 0 0 0 0 0 0

= B × BL+

1 0 0 1 0 BL+

BR

B R3 １７

E 0 0 0 0 0 1 0 0 0 = E 0 0 0 0 0 0 0 0 1 E 0 0 0 0 0 0 0 0 0 = E 0 0 0 0 0 0 0 0 1

E 0 0 0 0 0 0 0 0 0 = E 0 0 0 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 b 0 0 0 0 0 0 0 0 0 b 0 0 0 0 0 0 0 0 0 S M U E i t e a b S M U E i t e a b S 1 1 1 0 0 0 0 1 0 S 1 0 1 0 0 0 0 0 0 M 0 1 0 0 0 0 0 1 0 M 1 1 1 0 0 0 0 0 0 U 1 1 1 0 0 0 0 1 0 U 1 0 1 0 0 0 0 0 0 = E 0 0 0 0 0 0 0 0 1 = E 0 0 0 0 0 0 0 0 0 B R+ B (R+)T

*= E 0 0 0 1 0 0 0 0 1 E 0 0 0 0 0 0 0 0 0 L B

i 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 t 0 0 0 0 0 0 0 0 0 t 0 0 0 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 a 1 1 1 0 0 0 0 0 0 b 0 0 0 0 0 0 0 0 0 b 0 0 0 1 0 0 0 0 0

S M U E i t e a b S M U E i t e a b

S 1 1 1 0 1 0 0 1 0 S 0 0 0 0 0 0 0 0 0 M 0 1 0 0 1 0 0 1 0 M 0 0 0 0 0 0 1 0 0 U 0 0 1 0 1 0 0 0 0 = U 0 0 0 0 0 0 0 0 0 B (R+)T ×B i 0 0 0 0 1 0 0 0 0 i 0 0 0 0 0 0 0 0 0 t 0 0 0 0 0 1 0 0 0 t 0 0 0 0 0 0 0 0 0 e 0 0 0 0 0 0 1 0 0 e 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 1 0 a 0 0 0 0 0 0 1 0 0 b 0 0 0 0 0 0 0 0 1 b 0 0 0 0 0 1 0 0 0

S M U E i t e a b S M U E i t e a b

S 0 0 0 0 0 0 0 0 0 S 1 1 1 0 1 0 0 1 0 M 0 0 0 0 0 0 1 0 0 M 0 1 0 0 1 0 0 1 0 U 0 0 0 0 0 0 0 0 0 U 0 0 1 0 1 0 0 0 0 = B = E 0 0 0 0 0 0 0 0 0 × E 0 0 0 1 0 0 0 0 1 B (R+)T × B ×BL*

i 0 0 0 0 0 0 0 0 0 i 0 0 0 0 1 0 0 0 0 t 0 0 0 0 0 0 0 0 0 t 1 1 0 0 0 1 0 0 0 e 0 0 0 0 0 0 0 0 0 e 0 1 1 0 0 0 1 0 0 a 0 0 0 0 0 0 1 0 0 a 0 0 0 0 0 0 0 1 0 b 0 0 0 0 0 1 0 0 0 b 0 0 0 0 0 0 0 0 1 S M U E i t e a b S 0 0 0 0 0 0 0 0 0 M 0 0 0 0 0 0 1 0 0 U 0 0 0 0 0 0 0 0 0 = E 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 t 0 0 0 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 1 0 0 １８

b 0 0 0 0 0 1 0 0 0

优先关系矩阵如下： S M U i E t e a b S = = = M U = i E = t = = e a b 其中含多重定义的表项，因而该文法不是简单优先文法。

P145 12. 根据图4.25的语法树，确定全部优先关系：

(a) E=+ +=T T=* *=F (=E E=) *<( +* i>* )>+ T>+ F>+ (b) <说明表>=; BEGIN=<说明表> REAL=<标识符表> <变量>=:= ;=<语句表> :==i

BEGIN<<说明> BEGIN ;<<变量> ;>; <标识符表>>; i>; i>:=

P145 13. 利用表4.6文法G[E]的优先关系矩阵，来分析符号串#b(((aa)a)a)b#和#((aa)a)#。 (1) 步骤 符号栈 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 # #b #b( #b(( #b((( #b(((a #b(((M #b(((Ma #b(((Ma) #b(((L #b((M #b((Ma #b((Ma) #b((L #b(M #b(Ma 关系 < < < < < > = = > > = = > > = = 输入串 规则 b(((aa)a)a)b# (((aa)a)a)b# ((aa)a)a)b# (aa)a)a)b# aa)a)a)b# a)a)a)b# a)a)a)b# M∷=a )a)a)b# a)a)b# a)a)b# L∷=Ma) a)a)b# M∷=(L )a)b# a)b# a)b# L∷=Ma) a)b# M∷=(L )b# １９

17 18 19 20 21 (2) #b(Ma) #b(L #bM #bMb #Z > > = > > 关系 < < < > = = > > = = > > > b# b# L∷=Ma) b# M∷=(L # # Z∷=bMb 输入串 规则 ((aa)a)# (aa)a)# aa)a)# a)a)# a)a)# M∷=a )a)# a)# a)# L∷=Ma) a)# M∷=(L )# # # L∷=Ma) # M∷=(L 步骤 符号栈 1 2 3 4 5 6 7 8 9 10 11 12 13 # #( #(( #((a #((M #((Ma #((Ma) #((L #(M #(Ma #(Ma) #(L #M P146 17. 设已给文法G[S]: E∷＝E+T | T

T∷＝T*F | F F∷＝P↑F | P

P∷＝(E) | i

（1） 构造此文法的算符优先矩阵； 解：（1）

E T F P ( i * + ) ↑ E 0 0 0 0 0 0 0 0 0 0 T 0 0 0 0 0 0 0 0 0 0 F 0 0 0 0 0 0 0 0 0 0 = P 0 0 0 0 0 0 0 0 0 0 1 B

( 0 0 0 0 0 0 0 0 1 0 i 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 + 0 0 0 0 0 0 0 0 0 0 ) 0 0 0 0 0 0 0 0 0 0 ↑ 0 0 0 0 0 0 0 0 0 0

２０

E T F P ( i * + ) ↑ E 0 0 0 0 0 0 0 1 1 0 T 0 0 0 0 0 0 1 0 0 0 F 0 0 0 0 0 0 0 0 0 0 = P 0 0 0 0 0 0 0 0 0 1 8 B

( 1 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 0 * 0 0 1 0 0 0 0 0 0 0 + 0 1 0 0 0 0 0 0 0 0 ) 0 0 0 0 0 0 0 0 0 0 ↑ 0 0 1 0 0 0 0 0 0 0

E T F P ( i * + ) ↑ E 1 1 0 0 0 0 0 0 0 0 T 0 1 1 0 0 0 0 0 0 0 F 0 0 0 1 0 0 0 0 0 0 BL

=

P 0 0 0 0 1 1 0 0 0 0 7 ( 0 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 + 0 0 0 0 0 0 0 0 0 0 ) 0 0 0 0 0 0 0 0 0 0 ↑ 0 0 0 0 0 0 0 0 0 0

E T F P ( i * + ) ↑

E 1 1 1 1 1 1 0 0 0 0 T 0 1 1 1 1 1 0 0 0 0 F 0 0 1 1 1 1 0 0 0 0 B

L* =

P 0 0 0 1 1 1 0 0 0 0 ( 0 0 0 0 1 0 0 0 0 0 i 0 0 0 0 0 1 0 0 0 0 * 0 0 0 0 0 0 1 0 0 0 + 0 0 0 0 0 0 0 1 0 0 ) 0 0 0 0 0 0 0 0 1 0 ↑ 0 0 0 0 0 0 0 0 0 1

２１

E T F P ( i * + ) ↑ E 0 0 0 0 0 0 0 1 0 0 T 0 0 0 0 0 0 1 0 0 0 F 0 0 0 0 0 0 0 0 0 1 L B1 = P 0 0 0 0 1 1 0 0 0 0 5

( 0 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 + 0 0 0 0 0 0 0 0 0 0 ) 0 0 0 0 0 0 0 0 0 0 ↑ 0 0 0 0 0 0 0 0 0 0 B · < = B B L* B L 1 =

E T F P ( i * + ) ↑ E T F P ( i * + ) E 0 0 0 0 0 0 0 1 1 0 E 0 0 0 0 0 0 0 1 0 0 T 0 0 0 0 0 0 1 0 0 0 T 0 0 0 0 0 0 1 0 0 0 F 0 0 0 0 0 0 0 0 0 0 F 0 0 0 0 0 0 0 0 0 1 B ·< = P 0 0 0 0 0 0 0 0 0 1

( 1 1 1 1 1 1 0 0 0 0 ( 0 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 0 * 0 0 1 1 1 1 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 + 0 1 1 1 1 1 0 0 0 0 + 0 0 0 0 0 0 0 0 0 0 ) 0 0 0 0 0 0 0 0 0 0 ) 0 0 0 0 0 0 0 0 0 0 ↑ 0 0 1 1 1 1 0 0 0 0

E T F P ( i * + ) ↑ E 0 0 0 0 0 0 0 0 0 0 T 0 0 0 0 0 0 0 0 0 0 F 0 0 0 0 0 0 0 0 0 0 B ·< = P 0 0 0 0 0 0 0 0 0 0

( 0 0 0 0 1 1 1 1 0 1 i 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 1 1 0 0 0 1 + 0 0 0 0 1 1 1 0 0 1 ) 0 0 0 0 0 0 0 0 0 0 ↑ 0 0 0 0 1 1 0 0 0 1

↑ P 0 0 0 0 1 1 0 0 0 0 ↑ 0 0 0 0 0 0 0 0 0 0 ２２

×

E T F P ( i * + ) ↑ E 0 1 0 0 0 0 0 0 0 0 T 0 0 1 0 0 0 0 0 0 0 F 0 0 1 1 0 0 0 0 0 0 R B = P 0 0 0 0 0 1 0 0 1 0 6

( 0 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 + 0 0 0 0 0 0 0 0 0 0 ) 0 0 0 0 0 0 0 0 0 0 ↑ 0 0 0 0 0 0 0 0 0 0

E T F P ( i * + ) ↑ E 1 1 1 1 0 1 0 0 1 0 T 0 1 1 1 0 1 0 0 1 0 F 0 0 1 1 0 1 0 0 1 0 B

R* =

P 0 0 0 1 0 1 0 0 1 0 ( 0 0 0 0 1 0 0 0 0 0 i 0 0 0 0 0 1 0 0 0 0 * 0 0 0 0 0 0 1 0 0 0 + 0 0 0 0 0 0 0 1 0 0 ) 0 0 0 0 0 0 0 0 1 0 ↑ 0 0 0 0 0 0 0 0 0 1

E T F P ( i * + ) ↑ E 0 0 0 0 0 0 0 1 0 0 T 0 0 0 0 0 0 1 0 0 0 F 0 0 0 0 0 0 0 0 0 1 B

R 1 =

P 0 0 0 0 0 1 0 0 1 0 ( 0 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 + 0 0 0 0 0 0 0 0 0 0 ) 0 0 0 0 0 0 0 0 0 0 ↑ 0 0 0 0 0 0 0 0 0 0

２３

= B>· (B(R*) B(R1) )T B

E T F P ( i * + ) ↑ E 0 0 0 0 0 1 1 1 1 1 T 0 0 0 0 0 1 1 0 1 1 F 0 0 0 0 0 1 0 0 1 1 ( 0 0 0 0 0 0 0 0 0 0 i 0 0 0 1 0 0 0 0 0 0 * 0 1 0 0 0 0 0 0 0 0 + 1 0 0 0 0 0 0 0 0 0 ) 0 0 0 1 0 0 0 0 0 0 ↑ 0 0 1 0 0 0 0 0 0 0

E T F P ( i * + ) ↑ E 0 0 0 0 0 0 0 0 0 0 T 0 0 0 0 0 0 0 0 0 0 F 0 0 0 0 0 0 0 0 0 0 T ） (（R*（R1）) = P 0 0 0 0 0 0 0 0 0 0 ( 0 0 0 0 0 0 0 0 0 0 i 1 1 1 1 0 0 0 0 0 0 * 1 1 0 0 0 0 0 0 0 0 + 1 0 0 0 0 0 0 0 0 0 ) 1 1 1 1 0 0 0 0 0 0 ↑ 1 1 1 0 0 0 0 0 0 0

E T F P ( i * + ) ↑ E T F P ( i * + ) ↑ E 0 0 0 0 0 0 0 0 0 0 E 0 0 0 0 0 0 0 1 1 0 T 0 0 0 0 0 0 0 0 0 0 T 0 0 0 0 0 0 1 0 0 0 F 0 0 0 0 0 0 0 0 0 0 F 0 0 0 0 0 0 0 0 0 0

B （R*）（R1） = P 0 0 0 0 0 1 0 0 1 0

B

∴ B = P 0 0 0 0 0 0 0 0 0 0 P 0 0 0 0 0 0 0 0 0 1 >·

( 0 0 0 0 0 0 0 0 0 0 × ( 1 0 0 0 0 0 0 0 0 0 i 1 1 1 1 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 0 * 1 1 0 0 0 0 0 0 0 0 * 0 0 1 0 0 0 0 0 0 0 + 1 0 0 0 0 0 0 0 0 0 + 0 1 0 0 0 0 0 0 0 0 ) 1 1 1 1 0 0 0 0 0 0 ) 0 0 0 0 0 0 0 0 0 0 ↑ 1 1 1 0 0 0 0 0 0 0 ↑ 0 0 1 0 0 0 0 0 0 0

２４

E T F P ( i * + ) ↑ E 0 0 0 0 0 0 0 0 0 0 T 0 0 0 0 0 0 0 0 0 0 F 0 0 0 0 0 0 0 0 0 0 > B· = P 0 0 0 0 0 0 0 0 0 0

( 0 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 1 1 1 1 * 0 0 0 0 0 0 1 1 1 0 + 0 0 0 0 0 0 0 1 1 0 ) 0 0 0 0 0 0 1 1 1 1 ↑ 0 0 0 0 0 0 1 1 1 0 ( i * + ) ↑ 或 + * ↑ ( ) i + >· >· >· ·< >· >· * ·< >· >· ·< >· >· ↑ ·< ·< ·< ·< >· >· ( ·< ·< ·< ·< ) >· >· >· = >· >· i ·< ·< ·< ·< ( ·< ·< ·< ·< i ·< ·< ·< ·< * ·< >· >· ·< >· >· + ·< >· >· >· >· >· ) = >· >· >· >· >· ↑ ·< >· ·< ·< >· ·<

P146 19. 证明下面文法不是算符优先文法: S∷＝A[ ] | [

A∷＝aA | B] B∷＝a

证明： S→A[ ]

S A→aA

A [

∵A →aA

a A A→ B]

∴a ·< ]

B ]

∵A→B]

a

２５

]

B→a ∴ a >· ] a >· ] 和a ·< ]矛盾，所以该文法非算符优先文法

P146 21. 利用表4.8文法G[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是文法G[E]的句子；

再以i*(i*i)为例： 符号栈 ＃ ＃i ＃∨ ＃∨* ＃∨*( ＃∨*(i ＃∨*(∨ ＃∨*(∨* ＃∨*(∨*i ＃∨*(∨*∨ ＃∨*(∨ ＃∨*(∨) ＃∨*∨ ＃∨ ∴i*（i*i）是文法G[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 ∨+∨ 成功 ２６

第十一次作业

P146 22. 设有文法G[Z]: Z∷＝A | B

A∷＝aAb | c B∷＝aBb | d

（1） 试构造能识别此文法的全部活前缀DFA； （2） 试构造LR(0)分析表；

（3） 试分析符号串aacbb是否为此文法的句子。

解：在上述文法中引入新的开始符号Z’，并将Z’::=Z作为第0个规则，从而得到所谓的拓广文法G’，则其LR（0）项目有：

1Z’ ::= ·Z ○2 Z’ ::= Z· ○3 Z::= ·A ○4 Z::= A· ○

5 Z ::= ·B ○6 Z ::= B· ○7 A ::= ·aAb ○8 A ::= a·Ab ○

9 A::= aA ·b ○10 A ::=aAb· ○11 B ::= ·aBb ○12 B ::= a·Bb ○

13 B ::=aB ·b ○14 B ::= aBb· ○15 B::= ·d ○16 B::= d· ○

17 A::=·c ⒅A::= c· ○ (1)

２７

(2)构造LR（0）分析表 状态 0 1 2 3 4 5 6 7 8 9 10 ACTION a b c # S4 r1 r2 S4 r4 r6 r3 r5 S6 r1 r2 S6 r4 r6 S9 S10 r3 r5 S5 r1 r2 S5 r4 r6 r3 r5 acc r1 r2 r4 r6 r3 r5 GOTO Z A B 1 2 3 7 8

规则顺序：r1：Z→A r2：Z→B r3: A→aAb r4: A→C r5: B→aBb r6: B→d

(3)分析符号串aacbb是否为该文法的句子 步骤 1 2 3 4 5 6 7 8 9 10 状态栈 0 04 044 0445 0447 04479 047 0479 02 01 符号栈 ＃a ＃a ＃aa ＃aac ＃aaA ＃aaAb ＃aA ＃aAb ＃A ＃Z 输入串 aacbb＃ acbb＃ cbb＃ bb＃ bb＃ b＃ b＃ ＃ ＃ ＃ 分析动作 S4 S4 S5 r4 S9 r3 S9 r3 r1 acc 下一状态 4 4 5 GOTO[4,A]=7 9 GOTO[4,A]=7 9 GOTO[0,A]=2 GOTO[0,Z]=1 成功 ２８

第十二次作业

P147 24. 给定文法：

E∷＝EE+ | EE* | a

（1） 构造它的LR(0)项目集规范族；

（2） 它是SLR(1)文法吗？若是，构造它的SLR(1)分析表； 解：

(1) 在上述文法中引入新的开始符号E’,并将E’作为第0个规则 r1:E∷=EE+ r2: E∷=EE* r3: E∷=a 则基本LR(0)项目集为： ⑴E’∷=?E ⑵E’∷=E? ⑶E∷=?EE+ ⑷E∷=E?E+ ⑸E∷=EE?+ ⑹E∷=EE+? ⑺E∷=?EE* ⑻E∷=E?E* ⑼E∷=EE?* ⑽E∷=EE*? ⑾E∷=?a ⑿E∷=a? E E I1: E’∷=E? I3: E∷=?a I0: E’∷=?E + I4: E∷=EE+? E∷=?EE+ E∷=E?E+ E∷=EE?+ E∷=?EE+ E∷=E?E+ E∷=?EE* E∷=E?E* E∷=?EE+ E∷=?a E∷=?EE* E∷=EE?* * I5: E∷=EE*? E∷=?a E∷=E?E* E∷=?EE* a a a E I2: E∷=a?

(2) 在I1中存在“移进E->?a”和“归约：E’->E?”冲突，因此该文法不是LR(0)文法，但

有FOLLOW(E’)={#}∩{a}=Ф，而该动作冲突可用SLR(1)方法解决，该文法是SLR(1)文法，其分析表如下：

状态 ACTION + * a # acc r3 r1 r2 GOTO E 1 3 3 0 S2 1 S2 2 r3 r3 3 S4 S5 S2 4 r1 r1 5 r2 r2 (3) 拓广文法：

① S’::= E ② E::= EE+ ③ E ::= EE* ④ E::=a

识别G[S’] 的LR(1)项目集及状态转移图如下：

２９

I1：S’→ E . , # E→ E .E+, #/a E→ E .E*, #/a E→ .EE+, +/a/* E→ .EE*, */a/+ E→ .a, +/*/a E I0：S’→ .E, # E→ .EE+, #/a E→ .EE*, #/a E→ .a, #/a a I2: E→a . , #/a a I4: E→a . , a/+/* a a E E I3： E→ EE .+, #/a E→ EE .*, #/a E→ E .E+, +/a/* E→ E .E*, +/a/* E→ .EE+, +/a/* E→ .EE*, +/a/* E→ .a , +/*/a * I7: E→EE* . , #/a E I5： E→ EE .+, a/+/* E→ EE .*, a/+/* E→ E .E+, a/+/* E→ E .E*, a/+/* E→ .EE+, a/+/* E→ .EE*, a/+/* E→ .a , +/*/a + + I8: E→EE+ . , a/+/* * I9: E→EE* . , a/+/* I6: E→EE+ . , #/a

文法G[S’]LR(1)分析表：

状态 0 1 2 3 4 5 6 7 8 9 Action + S6 r4 S8 r2 r3 * S7 r4 S9 goto a S2 S4 r4 S4 r4 S4 r2 r3 r2 r3 # acc r4 r2 r3 E 1 3 5 5 r2 r3 不存在多重定义的元素，所以该文法是LR(1)文法。 （4）为LALR(1)文法，其分析如下： 状态 0 1 24 35 68 79

３０

Action + r4 S68 r2 r3 * r4 S79 r2 r3 a S24 S24 r4 S24 r2 r3 # acc r4 r2 r3 goto E 1 35 35 P194 2. 给出下面表达式的后缀式表示：

解： (2) ┐a∨┐(c∨┐d) : a┐cd┐∨┐∨

(3) a+b*(c+d/e) : abcde/+*+

(4) (a∧b)∨(┐c∨d) : ab∧c┐d∨∨ (5) –a+b*(-c+d) : a-bc-d+*+

(6) (a∨b) ∧(c∨┐d∧e) : ab∨cd┐e∧∨∧

(7) if (x+y)*z<>0 then (a+b)↑c else a↑b↑c : xy+z* p1 JEZ ab+c↑ p2 JUMP ab↑c↑

３１

P194 2. 给出下面表达式的后缀式表示：

解： (2) ┐a∨┐(c∨┐d) : a┐cd┐∨┐∨

(3) a+b*(c+d/e) : abcde/+*+

(4) (a∧b)∨(┐c∨d) : ab∧c┐d∨∨ (5) –a+b*(-c+d) : a-bc-d+*+

(6) (a∨b) ∧(c∨┐d∧e) : ab∨cd┐e∧∨∧

(7) if (x+y)*z<>0 then (a+b)↑c else a↑b↑c : xy+z* p1 JEZ ab+c↑ p2 JUMP ab↑c↑

３１