大连海事大学《编译原理》期末总复习讲述

1、编译原理编译原理期末总复习期末总复习考试题型及分数分布n填空题(10分）n单选题（20分）n判断题（10分）n解析题（60分）第二章第二章 文法与形式语言简介文法与形式语言简介（1 1）给出）给出句型句型或或句子句子最左推导或最右推导最左推导或最右推导（规范推导）；（规范推导）；（2 2）画出）画出句型句型或或句子的语法树；句子的语法树；（3 3）求句型的短语、简单短语、句柄；）求句型的短语、简单短语、句柄；（4 4）判断一个文法是二义性的文法）判断一个文法是二义性的文法P28#3n规范推导：规范推导： aa+a*S =SS*|SS+|a S=aa+a*Sa+a*=SS+a*=Sa*=SS*=

2、n语法树：语法树： SSS*SS+aaaP28#4n只含有4个符号的句子：Z =U0 V1U =Z1 1V =Z0 0P28#5S =AB A =aA B =bBcbc A =aA描述的语言描述的语言: an|n=0B =bBcbc描述的语言描述的语言:bncn|n=1L(GS)=anbmcm|n=0,m=1P28#7E =T E+T E-T T =F T*F T/FF =(E) i， 句型句型T+T*F+i的语法树：的语法树： EE+TTE+TT*FFi短语：短语：T+T*F+i,T+T*F简单短语：简单短语：T*F， T ，i句柄：句柄： T 已知文法已知文法GE:GE:E:=E+T|TE

3、:=E+T|TT:=TT:=T* *F|FF|FF:=(E)|iF:=(E)|i1 1、试给出句子、试给出句子i i* *(i+i)(i+i)的规范推导；的规范推导；2 2、画出相应的语法树；、画出相应的语法树；( (注意：相同的叶子节点用注意：相同的叶子节点用不同的下标加以区分，如：不同的下标加以区分，如：i1 i1、i2i2、i3i3) )3 3、指出该句子所有的短语、简单短语、句柄。、指出该句子所有的短语、简单短语、句柄。存在的问题存在的问题n给出的推导不是规范推导；给出的推导不是规范推导；n一次使用多条规则；一次使用多条规则；n没有标明句柄所在的位置；没有标明句柄所在的位置；n不是从文

4、法的开始符号进行推导；不是从文法的开始符号进行推导；句子句子i i* *(i+i)(i+i)的规范推导的规范推导E ET T T T* *F F T T* *(E)(E) T T* *(E+T) (E+T) T T* *(E+F) (E+F) T T* *(E+i) (E+i) T T* *(T+ i) (T+ i) T T* *(F + i) (F + i) T T* *(i + i) (i + i) F F* * (i + i) (i + i) i i * * (i + i) (i + i) 句子句子i i* *(i+i)(i+i)的语法树的语法树短语、简单短语、句柄短语、简单短语、句柄为

5、了区分相同的短语，可以采用加下标的方法。为了区分相同的短语，可以采用加下标的方法。i i1 1、i i3 3是相对于非终结符号是相对于非终结符号F F、T T的短语、简单短语的短语、简单短语; ;i i2 2是相对于非终结符号是相对于非终结符号F F、T T、E E的短语、简单短语的短语、简单短语; ;i i2 2+i+i3 3是相对于非终结符号是相对于非终结符号E E的短语的短语; ;(i (i2 2+i+i3 3) )是相对于非终结符号是相对于非终结符号F F的短语的短语; ;i i1 1* *(i (i2 2+i+i3 3) )是相对于非终结符号是相对于非终结符号T T、E E的短语的短

6、语; ;i i1 1是句柄是句柄; ;P28#8S =S*S|S+S|(S)|a 给出句子给出句子a+a*a 两棵不同的语法树两棵不同的语法树SSS*S+SaaaSSS+S*Saaa已知文法已知文法GS:GS:S:=iSeS|iS|iS:=iSeS|iS|i试说明该文法是二义性的文法。试说明该文法是二义性的文法。句子句子iiieiiiiei两棵不同的语法树两棵不同的语法树S:=iSeS|iS|i第三章第三章 词法分析词法分析1 1、正规文法和有限自动机的等价性正规文法和有限自动机的等价性2 2、正规式和有限自动机的等价性正规式和有限自动机的等价性3、NFANFA到到DFADFA转换的子集法及最

7、小化转换的子集法及最小化正则文法的状态图画法如下正则文法的状态图画法如下：1、文法中的每个非终结符号对应状态图中的一个结点，、文法中的每个非终结符号对应状态图中的一个结点，即图中的每个结点代表一个非终结符号。即图中的每个结点代表一个非终结符号。2、增设一个结点代表开始状态、增设一个结点代表开始状态S，而文法中的，而文法中的识别符号对识别符号对应的结点为终结状态应的结点为终结状态3、对于文法中的每一条形如、对于文法中的每一条形如Ua的规则，画一条从结点的规则，画一条从结点S指向结点指向结点U的弧线，并在弧上标记的弧线，并在弧上标记a。4、对于文法中每一条形如、对于文法中每一条形如U =Wa的规则

8、，画一条从结的规则，画一条从结点点W指向结点指向结点U的弧线，并在弧上标记的弧线，并在弧上标记a。SUa开始状态开始状态WUa有正则文法GZ：Z:=Ua|Vb，U:=Zb|b，V:=Za|a ，画出该文法的状态图，并检查句子abba是否合法。 SUVZaaabbbP60#1句子abba合法。Z:=Ua|VbU:=Zb|bV:=Za|aZ:=Ua|Vb，U:=Zb|b，V:=Za|a从正规式从正规式R R构造构造NFA MNFA M的步骤的步骤1 11 1、把正规式、把正规式R R表示为：表示为：初态初态终态终态xyR R从从上的正规式上的正规式R R构造构造NFA MNFA M的步骤的步骤2

9、22 2、把、把R R分裂并加进新的结点分裂并加进新的结点每条弧标记为每条弧标记为上的一个字符或上的一个字符或结点分裂规则结点分裂规则加入加入k结点结点1弧变弧变2弧弧结点分裂规则结点分裂规则1弧变弧变2弧弧结点分裂规则结点分裂规则加入加入k结点结点闭包去掉变闭环闭包去掉变闭环前后各前后各1条空弧条空弧kijR1子集法的基本思想子集法的基本思想NFANFA基本思想基本思想：NFANFA的的一组一组状态状态DFADFA的的一个一个状态状态对应对应等价的等价的DFA DFA 子子集集法法转转换换子集法子集法设已给具有设已给具有动作的动作的NFA M=NFA M=（K,f,SK,f,S0 0,Z),

