LL文法及其分析程序PPT課件

1、11.語法分析概念2.自上而下的語法分析的一般過程3.3.自上而下的語法分析面臨的問題4. 開始符號集5. 后跟符號集6.select集7.LL(1)文法第1頁/共63頁21。語法分析在語言的編譯實現(xiàn)中，把句子分析的過程稱為語法分析，即完成這個任務(wù)的程序稱為語法分析程序或稱為識別程序。分析算法又稱識別算法。從左到右的分析算法，即總是從左到右地識別輸入符號串，首先識別符號串中的最左符號，進而依次識別右邊的一個符號，直到分析結(jié)束。第2頁/共63頁3（上下文無關(guān)文法）句型的分析句型分析就是識別一個符號串是否為某文法的句型的過程，或者說是某個推導(dǎo)的構(gòu)造過程。第3頁/共63頁4語法樹推導(dǎo)的幾何表示 句型

2、aabbaa的可能推導(dǎo)序列和語法樹 例例: GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa第4頁/共63頁5分析算法分類分析算法可分為：自上而下分析法：從文法的開始符號出發(fā)，尋找與輸入符號串匹配的推導(dǎo)，或者說，為輸入串尋找一個最左推導(dǎo)。自下而上分析法：從輸入符號串開始，逐步進行歸約，直至歸約到文法的開始符號。 第5頁/共63頁6兩種方法反映了語法樹的兩種構(gòu)造過程。自上而下方法是從文法符號開始，將它做為語法樹的根

3、，向下逐步建立語法樹，使語法樹的結(jié)果正好是輸入符號串自下而上方法則是從輸入符號串開始，以它做為語法樹的結(jié)果，自底向上的構(gòu)造語法樹第6頁/共63頁72。自上而下分析方法 對任何輸入串，試圖用一切可能的辦法，從文法開始符號著手，自上而下地為輸入串構(gòu)造一棵語法樹，或者說，為輸入串尋找一個最左推導(dǎo)。本質(zhì)上是一個試探過程，反復(fù)使用不同地產(chǎn)生式謀求匹配輸入串的過程。 第7頁/共63頁8自上而下的語法分析的一般過程例：文法G： S cAd A ab A a識別輸入串w=cabd是否為該文法的句子SSScAdcAd a b推導(dǎo)過程：推導(dǎo)過程：S cAd cAd cabd第8頁/共63頁9自上而下的語法分析的一

4、般過程(1)S cAd (2) A ab (3) A a 識別輸入串w=cad是否為 該文法的該文法的句子句子1.S cAd 2.后選擇(2)擴展A，得到推導(dǎo)S cAd cabd這時這時 w的第二個符號可以與葉子結(jié)點a得以匹配，但第三個符號d卻不能與下一葉子結(jié)點b匹配怎么辦？怎么辦？-查看A有無另一個選擇，有！回溯回溯，把A為根的子樹剪掉，掃描過的輸入串中的a吐出來,再試探用產(chǎn)生式（3）構(gòu)造推導(dǎo)S cAd cad識別輸入串識別輸入串w=caa的的過程過程： 1.S cAd2.選擇(2)擴展A，得到推導(dǎo)S cAd cabd3.回溯回回溯回到推導(dǎo)S cAd 4.選擇(3)擴展A，得到推導(dǎo)S cAd

5、 cad5. A沒有選擇了！回溯回溯到推導(dǎo)S cAd 6.再回溯回溯S有無另一個選擇？沒有！ 宣告分析失敗。（請思考（請思考 若有 (4) S cB (5) B aa 會怎會怎樣樣? ）第9頁/共63頁10自上而下分析的進一步討論自上而下分析也稱面向目標的分析方法，也就是從文法的開始符號出發(fā)企圖推導(dǎo)出與輸入的符號串完全匹配的句子，若能構(gòu)造出推導(dǎo)則表明輸入串是給定文法的句子，否則表明該輸入不是給定文法的句子。自上而下分析對文法的要求文法不能含有左遞歸規(guī)則。自上而下分析又可分為確定的和不確定的兩種 不確定的分析方法稱為帶回溯的分析方法，這種方法實際上是一種窮舉的試探方法 確定的分析方法需對文法有一

