上傳人：s***

認證信息

認證類型：個人認證

認證主體：沃**（實名認證）

IP屬地：上海

IP屬地：上海 上傳時間：2022-05-18 格式：PPT 頁數(shù)：64 大?。?.21MB 積分：20 舉報 版權(quán)申訴

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

2、句型的過程，或者說是某個推導(dǎo)的構(gòu)造過程。第3頁/共63頁第三頁，共64頁。4語法樹推導(dǎo)(tudo)的幾何表示 句型aabbaa的可能推導(dǎo)序列(xli)和語法樹 例例: GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa第4頁/共63頁第四頁，共64頁。5分析算法(sun f)分類分析算法可分為：自上而下分析法：從文法的開始符號出發(fā)，尋找與輸入符號串匹配的推導(dǎo)，或者說，為輸入串尋找一個最左推導(dǎo)。自下而上分析法：從輸入

3、符號串開始，逐步進行(jnxng)歸約，直至歸約到文法的開始符號。 第5頁/共63頁第五頁，共64頁。6兩種方法反映了語法(yf)樹的兩種構(gòu)造過程。自上而下方法是從文法符號開始，將它做為語法(yf)樹的根，向下逐步建立語法(yf)樹，使語法(yf)樹的結(jié)果正好是輸入符號串自下而上方法則是從輸入符號串開始，以它做為語法(yf)樹的結(jié)果，自底向上的構(gòu)造語法(yf)樹第6頁/共63頁第六頁，共64頁。72。自上而下(z shn r xi)分析方法 對任何輸入串，試圖用一切可能的辦法，從文法開始符號著手，自上而下地為輸入串構(gòu)造一棵語法樹，或者說，為輸入串尋找一個最左推導(dǎo)(tudo)。本質(zhì)上是一個試探過

4、程，反復(fù)使用不同地產(chǎn)生式謀求匹配輸入串的過程。 第7頁/共63頁第七頁，共64頁。8自上而下的語法分析的一般(ybn)過程例：文法G： S cAd A ab A a識別輸入串w=cabd是否(sh fu)為該文法的句子SSScAdcAd a b推導(dǎo)推導(dǎo)(tudo)過程：過程：S cAd cAd cabd第8頁/共63頁第八頁，共64頁。9自上而下的語法分析的一般過程(1)S cAd (2) A ab (3) A a 識別(shbi)輸入串w=cad是否為 該文法的句子該文法的句子1.S cAd 2.后選擇后選擇(2)擴展擴展A，得到推導(dǎo)，得到推導(dǎo)(tudo)S cAd cabd這時這時 w的第

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

6、得到推導(dǎo)，得到推導(dǎo)S cAd cad5. A沒有選擇了！回溯到推導(dǎo)沒有選擇了！回溯到推導(dǎo)S cAd 6.再回溯再回溯S有無另一個選擇？沒有！有無另一個選擇？沒有！ 宣告分析失敗。宣告分析失敗。（請思考（請思考(sko) 若有若有 (4) S cB (5) B aa 會怎會怎樣樣? ）第9頁/共63頁第九頁，共64頁。10自上而下(z shn r xi)分析的進一步討論自上而下分析也稱面向目標的分析方法，也就是從文法的開始符號出發(fā)企圖推導(dǎo)出與輸入的符號串完全匹配的句子，若能構(gòu)造出推導(dǎo)則表明輸入串是給定文法的句子，否則表明該輸入不是給定文法的句子。自上而下分析對文法的要求文法不能含有(hn yu)

7、左遞歸規(guī)則。自上而下分析又可分為確定的和不確定的兩種 不確定的分析方法稱為帶回溯的分析方法，這種方法實際上是一種窮舉的試探方法 確定的分析方法需對文法有一定的限制第10頁/共63頁第十頁，共64頁。113。自上而下(z shn r xi)的語法分析面臨的問題-實現(xiàn)考慮 回溯(hu s) 文法的左遞歸性 SSa第11頁/共63頁第十一頁，共64頁。12自上而下(z shn r xi)分析對文法的要求例文法G0S: (1) SSa (2) Sb 分析baa是不是文法的句子按照自上而下的分析思想選用(xunyng)產(chǎn)生式(1)來推導(dǎo)SSa 語法樹末端結(jié)點最左符號為非終結(jié)符，所以選用(xunyng)（