10、Z)构造相应的确定的有限自动机构造相应的确定的有限自动机: : DFA M = DFA M =（KK,ff,q,q0 0,Z ),Z )构造构造K K 及及f f 的步骤可递归地描述如下：的步骤可递归地描述如下：（1 1）给出）给出MM的初态的初态 ： 递归描述步骤（递归描述步骤（1 1）K=K= qq0 0 q q0 0 = = -closure(S-closure(S0 0) )递归描述步骤（递归描述步骤（2 2）（2 2）对于）对于KK中尚未标记的状态中尚未标记的状态q qi i =S=Si1 i1 ,S,Si2 i2 , ,S,Simim, S, Sik ik K做做 ：标记标记q q

11、i i ；对于每一个对于每一个aa，置：，置：若若q qj j不在不在KK中中, ,则将则将q qj jf(qf(qi i , a)=q, a)=qj jKKMMJ=move(SJ=move(Si1 i1 ,S,Si2 i2 , ,S,Simim,a),a)， q qj j = = -closure(J)= I-closure(J)= Ia a递归描述步骤（递归描述步骤（3 3）（3 3）重复（）重复（2 2）直到）直到MM中不再有未标记的中不再有未标记的状态为止。状态为止。至少含有一个至少含有一个Z Z中元素的中元素的q qi i作为作为MM的终态的终态构造正规式构造正规式b(ab|bb)*

12、ab的的DFA（1）NFA初态初态终态终态xy初态初态终态终态xya a1b b23ab|bbab|bb4b b初态初态终态终态xya a1b b234b bbbbb初态初态终态终态xya a1b b23a a4b bb b56b bb babab（2）DFA1、-closure(x)=-closure(x)=xx =q=q0 0 初态初态终态终态xya a1b b23a a4b bb b56b bb bKK q q0 0 2 2、对、对KK中未标记状态中未标记状态q q0 0做：做：move(qmove(q0 0,a)=move(x,a)=,a)=move(x,a)=move(qmove(q

13、0 0,b)=move(x,b)= 1,b)=move(x,b)= 1-closure(1)=-closure(1)=1,2,3=1,2,3=q q1 f(qf(q0 0,b)=,b)= q1KK q0q0,q1,q13、对、对K中未标记状态中未标记状态q1做：做：初态初态终态终态xya a1b b23a a4b bb b56b bb bmove(q1,a)=move(1,2,3,a)=4,6-closure(4,6)= 4,6 =q2 f(q1,a) =q2move(q1,b)= move(1,2,3,b)=5-closure(5)= 5 =q3 f(q1,b) =q3KK q0q0, ,q

