編譯原理第5章.ppt

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

2、S AB (2) aA. A aA (3) aaA. A aA (4) aaaA. A aA (5) aaa B. A (6) aaab B b,aaabb. 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ù)下一個(gè)輸入符號為當(dāng)前要處理 的非終結(jié)符選擇產(chǎn)生式 要求文法是LL(1)的 第一個(gè)L 從左到右掃描輸入串 第二個(gè)L 生成的是最左推導(dǎo) 1 向前看一個(gè)輸入符號（loo

3、kahead) 預(yù)測分析程序的實(shí)現(xiàn)技術(shù) 1 遞歸下降子程序 2 表驅(qū)動(dòng)分析程序,PL/0語言的EBNF,程序=分程序. 分程序=常量說明部分變量說明部 分過程說明部分語句 常量說明部分=CONST常量定義部分，常量 定義； 變量說明部分=VAR標(biāo)識符，標(biāo)識符； 過程說明部分= PROCEDURE 標(biāo)識符分程序 ；過程說明部分； 語句= 標(biāo)識符：=表達(dá)式 |IF 條件 then語句|CALL|READ|BEGIN 語句；語句 END|WHILE|,begin(*statement*) if sym=ident then (*parsing ass.st.*) begin getsym; if s

4、ym=becomes then getsym else error(13); expression(fsys); end else 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_list function_li

5、st function function_list | function FUNC identifier ( parameter_list ) statement void ParseFunction() MatchToken(T_FUNC); ParseIdentifier(); MatchToken(T_LPAREN); ParseParameterList(); MatchToken(T_RPAREN); ParseStatement(); ,void MatchToken(int expected) if (lookahead != expected) printf(syntax er

6、ror n); exit(0); else / if match, consume token and move on lookahead = yylex(); ,例：遞歸子程序?qū)崿F(xiàn) 表達(dá)式的語法分析,表達(dá)式的EBNF表達(dá)式=+|-項(xiàng)（+|-）項(xiàng)項(xiàng)=因子（*|/）因子因子=ident|number|（表達(dá)式）,procedure expr;begin if sym in plus, minus then begin getsym; term; endelse term; while sym in plus, minus do begin getsym; term; endend;,Proced

7、ure term; begin factor; while sym in times,slash do begin getsym;factor end end;,Procedure factor; begin if sym=ident then getsym else if sym=number then getsym else if sym=( then begin getsym; expr; if sym=) then getsym else error end else error end;,表驅(qū)動(dòng)予測分析程序模型,Input,#,總控程序,預(yù)測分析表,stack,帶 a0 a1 a2

