第04章 语法分析-自顶向下分析

1、1S.PO.P语义分析及生成中间代码程序语义分析及生成中间代码程序代码生成程序代码生成程序代码优化程序代码优化程序语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管管理理2教学目标教学目标1.1. 要求明确要求明确语法分析在编译过程所处的阶段和作语法分析在编译过程所处的阶段和作用用。2.2. 明确明确语法分析的基本分析方法语法分析的基本分析方法。3.3. 掌握掌握FIRSTFIRST和和FOLLOWFOLLOW集合定义及构造方法。集合定义及构造方法。4.4. 掌握掌握递归下降分析方法递归下降分析方法。5.5. 掌握构造掌握构造LL(1)LL(1)分析表分析表的方法，

2、会使用的方法，会使用LL(1)LL(1)分分析法分析句子。析法分析句子。34.1 4.1 自顶向下分析方法自顶向下分析方法4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合4.3 4.3 递归下降分析递归下降分析4.4 LL(1)4.4 LL(1)分析方法分析方法教学内容教学内容4任务：任务：按照程序语言的语法规则，从由词法分析输按照程序语言的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进出的源程序符号串中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成作准备。行语法检查，为语义分析和代码生成作准备。单词符号单词符号语法树语法树源程

3、序源程序n输入：输入：TokenToken序列序列n输出：输出：n出错处理：出错处理：定位、续编译定位、续编译5文法产生语言文法产生语言自动机识别自动机识别语言语言6 EE+E a1+Ea1+E*Ea1+a2*Ea1+a2*a3 EE+EE+E*E E+E*a3E+a2*a3a1+a2*a37首先介绍带首先介绍带“回溯回溯”的自顶向下分析的一的自顶向下分析的一般方法般方法8【例例】 输入串：输入串：=acb=acb文法文法GS:GS:SaAbSaAbAcd|cAcd|c9 分析过程是设法建分析过程是设法建立一棵语法树立一棵语法树,使语法使语法树的末端结点与给定树的末端结点与给定符号串相匹配。符

4、号串相匹配。1.开始开始:令令S为根结点为根结点 S2.用用S的右部的右部,符号串去匹配输入串符号串去匹配输入串 SaAb完成一步推导完成一步推导SaAb 检查检查 a-a匹配匹配 A是非终结符是非终结符,将匹配任务交给将匹配任务交给A【例例】 输入串：输入串：=acb=acb文法文法GS:GS:SaAbSaAbAcd|cAcd|c103.选用选用A的右部符号串匹配输入串的右部符号串匹配输入串 A有两个右部有两个右部,选第一个选第一个 aAbcdS完成进一步推导完成进一步推导Acd 检查检查,c-c匹配匹配,b-d不匹配不匹配(失败失败)但是还不能冒然宣布但是还不能冒然宣布 L(GS) 4.回

5、溯回溯 即砍掉即砍掉A的子树的子树 改选改选A的第二右部的第二右部SaAbcAc 检查检查 c-c匹配匹配 b-b匹配匹配建立语法树建立语法树,末端结点为末端结点为acb与输入与输入acb相匹配相匹配,建立了推导序列建立了推导序列 SaAbacbacb L(GS)=acbGS: SaAb Acd|c11什么是回溯（什么是回溯（backtracking）?分析工作要部分地或全部地退回去重做叫分析工作要部分地或全部地退回去重做叫回溯回溯。造成回溯的条件：造成回溯的条件： 文法中，对于某个非终结符号的规则其文法中，对于某个非终结符号的规则其右部有多右部有多个选择个选择，并根据所面临的输入符号不能准确

6、的确定，并根据所面临的输入符号不能准确的确定所要选择时，就可能出现回溯。所要选择时，就可能出现回溯。回溯带来的问题：回溯带来的问题：严重的严重的低效率低效率，只有在理论上的意义而无实际意义。，只有在理论上的意义而无实际意义。12迷宫求解迷宫求解132、左递归问题、左递归问题【例例】文法文法GE：EE+T|TTT*F|FF(E)|i给出给出i*i+i自顶向下的分析过程。自顶向下的分析过程。 左递归文法会使自顶向下分析法陷入死循环左递归文法会使自顶向下分析法陷入死循环 从左向右扫描源程从左向右扫描源程序，同时实施最左序，同时实施最左推导推导如果文法具有间接左递归，则也将发生上述问题，如果文法具有间