14、1q1,q2,q3,q2,q34、对、对K中未标记状态中未标记状态q2做：做：move(q2,a)=初态初态终态终态xya a1b b23a a4b bb b56b bb bmove(4,6,a)=move(q2,b)= move(4,6,b)=2,y-closure(2,y)= 2,3,y =q4 f(q2,b) =q4KK q0q0, ,q1q1, ,q2q2,q3,q4,q3,q4初态初态终态终态xya a1b b23a a4b bb b56b bb b5、对、对K中未标记状态中未标记状态q3做：做：move(q3,a)=move(5,a)=move(q3,b)= move(5,b)=2

15、-closure(2)= 2,3 =q5 f(q3,b) =q5KK q0q0, ,q1q1, ,q2q2, ,q3q3,q4,q5,q4,q5初态初态终态终态xya a1b b23a a4b bb b56b bb b6、对、对K中未标记状态中未标记状态q4做：做：move(q4,a)=move(2,3,y,a)=4,6-closure(4,6)= 4,6 =q2 f(q4,a) =q2move(q4,b)= move(2,3,y,b)=5-closure(5)= 5 =q3 f(q4,b) =q3KK q0q0, ,q1q1, ,q2q2, ,q3q3, ,q4q4,q5,q5初态初态终态终

16、态xya a1b b23a a4b bb b56b bb b7、对、对K中未标记状态中未标记状态q5做：做：move(q5,a)=move(2,3,a)=4,6-closure(4,6)= 4,6 =q2 f(q5,a) =q2move(q5,b)= move(2,3,b)=5-closure(5)= 5 =q3 f(q5,b) =q3KK q0q0, ,q1q1, ,q2q2, ,q3q3, ,q4q4, ,q5q5等价的等价的DFA M DFA M 如下如下KK q q0 0 , q, q1 1 , , q q2 2 ,q,q3 3 , , q q4 4 ,q,q5 5f(q0,a) =

17、, f(q0,b) =q1f(q1,a) =q2, f(q1,b) =q3f(q2,a) = , f(q2,b) =q4f(q3,a) = , f(q3,b) =q5f(q4,a) =q2, f(q4,b) =q3Z q4 f(q5,a) =q2, f(q5,b) =q3NFA MNFA M转换为转换为DFA M DFA M 的过程的过程IIaIbq0=x=xq1 =1,2,3=1,2,3q2 =4,6=4,6q3 =5=5q4 =2,3,y=2,3,yq1 =1,2,3=1,2,3q2 =4,6=4,6q3 =5=5q2 =2,3,y=2,3,yq5=2,3=2,3q3 =5=5f(q0,b

18、) =q1f(q1,a) =q2, f(q1,b) =q3f(q2,b) =q4 f(q3,b) =q5f(q4,a) =q2, f(q4,b) =q3f(q5,a) =q2, f(q5,b) =q3q5 =2,3=2,3q2 =4,6=4,6q2 =4,6=4,6q3 =5=5DFA M DFA M 的状态图的状态图f(q0,a) = , f(q0,b) =q1, f(q1,a) =q2, f(q1,b) =q3, f(q2,a) = , f(q2,b) =q4, f(q3,a) = , f(q3,b) =q5, f(q4,a) =q2, f(q4,b) =q3, f(q5,a) =q2,

