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

1、第5章 LL(1)文法及其分析程序5.1 5.1 預(yù)測(cè)分析預(yù)測(cè)分析程序程序5.2 LL(1)5.2 LL(1)文法文法uFIRSTFIRST和和FOLLOWFOLLOW集定義和計(jì)算集定義和計(jì)算LL(1) LL(1) u文法定義文法定義LL(1)LL(1)分析程序的生成分析程序的生成 5.3 5.3 非非LL(1)LL(1)文法的改造文法的改造自上而下分析算法要點(diǎn)：.由根向下構(gòu)造語(yǔ)法樹(shù).構(gòu)造最左推導(dǎo).推導(dǎo)出的終結(jié)符是否與當(dāng)前輸入符匹配 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ù)測(cè)分析程序Predictive parser無(wú)回溯的自頂向下分析程序特征根據(jù)下一個(gè)輸入符號(hào)為當(dāng)前要處理 的非終結(jié)符選擇產(chǎn)生式要求文法是

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

4、過(guò)程說(shuō)明部分；過(guò)程說(shuō)明部分 ；語(yǔ)句語(yǔ)句= = 標(biāo)識(shí)符：標(biāo)識(shí)符：= =表達(dá)式表達(dá)式 |IF |IF 條件條件 thenthen語(yǔ)句語(yǔ)句|CALL|READ|BEGIN |CALL|READ|BEGIN 語(yǔ)句語(yǔ)句 ；語(yǔ)；語(yǔ)句句 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) 表達(dá)式的語(yǔ)法分析表達(dá)式的表達(dá)式的EBNF表

7、達(dá)式表達(dá)式=+|-=+|-項(xiàng)項(xiàng) （+|-+|-）項(xiàng)）項(xiàng) 項(xiàng)項(xiàng)=因子因子 （* *|/|/）因子）因子 因子因子=identident| |numbernumber|（表達(dá)式表達(dá)式）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ū)動(dòng)予測(cè)分析程序模型 Input Input

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

11、w,k,w, ) k:) k:當(dāng)前狀當(dāng)前狀態(tài)，態(tài)，w:w:余留輸入串，余留輸入串， ：棧中符號(hào)，最左邊的符號(hào)在棧頂。：棧中符號(hào)，最左邊的符號(hào)在棧頂。PdaPda的一次移動(dòng)用組態(tài)表示的一次移動(dòng)用組態(tài)表示終止和接受的條件終止和接受的條件: : 1. 1.到達(dá)輸入串結(jié)尾時(shí)，處在到達(dá)輸入串結(jié)尾時(shí)，處在Z Z中的一個(gè)狀態(tài)中的一個(gè)狀態(tài)或或 2. 2.某個(gè)動(dòng)作序列導(dǎo)致棧空時(shí)某個(gè)動(dòng)作序列導(dǎo)致?？諘r(shí) 例：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的過(guò)程的過(guò)程(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 首先把首先把#然后把文法開(kāi)始符號(hào)推入棧；把第一個(gè)輸入然后把文法開(kāi)始符號(hào)推入棧；把第一個(gè)輸入符號(hào)

14、讀進(jìn)符號(hào)讀進(jìn)b; FLAGb; FLAG：=TRUE=TRUE；WHILE FLAG DOWHILE FLAG DO BEGIN BEGIN 把棧頂符號(hào)上托出去并放在把棧頂符號(hào)上托出去并放在中；中； IF X IF X Vt THEN IF X=b THEN Vt THEN IF X=b THEN 把下一個(gè)輸入符號(hào)讀進(jìn)把下一個(gè)輸入符號(hào)讀進(jìn)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一一推進(jìn)棧一一推進(jìn)棧 ELSE ELSEERRORERROR END OF WHILE; END OF WHILE;STOP/STOP/* *分析成功，過(guò)程完畢分析成功，過(guò)程完畢* *ENDEND分析輸入串#a+a#棧內(nèi)容 棧頂符號(hào) 當(dāng)前輸入 余留串 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)是上下文無(wú)關(guān)文法是上下文無(wú)關(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) 文法計(jì)算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(bǔ) a加入到加入到FIRST(X)FIRST(X)中中; ;若若X X也是一條產(chǎn)生式也是一條產(chǎn)生式, ,則把則把 也加到也加到FIRST(X)FIRST(X)中中. .3.3.若若X XYY是一個(gè)產(chǎn)生式且是一個(gè)產(chǎn)生式且Y Y V VN

18、 N, ,則把則把FIRST(Y)FIRST(Y)中的中的所有非所有非 元元素都加到素都加到FIRST(X)FIRST(X)中中; ;若若X X Y Y1 1Y Y2 2YYK K 是是一個(gè)產(chǎn)生式一個(gè)產(chǎn)生式,Y,Y1 1,Y,Y2 2,Y,Y(i-1)(i-1)都是非終結(jié)符都是非終結(jié)符, ,而且而且, ,對(duì)對(duì)于任何于任何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)中中. . 計(jì)算FOLLOW集1.1.對(duì)于文法的開(kāi)始符號(hào)對(duì)于文法的開(kāi)始符號(hào)S,S,置置# #于于FOLLOW(S) FOLLOW(S) 中中; ;2.2.若若 B B 是一個(gè)產(chǎn)生式是一個(gè)產(chǎn)生式, ,則把則把 FIRST()FIRST() 加至加至FOLLOW(B)FOLLOW(B)中中; ;3.3.若若 B B是一個(gè)產(chǎn)生式是一個(gè)產(chǎn)生式, ,或或 B B是是 一個(gè)產(chǎn)生式而一個(gè)產(chǎn)生式而 =* ( (即即

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

21、)FOLLOW（A A） . . 也就是，也就是， 若若 =* . .則則所能推出的串的首符號(hào)不應(yīng)在所能推出的串的首符號(hào)不應(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）的）的予測(cè)分析表構(gòu)造算法1.1.

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

24、質(zhì)文法的性質(zhì)： LL(1)LL(1)文法是無(wú)二義的文法是無(wú)二義的 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)分析中的一種錯(cuò)誤處理辦法發(fā)現(xiàn)錯(cuò)誤發(fā)現(xiàn)錯(cuò)誤1棧頂?shù)慕K結(jié)符與當(dāng)前輸入符不匹配2非終結(jié)符A于棧頂，面臨的輸入符為a，但分析表M的MA,a為空“應(yīng)急應(yīng)急”恢復(fù)策略恢復(fù)策略跳過(guò)輸入串中的一些符號(hào)直至遇到“同步符號(hào)”為止。同步符號(hào)的選擇同步符號(hào)的選擇1把FOLLOW(A)中的所有符號(hào)作為A的同步符號(hào)。跳過(guò)輸入串中的一些符號(hào)直至遇到這些“同步符號(hào)”，把A從棧中彈出，可使分析繼續(xù)2把FIRST(A)中的符號(hào)加到A的同步符號(hào)集，

26、當(dāng)FIRST(A)中的符號(hào)在輸入中出現(xiàn)時(shí)，可根據(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