7、接左递归，则也将发生上述问题，只不过循环的圈子兜的更大只不过循环的圈子兜的更大要实行自顶向下分析，必须要消除文法的左递归要实行自顶向下分析，必须要消除文法的左递归14FIRSTFIRST集合定义：假定集合定义：假定是文法是文法G G的任一符号串，或的任一符号串，或(V Vt tV Vn n) )，则：则：FIRST()=a | =FIRST()=a | =* *aa, aV, aVt t 若若=* *, , 则规定则规定FIRST()FIRST()FIRST()：从从可能推导出的所有开头终结符号或可能推导出的所有开头终结符号或15【例例】 SaAbAcd|cFIRST(aAb) =aFIRST

8、(cd) =cFIRST(c) =c【例例】 SAaAa| FIRST(a) =aFIRST( ) = FIRST(Aa) =aFIRST(S) =aFIRST(A) =cFIRST(S) =aFIRST(A) =a, 16对于文法中的符号对于文法中的符号XVXVn nVVt t，其，其FIRST(X)FIRST(X)集合可反复应集合可反复应用下列规则计算，直到其用下列规则计算，直到其FIRST(X)FIRST(X)集合不再增大为止：集合不再增大为止： 1)1)若若XVXVt t，则，则FIRST(X)=XFIRST(X)=X2)2)若若XVXVn n，且具有形如，且具有形如XaXa的产生式的

9、产生式(aV(aVt t) )，或具，或具有形如有形如XX的产生式，则把的产生式，则把a a或或加进加进FIRST(X)FIRST(X)。【例例】 SAaAaA FIRST(a) =aFIRST( ) = FIRST(Aa) =aFIRST(S) =aFIRST(A) =a, 173)3)设设G G中有形如中有形如XYXY1 1Y Y2 2Y Yk k的产生式，若的产生式，若Y Y1 1VVn n，则把，则把FIRST(YFIRST(Y1 1) )中的一切非中的一切非符号加进符号加进FIRST(X)FIRST(X)；对于一切；对于一切2ik2ik，若，若Y Y1 1，Y Y2 2，Y Yi-1

10、i-1均为非终结符号，且均为非终结符号，且FIRST(YFIRST(Yj j) )，1ji-11ji-1，则将，则将FIRST(YFIRST(Yi i) )中的一切非中的一切非符号加进符号加进FIRST(X)FIRST(X)；但若对一切；但若对一切1ik1ik，均有，均有FIRST(YFIRST(Yj j) )，则将，则将符号加进符号加进FIRST(X)FIRST(X)。 【例例】 SABcAa| Bbb| FIRST(a) =aFIRST( ) = FIRST(ABc) =a,b,cFIRST(S) =a,b,cFIRST(A) =a, FIRST(B) =b, 18例例4.14.1，有文法