6、定的限制第10頁/共63頁113。自上而下的語法分析面臨的問題-實現(xiàn)考慮 回溯 文法的左遞歸性 SSa第11頁/共63頁12自上而下分析對文法的要求例文法G0S: (1) SSa (2) Sb 分析baa是不是文法的句子按照自上而下的分析思想選用產(chǎn)生式(1)來推導(dǎo)SSa 語法樹末端結(jié)點最左符號為非終結(jié)符，所以選用（1）繼續(xù)推導(dǎo)SSaSaa 此時語法樹末端結(jié)點最左符號仍為非終結(jié)符，所以選用（1）繼續(xù)推導(dǎo)SSaSaa Saaa 問題試圖用S匹配輸入串時，出現(xiàn)：在沒有讀入任何輸入符 號的情況下，又得重新要求S去進行新的匹配.無法確定什么時候使用（2）產(chǎn)生式最適當，只能采用帶回溯的不確定方法解決。原因

7、文法含有左遞歸。第12頁/共63頁13回溯的原因例GS: SxAy Aaba 若當前輸入串為xay，首先構(gòu)造的推導(dǎo)SxAy 匹配 進一步推導(dǎo)對A可選擇Aab替換，得SxAy xaby xay xaby 匹配 xa都已匹配，當前面臨輸入符為y與b不能匹配，所以將輸入串指針退回到a，對A的替換重新選用下一個產(chǎn)生式Aa進行試探， SxAy xay輸入串中當前符a得到匹配，指針向前移動到y(tǒng)，與語法樹中y匹配，匹配成功。由于相同左部的產(chǎn)生式的右部開始符號相同而引起回溯。第13頁/共63頁14在自上而下的分析方法中如何選擇使用哪個產(chǎn)生式進行推導(dǎo)？假定要被代換的最左非終結(jié)符號是B，且有n條規(guī)則：BA1|A2

8、|An，那么如何確定用哪個右部去替代B？-什么信息用于Parser做正確選擇?(輸入串,文法特點)第14頁/共63頁15可預(yù)測的試探推導(dǎo)過程例 文法GS: S pA |qB A cAd| |a B d B | |c 識別輸入串w= pccadd是否是G1S的句子可預(yù)測的試探推導(dǎo)過程：S pA pcAd pccAddpccadd 試探成功。第15頁/共63頁164 4。 開始符號集-FIRST-FIRST集設(shè)G=(VG=(VT T,V,VN N,P,P，S)S)是上下文無關(guān)文法FIRSTFIRST（ ）=a|=a| =* a a ,a,aV VT T, , 、 VV* * 若 =* 則規(guī)定FRI

9、STFRIST（ ）第16頁/共63頁17FOLLOWFOLLOW（A A）=a=a S S =* A A 且a a FRISTFRIST（ ）， VV* *， VV+ + 若S S =* u A u A , ,且 =* ，則#F#FOLLOW(A)OLLOW(A)5 5。后跟符號集-FOLLOW-FOLLOW集第17頁/共63頁186。SELECT集給定上下文無關(guān)文法的產(chǎn)生式 A AV VN N, , VV* *若* ，則SELECT(SELECT()=FIRST()=FIRST() )若=* , ,則SELECT(SELECT()=(FIRST()=(FIRST()-)- )FOLLOW(

