第五部分LL1文法及其分析程序教學(xué)ppt課件

1、第五章第五章 LL(1)LL(1)文法及其分析程序文法及其分析程序z5.1 5.1 預(yù)測(cè)分析程序預(yù)測(cè)分析程序z5.2 LL(1)5.2 LL(1)文法文法z FIRST FIRST和和FOLLOWFOLLOW集定義和計(jì)集定義和計(jì) 算算z LL(1) LL(1) 文法定義文法定義z LL(1) LL(1)分析程序的生成分析程序的生成z5.3 5.3 非非LL(1)LL(1)文法的改造文法的改造自上而下分析算法自上而下分析算法要點(diǎn)：.由根向下構(gòu)造語法樹.構(gòu)造最左推導(dǎo).推導(dǎo)出的終結(jié)符能否與當(dāng)前輸入符匹配 S aaab A Ba AS ABA aA | B b | bBaaab.S AB S AB a

2、AB A aA aaAB A aA aaaAB A aA aaa 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無回溯的自頂向下分析程序

3、特征根據(jù)下一個(gè)輸入符號(hào)為當(dāng)前要處置 的非終結(jié)符選擇產(chǎn)生式要求文法是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/0PL/0言語的言語的EBNFEBNFv程序程序=分程序分程序. .v分程序分程序=常量闡明部分常量闡明部分變量闡明部變量闡明部 分分過程闡明部分過程闡明部分 語句語句v常量闡明部分常量闡明部分=CONST=CONST常量定義部分常量定義部分 ，常，常量量 定義定義 ；v變量闡明部分變量闡明部分=VAR=VAR標(biāo)識(shí)符標(biāo)識(shí)符 ，標(biāo)識(shí)符，標(biāo)識(shí)符 ；v過程

4、闡明部分過程闡明部分= PROCEDURE = PROCEDURE 標(biāo)識(shí)符分程序標(biāo)識(shí)符分程序 ；過程闡明部分；過程闡明部分 ；v語句語句= = 標(biāo)識(shí)符：標(biāo)識(shí)符：= =表達(dá)式表達(dá)式 |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); expr

5、ession(fsys); endelse if sym=readsym then(* parsing 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 i

6、dentifier ( parameter_list ) statementvoid ParseFunction()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 mo

7、ve onlookahead = yylex();例：遞歸子程序?qū)崿F(xiàn)例：遞歸子程序?qū)崿F(xiàn) 表達(dá)式的語法分析表達(dá)式的語法分析表達(dá)式的表達(dá)式的EBNF表達(dá)式表達(dá)式 =+|-項(xiàng)項(xiàng)+|-項(xiàng)項(xiàng)項(xiàng)項(xiàng) =因子因子*|/因子因子因子因子 =ident|number|表達(dá)式表達(dá)式zprocedure 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

8、sym in plus, minus do while sym in plus, 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;Proced

9、ure factor; begin if sym=ident begin if sym=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 e

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

11、是K K * * H H 中的一個(gè)中的一個(gè)k,w,k,w,) k:) k:當(dāng)前當(dāng)前形狀，形狀，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è)形狀中的一個(gè)形狀或或 2. 2.某個(gè)動(dòng)作序列導(dǎo)致?？諘r(shí)某個(gè)動(dòng)作序列導(dǎo)致棧空時(shí) 例：例：Pda P=(A,B,C),a,b,c),f,h,i,iPda P=(A,B,C),a,b,c),f,h,i,i A, ) A, )f(A,a,i) = (B,h

12、) f(B,a,h) = (B,hh)f(A,a,i) = (B,h) f(B,a,h) = (B,hh) f(C,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,aacbb,i) 讀讀a, pop i, push h, goto Ba, pop i, push h, goto B (B,acbb,h) (B,acbb,h) 讀讀a, pop h, push hh,

