第5章LL(1)文法及其分析程序

1、第5章 LL(1)文法及其分析程序5.1 5.1 預(yù)測分析預(yù)測分析程序程序5.2 LL(1)5.2 LL(1)文法文法uFIRSTFIRST和和FOLLOWFOLLOW集定義和計算集定義和計算LL(1) LL(1) u文法定義文法定義LL(1)LL(1)分析程序的生成分析程序的生成 5.3 5.3 非非LL(1)LL(1)文法的改造文法的改造自上而下分析算法要點：.由根向下構(gòu)造語法樹.構(gòu)造最左推導(dǎo).推導(dǎo)出的終結(jié)符是否與當前輸入符匹配 S aaab A Ba AS ABA aA | B b | bBaaab.S AB S AB aAB A aA aaAB A aA aaaAB A aA aaa

2、B A aaab B b帶回溯的自上而下分析S ABA aA | B b | bBa a a b b.S(1) A. S AB(2) aA. A aA(3) aaA. A aA (4) aaaA. A aA (5) aaa B. A (6) aaab B baaabb.S(1) A. S AB (2) aA. A aA (3) aaA. A aA (4) aaaA. A aA (5) aaa B A (6) aaa b B B bB(7) aaabb B b 預(yù)測分析程序Predictive parser無回溯的自頂向下分析程序特征根據(jù)下一個輸入符號為當前要處理 的非終結(jié)符選擇產(chǎn)生式要求文法是

3、LL(1)的 第一個L 從左到右掃描輸入串 第二個L 生成的是最左推導(dǎo) 1 向前看一個輸入符號（lookahead)預(yù)測分析程序的實現(xiàn)技術(shù) 1 遞歸下降子程序 2 表驅(qū)動分析程序PL/0語言的EBNF程序程序=分程序分程序. .分程序分程序=常量說明部分常量說明部分變量說明部變量說明部 分分過程說明部分過程說明部分 語句語句常量說明部分常量說明部分=CONST=CONST常量定義部分常量定義部分 ，常量，常量 定義定義 ；變量說明部分變量說明部分=VAR=VAR標識符標識符 ，標識符，標識符 ；過程說明部分過程說明部分= PROCEDURE = PROCEDURE 標識符分程序標識符分程序 ；

4、過程說明部分；過程說明部分 ；語句語句= = 標識符：標識符：= =表達式表達式 |IF |IF 條件條件 thenthen語句語句|CALL|READ|BEGIN |CALL|READ|BEGIN 語句語句 ；語；語句句 END|WHILE| END|WHILE|begin(*statement*) if sym=ident then (*parsing ass.st.*) begin getsym; if sym=becomes then getsym else error(13); expression(fsys); endelse if sym=readsym then(* parsi

5、ng read st.*)begin getsym; if symlparen then error(34) else repeat getsym; if sym ident then error(35) else getsym until symcomma; if symrparen then error(33);end遞歸下降子程序program function_listfunction_list function function_list | function FUNC identifier ( parameter_list ) statementvoid ParseFunction

6、()MatchToken(T_FUNC);ParseIdentifier();MatchToken(T_LPAREN);ParseParameterList();MatchToken(T_RPAREN);ParseStatement();void MatchToken(int expected)if (lookahead != expected) printf(syntax error n);exit(0); else / if match, consume token and move onlookahead = yylex();例：遞歸子程序?qū)崿F(xiàn) 表達式的語法分析表達式的表達式的EBNF表

7、達式表達式=+|-=+|-項項 （+|-+|-）項）項 項項=因子因子 （* *|/|/）因子）因子 因子因子=identident| |numbernumber|（表達式表達式）procedure expr;procedure expr;beginbegin if sym in plus, minus then if sym in plus, minus then begin begin getsym; term; getsym; term; end endelse term;else term; while sym in plus, minus do while sym in plus,

8、minus do begin begin getsym; term; getsym; term; end endend;end; Procedure term;Procedure term; begin factor; begin factor; while sym in times,slash do while sym in times,slash do begin getsym;factor end begin getsym;factor endend;end; Procedure factor;Procedure factor; begin if sym=ident begin if s