10、A)FOLLOW(A) )第18頁/共63頁19 7 7。 LLLL（1 1）文法 一個文法G G是LLLL（1 1）的，當且僅當對于G G的每一個非終結(jié)符的任何兩個不同產(chǎn)生式 ，下面的條件成立： SELECT(SELECT() SELECT(SELECT()=)= 其中和不能同時=* 第19頁/共63頁20 書中例子第20頁/共63頁21 5.2 LL5.2 LL（1 1）文法的判別判別步驟：1 1）。求出能推出的非終結(jié)符第21頁/共63頁222 2）。 計算FIRSTFIRST集X X V V , ,則FIRST(X)=XFIRST(X)=X2.2.若X X V VN N, ,且有產(chǎn)生式X

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

12、則把FIRST(YFIRST(Yj j) )中的所有非 元素和FIRST(YFIRST(Yi i) )中的所有元素都加到FIRST(X)FIRST(X)中; ;特別是, ,若所有的FIRST(YFIRST(Yj j , , j=1,2,K)j=1,2,K)均含有 , ,則把 加到FRIST(X)FRIST(X)中. . 第22頁/共63頁233 3）。 計算FOLLOWFOLLOW集1.1.對于文法的開始符號S,S,置# #于FOLLOW(S) FOLLOW(S) 中; ;BB是一個產(chǎn)生式, ,則把 FIRST()-FIRST()- 加至FOLLOW(B)FOLLOW(B)中; ;3.3.若B

13、B是一個產(chǎn)生式, ,或 B B是 一個產(chǎn)生式而 =* ( (即FIRST()FIRST()）， 則把FOLLOWFOLLOW（A A）加至FOLLOWFOLLOW（B B）中第23頁/共63頁24G 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)=(,aFIRST(E)=+,FIRST(T)=(,aFIRST(T)=*,FIRST(F)=(,a各非終結(jié)符的FOLLOW集合為：FOLLOW(E)=),FOLLOW(E)=)，F(xiàn)OLLOW(T)=，)，F(xiàn)OL

14、LOW(T)=,)，# FOLLOW(F)=*,，),# 第24頁/共63頁254）。 計算SELECT集 計算產(chǎn)生式的SELECT集第25頁/共63頁26G 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

15、)=( ( FIRST( a)=FIRST( a)=a a所以GEGE是LLLL（1 1）的第26頁/共63頁275）。判斷文法是否LL（1）文法 若文法所有具有相同左部產(chǎn)生式的SELECT集兩兩不相交，則文法是LL(1)文法。第27頁/共63頁28LL(1)LL(1)文法的性質(zhì)： LL(1)LL(1)文法是無二義的 LL(1)LL(1)文法不含左遞歸第28頁/共63頁295.3 5.3 某些非LL(1)LL(1)文法的改造1 1。提取左公共因子 提左公因子： 將產(chǎn)生式 | 變換為： B B B B | 第29頁/共63頁30一般形式： 1 1| | 2 2| n n 提取左公共因子后： A

16、AAA A A1 1|2 2|n n第30頁/共63頁312。消除左遞歸左遞歸 關(guān)于非終結(jié)符P的規(guī)則直接左遞歸 ： P P | | 、 V V* *且、不以P開頭一般 左遞歸 ： P =* P 例： SAa SAa A ASbSb 第31頁/共63頁32消除文法中左遞歸規(guī)則1） 消除直接左遞歸： 形如：P P | | 非 ， ，不以P P打頭 改寫為：P Q Q Q Q Q| Q| 其中Q為新增加的非終結(jié)符第32頁/共63頁33消除文法中左遞歸規(guī)則舉例例:E E+T|T |T T T TT* *F|FF|F F F (E)| a(E)| a G E: (1) E TE (2) E +TE (3

17、) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a第33頁/共63頁34消除一般左遞歸對文法要求: 1. 無回路(A(=+(A) 2. 無空產(chǎn)生式2 2） 消除一般左遞歸的方法：（1 1） .以某種順序?qū)⑽姆ǚ墙K結(jié)符排列A1 ,A2 An（2 2） for i:=1 to n dofor i:=1 to n do begin begin for j:=1 to i-1 do 用Aj-1| 2| k 替代形如Ai- Ajr的規(guī)則, 其中Aj- 1| 2| k是關(guān)于Aj的全部產(chǎn)生式; 消除Ai規(guī)則的直接左遞歸; end; end;（3 3）化簡由（2）得到

18、的文法:去掉無用產(chǎn)生式第34頁/共63頁35 例P90第35頁/共63頁36消除左遞歸和提左公因子并不一定都能將非LL(1)LL(1)文法改造為LL(1)LL(1)的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 S | First First集集 FollowFollow集集S S ifif #,e #,eA e, A e, #, eC b tSelect(AeSAeS)Select(A A ) =e#, e 改造后文法不是LL(1)文法第

19、36頁/共63頁375.5 確定的自頂向下分析方法特征根據(jù)下一個(幾個）輸入符號為當前要處理 的非終結(jié)符選擇產(chǎn)生式要求文法是LL(1)的 第一個L 從左到右掃描輸入串 第二個L 生成的是最左推導(dǎo) 1 向前看一個輸入符號（lookahead)第37頁/共63頁38無回溯的自頂向下分析程序預(yù)測分析程序的實現(xiàn)技術(shù) 1. 遞歸（下降）子程序 2. 表驅(qū)動分析程序第38頁/共63頁39例：遞歸下降子程序ParseFunction()BNF（Backus-Naur Form）描述program function_listfunction_list function function_list | func

20、tion FUNC identifier ( parameter_list ) statementvoid ParseFunction()MatchToken(T_FUNC);ParseIdentifier();MatchToken(T_LPAREN);ParseParameterList();MatchToken(T_RPAREN);ParseStatement();第39頁/共63頁40例：遞歸下降子程序ParseFunction()（續(xù)）void MatchToken(int expected)if (lookahead != expected) printf(syntax error

21、n);exit(0); else / if match, consume token and move onlookahead = yylex();/讀入一個單詞第40頁/共63頁41預(yù)測分析程序的實現(xiàn)表驅(qū)動預(yù)測分析程序模型 Input Input #總控程序總控程序預(yù)測分析表預(yù)測分析表stack第41頁/共63頁42預(yù)測分析表構(gòu)造算法1.1.對文法G G的每個產(chǎn)生式 執(zhí)行第二步 和第三步；2.2.對每個終結(jié)符a a FIRST(FIRST( ) )，把 加 至A,aA,a中， FIRST(FIRST( ) )，則對任何b b FOLLOW(A)FOLLOW(A) 把 加至A,bA,b中，A,

22、aA,a標上“出錯標志”?？梢宰C明，一個文法可以證明，一個文法G G的預(yù)測分析表不含多重入口，當且僅當該文法是的預(yù)測分析表不含多重入口，當且僅當該文法是LL(1)LL(1)的的第42頁/共63頁43 例：表驅(qū)動予測分析程序G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a 用預(yù)測分析表表示狀態(tài)轉(zhuǎn)換。第43頁/共63頁44 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)

23、E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a 預(yù)測分析表預(yù)測分析表第44頁/共63頁45表驅(qū)動預(yù)測分析程序分析算法 首先把#然后把文法開始符號推入棧；把第一個輸入符號讀進b;b; FLAGFLAG：=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 把下一個輸入符號讀進b b ELSE ERROR ELSE ERROR ELSE IF X= ELSE I

24、F X=# # THEN THEN IF b= IF b=# # THEN FLAG:=FALSE THEN FLAG:=FALSE ELSE ERROR ELSE ERROR 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/* *分析成功，過程完畢* *第45頁/共63頁46分析輸入串#a+a#的步驟棧內(nèi)容 棧頂符號 當前輸入 余留串 MX

25、,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 a # T FT 9 #ETF F a # F a10 #ETa a a #11 #ET T # T 12 #E E # E 13 # # #第46頁/共63頁47LL(1)分析中的一種錯誤處理辦法發(fā)現(xiàn)錯誤1棧頂?shù)慕K結(jié)符與當前輸入符不匹配2非終結(jié)符A于棧頂，面臨的輸入符為a，但分析表M的MA,a為空“應(yīng)急”恢復(fù)策略跳過輸入串中的一些符號直至遇到“同

26、步符號”為止。同步符號的選擇1把FOLLOW(A)中的所有符號作為A的同步符號。跳過輸入串中的一些符號直至遇到這些“同步符號”，把A從棧中彈出，可使分析繼續(xù)2把FIRST(A)中的符號加到A的同步符號集，當FIRST(A)中的符號在輸入中出現(xiàn)時，可根據(jù)A恢復(fù)分析第47頁/共63頁48review-parsingThe syntax analysis phase of a compiler verifies that the sequence of tokens returned from the scanner represent valid sentences in the grammar

27、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 and reduce it to the start symbol by app

28、lying the productions backwards. 第48頁/共63頁49In 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 derivat

29、ion 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 back to the start symbol. I

30、f you read from the bottom to top, the bottom-up parse prints out a rightmost derivation of the sentence.第49頁/共63頁50 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 t

31、o 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 one or ran out of

32、choices.第50頁/共63頁51predictive 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 this

33、, 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.第51頁/共63頁52recursive-descentThe first technique for implementing a pr

34、edictive 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

35、. If these productions are recursive, we end up calling the functions recursively.第52頁/共63頁53Table-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 ou

36、r 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.第53頁/共63頁54 How a table-driven predictive parser works We push the start symbol on the stack a

37、nd 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 successfully2. If X = a and a != #: successful match, pop X

38、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 table entry fro

39、m step 3 is blank, there has been a parse error第54頁/共63頁55The 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 , w

40、here v begins with someterminal, that terminal is in First(u). If u =* , then is in First(u ).第55頁/共63頁56The follow set of a nonterminal A is the set of terminal symbols that can appear immediately to the right of A in a valid sentential form. A bit more formally, for every valid sentential form S =

41、*uAv , where v begins with some terminal, that terminal is in Follow(A).第56頁/共63頁57Calculating first setTo 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.

42、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 first nonnullable one.3. If X1X2.Xn =* , add to the first set.第57頁/共63頁58Calculating follow sets. For each nonterminal in the grammar, do the following:1. Place# in F

43、ollow(S) where S is the start symbol and # 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 symbols 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 ever