11、，有文法 E TEE TE E +TE E +TE E E T FT T FT T T * *FTFT T T F (E)|i F (E)|i求文法中非终结符求文法中非终结符号以及符号串的号以及符号串的FIRSTFIRST集。集。解：首先求各符号的解：首先求各符号的FIRST集：该文法共有集：该文法共有非终结符号为非终结符号为E，E，T，T，FFIRST(E)=FIRST(T)=FIRST(F)= ( ，i FIRST(E)= + ，FIRST(T)= * ，下面求文法中各产生式右部符号串的下面求文法中各产生式右部符号串的FIRST集：集：FIRST(TE)=FIRST(T)=FIRST(F)

12、= ( ，i FIRST(+TE)= + FIRST()=FIRST(FT)=FIRST(F)= ( ，i FIRST(*FT)= * FIRST(E)= ( FIRST(i)= i 19FOLLOW(A)：是所有句型中紧接是所有句型中紧接A之后的终结之后的终结符号或符号或#对 于 文 法对 于 文 法 G 的的 非 终 结 符 的 后 继 符 号 集 称 为非 终 结 符 的 后 继 符 号 集 称 为FOLLOW集，定义如下：集，定义如下： A，则规定，则规定#FOLLOW(A)若若SAa，a VTFOLLOW(A) =a|S T+TE ，则，则+FOLLOW(T)E【例例】20构造集合构

13、造集合FOLLOW的算法的算法（1）若为开始符号，则把）若为开始符号，则把“#”加加入入 FOLLOW(A)中；中；（2）若）若B A ( )，则把，则把FIRST( )- 加入加入FOLLOW(A)中；中； 注：注：FOLLOW集合中不能有集合中不能有（3）若）若B A 或或B A ，且，且 则把则把FOLLOW(B)加入加入FOLLOW(A) 中。中。 ，ETEE+TE| TFTT*FT| F(E)|i#FOLLOW(E)由由F(E)可知，可知， )FOLLOW(E)由由ETE，应把，应把FOLLOW(E)加入加入FOLLOW(E)由由E + TE 且且E ，应把应把FOLLOW(E )加

14、入加入FOLLOW(T)21【例例4 42 2】 GE GEETEE+TE| TFTT*FT| F(E)|i求求FOLLOWFOLLOW(E)=#,) E是开始符号是开始符号 #FOLLOW(E) 又又 F (E) )FOLLOW(E)FOLLOW(E)=#,) E TE FOLLOW(E)加入加入 FOLLOW(E)FOLLOW(T)=+,),# E +TE FIRST(E)-加入加入FOLLOW(T) 又又 E， FOLLOW(E)加入加入FOLLOW(T)FOLLOW(T)= FOLLOW(T)= +,),# T FT FOLLOW(T)加入加入FOLLOW(T)FOLLOW(F)=*,

15、+,),# T FT FOLLOW(F)=FIRST（T）- 又又T FOLLOW(T)加入加入FOLLOW(F)FIRST(F)= FIRST(T) = FIRST(E)=(,iFIRST(T)=*,FIRST(E)=+,2223文法文法GS：S aS|bS( ) if (sym=“a) getsym( ); S( ); else if(sym=“b”) getsym(); return 0; else error();过程过程SINPUTSYM=下一个符号下一个符号S出口出口INPUTSYM =bYNNY错误错误INPUTSYM =aINPUTSYM=下一个符号下一个符号Y24文法文法GT

16、：T F (*|/)F T( ) F( ); while(sym=*| sym=/) getsym( );F( );TFYN出口出口INPUTSYM=下一个符号下一个符号INPUTSYM =*INPUTSYM =/NY25例例4.34.3，考虑文法，考虑文法Z:=(U)|aUb Z:=(U)|aUb ，U:=dZ|eU:=dZ|e，为其构造，为其构造递归下降分析子程序。并对输入串递归下降分析子程序。并对输入串aebaeb进行语法分析进行语法分析 。Z:=(U)|aUb过程过程ZINPUTSYM=下一个符号下一个符号U出口出口语法错误：语法错误：输入串少输入串少)INPUTSYM =aYNNNN

17、YY语法错误：语法错误：输入串少输入串少(、a语法错误：语法错误：输入串少输入串少bINPUTSYM =(INPUTSYM =)INPUTSYM =bINPUTSYM=下一个符号下一个符号INPUTSYM=下一个符号下一个符号UY图4.1(a) 非终结符号Z的分析程序 26过程过程UINPUTSYM=下一个符号下一个符号Z出口出口INPUTSYM =eYNNY语法错误：语法错误：输入串少输入串少d、eINPUTSYM =dINPUTSYM=下一个符号下一个符号YU:=dZ|e图4.1(b) 非终结符号U的分析程序 每个非终结符号的子程序设计好后，就可以对输入每个非终结符号的子程序设计好后，就可

18、以对输入串进行语法分析。假设输入串为串进行语法分析。假设输入串为aeb,aeb,从从Z Z子程序开始识子程序开始识别过程相当于构造了如下推导过程：别过程相当于构造了如下推导过程：Z=aUb=aebZ=aUb=aeb 27q构造方法非常构造方法非常简单简单q程序结构程序结构清晰清晰q递归调用较多，占用递归调用较多，占用内存多内存多、速度慢速度慢q如果所采用的高级语言如果所采用的高级语言不允许递归不允许递归，则，则不能不能使用此方法使用此方法 优点优点缺点缺点281)1) 左递归问题左递归问题例如文法例如文法EE+T|TEE+T|T。实际上，当文法含有直接或间接。实际上，当文法含有直接或间接左递归

19、时，都会出现无穷递归。左递归时，都会出现无穷递归。2)2) 右部多个侯选式的第一个符号相同问题，即局部右部多个侯选式的第一个符号相同问题，即局部二义性问题。二义性问题。例如对例如对Aab|aAab|a。3)3) 右部侯选式的第一个符号是非终结符号。右部侯选式的第一个符号是非终结符号。如如SA|BSA|B时，何时使用时，何时使用SASA选项？何时使用选项？何时使用SBSB选项？选项？ 29方法一：使用方法一：使用EBNF表示来改写文法表示来改写文法【例例】文法文法GE：EE+T|TTT*F|FF(E)|iE T+TT F*F F(E)|i A |A 规则一规则一A 30【例例】文法文法GE：EE