8、a3 a4 a5 a6 a7 a8 an-1 an,有限控制器,磁頭,識別程序的數(shù)學(xué)模型下推自動(dòng)機(jī),上下文無關(guān)語言句型分析（識別）程序的數(shù)學(xué)模型,下推自動(dòng)機(jī)Pda=(K,f,H,h0,S,Z) H:下推棧符號的有窮字母表 h0 :H中的初始符號 f: K （) H K H* Pda的一個(gè)組態(tài)是K * H 中的一個(gè)（k,w,) k:當(dāng)前狀態(tài)，w:余留輸入串， ：棧中符號，最左邊的符號在棧頂。Pda的一次移動(dòng)用組態(tài)表示 終止和接受的條件: 1.到達(dá)輸入串結(jié)尾時(shí)，處在Z中的一個(gè)狀態(tài) 或 2.某個(gè)動(dòng)作序列導(dǎo)致?？諘r(shí),例：Pda P=(A,B,C),a,b,c),f,h,i,i A, ),f(A,a,i

9、) = (B,h) f(B,a,h) = (B,hh) f(C,b,h) = (C, ) f(A,c,i) = (A, ) f(B,c,h) = (C,h) 接受輸入串a(chǎn)acbb的過程 (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 , goto C (C, , ),G E: (1) E TE (2)

10、 E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F 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,分析算法,BEGIN 首先把#然后把文法開始符號推入棧；把第一個(gè)輸入符號讀進(jìn)b; FLAG：=TRUE； WHILE FLAG DO BEGIN 把棧頂符號上托出去并放在中； IF X Vt THEN IF X=b THEN 把下一個(gè)輸入符號讀進(jìn)a ELSE ERROR ELSE IF X=# THEN IF X=b THEN FLAG:=

11、FALSE ELSE ERROR ELSE IF X,b=X X1X2.XK THEN 把XK，X K-1,.,X1一一推進(jìn)棧 ELSEERROR END OF WHILE; STOP/*分析成功，過程完畢* END,分析輸入串#a+a#,棧內(nèi)容 棧頂符號 當(dāng)前輸入 余留串 MX,b 1 #E E a +a# E TE 2 #ET T a +a# T FT 3 #ETF F a +a# F a 4 #ETa a a +a# 5 # ET T + a# T 6 #E E + a# E +TE 7 #ET+ + + a# 8 # ET T a # T FT 9 #ETF F a # F a 10

12、#ETa a a # 11 #ET T # T 12 #E E # E 13 # # #,FIRST集和FOLLOW集的定義 設(shè)G=(VT,VN,P，S)是上下文無關(guān)文法 FIRST（）=a| =* a,aVT, , V* 若 =* 則規(guī)定FRIST（） FOLLOW（A）=aS =* A 且a FRIST（）， V*， V+ 若S =* u A ,且 =* ，則#FOLLOW(A),LL (1) 文法,計(jì)算FIRST集,1.若XV,則FIRST(X)=X 2.若XVN,且有產(chǎn)生式Xa，則把a(bǔ)加入到FIRST(X)中;若X也是一條產(chǎn)生式,則把也加到FIRST(X)中. 3.若XY是一個(gè)產(chǎn)生式且

13、YVN,則把FIRST(Y)中的所有非元素都加到FIRST(X)中;若X Y1Y2YK 是一個(gè)產(chǎn)生式,Y1,Y2,Y(i-1)都是非終結(jié)符,而且,對于任何j,1j i-1, FIRST(Yj)都含有 (即Y1.Y(i-1) =* ),則把FIRST(Yj)中的所有非元素都加到FIRST(X)中;特別是,若所有的FIRST(Yj , j=1,2,K)均含有,則把加到FRIST(X)中.,計(jì)算FOLLOW集,1.對于文法的開始符號S,置#于FOLLOW(S) 中; 2.若 B 是一個(gè)產(chǎn)生式,則把 FIRST()加至FOLLOW(B)中; 3.若 B是一個(gè)產(chǎn)生式,或 B是 一個(gè)產(chǎn)生式而 =* (即F

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

15、,i FIRST(E)=+, FIRST(T)=(,i FIRST(T)=*, FIRST(F)=(,i,各非終結(jié)符的FOLLOW集合為： FOLLOW(E)=), FOLLOW(E)=)， FOLLOW(T)=，)， FOLLOW(T)=,)，# FOLLOW(F)=*,，),#,G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a,E +TE | FIRST(+TE)=+ FOLLOW(E)=)， T *FT | FIRST(*FT)=* FOLLOW(T)=+,)， F (E) | a FIRST

16、( (E)=( FIRST( a)=a 所以GE是LL（1）的,予測分析表構(gòu)造算法,1.對文法G的每個(gè)產(chǎn)生式 執(zhí)行第二步 和第三步； 2.對每個(gè)終結(jié)符aFIRST()，把 加 至A,a中， 3.若 FIRST()，則對任何bFOLLOW(A) 把 加至A,b中， 4.把所有無定義的A,a標(biāo)上“出錯(cuò)標(biāo)志”。 可以證明，一個(gè)文法G的予測分析表不含多重入口，當(dāng)且僅當(dāng)該文法是LL(1)的,LL(1)文法的性質(zhì)： LL(1)文法是無二義的 LL(1)文法不含左遞歸 非LL(1)文法的改造 消除左遞歸 提左公因子 將產(chǎn)生式 | 變換為： B B |,EE+TT TT*FF Fi(E) FIRST(E)=(

17、,i FIRST(T)=(,i FIRST(F)=(,i 消左遞歸 E TE E +TE E ,S if C t S | if C t S e S C b 提左因子 S if C t S A A e S | First集 Follow集 S if #,e A e, #, e C b t MA,e=A e S A ,LL(1)分析中的一種錯(cuò)誤處理辦法,發(fā)現(xiàn)錯(cuò)誤 1棧頂?shù)慕K結(jié)符與當(dāng)前輸入符不匹配 2非終結(jié)符A于棧頂，面臨的輸入符為a，但分析表M的MA,a為空 “應(yīng)急”恢復(fù)策略 跳過輸入串中的一些符號直至遇到“同步符號”為止。 同步符號的選擇 1把FOLLOW(A)中的所有符號作為A的同步符號。跳過

18、輸入串中的一些符號直至遇到這些“同步符號”，把A從棧中彈出，可使分析繼續(xù) 2把FIRST(A)中的符號加到A的同步符號集，當(dāng)FIRST(A)中的符號在輸入中出現(xiàn)時(shí)，可根據(jù)A恢復(fù)分析,a,+,*,(,),#,E,(1),(1),E,(2),(3),(3),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,syn,review-parsing,The syntax analysis phase of a compiler verifies that the sequence of tokens

19、returned from the scanner represent 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,

20、 you start with the string and 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 termi

21、nals remain. The top-down parse 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 unt

22、il we have substituted our way 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 curr

23、ently has about the input, a decision 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 product

24、ion that was the appropriate one or ran out of choices.,predictive parser and LL(1)grammar,Predictive 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 nonte

25、rminal being processed. To enable 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-descent,The first te

26、chnique for implementing a predictive 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 th

27、e productions we are applying. If these 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

28、keeping track of our progress through 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

29、 stack and read the first input token. 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 successfully 2. If X = a and a != #: successful mat

30、ch, pop X and advance to next input token. 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 tab

31、le entry from step 3 is blank, there has been a parse error,The first set of a sequence of symbols u, written as First(u ) is the set of terminals which start all the sequences of symbols derivable from u. A bit more formally, consider all strings derivable from u by a leftmost derivation. If u =* v

32、 , where v begins with some terminal, that terminal 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 begi

33、ns 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 F

34、irst(u). Furthermore, if X2 can also go to , then 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

35、 # is the inputs right endmarker.The endmarker might 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 s

36、ymbols and B is a nonterminal, everything in First(v) 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 table,1. For each production A u of the

37、grammar, do steps 2 and 3 2. For each terminal a in First(u), add A u to MA,a 3. If in First(u), (i.e. A is nullable) add A u to MA,b for each terminal b in Follow(A), If in First(u), and # is in Follow(A), add A u to MA,# 4. All undefined entries are errors,LL(1) grammar,A grammar G is LL(1) iff whenever A u | v are two d