编译原理习题解答

编译原理习题解答 页1/1

第二章：习题2-4 Table表

var x,y; procedure p; var a;

procedure q; var b; begin b:=10; end; procedure s; var c,d; procedure r; var e,f; begin call q; end; begin call r; end; begin call s; end;

begin call p; end

根据：Page289，变量table:array[0..txmax] of record 结构体以及block函数得到下表，而表中各部分的含义，见教材Page18,Page19 Name x y p a q s c d r

Kink variable variable procedur variable procedur procedur variable variable procedur Val /Level 0 0 0 1 1 1 2 2 2 Adr 3 4 1 3 3 7 3 4 0 Size 0 0 0 0 4 0 0 0 0 编译原理习题解答 页2/2

第三章 文法和语言

5. 写一文法，使其语言是偶正整数的集合 要求：

(1) 允许0打头 (2) 不允许0打头 解：

(1) G[S]=({S,P,D,N},{0,1,2,…,9},P,S)

P:

S?PD|D P->NP|N

D?0|2|4|6|8

N->0|1|2|3|4|5|6|7|8|9

(2) G[S]=({S,P,R,D,N,Q },{0,1,2,…,9},P,S)

P:

S?PD|P0|D P->NR|N R->QR|Q D?2|4|6|8

N->1|2|3|4|5|6|7|8|9 Q->0|1|2|3|4|5|6|7|8|9

6. 已知文法G：

<表达式>::=<项>|<表达式>+<项>|<表达式>-<项> <项>::=<因子>|<项>*<因子>|<项>/<因子> <因子>::=(<表达式>)|i。

试给出下述表达式的推导及语法树。

(1)i; (2)(i) (3)i*i; (4)i*i+i; (5)i+(i+i); (6)i+i*i。

解：

(1) v=<表达式>=><项>=><因子>=>i=w

(2) v=<表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(<因子>)=>(i)=w (3) v=<表达式>=><项>=><项>*<因子>=><因子>*<因子>=>i*i=w (4) v=<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项>

=><因子>*<因子>+<因子>=>i*i+i=w

(5) v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<因子>=>i+(<表达式>)

=> i+(<表达式>+<项>)=>i+(<项>+<项>)=> i+(<因子>+<因子>)=>i+(i+i)=w (6) v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项>

=>i+<项>*<因子>=> i+<因子>*<因子>=> i+i*i=w

语法树见下图:

编译原理习题解答 页3/3

(1)i <表达式> <项> <因子> i

(2)(i) <表达式> <项> <因子> ( <表达式> )

<项> <因子> i

(4) i*i+i <表达式>

(5) i+(i+i) <表达式>

<表达式> + <项> <项> <因子> i

<因子> ( <表达式> ) <表达式> + <项> <项> <因子>

<因子> i

(3)i*i <表达式> <项>

<项> * <因子> <因子> i

i

(6) i+i*i <表达式>

<表达式> + <项> <项> <因子> i

<项> * <因子> <因子> i

i

<表达式> + <项> <项> <项> * <因子> <因子> i

i

<因子> i

i

7. 为句子i+i*i构造两棵语法树，从而证明下述文法G[<表达式>]是二义的。 <表达式>::=i|(<表达式>)|<表达式><运算符><表达式> <运算符>::=+|-|*|/

解：为句子i+i*i构造的两棵语法树如下：

<表达式> <表达式>

<表达式> + <表达式> <表达式> * <表达式>

i <表达式> * <表达式> <表达式> + <表达式> i

i i i i

所以，该文法是二义的。

编译原理习题解答 页4/4

8. 习题1中的文法G[S]是二义的吗？为什么？

答：是二义的。因为对于句子abc可以有两种不同的生成树，即：S=>Ac=>abc和S=>aB=>abc 11. 令文法G[E]为： E?T|E+T|E-T T?F|T*F|T/F F?(E)|i

证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。 解：可为E+T*F构造一棵语法树（见下图），所以它是句型。 E

E + T

T * F

从语法树中容易看出，E+T*F的短语有：