9、ym=ident then getsym then getsym else else if sym=number if sym=number then getsym then getsym else else if sym=( if sym=( then begin then begin getsym; getsym; expr; expr; if sym=) if sym=) then getsym then getsym else error else error end end else error else error end; end; 表驅(qū)動予測分析程序模型 Input Input

10、 #總控程序總控程序預(yù)測分析表預(yù)測分析表stack 帶帶 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an 有限控制器有限控制器磁頭磁頭識別程序的數(shù)學模型下推自識別程序的數(shù)學模型下推自動機動機上下文無關(guān)語言句型分析（識別）程序的數(shù)學模型下推自動機下推自動機Pda=(K,f,H,hPda=(K,f,H,h0 0,S,Z),S,Z) H: H:下推棧符號的有窮字母表下推棧符號的有窮字母表 h h0 0 :H :H中的初始符號中的初始符號 f: K f: K （ ) H H K K H H* * PdaPda的一個組態(tài)是的一個組態(tài)是K K * * H H 中的一個（中的一個（k,

11、w,k,w, ) k:) k:當前狀當前狀態(tài)，態(tài)，w:w:余留輸入串，余留輸入串， ：棧中符號，最左邊的符號在棧頂。：棧中符號，最左邊的符號在棧頂。PdaPda的一次移動用組態(tài)表示的一次移動用組態(tài)表示終止和接受的條件終止和接受的條件: : 1. 1.到達輸入串結(jié)尾時，處在到達輸入串結(jié)尾時，處在Z Z中的一個狀態(tài)中的一個狀態(tài)或或 2. 2.某個動作序列導(dǎo)致?？諘r某個動作序列導(dǎo)致?？諘r 例：Pda P=(A,B,C),a,b,c),f,h,i,i A, )f(A,a,i) = (B,h) f(B,a,h) = (B,hh)f(A,a,i) = (B,h) f(B,a,h) = (B,hh) f(C

12、,b,h) = (C, f(C,b,h) = (C, ) f(A,c,i) = (A, ) f(A,c,i) = (A, ) ) f(B,c,h) = (C,h) f(B,c,h) = (C,h) 接受輸入串接受輸入串a(chǎn)acbbaacbb的過程的過程(A,aacbb,i) 讀a, pop i, push h, goto B (B,acbb,h) 讀a, pop h, push hh, goto B (B,cbb,hh) 讀c, pop h, push h , goto C (C,bb,hh) 讀b, pop h, push , goto C (C,b,h) 讀b ,pop h, push ,

13、goto C (C, , , ) ) G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a a + * ( ) # E (1) (1) E (2) (3) (3) T (4) (4) T (6) (5) (6) (6) F (8) (7)G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a分析算法 BEGINBEGIN 首先把首先把#然后把文法開始符號推入棧；把第一個輸入然后把文法開始符號推入棧；把第一個輸入符號

14、讀進符號讀進b; FLAGb; FLAG：=TRUE=TRUE；WHILE FLAG DOWHILE FLAG DO BEGIN BEGIN 把棧頂符號上托出去并放在把棧頂符號上托出去并放在中；中； IF X IF X Vt THEN IF X=b THEN Vt THEN IF X=b THEN 把下一個輸入符號讀進把下一個輸入符號讀進a a ELSE ERROR ELSE ERROR ELSE IF X=# THEN ELSE IF X=# THEN IF X=b THEN FLAG:=FALSE IF X=b THEN FLAG:=FALSE ELSE ERROR ELSE ERROR

