第四章 语法分析-自顶向下分析方法

1、主要内容：主要内容：l自顶向下语法分析的基本思想自顶向下语法分析的基本思想l三个重要的集合三个重要的集合 l自顶向下分析的条件自顶向下分析的条件l递归下降语法分析递归下降语法分析lLL(1)LL(1)语法分析语法分析q语法分析器和识别器语法分析器和识别器q语法分析的功能语法分析的功能q语法错误类别语法错误类别q语法错误的处理语法错误的处理 q自顶向下分析的基本思想自顶向下分析的基本思想 l 语法分析器和识别器语法分析器和识别器l 语法分析器的功能：语法分析器的功能：l 语法错误类别语法错误类别 程序的开始符，语句（表达式）的开始符程序的开始符，语句（表达式）的开始符 （后继符）错（后继符）错

2、标识符（常量）错：该出现时未出现标识符（常量）错：该出现时未出现 括号类错误：不匹配括号类错误：不匹配 分隔符错：分隔符错：assignmentassignmentToken/TokenListParser语法树语法树/语法错误信息语法错误信息l 语法错误处理语法错误处理 要求：要求：报告错误出现的位置报告错误出现的位置 修复错误并继续检查后续部分修复错误并继续检查后续部分 执行开销不应太大执行开销不应太大 处理策略：处理策略：1 1）紧急方式恢复；）紧急方式恢复； 2 2）短语级恢复；）短语级恢复；3 3）出错产生式；）出错产生式；4 4）全局纠正。）全局纠正。 从文法开始符出发试图推导出所

3、给的终极符串。从文法开始符出发试图推导出所给的终极符串。 例例 Gz : 1 Z aBd 2 B d 3 B c 4 B bB 对给定的终极符串对给定的终极符串abcd，推导过程：推导过程： Z 1 aBd 4 abBd 3 abcd Z Za aB Bd db bB Bc c aBd # abcd # aBd # abcd # MatchMatch Bd # bcd # Bd # bcd # DerivationDerivation bBd # bcd # bBd # bcd # MatchMatch Bd # cd # Bd # cd # DerivationDerivation cd #

4、 cd # cd # cd # MatchMatch d # d # d # d # MatchMatch # # Success # # Success自顶向下的语法分析过程【自顶向下的语法分析过程【Sf,Rest,Action(D/M/S/E)Sf,Rest,Action(D/M/S/E)】 Z # abcd # DerivationZ # abcd # Derivation设设G=(VT，VN，S，P)是上下文无关文法是上下文无关文法, (VT VN )*，则：，则： First( )= a VT | * a. (if * then else ) 作用：可以根据当前的输入符号是属于哪个产

5、生作用：可以根据当前的输入符号是属于哪个产生式右部的首符集而决定选择相应产生式进行推导。式右部的首符集而决定选择相应产生式进行推导。 文法文法G3S: S aA | d A bAS | 输入串输入串W=abd。自顶向下的推导过程为自顶向下的推导过程为: S aA abAS abS abd相应的语法树为：相应的语法树为：S Sa aA Ab bA AS S d d设设G=(VG=(VT T，V VN N，S S，P)P)是上下文无关文法，是上下文无关文法，A A V VN N，S S是开始符号，则：是开始符号，则：Follow(A)Follow(A)= a = a V VT T | S | S+