20、+T| E-T|TTT*F| T/F|F F(E)|iE T(+|)TT F(*|/)F F(E)|i AA |A 规则二规则二A A( | ) 31方法二：将左递归规则改为右递归规则方法二：将左递归规则改为右递归规则AA | 课堂练习课堂练习【例例】文法文法GE：EE+T| E-T|TTT*F| T/F|F F(E)|iETEE(+|-)TE| TFTT(*|/)FT| F(E)|i消除左递归消除左递归A AA A| 321.把把G的非终结符整理成某种顺序的非终结符整理成某种顺序A1，A2，An2. For i:=1 to n do for j :=1 to i-1 do 把每个形如把每个形

21、如Ai =Ajr的规则用的规则用Aj的右部带入替换成的右部带入替换成 Ai =(1|2|k)r 其中其中Aj =1|2|k是当前全部是当前全部Aj 的规则的规则 消除消除Ai规则中的直接左递归规则中的直接左递归 3.去掉无用的产生式去掉无用的产生式33 对于局部二义性问题，即右部多个侯选式的第一对于局部二义性问题，即右部多个侯选式的第一个符号相同时，可通过提取公因子、加入新的非终个符号相同时，可通过提取公因子、加入新的非终结符号来实现。结符号来实现。 假设文法中有规则为：假设文法中有规则为：U:=xV|xW U:=xV|xW ，解决办法如，解决办法如下：下：1)1) 提取公因子，将规则变成：提

22、取公因子，将规则变成：U:=x(V|W)U:=x(V|W)2 2）加入一个新的非终结符号）加入一个新的非终结符号A A，令，令A=V|WA=V|W，则将规，则将规则改为：则改为：U:=xA U:=xA ，A:=V|W A:=V|W 34对于这种问题，我们首先要求出每个侯选式的首符对于这种问题，我们首先要求出每个侯选式的首符号集，然后根据各侯选式的首符号集内容来选择侯号集，然后根据各侯选式的首符号集内容来选择侯选式。选式。设文法设文法G G是没有左递归的文法，规则形式为：是没有左递归的文法，规则形式为： U=|U=|首先，求出每个侯选式的首符号集，即首先，求出每个侯选式的首符号集，即FIRST(

23、)FIRST()、FIRST()FIRST()，且，且FIRST()FIRST()=FIRST()FIRST()=。若若FIRST()FIRST()，那么，那么，FIRST()FOLLOW(U)=FIRST()FOLLOW(U)=35求出首符号集后，并保证满足上述的不相交条件，那么，求出首符号集后，并保证满足上述的不相交条件，那么，对于规则对于规则U=|U=|，就可以根据下列规则来选择侯选，就可以根据下列规则来选择侯选式：式：设当前的输入符号是设当前的输入符号是a a ，aVtaVt1.1. 若若aFIRST() aFIRST() 或或FIRST()FIRST()且且aFOLLOW(U)aFO

24、LLOW(U)，则用则用侯选式。侯选式。 若若aFIRST() aFIRST() 或或FIRST()FIRST()且且aFOLLOW(U)aFOLLOW(U)，则用则用侯选式。侯选式。 若若aFIRST() aFIRST() 且且aFIRST() aFIRST() ，则语法错，转出，则语法错，转出错处理。错处理。 36 要实现没有回溯的自顶向下分析，文法必要实现没有回溯的自顶向下分析，文法必须满足两个条件：须满足两个条件：1.1. 文法是非左递归的。文法是非左递归的。2.2. 对文法的任一非终结符号，若其规则右部对文法的任一非终结符号，若其规则右部有多项选择，那么各选项所推出的终结符有多项选择

25、，那么各选项所推出的终结符号串的头符号集合要两两不相交。号串的头符号集合要两两不相交。37例例4.6，有文法，有文法GZ： Z:=AcB|Bd A:=AaB|c B:=aA|a设计递归下降分析设计递归下降分析程序。程序。解解: :首先将左递归去掉，首先将左递归去掉，将规则将规则 A:=AaB|cA:=AaB|c 改成改成 A:=caBA:=caB 提取公因子，提取公因子，将规则将规则 B := aA|a B := aA|a 改成改成 B := a(A|) B := a(A|) 改后的文法为：改后的文法为：Z := AcB|Bd , A := caB , B := a(A|)Z := AcB|B