T*F是句型E+T*F的相对于T的短语，也是相对于规则T?T*F的直接短语。 E+T*F是句型E+T*F的相对于E的短语。 句型E+T*F的句柄（最左直接短语）是T*F。

12. 下述文法G[E]生成的语言是什么？给出该文法的一个句子，该句子至少含五个终结符，构造该句子的语法树。证明：是G[]的句型，并指出该句型的所有短语、直接短语和句柄。 ?| ?| ?a|b|c ?+|- ?*|/ 解：

(1)计算文法G[E]的语言：

由于L(T)={(a|b|c)((a|b|c)(*|/))|n>=0} 所以L(E)={L(T)(L(T)(+|-))|n>=0}

n

n

(2)该文法的一个句子是aab*+,它的语法树是：

+

b *

a a

(3) 证明：是G[]的句型，并指出该句型的所有短语、直接短语和句柄。

由于下面的语法树可以生成，所以它是G[]的句型。

编译原理习题解答 页5/5

由于 => ,且 => ,所以是句型相对于的短语，也是相对于规则 ? 的直接短语。

由于 => 且 => ,所以是句型相对于的短语。

显然，句型的句柄是。 14. 给出生成下述语言的上下文无关文法：

（1）{abab|n,m>=0} （2）{1010|n,m>=0}

（3）{WaW|W属于{0|a},W表示W的逆}

解：

（1）所求文法为G[S]=({S,A},{a,b},P,S),其中P为： S?AA A?aAb|ε

（2）所求文法为G[S]=({S,A},{0,1},P,S),其中P为： S?1S0|A

A?0A1|ε

（3）W属于{0|a}是指W可以的取值为{ε,0,a,00,a0,aa0,00aa,a0a0,…}

如果W=aa0a00,则W=00a0aa。

所求文法为G[S]=({S,P,Q},{0,a},P,S),其中P为： S?0S0|aSa|a

nmnm

t

*

t

*

t

nmmnnnmm

15. 语言{WaW}和{abcd}是上下文无关的吗？能看出它们反映程序设计语言的什么特性吗？

答：生成语言{WaW}的文法非常简单，如 G[S]: S?WaW

W?aW|bW|ε

可见G[S]是上下文无关的。

nmnm

生成语言{abcd}的文法非常复杂，用上下文无关文法不可能办到，只能用上下文有关文法。这是因

nnmm

为要在ac的中间插入b而同时要在其后面插入d。即a,c相关联，b,d相关联。 这说明对语言的限定越多（特别是语言中的符号前后关联越多），生成它的文法越复杂，甚至于很难找到一个上下文法无关文法。

16．给出生成下述语言的三型文法：

n

(1){a|n>=0}

nm

(2){ab|n,m>=1}

nmk

(3){abc|n,m,k>=0} 解：

编译原理习题解答 页6/6

(1) 生成的3型文法是：

G[S]：S?aS|ε

(2) 生成的2型文法是：

G[S]: S?AB A?aA|a B?bB|b 生成的3型文法是： G[S]： S?aP P?aP|bD D?bD|ε (3) 生成的2型文法是：

G[S]: S?ABC A?aA|ε B?bB|ε C->cC|ε

生成的3型方法是： G[S]： A?aA|bB|cC|ε B?bB|cC|ε C?cC|ε

编译原理习题解答 页7/7

第四章 词法分析

1．构造下列正规式相应的DFA：

*

(1) 1(0|1)101

* * *

(2) 1(1010| 1(010)1)0

***

(3) a((a|b)|aba) b

* *

(4) b((ab)| bb)ab 解：

*

(1)1(0|1)101对应的NFA为

0

0 1 1 1 下表由子集法将NFA转换为DFA：

I A[0] B[1] C[1,2] D[1,3] E[1,4] B[1] D[1,3] B[1] B[1] I0 = ε-closure(MoveTo(I,0)) I1 = ε-closure(MoveTo(I,1)) B[1] C[1,2] C[1,2] E[1,4] B[1] 1 2 0 3 1 4

0