15、ELSE IF ELSE IF X,b=X X,b=X X X1 1X X2 2.X.XK K THEN THEN 把把X XK K，X X K-1K-1,.,X,.,X1 1一一推進棧一一推進棧 ELSE ELSEERRORERROR END OF WHILE; END OF WHILE;STOP/STOP/* *分析成功，過程完畢分析成功，過程完畢* *ENDEND分析輸入串#a+a#棧內(nèi)容 棧頂符號 當前輸入 余留串 MX,b 1 #E E a +a# E TE2 #ET T a +a# T FT3 #ETF F a +a# F a4 #ETa a a +a#5 # ET T + a#

16、T 6 #E E + a# E +TE7 #ET+ + + a#8 # ET T a # T FT 9 #ETF F a # F a10 #ETa a a #11 #ET T # T 12 #E E # E 13 # # #FIRSTFIRST集和集和FOLLOWFOLLOW集的定義集的定義 設(shè)設(shè)G=(VG=(VT T,V,VN N,P,P，S)S)是上下文無關(guān)文法是上下文無關(guān)文法FIRSTFIRST（ ）=a|=a| =* a a ,a,aV VT T, , , , VV* * 若若 =* 則規(guī)定則規(guī)定FRISTFRIST（ ）FOLLOWFOLLOW（A A）=a=a S S =* A A

17、 且且a a FRISTFRIST（ ），）， VV* *， VV+ + 若若S S =* u A u A , ,且且 =* ，則，則#F#FOLLOW(A)OLLOW(A)LL (1) 文法計算FIRST集1.1.若若X X V V , ,則則FIRST(X)=XFIRST(X)=X2.2.若若X X V VN N, ,且有產(chǎn)生式且有產(chǎn)生式X Xaa，則把，則把a a加入到加入到FIRST(X)FIRST(X)中中; ;若若X X也是一條產(chǎn)生式也是一條產(chǎn)生式, ,則把則把 也加到也加到FIRST(X)FIRST(X)中中. .3.3.若若X XYY是一個產(chǎn)生式且是一個產(chǎn)生式且Y Y V VN

18、 N, ,則把則把FIRST(Y)FIRST(Y)中的中的所有非所有非 元元素都加到素都加到FIRST(X)FIRST(X)中中; ;若若X X Y Y1 1Y Y2 2YYK K 是是一個產(chǎn)生式一個產(chǎn)生式,Y,Y1 1,Y,Y2 2,Y,Y(i-1)(i-1)都是非終結(jié)符都是非終結(jié)符, ,而且而且, ,對對于任何于任何j,1j,1j j i-i-1, FIRST(Y1, FIRST(Yj j) )都含有都含有 ( (即即Y Y1 1.Y.Y(i-1) (i-1) =* ), ),則把則把FIRST(YFIRST(Yj j) )中的所有非中的所有非 元素元素都加到都加到FIRST(X)FIRS

19、T(X)中中; ;特別是特別是, ,若所有的若所有的FIRST(YFIRST(Yj j , , j=1,2,K)j=1,2,K)均含有均含有 , ,則把則把 加到加到FRIST(X)FRIST(X)中中. . 計算FOLLOW集1.1.對于文法的開始符號對于文法的開始符號S,S,置置# #于于FOLLOW(S) FOLLOW(S) 中中; ;2.2.若若 B B 是一個產(chǎn)生式是一個產(chǎn)生式, ,則把則把 FIRST()FIRST() 加至加至FOLLOW(B)FOLLOW(B)中中; ;3.3.若若 B B是一個產(chǎn)生式是一個產(chǎn)生式, ,或或 B B是是 一個產(chǎn)生式而一個產(chǎn)生式而 =* ( (即即

20、FIRST()FIRST()）， 則把則把FOLLOWFOLLOW（A A）加至）加至FOLLOWFOLLOW（B B）中）中 一個文法一個文法G G是是LLLL（1 1）的，當且僅當對于）的，當且僅當對于G G的每一個的每一個非終結(jié)符的任何兩個不同產(chǎn)生式非終結(jié)符的任何兩個不同產(chǎn)生式 ，下面的條件成立：下面的條件成立：FIRSTFIRST（）FIRST()=FIRST()= , ,也就是也就是 和和推推導(dǎo)不出以同一個終結(jié)符導(dǎo)不出以同一個終結(jié)符a a為首的符號串；它們不為首的符號串；它們不應(yīng)該都能推出空字應(yīng)該都能推出空字 . .假若假若 =* ，那么，那么， FIRSTFIRST（)FOLLOW

21、)FOLLOW（A A） . . 也就是，也就是， 若若 =* . .則則所能推出的串的首符號不應(yīng)在所能推出的串的首符號不應(yīng)在FOLLOW(AFOLLOW(A）中）中G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a各非終結(jié)符的FIRST集合如下：FIRST(E)=(,iFIRST(E)=+,FIRST(T)=(,iFIRST(T)=*,FIRST(F)=(,i各非終結(jié)符的FOLLOW集合為：FOLLOW(E)=),FOLLOW(E)=)，F(xiàn)OLLOW(T)=，)，F(xiàn)OLLOW(T)=,)，# FOL

22、LOW(F)=*,，),# G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F aE +TE | FIRST(+TE)=FIRST(+TE)=+ + FOLLOW(E)=FOLLOW(E)=) )，T *FT | FIRST(FIRST(* *FT)=FT)=* * FOLLOW(T)=FOLLOW(T)=+,)+,)，F(xiàn) (E) | a FIRST( (E)=FIRST( (E)=( ( FIRST( a)=FIRST( a)=a a所以所以GEGE是是LLLL（1 1）的）的予測分析表構(gòu)造算法1.1.

23、對文法對文法G G的每個產(chǎn)生式的每個產(chǎn)生式 執(zhí)行第二步執(zhí)行第二步 和第三步；和第三步；2.2.對每個終結(jié)符對每個終結(jié)符a a FIRST(FIRST( ) )，把，把 加加 至至A,aA,a中，中，3.3.若若 FIRST(FIRST( ) )，則對任何，則對任何b b FOLLOW(A)FOLLOW(A) 把把 加至加至A,bA,b中，中，4.4.把所有無定義的把所有無定義的A,aA,a標上標上“出錯標志出錯標志”?？梢宰C明，一個文法可以證明，一個文法G G的予測分析表不含多重的予測分析表不含多重入口，當且僅當該文法是入口，當且僅當該文法是LL(1)LL(1)的的LL(1)LL(1)文法的性

24、質(zhì)文法的性質(zhì)： LL(1)LL(1)文法是無二義的文法是無二義的 LL(1)LL(1)文法不含左遞歸文法不含左遞歸非非LL(1)LL(1)文法的改造文法的改造消除左遞歸消除左遞歸提左公因子提左公因子 將產(chǎn)生式將產(chǎn)生式 | 變換為：變換為： B B B B | EE+TTTT*FFFi(E)FIRST(E)=(,iFIRST(T)=(,iFIRST(F)=(,i消左遞歸 E TE E +TE E S S ifif C t S | C t S | ifif C t S e S C t S e SC bC b提左因子提左因子 S S ifif C t S A C t S A A e S | A e

25、S | First First集集 FollowFollow集集S S ifif #,e #,eA e, A e, #, eC b tMA,e=A e S A e S A A LL(1)分析中的一種錯誤處理辦法發(fā)現(xiàn)錯誤發(fā)現(xiàn)錯誤1棧頂?shù)慕K結(jié)符與當前輸入符不匹配2非終結(jié)符A于棧頂，面臨的輸入符為a，但分析表M的MA,a為空“應(yīng)急應(yīng)急”恢復(fù)策略恢復(fù)策略跳過輸入串中的一些符號直至遇到“同步符號”為止。同步符號的選擇同步符號的選擇1把FOLLOW(A)中的所有符號作為A的同步符號。跳過輸入串中的一些符號直至遇到這些“同步符號”，把A從棧中彈出，可使分析繼續(xù)2把FIRST(A)中的符號加到A的同步符號集，

26、當FIRST(A)中的符號在輸入中出現(xiàn)時，可根據(jù)A恢復(fù)分析 a + * ( ) # E (1) (1) E (2) (3) (3) T (4) (4) T (6) (5) (6) (6) F (8) (7)G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a syn review-parsingThe syntax analysis phase of a compiler verifies that the sequence of tokens returned from the scanner rep

27、resent valid sentences in the grammar of the programming language. There are two major parsing approaches: top-down and bottom-up. In top-down parsing, you start with the start symbol and apply the productions until you arrive at the desired string. In bottom-up parsing, you start with the string an

28、d reduce it to the start symbol by applying the productions backwards. In the top-down parsing,we begin with the start symbol and at each step, expand one of the remaining nonterminals by replacing it with the right side of one its productions.We repeat until only terminals remain. The top-down pars

29、e prints a leftmost derivation of the sentence.A bottom-up parse works in reverse. We begin with the sentence of terminals and each step applies a production in reverse, replacing a substring that matches the right side with the nonterminal on the left. We continue until we have substituted our way

30、back to the start symbol. If you read from the bottom to top, the bottom-up parse prints out a rightmost derivation of the sentence. lookahead symbol. The lookahead symbol is the next symbol coming up in the input. backtracking. Based on the information the parser currently has about the input, a de

31、cision is made to go with one particular production. If this choice leads to a dead end, the parser would have to backtrack to that decision point, moving backwards through the input, and start again making a different choice and so on until it either found the production that was the appropriate on

32、e or ran out of choices.predictive parser and LL(1)grammarPredictive parser is a non-backtracking top-down parser. A predictive parser is characterized by its ability to choose the production to apply solely on the basis of the next input symbol and the current nonterminal being processed. To enable

33、 this, the grammar must take a particular form. We call such a grammar LL(1). The first “L” means we scan the input from left to right; the second “L” means we create a leftmost derivation; and the 1 means one input symbol of lookahead.recursive-descentThe first technique for implementing a predicti

34、ve parser is called recursive-descent. A recursive descent parser consists of several small functions(procedures), one for each nonterminal in the grammar. As we parse a sentence, we call the functions (procedures) that correspond to the left side nonterminal of the productions we are applying. If t

35、hese productions are recursive, we end up calling the functions recursively.Table-driven LL(1) parsing In a recursive-descent parser, the production information is embedded in the individual parse functions for each nonterminal and the run-time execution stack is keeping track of our progress throug

36、h the parse. There is another method for implementing a predictive parser that uses a table to store that production along with an explicit stack to keep track of where we are in the parse. How a table-driven predictive parser works We push the start symbol on the stack and read the first input toke

37、n. As the parser works through the input, there are the following possibilities for the top stack symbol X and the input token nonterminal a:1. If X = a and a = end of input (#): parser halts and parse completed successfully2. If X = a and a != #: successful match, pop X and advance to next input to

38、ken. This is called a match action.3. If X != a and X is a nonterminal, pop X and consult table at X,a to see which production applies, push right side of production on stack. This is called a predict action.4. If none of the preceding cases applies or the table entry from step 3 is blank, there has

39、 been a parse errorThe first set of a sequence of symbols u, written as First(u ) is the set of terminals whichstart all the sequences of symbols derivable from u. A bit more formally, consider allstrings derivable from u by a leftmost derivation. If u =* v , where v begins with someterminal, that t

40、erminal is in First(u). If u =* , then is in First(u ).The follow set of a nonterminal A is the set of terminal symbols that can appear immediately to the right of A in a valid sentence. A bit more formally, for every valid sentence S =*uAv , where v begins with some terminal, that terminal is in Fo

41、llow(A).Computing first To calculate First(u) where u has the form X1X2.Xn, do the following:1. If X1 is a terminal, then add X1 to First(u), otherwise add First(X1) - to First(u ) .2. If X1 is a nullable nonterminal, i.e., X1 =* , add First(X2) - to First(u). Furthermore, if X2 can also go to , the

42、n add First(X3) - and so on, through all Xn until the first nonnullable one.3. If X1X2.Xn =* , add to the first set.Calculating follow sets. For each nonterminal in the grammar, do the following:1. Place# in Follow(S) where S is the start symbol and # is the inputs right endmarker.The endmarker migh

43、t be end of file, it might be newline, it might be a special symbol, whatever is the expected end of input indication for this grammar. We will typically use # as the endmarker.2. For every production A uBv where u and v are any string of grammar symbols and B is a nonterminal, everything in First(v

44、) except is placed in Follow(B).3. For every production A uB, or a production A u Bv where First(v ) contains (i.e. v is nullable), then everything in Follow(A) is added to Follow(B).Constructing the parse table1. For each production A u of the grammar, do steps 2 and 32. For each terminal a in First(u), add A