6、 + .Aa. .Aa. (if S(if S* *.A then # else .A then # else ) ) 作用：当文法中存在作用：当文法中存在产生式产生式形如：形如：A A时，时，如果当前的字符属于如果当前的字符属于Follow(A)Follow(A)，则用空取，则用空取代代A A的出现。的出现。lFirst(First( ) )= a = a V VT T | | * * a. a. (if (if * * then then else else ) ) lFollow(A)Follow(A)= a = a V VT T | S | S+ + .Aa. .Aa. (if S(i

7、f S* *.A then # else .A then # else ) )lPredict(APredict(A ) ) = First(= First( ) ) ， 当当First(First( ) )= First(= First( )-)- Follow(A) Follow(A) ，当当First(First( ) )对每一文法符号对每一文法符号X X计算计算First(X)First(X)l若若X X V VT T, ,First(X)=XFirst(X)=Xl若若X X V VN N则则 First(X)=a| XFirst(X)=a| Xaa PSet,aPSet,a V VT

8、 T l若若X X V VN N, ,且有产生式且有产生式X X, ,则则 First(X)First(X)l若若X X V VN N, ,有产生式有产生式X XY Y1 1Y Y2 2YYn n，且且Y Y1 1,Y,Y2 2,Y,Yi i V VN N 当当Y Y1 1,Y,Y2 2,Y,Yi-1i-1* * ， 则则First(YFirst(Y1 1)-)- ,First(Y,First(Y2 2)-)- , First(Y First(Yi-1i-1)-)- , First(Y, First(Yi i) )都包含在都包含在First(X)First(X)中中。 当当Y Yi i * *

9、 (i=1,2,n), (i=1,2,n), 将将 并入并入First(X)First(X) 中。中。若符号串若符号串 = =X X1 1X X2 2XXn n，l当当X X1 1,X,X2 2,X,Xi-1i-1* * ，X Xi i不能不能 * * ，则，则First(First( )=)= 1 1i-1i-1(First(X(First(Xj j)-)- ) ) First(X First(Xi i) )l若所有若所有X Xi i都能都能* * ，则，则First(First( )= )= 1 1n nFirst(XFirst(Xj j) )1:1:对所有对所有A A V VN N，令令

10、Follow(A):= Follow(A):= ；对开始符对开始符S,S, 令令Follow(S):=# Follow(S):=# ； 2:2:若有产生式若有产生式AxByAxBy， 如果如果First(y) First(y) 则：则： Follow(B):= First(y)Follow(B):= First(y) 否则否则 Follow(B):=(First(y)Follow(B):=(First(y) ) ) Follow(A) Follow(A)3:3:重复重复2 2和和3 3，直至对所有，直至对所有A A V VN N，Follow(A)Follow(A)收收 敛为止。敛为止。lPr

11、edict(A ) = First( ) ，当当First( )不含不含 = First( )- Follow(A) ， 当当First( )含含 例子：E E T E T EE E + T E + T E | | T T F T F TT T * * F T F T | | F F id | ( E ) id | ( E )lPredict( ETE ) = first(TE) = id , ( lPredict( E +TE ) = first(+TE) = + lPredict( E ) = follow(E) = ) , # lPredict( T FT ) = first(FT) =

12、 id , ( lPredict( T *FT ) = first(*FT) = * lPredict( T ) = follow(T) = + , ) , # lPredict( F id ) = first(id) = id lPredict( F (E) ) = first(E) = ( q自顶向下分析方法的条件：自顶向下分析方法的条件： predict(Apredict(A k k) ) predict(Apredict(A j j )=)=，当当k k j j q产生式产生式AA 被选择的条件是：被选择的条件是： 当前的输入符属于当前的输入符属于predict(predict(AA

13、) )。q至多一个产生式被选择的条件是：至多一个产生式被选择的条件是： predict(A predict(A k k) ) predict(A predict(A j j )=)=，当当k k j jl自顶向下分析的条件自顶向下分析的条件递归下降法递归下降法( (Recursive-Descent Parsing)Recursive-Descent Parsing) 对每个非终极符按其产生式结构产生相对每个非终极符按其产生式结构产生相应语法分析子程序应语法分析子程序. . 终极符产生匹配命令终极符产生匹配命令 非终极符则产生调用命令非终极符则产生调用命令 文法递归相应子程序也递归，所以称这文

14、法递归相应子程序也递归，所以称这种方法为种方法为递归子程序方法或递归下降法递归子程序方法或递归下降法则对应产生式右部的语法分析程序部分则对应产生式右部的语法分析程序部分如下：如下：begin Match($while)； Exp； Match($do)； Stm end whilewhile xyxy dodo if xz then x:= x+y else x:= yif xz then x:= x+y else x:= y Begin Begin Match($while)Match($while); ; ExpExp; ; Match($do)Match($do); ; StmStm E

15、nd Endl 当产生式中形如当产生式中形如: : A A 1 1| | 2 2| | | | n n 则按下面的方法编写子程序则按下面的方法编写子程序A A： procedure A( )procedure A( ) begin if token begin if token Predict(APredict(A1 1) then ) then ( ( 1 1) ) else else if token if token Predict(APredict(A2 2) then ) then ( ( 2 2) ) else else if token if token Predict(APre

16、dict(An) then n) then ( ( n n) ) else else err( ) err( ) end end 其中对其中对 i=X1X2Xn， ( i) = (X1); (X2); (Xn); 如果如果X V VN N， (X)= X 如果如果X V VT T， (X)= Match(X) 如果如果X= , ( ) = skip(空语句空语句)假设有文法假设有文法Z Z a a B B a aB B b b B B | | c c则相应的递归子程序可如下：则相应的递归子程序可如下：procedure procedure Z( )Z( )beginbegin ifif tok