A 1 B 1 0 C 1 1 0,1 0 D 1 E

* * *

(2)1(1010| 1(010)1)0对应的NFA为

ε ε 0 1 1 1 2 1 0 0 3 1 4 0 5 ε 1 6 0 10 ε 0 7 8 1 9 ε

下表由子集法将NFA转换为DFA：

编译原理习题解答 页8/8 I A[0] B[1,6] C[10] D[2,5,7] E[3,8] F[1,4,6,9] G[1,2,5,6,9,10] H[1,3,6,9,10] I[1,2,5,6,7] J[1,6,9,10] K[2,4,5,7] L[3,8,10] M[2,3,5,8] N[3] O[4] P[2,5] I0 = ε-closure(MoveTo(I,0)) C[10] E[3,8] G[1,2,5,6,9,10] H[1,3,6,9,10] J[1,6,9,10] L[3,8,10] J[1,6,9,10] M[2,3,5,8] N[3] P[2,5] N[3] 1 1 1 1 D 0 E 1 F 0 G 0 1 I1 = ε-closure(MoveTo(I,1)) B[1,6] D[2,5,7] B[1,6] F[1,4,6,9] D[2,5,7] I[1,2,5,6,7] K[2,4,5,7] I[1,2,5,6,7] D[2,5,7] B[1,6] F[1,4,6,9] F[1,4,6,9] O[4] B[1,6]

1 1 0 I 1 H 0 L 0 K 0 J 0 0 M

A 1 B 0 C 1 1 1 P 0 O 0 1 N

(3)a((a|b)|aba) b (略)

* *

(4)b((ab)| bb)ab (略)

2．已知NFA=（{x,y,z},{0,1},M,{x},{z}）其中：M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x}, M(y,1)=φ,M(z,1)={y},构造相应的DFA。 解：根据题意有NFA图如下

0 1 0 x y

0 1 0 z 0

***

编译原理习题解答 页9/9

下表由子集法将NFA转换为DFA：

I A[x] B[z] C[x,z] D[y] E[x,y] F[x,y,z]

I0 = ε-closure(MoveTo(I,0)) B[z] C[x,z] C[x,z] E[x,y] F[x,y,z] F[x,y,z] I1 = ε-closure(MoveTo(I,1)) A[x] D[y] E[x,y] A[x] E[x,y] 0

1 A 0 B 0 1 C 0 1

D 1 0 E 0 1 F

下面将该DFA最小化：

(1) 首先将它的状态集分成两个子集：P1={A,D,E},P2={B,C,F}

(2) 区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。由于F(B,0)=F(C,0)=C,

F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。有P21={C,F},P22={B}。

(3) 区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11={A,E},P12={D}。 (4) 由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。

(5) 综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。所以最小化的DFA如下：

1 1 A 0 B 1 D 0 0 E 1 0 F 0

3.将图4.16确定化：

0 0，1 V 0 0 S Q 1 1 Z 0，1

1 U 图4.16

1 编译原理习题解答 页10/10

解：下表由子集法将NFA转换为DFA： I A[S] B[Q,V] C[Q,U] D[V,Z] E[V] F[Q,U,Z] G[Z]

I0 = ε-closure(MoveTo(I,0)) B[Q,V] D[V,Z] E[V] G[Z] G[Z] D[V,Z] G[Z] C 1 A 1 0 D 0 1 F 1 0，1 E 0 I1 = ε-closure(MoveTo(I,1)) C[Q,U] C[Q,U] F[Q,U,Z] G[Z] F[Q,U,Z] G[Z] G 0，1

0 0 B

4.把图4.17的(a)和(b)分别确定化和最小化：

a

a,b

0 a

解： (a):

下表由子集法将NFA转换为DFA：

I A[0] B[0,1] C[1]

0 a a 1 a b b 2 b a b 4 b 5 a 3 a 1 b (a) (b)

Ia = ε-closure(MoveTo(I,a)) B[0,1] B[0,1] A[0] Ib = ε-closure(MoveTo(I,b)) C[1] C[1] 可得图（a1），由于F(A,b)=F(B,b)=C,并且F(A,a)=F(B,a)=B,所以A,B等价，可将DFA最小化，即：删除