13、goto B a, pop h, push hh, goto B (B,cbb,hh) (B,cbb,hh) 讀讀c, pop h, push h , goto Cc, pop h, push h , goto C (C,bb,hh) (C,bb,hh) 讀讀b, pop h, push b, pop h, push , goto C , goto C (C,b,h) (C,b,h) 讀讀b ,pop h, push b ,pop h, push , goto C , goto C (C, (C, , , ) ) G E: (1) E TE (2) E +TE (3) E (4) T FT (

14、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分析算法分析算法 z BEGINBEGINz 首先把首先把# #然后把文法開場(chǎng)符號(hào)推入棧；把第一個(gè)輸入符然后把文法開場(chǎng)符號(hào)推入棧；把第一個(gè)輸入符號(hào)讀進(jìn)號(hào)讀進(jìn)b; FLAGb; FLAG：=TRUE=TRUE；z WHILE FLAG DOWHI

15、LE FLAG DO BEGIN BEGINz 把棧頂符號(hào)上托出去并放在中；把棧頂符號(hào)上托出去并放在中；z IF X IF X Vt THEN IF X=b THEN Vt THEN IF X=b THENz 把下一個(gè)輸入符號(hào)讀進(jìn)把下一個(gè)輸入符號(hào)讀進(jìn)a az ELSE ERROR ELSE ERROR ELSE IF X= ELSE IF X=# # THEN THENz IF X=b THEN FLAG:=FALSE IF X=b THEN FLAG:=FALSEz ELSE ERROR ELSE ERRORz ELSE IF ELSE IF X,b=X X1X2.XKX,b=X X1X2.

16、XKz THEN THEN 把把XKXK，X K-1,.,X1X K-1,.,X1一一推進(jìn)棧一一推進(jìn)棧 z ELSE ELSEERRORERRORz END OF WHILE; END OF WHILE;z STOP/STOP/* *分析勝利，過程終了分析勝利，過程終了* *z 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# T 6 #E E + a# E +TE7 #ET+ + + a#8 # ET T

17、 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=(VT,VN,PG=(VT,VN,P，S)S)是上下文無關(guān)文法是上下文無關(guān)文法FIRSTFIRST=a|=a| = =* * a a,aVT, ,aVT, , , VV* * 假設(shè)假設(shè) = =* * 那么規(guī)定那么規(guī)定FRISTFRISTFOLLOWFOLLOWA A=a=aS =S =* * A A 且且a FRISTa FRIST， V V* *， V+ V+ 假設(shè)假設(shè)S

18、=S =* * u A u A , ,且且 = =* * ，那么，那么#FOLLOW(A)#FOLLOW(A)LL (1) LL (1) 文法文法計(jì)算計(jì)算FIRSTFIRST集集1.1.假設(shè)假設(shè)X XV V, ,那么那么FIRST(X)=XFIRST(X)=X2.2.假設(shè)假設(shè)X XVN,VN,且有產(chǎn)生式且有產(chǎn)生式X Xaa，那么把，那么把a(bǔ) a參與參與到到FIRST(X)FIRST(X)中中; ;假設(shè)假設(shè)X X也是一條產(chǎn)生式也是一條產(chǎn)生式, ,那那么把么把也加到也加到FIRST(X)FIRST(X)中中. .3.3.假設(shè)假設(shè)X XYY是一個(gè)產(chǎn)生式且是一個(gè)產(chǎn)生式且Y YVN,VN,那么把那么把F

19、IRST(Y)FIRST(Y)中的一切非中的一切非元素都加到元素都加到FIRST(X)FIRST(X)中中; ;假設(shè)假設(shè)X X Y1Y2YK Y1Y2YK 是一個(gè)產(chǎn)生是一個(gè)產(chǎn)生式式,Y1,Y2,Y(i-1),Y1,Y2,Y(i-1)都是非終結(jié)符都是非終結(jié)符, ,而且而且, ,對(duì)對(duì)于任何于任何j,1j i-1, FIRST(Yj)j,1j i-1, FIRST(Yj)都含有都含有 ( (即即Y1.Y(i-1) =Y1.Y(i-1) =* * ), ),那么把那么把FIRST(Yj)FIRST(Yj)中的一切非中的一切非元素都加到元素都加到FIRST(X)FIRST(X)中中; ;特別是特別是,

20、,假設(shè)一切的假設(shè)一切的FIRST(Yj , j=1,2,K)FIRST(Yj , j=1,2,K)均含有均含有, ,那么把那么把加到加到FRIST(X)FRIST(X)中中. . 計(jì)算計(jì)算FOLLOWFOLLOW集集1.1.對(duì)于文法的開場(chǎng)符號(hào)對(duì)于文法的開場(chǎng)符號(hào)S,S,置置# #于于FOLLOW(S) FOLLOW(S) 中中; ;2.2.假設(shè)假設(shè) B B 是一個(gè)產(chǎn)生式是一個(gè)產(chǎn)生式, ,那么把那么把 FIRST() FIRST() 加至加至FOLLOW(B)FOLLOW(B)中中; ;3.3.假設(shè)假設(shè) B B是一個(gè)產(chǎn)生式是一個(gè)產(chǎn)生式, ,或或 B B是是 一個(gè)產(chǎn)生式而一個(gè)產(chǎn)生式而 = =* *

21、( (即即FIRST()FIRST()， 那么把那么把FOLLOWFOLLOWA A加至加至FOLLOWFOLLOWB B中中 一個(gè)文法一個(gè)文法G G是是LLLL1 1的，當(dāng)且僅當(dāng)對(duì)于的，當(dāng)且僅當(dāng)對(duì)于G G的每一個(gè)的每一個(gè)非終結(jié)符的任何兩個(gè)不同產(chǎn)生式非終結(jié)符的任何兩個(gè)不同產(chǎn)生式 ，下面的條件成立：下面的條件成立：FIRSTFIRSTFIRST()=FIRST()=, ,也就是也就是和和推導(dǎo)不出以同一個(gè)終結(jié)符推導(dǎo)不出以同一個(gè)終結(jié)符a a為首的符號(hào)串；它們?yōu)槭椎姆?hào)串；它們不應(yīng)該都能推出空字不應(yīng)該都能推出空字. .假假設(shè)假假設(shè) = =* * ，那么，那么， FIRST FIRST)FOLLOW)F

22、OLLOWA A. . 也就是，也就是， 假設(shè)假設(shè) = =* * . .那么那么所能推出的串的首符號(hào)不所能推出的串的首符號(hào)不應(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)=,)，# FO

23、LLOW(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)=+ FOLLOW(E)=)，T *FT | FIRST(*FT)=* FOLLOW(T)=+,)，F(xiàn) (E) | a FIRST( (E)=( FIRST( a)=a所以所以GE是是LL1的的予測(cè)分析表構(gòu)造算法予測(cè)分析表構(gòu)造算法1.1.對(duì)文法對(duì)文法G G的每個(gè)產(chǎn)生式的每個(gè)產(chǎn)生式 執(zhí)行第二步執(zhí)行第二步 和第三步；和第三步；2.2.對(duì)每個(gè)終結(jié)符對(duì)每個(gè)終結(jié)符a aFIRST(FIRST()

24、)，把，把 加加 至至A,aA,a中，中，3.3.假設(shè)假設(shè) FIRST( FIRST() )，那么對(duì)任何，那么對(duì)任何b bFOLLOW(A) FOLLOW(A) 把把 加加至至A,bA,b中，中，4.4.把一切無定義的把一切無定義的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)文法的性質(zhì)：文法的性質(zhì)： LL(1) LL(1)文法是無二義的文法是無二義的 LL(1) LL(1)文法不含左遞歸文法不含左遞歸非非LL(1)LL(1)文法

25、的改造文法的改造消除左遞歸消除左遞歸提左公因子提左公因子 將產(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 if C t S |S if C t S | if C t S e S if C t S e SC bC b提左因子提左因子 S if C t S A S if C t S A A e S | A e S | First First集集 Follow Follow集集S if #,eS if #,eA e, A e, #, #, e e

26、C b C b t tMA,e=A e S MA,e=A e S A A LL(1)分析中的一種錯(cuò)誤處置方法發(fā)現(xiàn)錯(cuò)誤發(fā)現(xiàn)錯(cuò)誤1棧頂?shù)慕K結(jié)符與當(dāng)前輸入符不匹配棧頂?shù)慕K結(jié)符與當(dāng)前輸入符不匹配2非終結(jié)符非終結(jié)符A于棧頂，面臨的輸入符為于棧頂，面臨的輸入符為a，但分析表，但分析表M的的MA,a為為空空“應(yīng)急恢復(fù)戰(zhàn)略應(yīng)急恢復(fù)戰(zhàn)略跳過輸入串中的一些符號(hào)直至遇到跳過輸入串中的一些符號(hào)直至遇到“同步符號(hào)為止。同步符號(hào)為止。同步符號(hào)的選擇同步符號(hào)的選擇1把把FOLLOW(A)中的一切符號(hào)作為中的一切符號(hào)作為A的同步符號(hào)。跳過輸入串中的同步符號(hào)。跳過輸入串中的一些符號(hào)直至遇到這些的一些符號(hào)直至遇到這些“同步符號(hào)，

27、把同步符號(hào)，把A從棧中彈出，可使從棧中彈出，可使分析繼續(xù)分析繼續(xù)2把把FIRST(A)中的符號(hào)加到中的符號(hào)加到A的同步符號(hào)集，當(dāng)?shù)耐椒?hào)集，當(dāng)FIRST(A)中的中的符號(hào)在輸入中出現(xiàn)時(shí)，可根據(jù)符號(hào)在輸入中出現(xiàn)時(shí)，可根據(jù)A恢復(fù)分析恢復(fù)分析review-parsingThe syntax analysis phase of a compiler verifies that the sequence of tokens returned from the scanner represent valid sentences in the grammar of the programming lang

28、uage. 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 and reduce it to the start symbol by applying the productions b

29、ackwards. 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 parse prints a leftmost derivation of the sentence.A bottom-up pa

30、rse 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 back to the start symbol. If you read from the bottom to top,

31、 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 decision is made to go with one particular production. If this c

32、hoice 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 one or ran out of choices.predictive parser and LL(1)grammarPred

33、ictive 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 this, the grammar must take a particular form. We call such a

34、 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 predictive parser is called recursive-descent. A recursive descent parse

35、r 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 these productions are recursive, we end up calling the functions

36、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 through the parse. There is another method for implementing a predicti

37、ve 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 token. As the parser works through the input, there are the followin

38、g 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 token. This is called a match action.3. If X != a and X is a nonte

39、rminal, 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 been a parse errorThe first set of a sequence of symbols u, wri

40、tten 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 terminal is in First(u). If u =* , then is in First(u ).The follo

41、w 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 Follow(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 , then add First(X3) - and so on, through all Xn until the f