17、en=a token=a thenthen Match(a)Match(a)； B B； Match(a)Match(a) else else err( )err( )end;end;procedureprocedure B ( ) B ( )beginbegin if if token = b token = b thenthen Match(b)Match(b); ; B; B; elseelse if if token = token = c c thenthen Match(c);Match(c); elseelse err( )err( )end;end;主程序：主程序：BeginB

18、egin ReadToken ReadToken; ; Z Z endendReadTokenReadTokenReadTokenReadTokenlLL(1)LL(1)是是LL(k)LL(k)的特例的特例, ,其中的其中的k k则表示向前看则表示向前看k k个符号。个符号。 lLL(1)LL(1)方法和递归下降法属于同一级别的自顶方法和递归下降法属于同一级别的自顶向下分析法，但有一些区别向下分析法，但有一些区别. . 递归下降法对每个非终极符产生子程序，而递归下降法对每个非终极符产生子程序，而LL(1)LL(1)方方法则产生法则产生LLLL分析表；分析表；递归下降法能判断每个产生式的结束，而

19、递归下降法能判断每个产生式的结束，而LL(1)LL(1)方法方法则不能；则不能；递归下降法分析法不用符号栈，而递归下降法分析法不用符号栈，而LL(1)LL(1)方法则用符方法则用符号栈。号栈。 对于任一非终极符对于任一非终极符A A，其任意两个产生式其任意两个产生式AA 和和AA ，都要满足下面条件：都要满足下面条件： Predict(APredict(A ) ) Predict(APredict(A )= )= 满足这一条件的文法称为满足这一条件的文法称为LL(1)LL(1)文法。文法。 l文法文法GA: A GA: A a B c a B c11l B B d d 22| b B| b B

20、33l输入串：输入串：abbdcabbdcl分析过程：分析过程：l( (A,abbdc)A,abbdc)1 1(aBc,abbdc) (aBc,abbdc) (Bc,bbdc) (Bc,bbdc) 3 3(bBc,bbdc) (bBc,bbdc) (Bc,bdc) (Bc,bdc) 3 3 (bBc,bdc) (bBc,bdc) (Bc,dc) (Bc,dc) 2 2 (dc,dc) (dc,dc) (c,c) (c,c) ( , )( , )l替换：替换：当当X X1 1 V VN N时选相应候选式时选相应候选式 去替换去替换X X1 1。l匹配：匹配：当当X X1 1 V VT T时它与时

21、它与Y Y1 1进行匹配，其结果可进行匹配，其结果可能成功，也可能失败，如果成功则去掉能成功，也可能失败，如果成功则去掉X X1 1和和Y Y1 1，否则报错。否则报错。l接受：接受：当格局为（空，空）时报分析成功。当格局为（空，空）时报分析成功。l报错：报错：出错后，停止分析。出错后，停止分析。lLLLL（1 1）语法分析表（）语法分析表（LLLL（1 1）矩阵）矩阵）lLLLL（1 1）语法分析驱动程序）语法分析驱动程序lT T：V VN N V VT T P P Error Error T(A,t)=AT(A,t)=A 若若t t Predict( APredict( A ) ) T(A

22、,t)=Error T(A,t)=Error 否则否则 其中其中P P表示所有产生式的集合表示所有产生式的集合 StackInputa 栈为空情形的处理栈为空情形的处理 X VT情形的处理情形的处理 X VN情形的处理情形的处理 XLL1分析分析表表11初始化：初始化： Stack :=emptyStack :=empty；Push(S)Push(S)；22读下一个输入符：读下一个输入符： Read(a)Read(a)；33若当前格局是若当前格局是( ( empty, # )empty, # )，则成功结束；则成功结束； 否则转下；否则转下；44设当前格局为（设当前格局为（ X., a.)X.

23、, a.)，则则 若若 X X V VT T & X=a& X=a 则则 Pop(1)Pop(1)；Read(a)Read(a)；goto 3 goto 3 若若 X X V VT T & X & X a a 则则 ErrorError； 若若 X X V VN N，则：则： if T(X,a)=XYif T(X,a)=XY1 1Y Y2 2 Y Yn n then Pop(1)then Pop(1)；Push(YPush(Y1 1 , ,.,Y,Yn n) )；goto3 goto3 else Error else Error l文法文法G:G: E TE1E+TE2| 3TFT4T*FT5| 6Fid7|(E)8符号串符号串 i + i i + i * * i #