B，将原来引向B的引线引向与其等价的状态A，有图(a2)。（DFA的最小化，也可看作将上表中的B全部替换为A，然后删除B所在的行。）

a A b a B b C a

a A b C a （a1）确定化的DFA （a2）最小化的DFA

编译原理习题解答 页16/16

第五章 自顶向下语法分析方法

1．对文法G[S]

S?a|∧|(T) T?T,S|S

(1) 给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。

(2) 对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。 (3) 经改写后的文法是否是LL(1)的？给出它的预测分析表。 (4) 给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。 解：

(1) (a,(a,a))的最左推导为S?(T)?(T,S)?(S,S)?(a,(T))?(a,(T,S))?(a,(S,a))?(a,(a,a))

(((a,a),∧,(a)),a)的最左推导为

S?(T)?(T,S)?(S,a)?((T),a)?((T,S),a)?((T,S,S),a)?((S,∧,(T)),a)?(((T),∧,(S)),a) ?(((T,S),∧,(a)),a)?(((S,a),∧,(a)),a)?(((a,a),∧,(a)),a)

/

(2)由于有T?T,S的产生式，所以消除该产生式的左递归，增中一个非终结符U有新的文法G[S]:

S?a|∧|(T) T?SU U?，SU|ε

分析子程序的构造方法

对满足条件的文法按如下方法构造相应的语法分析子程序。 (1) 对于每个非终结号U，编写一个相应的子程序P(U)；

(2) 对于规则U::=x1|x2|..|xn,有一个关于U的子程序P(U),P(U)按如下方法构造：

IF CH IN FIRST(x1) THEN P(x1) ELSE IF CH IN FIRST(x2) THEN P(x2) ELSE ...

. . .

IF CH IN FIRST(xn) THEN P(xn) ELSE ERROR

其中，CH存放当前的输入符号，是一个全程变量；ERROR是一段处理出错信息的程序； P(xj)为相应的子程序。

BEGIN END

P(y1); P(y2); ... P(yn);

(3) 对于符号串x=y1y2...yn;p(x)的含义为：

如果yi是非终结符，则P(yi)代表调用处理yi的子程序； 如果yi是终结符，则P(yi)为形如下述语句的一段子程序

IF CH=yi THEN READ(CH) ELSE ERROR

即如果当前文法中的符号与输入符号匹配，则继续读入下一个待输入符号到CH中， 否则表明出错。

IF CH IN FIRST(xn) THEN P(xn)

(4) 如果文法中有空规则U::=EPSILON,则算法中的语句

编译原理习题解答 页17/17

ELSE ERROR 改写为：

IF CH IN FIRST(xn) THEN P(xn)

ELSE IF CH IN FOLLOW(U) THEN RETURN

ERROR

(5) 要分析一个OrgStr,应在该串的后面加上一个串括号'#',并从子程序P(S)(S为文法的开始符号)开始，

如果中途没有产生错误，并且最后CH='#',则说明OrgStr串合法，否则该串不合法。

对每个非终结符写出不带回溯的递归子程序如下： char CH;//存放当前的输入符号 void P_S()//非终结符S的子程序 {

if(CH==’a’) READ(CH);//产生式S?a else if(CH==’^’) READ(CH);//产生式S?^ else if(CH==’(’)//产生式S?(T) {

READ(CH); P_T();

IF (CH==’)’) THEN READ(CH) else ERROR }

else ERR; } void P_T()//非终结符S的子程序

{

if(IsIn(CH,FIRST_SU)) //FIRST_SU为T?SU的右部的FIRST集合 { P_S(); P_U(); } } void P_U()//非终结符U的子程序

{

if(CH==’,’)//产生式U?，SU {

READ(CH); P_S(); P_U(); }

else//产生式U?ε {

if(IsIn(CH,FOLLOW_U)) //FOLLOW_U为U的FOLLOW集合

return ; else ERR; } }