8、1）繼續(xù)推導(dǎo)SSaSaa 此時語法樹末端結(jié)點最左符號仍為非終結(jié)符，所以選用(xunyng)（1）繼續(xù)推導(dǎo)SSaSaa Saaa 問題試圖用S匹配輸入串時，出現(xiàn)：在沒有讀入任何輸入符 號的情況下，又得重新要求S去進行新的匹配.無法確定什么時候使用（2）產(chǎn)生式最適當，只能采用帶回溯的不確定方法解決。原因文法含有左遞歸。第12頁/共63頁第十二頁，共64頁。13回溯(hu s)的原因例GS: SxAy Aaba 若當前輸入串為xay，首先構(gòu)造的推導(dǎo)SxAy 匹配 進一步推導(dǎo)對A可選擇Aab替換，得SxAy xaby xay xaby 匹配 xa都已匹配，當前面臨輸入符為y與b不能匹配，所以將輸入串指

9、針退回(tuhu)到a，對A的替換重新選用下一個產(chǎn)生式Aa進行試探， SxAy xay輸入串中當前符a得到匹配，指針向前移動到y(tǒng)，與語法樹中y匹配，匹配成功。由于相同左部的產(chǎn)生式的右部開始符號相同而引起回溯。第13頁/共63頁第十三頁，共64頁。14在自上而下的分析方法中如何選擇使用哪個產(chǎn)生式進行推導(dǎo)？假定要被代換(di hun)的最左非終結(jié)符號是B，且有n條規(guī)則：BA1|A2|An，那么如何確定用哪個右部去替代B？-什么信息用于Parser做正確選擇?(輸入串,文法特點)第14頁/共63頁第十四頁，共64頁。15可預(yù)測(yc)的試探推導(dǎo)過程例 文法GS: S pA |qB A cAd|a B

10、 d B |c 識別(shbi)輸入串w= pccadd是否是G1S的句子可預(yù)測的試探推導(dǎo)過程：S pA pcAd pccAddpccadd 試探成功。第15頁/共63頁第十五頁，共64頁。164 4。 開始符號集-FIRST-FIRST集設(shè)G=(VT,VN,PG=(VT,VN,P，S)S)是上下文無關(guān)文法(wnf)(wnf)FIRSTFIRST（）=a|=a| = =* * a a,aVT, ,aVT, 、VV* * 若 = =* * 則規(guī)定FRISTFRIST（）第16頁/共63頁第十六頁，共64頁。17FOLLOWFOLLOW（A A）=a=a S S =* A A 且a a FRIST

11、FRIST（ ）， VV* *， VV+ + 若S S =* u A u A , ,且 =* ，則#F#FOLLOW(A)OLLOW(A)5 5。后跟符號(fho)(fho)集-FOLLOW-FOLLOW集第17頁/共63頁第十七頁，共64頁。186。SELECT集給定上下文無關(guān)文法(wnf)(wnf)的產(chǎn)生式 AVN, AVN, VV* *若* * ，則SELECT(SELECT()=FIRST()=FIRST()若=* * , ,則SELECT(SELECT()=(FIRST()-)=(FIRST()- )FOLLOW(A)FOLLOW(A)第18頁/共63頁第十八頁，共64頁。19 7

12、7。 LL LL（1 1）文法 一個文法G G是LLLL（1 1）的，當且僅當對于G G的每一個非終結(jié)符的任何(rnh)(rnh)兩個不同產(chǎn)生式 ，下面的條件成立： SELECT( SELECT() SELECT() SELECT()=)= 其中和不能同時=* * 第19頁/共63頁第十九頁，共64頁。20 書中例子(l zi)第20頁/共63頁第二十頁，共64頁。21 5.2 LL5.2 LL（1 1）文法的判別(pnbi)(pnbi)判別(pnbi)(pnbi)步驟：1 1）。求出能推出的非終結(jié)符第21頁/共63頁第二十一頁，共64頁。222 2）。 計算(j sun)FIRST(j su

13、n)FIRST集X XV V, ,則FIRST(X)=XFIRST(X)=X2.2.若X XVN,VN,且有產(chǎn)生式X Xaa，則把a a加入到FIRST(X)FIRST(X)中; ;若X X也是一條產(chǎn)生式, ,則把也加到FIRST(X)FIRST(X)中. .X XYY是一個產(chǎn)生式且Y YVN,VN,則把FIRST(Y)FIRST(Y)中的所有非元素都加到FIRST(X)FIRST(X)中; ;若X X Y1Y2YK Y1Y2YK 是一個產(chǎn)生式,Y1,Y2,Y(i-1),Y1,Y2,Y(i-1)都是非終結(jié)符, ,而且(r qi),(r qi),對于任何j,1j i-1, FIRST(Yj)j,