26、d , A := caB , B := a(A|)对于规则对于规则Z := AcB|BdZ := AcB|Bd，要求出每个选项的头符号集，要求出每个选项的头符号集，即即FIRST(AcB)=cFIRST(AcB)=c，FIRST(Bd)=aFIRST(Bd)=a，分析程序如图所示。，分析程序如图所示。 38INPUTSYM=cAINPUTSYM=cINPUTSYM=下一个符号下一个符号INPUTSYM=dERRINPUTSYM=aERRINPUTSYM=下一个符号下一个符号z出口出口BBNYYYYNNN39对于规则对于规则A := caB,分析程序如图分析程序如图4.3(b)所示。所示。 对于

27、规则对于规则B := a(A|),FIRST(A)=c，分析程序如图，分析程序如图4.3(c)所示。所示。INPUTSYM=cINPUTSYM=aINPUTSYM=下一个符号下一个符号ERRINPUTSYM=下一个符号下一个符号A出口出口BYYNNINPUTSYM=aINPUTSYM=cERRINPUTSYM=下一个符号下一个符号B出口出口AYYNN图4.3(c)B分析程序 图4.3(b)A分析程序 40基本思想：基本思想：自左向右自左向右扫描分析输入符号串扫描分析输入符号串从识别符号开始生成句子的从识别符号开始生成句子的最左推导最左推导 LL(1):向前看向前看一个一个输入符号，便能唯一确定

28、产生式输入符号，便能唯一确定产生式 LL(k):向前看向前看k个个输入符号，才能唯一确定产生式输入符号，才能唯一确定产生式预测分析法预测分析法第一个第一个L L表示自左向右顺序扫描输入符号串表示自左向右顺序扫描输入符号串; ;第二个第二个L L表示分析过程产生一个句子的最左推导表示分析过程产生一个句子的最左推导41#ana2a1#SZX LL（1）总控程序总控程序分析表分析表输出流输出流42输入符号串输入符号串: :指要分析的输入符号串。指要分析的输入符号串。为了分析算法的统一，我们需要在输入串的末尾放置一为了分析算法的统一，我们需要在输入串的末尾放置一个特殊符号个特殊符号# #，这个符号不属

29、于终结符号集。，这个符号不属于终结符号集。分析表分析表M:M:是一个二维表，可用一个二维数组是一个二维表，可用一个二维数组MAMA，aa来来表示，它概括了文法的全部信息。表示，它概括了文法的全部信息。分析栈：分析栈：用来存放一系列文法符号。分析开始时，先将用来存放一系列文法符号。分析开始时，先将# #入栈，然后再将文法的开始符号入栈。入栈，然后再将文法的开始符号入栈。输出流：输出流：分析过程中使用的产生式序列。分析过程中使用的产生式序列。总控程序：总控程序：分析器对输入串的分析靠总控程序完成分析器对输入串的分析靠总控程序完成. .根根据分析栈的栈顶符号据分析栈的栈顶符号X X和当前的输入符号，

30、总控程序按和当前的输入符号，总控程序按照分析表的指示来决定分析器的动作。工作过程如下：照分析表的指示来决定分析器的动作。工作过程如下： 43输入符号串：输入符号串： 分析栈：分析栈：图图4.5分析开始时状况分析开始时状况 #X1X2Xm-1Xm 图图4.6分析进行中的状况分析进行中的状况 44#X1X2Xm-1WVU图图4.7 UVW反序入栈反序入栈 45考虑算术表达式文法考虑算术表达式文法ETE， E+TE，E， TFT，T*FT， T，F(E)|i，该文法的分析表如表该文法的分析表如表4.1所示。所示。POPPOP为过程，功能是将栈顶元素从栈内弹出。为过程，功能是将栈顶元素从栈内弹出。PU

31、SH()PUSH()为过程，其中为过程，其中VV+ + , ,功能是将功能是将压栈。压栈。NEXTSYMNEXTSYM为读符号过程，将读符号指针指向下一个符号。为读符号过程，将读符号指针指向下一个符号。ACCEPTACCEPT表示分析成功，输入符号串语法正确。表示分析成功，输入符号串语法正确。空白处表示错误入口，应该调用错误处理程序。空白处表示错误入口，应该调用错误处理程序。 4647LL（1）总控程序总控程序分析表分析表输出流输出流i+i*i#E#ETTF iET+ F i FT*iT48基本思想：基本思想：当文法中某一非终结符出现在栈顶时，根据当前的当文法中某一非终结符出现在栈顶时，根据当