/

(3)判断文法G[S]是否为LL(1)文法。

各非终结符的FIRST集合如下： FIRST(S)={a,∧,（}

FIRST(T)=FIRST(S)={a,∧,（} FIRST(U)={，,ε}

各非终结符的FOLLOW集合如下：

FOLLOW(S)={#} ∪ FIRST(U) ∪ FOLLOW(T) ∪ FOLLOW(U)={#,，,)} FOLLOW(T)={)}

FOLLOW(U)=FOLLOW(T)={)} 每个产生式的SELECT集合如下：

编译原理习题解答 页18/18

SELECT(S?a)={a} SELECT(S?∧)={∧} SELECT(S?(T))={(}

SELECT(T?SU)=FIRST(S)={a,∧,（} SELECT(U?，SU)={，} SELECT(U?ε)=FOLLOW(U)={)}

可见，相同左部产生式的SELECT集的交集均为空，所以文法G[S]是LL(1)文法。 文法G[S]的预测分析表如下：

S T U

(5) 给出输入串(a,a)#的分析过程

步骤 1 2 3 4 5 6 7 8 9 10 11 12 2．对下面的文法G：

E?TE

/

/ /

/

a ?a ?SU ∧ ?∧ ?SU ( ?(T) ?SU ) ?ε ， ?，SU # 分析栈 #S #)T( #)T #)US #)Ua #)U #)US, #)US #)Ua #)U #) # 剩余输入串 所用产生式 (a,a)# S?(T) (a,a)# ( 匹配 a,a)# T?SU a,a)# S?a a,a)# a匹配 ,a)# U?，SU ,a)# ,匹配 a)# S?a a)# a匹配 )# U?ε )# )匹配 # 接受 E?+E|ε T?FT

/

/

T?T|ε F?PF

F?*F|ε P?(E)|a|b|^

/

//

(1) 计算这个文法的每个非终结符的FIRST集和FOLLOW集。 (2) 证明这个方法是LL(1)的。 (3) 构造它的预测分析表。 (4) 构造它的递归下降分析程序。 解：

（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。 FIRST集合有：

FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(E)={+,ε}

FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(T)=FIRST(T)∪{ε}={(,a,b,^,ε};

//

编译原理习题解答 页19/19

FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(F)=FIRST(P)={*,ε}; FIRST(P)={(,a,b,^}; FOLLOW集合有： FOLLOW(E)={),#};

FOLLOW(E)=FOLLOW(E)={),#};

FOLLOW(T)=FIRST(E)∪FOLLOW(E)={+,),#};//不包含ε FOLLOW(T)=FOLLOW(T)=FIRST(E)∪FOLLOW(E)={+,),#}; FOLLOW(F)=FIRST(T)∪FOLLOW(T)={(,a,b,^,+,),#};//不包含ε FOLLOW(F)=FOLLOW(F)=FIRST(T)∪FOLLOW(T)={(,a,b,^,+,),#}; FOLLOW(P)=FIRST(F)∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε (2)证明这个方法是LL(1)的。 各产生式的SELECT集合有：

/

/

/

/

/

/

/

//

SELECT(E?TE)=FIRST(T)={(,a,b,^}; SELECT(E?+E)={+};

SELECT(E?ε)=FOLLOW(E)={),#}

SELECT(T?FT)=FIRST(F)={(,a,b,^};

/

/

/

/

/

SELECT(T?T)=FIRST(T)={(,a,b,^}; SELECT(T?ε)=FOLLOW(T)={+,),#};

SELECT(F?PF)=FIRST(P)={(,a,b,^};

/

/

/

/

SELECT(P?(E))={(} SELECT(P?a)={a} SELECT(P?b)={b} SELECT(P?^)={^}

可见，相同左部产生式的SELECT集的交集均为空，所以文法G[E]是LL(1)文法。 (3)构造它的预测分析表。

SELECT(F?*F)={*};

SELECT(F?ε)=FOLLOW(F)={(,a,b,^,+,),#};

/

/

/

/

编译原理习题解答 页20/20

文法G[E]的预测分析表如下：

E E T T F F P

(4)构造它的递归下降分析程序。

对每个非终结符写出不带回溯的递归子程序如下： char CH;//存放当前的输入符号 void P_E()//非终结符E的子程序 {

/ /

if(IsIn(CH,FIRST_TEP)) //FIRST_TEP为T?TE的右部的FIRST集合，产生式E?TE { P_T(); P_EP(); }

else ERR; }

/

void P_EP()//非终结符E的子程序 {

/

if(CH==’+’) //产生式E?+E { READ(CH); P_E(); }

/

else//产生式E?ε {

/

if(IsIn(CH,FOLLOW_EP)) //FOLLOW_EP为E的FOLLOW集合

return ; else ERR; } }

void P_T()//非终结符T的子程序 {

/ /

if(IsIn(CH,FIRST_FTP)) //FIRST_TEP为T?FT的右部的FIRST集合，产生式T?FT { P_F(); P_TP(); }

else ERR; }

/

void P_TP()//非终结符T的子程序 {

/ /

if(IsIn(CH,FIRST_T)) //FIRST_T为产生式T?T的右部的FIRST集合，产生式T?T { P_T(); }

/

else//产生式T?ε {

/

if(IsIn(CH,FOLLOW_TP)) //FOLLOW_TP为T的FOLLOW集合

return ;

///+ ?+E ?ε ?ε * ?*F /( ?TE ?FT ?T ?PF ?ε ?(E) ///) ?ε ?ε ?ε a ?TE ?FT ?T ?PF ?ε ?a ///b ?TE ?FT ?T ?PF ?ε ?b ///^ ?TE ?FT ?T ?PF ?ε ?^ ///# ?ε ?ε ?ε

编译原理习题解答 页26/26 ACTION 状态 0 1 2 3 4 5 6 7 8 9 GOTO ) r1 r2 S7 r5 r3 r4 , r1 r2 S8 r5 r3 r4 # acc r1 r2 r5 r3 r4 S 1 6 9 T 5 a S2 r1 r2 S2 r5 r3 S2 r4 ^ S3 r1 r2 S3 r5 r3 S3 r4 ( S4 r1 r2 S4 r5 r3 S4 r4 编译原理习题解答 页27/27 下面构造它的LR(1)项目集规范族为： I0: /S??S,# S??a,# S??^,# S??(T),# a I2: S?a?,# ^ I3: S?^?,# ( ) , # S I1: /S?S?,# T I4: S?(?T),# T??T,S,)， T??S,)， S??a,)， S??^,)， S??(T),)， I1 I2 I3 I4: I7: I8: I9: S?(?T),# S?a?,)， S?^?,)， S?(?T),)， T??T,S,)， T??T,S,)， T??S,)， T??S,)， S??a,)， S??a,)， S??^,)， S??^,)， S??(T),)， S??(T),)， I5: S?(T?),# T?T?,S,)， acc I6: T?S?,)， I5: S?(T?),# T?T?,S,)， I10: S?(T)?,# I11: T?T,?S,)， S??a,)， S??^,)， S??(T),)， I6 I7: I8 I8 I9 I6 I12: S?(T?),)， T?T?,S,)， I9: I7 S?(?T),)， T??T,S,)， T??S,)， S??a,)， S??^,)， S??(T),)， I10 I11: I7 T?T,?S,)， S??a,)， S??^,)， S??(T),)， I12: S?(T?),)， T?T?,S,)， I13 I14 I8 I9 I13： T?T,S?,)， I14: I11 S?(T)?,)， 从上表可看出,不存在移进-归约冲突以及归约归约冲突，所以该文法是LR(1)文法。从而有下面的LR(1)分析表： 编译原理习题解答 页28/28

表7.15.2 文法的LR(1)分析表 ACTION 状态 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 GOTO ) , S11 r5 r1 r2 S11 r4 r3 # acc r1 r2 r3 S 1 6 6 13 GOTO ) , r1 r2 S11 r5 r3 r4 # acc r1 r2 r3 S 1 6 13 T 5 T 5 12 a S2 S7 S7 S7 ^ S3 S8 S8 S8 ( S4 S9 S9 S9 S10 r5 r1 r2 S14 r4 r3 ACTION 由上图可知I2与I7，I3与I8，I4与I9，I5与I12，I10与I14是同心集。现在合并同心集有文法的LALR(1)分析表： 状态 0 1 2 3 4 5 6 10 11 13 a S2 S2 S2 ^ S3 S3 S3 ( S4 S4 S4 r1 r2 S10 r5 r3 r4 将状态10,11,13分别重新命名为7,8,9有： 表7.15.3 文法的LALR(1)分析表 ACTION 状态 a ^ ( ) , # S 1 6 9 GOTO T 5 0 S2 S3 S4 1 acc 2 r1 r1 r1 3 r2 r2 r2 4 S2 S3 S4 5 S7 S8 6 r5 r5 7 r3 r3 r3 8 S2 S3 S4 9 r4 r4 可以看出，表7.15.3与 表7.15.1非常接近，但句子判断错误的速度要高很多。 编译原理习题解答 页29/29

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

该文法的LR(0)项目集及状态转换矩阵是： I0: S/??S S??iSeS S??iS S??S;S S??a i I2: S?i?SeS S?i?S S??iSeS S??iS S??S;S S??a e ; I3: a S?a? # S I1: S/?S? S?S?;S I1: S/?S? S?S?;S I4: S?S;?S S??iSeS S??iS S??S;S S??a acc I2: S?i?SeS S?i?S S??iSeS S??iS S??S;S S??a I3: S?a? I4: S?S;?S S??iSeS S??iS S??S;S S??a I2 I3 I5: S?iS?eS S?iS? S?S?;S I2 I3 I6: S?S;S? S?S?;S I5: S?iS?eS S?iS? S?S?;S I7: S?iSe?S S??iSeS S??iS S??S;S S??a I4 I6: S?S;S? S?S?;S I2 I4 I3 I8: S?iSeS? S?S?;S I7: S?iSe?S S??iSeS S??iS S??S;S S??a I4 I8: S?iSeS? S?S?;S 编译原理习题解答 页30/30 由习惯可知，定义文法中i,e,;,a4个算符的优先关系为：a>e>i>;。并且i与;的结合方向均为自左至右。

由上述状态项目集可见：

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

应移进。

b. 状态I5存在移进-归约冲突，由于FOLLOW(S)={e,;,#}与{;}或{e}交集不空，所以不是SLR(1)文法，

根据优先级与结合性有，如果面临#号应该归约到S。如果面临e，由于e优先于i，应移进；如果面临;，由于i优先于;，应归约。

c. 状态I6存在移进-归约冲突，由于FOLLOW(S)={e,;,#}与{;}交集不空，根据优先级与结合性有，

如果面临#或e号应该归约到S。如果面临;，由于;服从左结合，应归约到S。

d. 状态I8存在移进-归约冲突，由于FOLLOW(S)={e,;,#}与{;}交集不空，根据优先级与结合性有，

如果面临#或e号应该归约到S。如果面临;，由于e优先于;，应归约到S；

由上述分析得到该文法的无二义性的LR分析表如下：

表7.17.1 二义性文法的LR分析表 ACTION GOTO 状态 i e ; a # S 0 S2 S3 1 1 S4 acc 2 S2 S3 5 3 r4 r4 r4 4 S2 S3 6 5 S7 r2 r2 6 r3 r3 r3 7 S2 S3 8 8 r1 r1 r1 下面对输入串iiaea#给出分析过程: 步骤 状态栈 符号栈 输入串 ACTION GOTO 1 2 3 4 5 6 7 8 9 10 0 02 022 0223 0225 02257 022573 022578 025 01 # #i #ii #iia #iiS #iiSe #iiSea #iiSeS #iS #S iiaea# iaea# aea# ea# ea# a# # # # # S2 S2 S3 r4 S7 S3 r4 r1 r2 acc 5 8 5 1

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