14、1j i-1, FIRST(Yj)都含有 ( (即Y1.Y(i-1) =Y1.Y(i-1) =* * ), ),則把FIRST(Yj)FIRST(Yj)中的所有非元素和FIRST(Yi)FIRST(Yi)中的所有元素都加到FIRST(X)FIRST(X)中; ;特別是, ,若所有的FIRST(Yj , j=1,2,K)FIRST(Yj , j=1,2,K)均含有, ,則把加到FRIST(X)FRIST(X)中. . 第22頁/共63頁第二十二頁，共64頁。233 3）。 計算(j sun)FOLLOW(j sun)FOLLOW集1.1.對于(duy)(duy)文法的開始符號S,S,置# #于F

15、OLLOW(S) FOLLOW(S) 中; ;BB是一個產(chǎn)生式, ,則把 FIRST()- FIRST()- 加至FOLLOW(B)FOLLOW(B)中; ;3.3.若BB是一個產(chǎn)生式, ,或 B B是 一個產(chǎn)生式而 = =* * ( (即FIRST()FIRST()）， 則把FOLLOWFOLLOW（A A）加至FOLLOWFOLLOW（B B）中第23頁/共63頁第二十三頁，共64頁。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集合(jh)如下：FIRST(E)=(

16、,aFIRST(E)=+,FIRST(T)=(,aFIRST(T)=*,FIRST(F)=(,a各非終結(jié)符的FOLLOW集合(jh)為：FOLLOW(E)=),FOLLOW(E)=)，F(xiàn)OLLOW(T)=，)，F(xiàn)OLLOW(T)=,)，# FOLLOW(F)=*,，),# 第24頁/共63頁第二十四頁，共64頁。254）。 計算(j sun)SELECT集 計算( j sun)產(chǎn)生式的SELECT集第25頁/共63頁第二十五頁，共64頁。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

17、 | FIRST(+TE)=+ FOLLOW(E)=)，T *FT | FIRST(*FT)=* FOLLOW(T)=+,)，F(xiàn) (E) | a FIRST( (E)=( FIRST( a)=a所以(suy)GE是LL（1）的第26頁/共63頁第二十六頁，共64頁。275）。判斷(pndun)文法是否LL（1）文法 若文法(wnf)所有具有相同左部產(chǎn)生式的SELECT集兩兩不相交，則文法(wnf)是LL(1)文法(wnf)。第27頁/共63頁第二十七頁，共64頁。28LL(1)LL(1)文法(wnf)(wnf)的性質(zhì)： LL(1) LL(1)文法(wnf)(wnf)是無二義的 LL(1) LL

18、(1)文法(wnf)(wnf)不含左遞歸第28頁/共63頁第二十八頁，共64頁。295.3 5.3 某些非LL(1)LL(1)文法(wnf)(wnf)的改造1 1。提取(tq)(tq)左公共因子 提左公因子： 將產(chǎn)生式 | 變換為： B B B B | |第29頁/共63頁第二十九頁，共64頁。30一般(ybn)形式： 1|1|2|2|nn 提取(tq)(tq)左公共因子后： A AA A A A1|2|n1|2|n第30頁/共63頁第三十頁，共64頁。312。消除(xioch)左遞歸左遞歸 關(guān)于非終結(jié)符P的規(guī)則直接左遞歸 ： P P | 、 V*且、不以(b y)P開頭一般 左遞歸 ： P

19、=* P 例： SAa ASb 第31頁/共63頁第三十一頁，共64頁。32消除(xioch)(xioch)文法中左遞歸規(guī)則1） 消除直接(zhji)左遞歸： 形如：P P | 非， ，不以P打頭 改寫為：P Q Q Q| 其中Q為新增加的非終結(jié)符第32頁/共63頁第三十二頁，共64頁。33消除文法中左遞歸規(guī)則(guz)(guz)舉例例: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) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a第33頁/共63頁第三十三頁

20、，共64頁。34消除(xioch)(xioch)一般左遞歸對文法要求: : 1. 1. 無回路(A(=+(A) 2. (A(=+(A) 2. 無空產(chǎn)生式2 2） 消除一般(ybn)(ybn)左遞歸的方法：（1 1） . .以某種順序?qū)⑽姆ǚ墙K結(jié)符排列A1 ,A2 AnA1 ,A2 An（2 2） for i:=1 to n do for i:=1 to n do begin begin for j:=1 to i-1 do for j:=1 to i-1 do 用Aj-Aj-1| 1| 2| 2| k k 替代形如Ai- AjrAi- Ajr的規(guī)則, , 其中Aj- Aj- 1| 1| 2|

21、2| k k是關(guān)于AjAj的全部產(chǎn)生式; ; 消除AiAi規(guī)則的直接左遞歸; ; end; end;（3 3）化簡由（2 2）得到的文法: :去掉無用產(chǎn)生式第34頁/共63頁第三十四頁，共64頁。35 例P90第35頁/共63頁第三十五頁，共64頁。36消除(xioch)(xioch)左遞歸和提左公因子并不一定都能將非LL(1)LL(1)文法改造為LL(1)LL(1)的S if C t S |S if C t S | if C t S e S if C t S e SC bC b提左因子提左因子(ynz)(ynz) S if C t S A S if C t S A A e S | A e S

22、 | First First集集 Follow Follow集集S if #,eS if #,eA e, A e, #, e#, eC b C b t tSelect(AeS)SelectSelect(AeS)Select(A(A ) =e#, e ) =e#, e 改造改造(gizo)(gizo)后文法不是后文法不是LL(1)LL(1)文法文法第36頁/共63頁第三十六頁，共64頁。375.5 確定(qudng)的自頂向下分析方法特征根據(jù)下一個(幾個）輸入符號為當前要處理 的非終結(jié)符選擇產(chǎn)生式要求文法是LL(1)的 第一個L 從左到右掃描(somio)輸入串 第二個L 生成的是最左推導(dǎo) 1

23、向前看一個輸入符號（lookahead)第37頁/共63頁第三十七頁，共64頁。38無回溯(hu s)的自頂向下分析程序預(yù)測分析程序的實現(xiàn)技術(shù)( jsh) 1. 遞歸（下降）子程序 2. 表驅(qū)動分析程序第38頁/共63頁第三十八頁，共64頁。39例：遞歸下降(xijing)(xijing)子程序ParseFunction()ParseFunction()BNF（Backus-Naur Form）描述(mio sh)program function_listfunction_list function function_list | function FUNC identifier ( para

24、meter_list ) statementvoid ParseFunction()MatchToken(T_FUNC);ParseIdentifier();MatchToken(T_LPAREN);ParseParameterList();MatchToken(T_RPAREN);ParseStatement();第39頁/共63頁第三十九頁，共64頁。40例：遞歸下降(xijing)(xijing)子程序ParseFunction()ParseFunction()（續(xù)）void MatchToken(int expected)if (lookahead != expected) print

25、f(syntax error n);exit(0); else / if match, consume token and move onlookahead = yylex();/讀入一個(y )單詞第40頁/共63頁第四十頁，共64頁。41預(yù)測分析程序的實現(xiàn)(shxin)(shxin)表驅(qū)動預(yù)測分析程序模型 Input Input #總控程序總控程序(chngx)(chngx)預(yù)測預(yù)測(yc)(yc)分析表分析表stack第41頁/共63頁第四十一頁，共64頁。42預(yù)測分析表構(gòu)造(guzo)(guzo)算法1.1.對文法G G的每個產(chǎn)生式 執(zhí)行第二步 和第三步；2.2.對每個終結(jié)符a aFI

26、RST(FIRST() )，把 加 至A,aA,a中， FIRST( FIRST() )，則對任何b bFOLLOW(A) FOLLOW(A) 把 加至A,bA,b中，A,aA,a標上“出錯標志”?？梢宰C明(zhngmng)(zhngmng)，一個文法G G的預(yù)測分析表不含多重入口，當且僅當該文法是LL(1)LL(1)的第42頁/共63頁第四十二頁，共64頁。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)(zhungti)轉(zhuǎn)換。第43頁/共63頁第

27、四十三頁，共64頁。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) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a 預(yù)測預(yù)測(yc)分析表分析表第44頁/共63頁第四十四頁，共64頁。45表驅(qū)動預(yù)測(yc)分析程序分析算法 首先把# #然后把文法開始符號推入棧；把第一個輸入符號讀進b;b; FLAG FLAG：=TRUE=TRUE； WHILE FLAG DO WHILE FLAG DO BEG

28、IN 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 IF X=# # THEN THEN IF b= IF b=# # THEN FLAG:=FALSE THEN FLAG:=FALSE ELSE ERROR ELSE ERROR ELSE IF ELSE IF X,b=X X1X2.XKX,b=X X1X2.XK THEN THEN 把XKXK，X K-1,.,X1X K-1,.,X1一一推進棧

29、 ELSE ELSEERRORERROR END OF WHILE; END OF WHILE; STOP/ STOP/* *分析成功，過程(guchng)(guchng)完畢* *第45頁/共63頁第四十五頁，共64頁。46分析(fnx)輸入串#a+a#的步驟棧內(nèi)容(nirng) 棧頂符號 當前輸入 余留串 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 a # T FT 9 #ETF F

30、 a # F a10 #ETa a a #11 #ET T # T 12 #E E # E 13 # # #第46頁/共63頁第四十六頁，共64頁。47LL(1)分析中的一種(y zhn)錯誤處理辦法發(fā)現(xiàn)錯誤1棧頂?shù)慕K結(jié)符與當前輸入符不匹配2非終結(jié)符A于棧頂，面臨的輸入符為a，但分析表M的MA,a為空“應(yīng)急”恢復(fù)策略跳過輸入串中的一些符號直至遇到“同步符號”為止。同步符號的選擇1把FOLLOW(A)中的所有符號作為A的同步符號。跳過輸入串中的一些符號直至遇到這些“同步符號”，把A從棧中彈(zhn dn)出，可使分析繼續(xù)2把FIRST(A)中的符號加到A的同步符號集，當FIRST(A)中的符號在

31、輸入中出現(xiàn)時，可根據(jù)A恢復(fù)分析第47頁/共63頁第四十七頁，共64頁。48review-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 language. There are two major parsing approaches: top-down and bottom-up. In top-down

32、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 backwards. 第48頁/共63頁第四十八頁，共64頁。49In the top-down parsing,we begin with the start sy

33、mbol 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 parse works in reverse. We begin with the sentence of terminal

34、s 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, the bottom-up parse prints out a rightmost derivation of th

35、e sentence.第49頁/共63頁第四十九頁，共64頁。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 to go with one particular production. If this choice leads to a dead end, the parser

36、 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.第50頁/共63頁第五十頁，共64頁。51predictive parser and LL(1)grammarPredictive parser is

37、 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 grammar LL(1).

38、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頁第五十一頁，共64頁。52recursive-descentThe first technique for implementing a predictive parser is called recursive-descent. A recursive desce

39、nt 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 these productions are recursive, we end up calling the fu

40、nctions recursively.第52頁/共63頁第五十二頁，共64頁。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 our progress through the parse. There is another meth

41、od 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頁第五十三頁，共64頁。54 How a table-driven predictive parser works We push the start symbol on the stack and read the first input token. As the pa

42、rser 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 token. This is

43、 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 been a pars

44、e error第54頁/共63頁第五十四頁，共64頁。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 , where v begins with sometermin

45、al, that terminal is in First(u). If u =* , then is in First(u ).第55頁/共63頁第五十五頁，共64頁。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 =*uAv , where v beg

46、ins with some terminal, that terminal is in Follow(A).第56頁/共63頁第五十六頁，共64頁。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.e., X1

47、=* , 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頁第五十七頁，共64頁。58Calculating follow sets. For each nonterminal in the grammar, do the following:1. Place#

48、in Follow(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 everything in Foll