19、f(q5,b) =q3bq0初态初态bq1q2aq3b0q4终态终态q5babab最小化q0初态初态bq1q2aq3b0q4 终态终态q5babab1、初始划分由两个子集组成，即：、初始划分由两个子集组成，即：q q0 0,q,q1 1,q,q2 2,q,q3 3，q q5 5( (非终态）非终态）q q4 4（终态）（终态）b2、考查子集、考查子集q0,q1,q2,q3,q5 q q0 0,q,q1 1,q,q2 2,q,q3,3,q q5 5 a a：=q=q2 2 q0,q1,q2,q3,q5 q q0 0,q,q1 1,q,q2 2,q,q3,3,q q5 5 b b：=q1,q3,q

20、4,q5 q q4 4 q0初态初态bq1q2aq3b0q4 终态终态q5bababb q q0 0,q,q1 1,q,q2 2,q,q3,3,q q5 5 ： q0,q1,q3,q5 qq2 2 = q0,q1,q3,q5 q0,q1,q3,q5 , ,q q2 2，q q4 4 q0初态初态bq1q2aq3b0q4 终态终态q5bababb3、考查子集、考查子集q0,q1,q3,q5 q q1 1,q,q5 5 a a：=q=q2 2 q q0 0,q,q1 1,q,q3,3,q q5 5 b b：=q1,q3,q5 q0,q1,q3,q5 子集子集 q0,q1,q3,q5 再分割再分割:

21、 :f(q0,a) = f(q3,a) = q q0 0, ,q q3 3, ,a a：= q q0 0, ,q q3 3, , q q1 1,q,q5 5 q0初态初态bq1q2aq3b0q4 终态终态q5bababbq0初态初态bq1q2aq3b0q4 终态终态q5bababq0初态初态bq20q4ab q q0 0, ,q q3 3, , q q1 1,q,q5 5 qq2 2 qq4 4 q1abbb考察字符串：bab左图识别过程：q0-q1-q2-q4右图识别过程：q0-q1-q2-q4考察字符串：bbbab左图识别过程：q0-q1-q3-q5-q2-q4右图识别过程：q0-q1-q

22、0-q1-q2-q4q0初态初态bq20q4abq1abbq0初态初态bq1q2aq3b0q4 终态终态q5bababb设字母表设字母表a,ba,b上的正规式上的正规式R=(a|ba)R=(a|ba)* *1 1、构造、构造NFA MNFA M , ,使得使得L(ML(M )=L(R) ; )=L(R) ;2 2、将、将NFA MNFA M确定化，得到确定化，得到DFA M DFA M 使得使得L(ML(M )=L(M); )=L(M);3 3、将、将DFA MDFA M最小化。最小化。构造构造NFA MNFA Mxy1aR=(a|ba)*2ba将将NFA MNFA M确定化确定化xy12ba

23、a1、-closure(x)=-closure(x)=x,1,y=q0 x,1,y=q0 K K q q0 0 2、对、对K中未标记状态中未标记状态q0做：做：(1)(1)标记标记q q0 0(2)move(q(2)move(q0 0,a)=move(,a)=move(x,1,y,a)=1,a)=1-closure(1)= -closure(1)= 1,y=q11,y=q1 f(qf(q0 0,a)=q1,a)=q1xy12baamove(q0,b)=move(x,1,y,b)=move(x,1,y,b)= 22-closure(2)= -closure(2)= 2=q22=q2 q q0 0

24、 =x,1,y=x,1,y， q q1 1 =1,y =1,y f(qf(q0 0,b)=q2,b)=q2KK q q0 0 , , q q1 1 , , q q2 2 3 3、对、对KK中未标记状态中未标记状态q q1 1做：做：(1)标记标记q1(2)move(q1,a)= move(1,y,a)= 1-closure(1)= -closure(1)= 1,y=q11,y=q1 f(qf(q1 1,a)=q1,a)=q1 q q0 0 =x,1,y=x,1,y， q q1 1 =1,y =1,y， q2=2xy12baamove(q1,b)= move(1,y,b)=2 f(qf(q1 1

25、,b)=q2,b)=q2KK q q0 0 , , q q1 1 , , q q2 2 4 4、对、对KK中未标记状态中未标记状态q q2 2做：做：(1)标记标记q2(2)move(q2,a)= move(2,a)= 1-closure(1)= -closure(1)= 1,y=q11,y=q1 f(qf(q2 2,a)=q1,a)=q1move(q2,b)= move(2,b)= 等价的等价的DFA M 如下如下 f(qf(q0 0,a)=q1,a)=q1 f(qf(q0 0,b)=q2,b)=q2 f(qf(q1 1,a)=q1,a)=q1 f(qf(q1 1,b)=q2,b)=q2 f

26、(qf(q2 2,a)=q1,a)=q1NFA M 转换为转换为DFA M 的过程的过程 f(qf(q0 0,a)=q1,a)=q1 f(qf(q0 0,b)=q2,b)=q2 f(qf(q1 1,a)=q1,a)=q1 f(qf(q1 1,b)=q2,b)=q2 f(qf(q2 2,a)=q1,a)=q1IIaIbq0 =x,1,yq1 =1,yq2=2q1 =1,yq1 =1,yq2=2q2=2q1 =1,yDFA M 的状态图的状态图 f(qf(q0 0,a)=q1,a)=q1 f(qf(q0 0,b)=q2,b)=q2 f(qf(q1 1,a)=q1,a)=q1 f(qf(q1 1,b

27、)=q2,b)=q2 f(qf(q2 2,a)=q1,a)=q1q20q00q1初态初态ababa将DFA M最小化q20q00q1初态初态ababa1、初始划分由两个子、初始划分由两个子集组成，即：集组成，即：q q0 0,q,q1 1( (终态）终态）q q2 2（非终态）（非终态）q q0 0,q,q1 1a a= = qq1 1 q q0 0,q,q1 1b b= = qq2 2 2 2、考查子集、考查子集q q0 0,q,q1 1q20q00q1初态初态ababaq q0 0,q,q1 1a a= = qq1 1 q q0 0,q,q1 1b b= = qq2 2 子集子集q q0

28、0,q,q2 2不能再分割，即不能再分割，即q0,q1为等价状态为等价状态进行合并进行合并0q0q2初态初态终态终态aba第四章第四章 自顶向下的语法分析自顶向下的语法分析（1 1）消除直接左递归）消除直接左递归（2 2）消除间接左递归的算法）消除间接左递归的算法（3 3）FirstFirst集合和集合和FollowFollow集合的求解方法集合的求解方法（4 4）避免回溯的判断方法）避免回溯的判断方法（5 5）简单回溯的消除方法）简单回溯的消除方法（6 6）LL(1)LL(1)分析表的构造算法分析表的构造算法（7 7）LL(1)LL(1)分析方法分析方法一、消除左递归一、消除左递归消除间接左

29、递归的算法消除间接左递归的算法消除直接左递归消除直接左递归引进新的非终结符引进新的非终结符提公因子提公因子1. 引进新的非终结符的方法U:=Ux1|Ux2|Uxm|y1|y2|yn左递归规则形如：左递归规则形如：U:=x1 U| x2 U| xm U|左递归规则左递归规则不以不以U开头开头方法：方法：引进新的非终结符号引进新的非终结符号U改改写写U:= y1 U | y2 U | yn U 2.提公因子的方法提公因子的方法U:=(y1|y2|yn)U:=Ux1|Ux2|Uxm|y1|y2|yn左递归规则形如：左递归规则形如：左递归规则左递归规则不以不以U开头开头改改写写x1|x2|xm3.消除

30、间接左递归的算法步骤（消除间接左递归的算法步骤（1）(1)(1)将文法中所有的非终结符号排序将文法中所有的非终结符号排序: : U U1 1,U,U2 2, ,U,Un n; ;消除间接左递归的算法步骤（消除间接左递归的算法步骤（2）i=2i=n?j=1Yj=i-1?Y存在存在Ui :=U:=Ujy y?Y如果如果U Uj:= := x1 | | x2 | | | | xk则则U Ui:= := x1 y| | x2 y | | | | xk y消除消除U Ui i 规则中的直接左递归规则中的直接左递归j=j+1NNi=i+1N结束结束考查是否存在排在考查是否存在排在后面的非终结符后面的非终结

31、符（ Ui i ）定义为定义为（：（：= =）以排在）以排在U Ui i 前面的非终结前面的非终结符号（符号（U Uj j）开头的）开头的规则。规则。消除间接左递归的算法步骤（消除间接左递归的算法步骤（3）(3)消去多余规则消去多余规则(压缩文法压缩文法)此算法要求此算法要求1）文法没有回路）文法没有回路(U2）文法不存在规则）文法不存在规则U:=U) FIRST集的定义集的定义*符号串符号串x推导推导终结头符号集终结头符号集FIRST(x)= a|xa aVTxFIRST(x)文法避免回溯的条件文法避免回溯的条件多选规则：多选规则：U:=xU:=x1 1|x|x2 2| |x|xn n文法避

32、免回溯的条件文法避免回溯的条件: :不含空规则不含空规则FIRST(xFIRST(xi i ) ) FIRST( xFIRST( xj j ) = ) = (ij)(ij)FOLLOW(U)FOLLOW(U)的定义的定义*非终结符号非终结符号U U的的后继后继终结终结符号集。符号集。FOLLOW(U)= aFOLLOW(U)= a |Z|ZU Ua a aVaVT T识别符号识别符号特别地特别地：Z ZU U# FOLLOW(U)# FOLLOW(U)输入结束符输入结束符求求FOLLOW(U)FOLLOW(U)的算法步骤的算法步骤1)1)1)1) # #FOLLOW(Z);FOLLOW(Z);

33、识别符号识别符号求求FOLLOW(U)FOLLOW(U)的算法步骤的算法步骤2)2)2) A:=2) A:=U UFIRST()-FIRST()-FOLLOW(U)FOLLOW(U)文法满足避免回溯的条件文法满足避免回溯的条件*U:=xU:=x1 1|x|x2 2| |x|xn n1)FIRST(x1)FIRST(xi i)FIRST(x)FIRST(xj j)= (ij)= (ij)2)2)若若x xj jFIRST(xFIRST(xi i)FOLLOW(U)= (ij)FOLLOW(U)= (ij)非空规则非空规则消除回溯的简单方法消除回溯的简单方法U:=xU:=xi i|x|xj jFI

34、RST(xFIRST(xi i)FIRST(x)FIRST(xj j) ) =a=aU:=xU:=xi i|x|xj j改写改写U:=aW|aVU:=aW|aV提取提取a aU:=a(W|V)U:=a(W|V)引入引入X XU:=aXU:=aXX:=W|VX:=W|V LL(1)分析表分析表M的结构的结构行标题行标题非终结符号非终结符号U列标题列标题终结符号终结符号a结束符结束符#MU,a规则规则当当U面临输入符号面临输入符号a时应选择的规则时应选择的规则出错标志出错标志构造构造LL(1)分析表分析表M的算法的算法(3)其它均置其它均置ERROR规则规则U:=x(1)aFIRST(x)U:=x

35、MU,a(2)FIRST(x)U:=xMU,b MU,#FOLLOW(U)空空LL(1)分析方法基本思想分析方法基本思想从从左左到右扫描源程序到右扫描源程序从识别符号开始生成句子的最从识别符号开始生成句子的最左左推导推导只要向前查看只要向前查看一个一个输入符号输入符号便能确定当前应选择的规则便能确定当前应选择的规则LL(1)方法方法LL(1)分析方法的实现分析方法的实现LL(1)方法方法LL(1)分析表分析表M符号栈符号栈SK: 符号栈符号栈S的栈顶指针的栈顶指针J:输入串输入串R的指针的指针实现步骤实现步骤(3)栈顶元素栈顶元素=(1)栈顶元素栈顶元素当前符号当前符号匹配匹配k:=k-1j:

36、=j+1(2)栈顶元素栈顶元素SkVN当前输入符号为当前输入符号为Rj查查M表表MSk,Rj元素元素Sk:=x1x2xnx1x2xn代替代替Sk入栈顺序入栈顺序由右向左由右向左输入符号输入符号= #成功成功S栈栈Skxnx2x1栈顶元素出栈栈顶元素出栈输入下一符号输入下一符号出栈出栈P78#4P78#4(续)（2）不是不是LL(1)文法文法，文法中有直接左递归的规，文法中有直接左递归的规则：则：（3）消除直接左递归消除直接左递归：引进新的非终结符号引进新的非终结符号BP78#4(续)（4）构造构造LL(1)分析表分析表abe#ABB A aABeA A B bBB bBB 对文法GS:(1)(1)句子句子(a,(a,a)(a,(a,a)的最左推导：的最左推导：S S ( (T T) )( (T T,S) ,S) ( (S S,S),S)(a,(a,S S) ) (a,(a,(T T) )(a,(a,(T T,S) ,S) (a,(a,(S S,S),S)(a,(a,(a,(a,S S) ) (a,(a,a)(a,(a,a)（2）改写文法：消除直接左递归T T,S|S引入新的非终结符号引入新的非终结符号TT STT ,ST|改写后的文法：改写后的文法：S a| |(T)T STT ,ST|消除间接左递归后：消除间接左递归后：