32、前的输入符号，分析表应指示要用该非终结符里的哪一输入符号，分析表应指示要用该非终结符里的哪一条产生式规则条产生式规则(即进行下一步最左推导即进行下一步最左推导) 49首先，要求出首先，要求出每个非终结符号的每个非终结符号的FOLLOWFOLLOW集合集合和和每个候每个候选式的选式的FIRSTFIRST集合集合。然后，对文法然后，对文法G G中的每个产生式中的每个产生式AA，按下列规则确，按下列规则确定分析表中的元素定分析表中的元素M M： 1) 1) 对对FIRST()FIRST()中的每个终结符中的每个终结符a,a,置置MA,a=MA,a=“POPPOP，PUSH(PUSH() )”，其中，

33、其中为为的倒置的倒置。2) 2) 若若FIRST()FIRST()，则对属于，则对属于FOLLOW(A)FOLLOW(A)的每个符的每个符号号b(bb(b为终结符或为终结符或#)#)，置，置MAMA，b=b=“POPPOP”。3) 3) 把把M M中的所有中的所有MaMa，aa置为置为“POPPOP，NEXTSYMNEXTSYM”。4) 4) 把把M M中所有不按规则中所有不按规则1 1、2 2定义的元素均置为空或定义的元素均置为空或“ERRORERROR”。 例：例：P75765051POP,PUSH(ET)NEXTSYMPOP,PUSH( TF)NEXTSYMPOP,NEXTSYMPOP,

34、PUSH( )E)NEXTSYM52注意注意:用上述算法可以构造出任意给定文法的分析表用上述算法可以构造出任意给定文法的分析表,但但不是所有文法都能构造出上述那种形状的分析表，不是所有文法都能构造出上述那种形状的分析表，即即MA,a=一条规则或一条规则或Error.LL(1)分析表不含多重定义分析表不含多重定义LL(1)文法文法二义性文法不是二义性文法不是LL(1)文法文法53LL(1)LL(1)分析法的优缺点分析法的优缺点q效率高于递归下降分析法效率高于递归下降分析法优点优点q对文法的限制较多要求文法必须为对文法的限制较多要求文法必须为LL(1)LL(1)文法文法缺点缺点主要问题：主要问题：

35、 不能处理左递归文法不能处理左递归文法 分析表不能有多重定义分析表不能有多重定义54（1 1）文法）文法不含左递归不含左递归；（2 2）对于每个非终结符）对于每个非终结符A A的各个候选式的的各个候选式的终结首符终结首符号集两两不相交号集两两不相交。即，如果。即，如果AA1 1|2 2| |n n，则，则FIRST(FIRST(i i)FIRST()FIRST(j j)= )= ，其中，其中1i1i，jnjn，且且ijij。（3 3）对于文法中每个非终结符）对于文法中每个非终结符A A，若它某个候选式的，若它某个候选式的终结首符号集包含终结首符号集包含，则，则FIRST(A)FOLLOW(A)

36、FIRST(A)FOLLOW(A)55LL(1)LL(1)分析不能处理左递归文法，但也不能像递归下降分析那样分析不能处理左递归文法，但也不能像递归下降分析那样将左递归改为采用扩充将左递归改为采用扩充BNFBNF表示。在表示。在LL(1)LL(1)分析中，必须将左递归分析中，必须将左递归文法变成右递归文法，其变换方法如下：文法变成右递归文法，其变换方法如下：1 1） 对形如对形如U:=x|y|U:=x|y|z|Uv|z|Uv的直接左递归文法规则，增加一个新的直接左递归文法规则，增加一个新的非终结符号的非终结符号U U，令，令U U为左递归规则中的不含左递归符号的部分为左递归规则中的不含左递归符号的部分加上新的非终结符号加上新的非终结符号U U，即，即U:= (x|y|U:= (x|y|.|z )U.|z )U。2 2） 新的非终结符号新的非终结符号U U有两个侯选式，一为含左递归符号的部分有两个侯选式，一为含左递归符号的部分去掉含左递归符号，再加上新的非终结符号去掉含左递归符号，再加上新的非终结符号U U，即，即U