語法分析自上而下分析完美版資料

第四章語法分析—自上而下分析本章主要引見語法分析的處置要進(jìn)展語法分析，必需對言語的語法構(gòu)造進(jìn)展描畫。采用正規(guī)式和有限自動(dòng)機(jī)可以描畫和識(shí)別言語的單詞符號(hào)；用上下文無關(guān)文法來描畫語法規(guī)那么。上下文無關(guān)文法的定義：一個(gè)上下文無關(guān)文法G是一個(gè)四元式G=(VT，VN，S，P)，其中VT：終結(jié)符集合(非空)VN：非終結(jié)符集合(非空)，且VTVN=S：文法的開場符號(hào)，SVNP：產(chǎn)生式集合(有限)，每個(gè)產(chǎn)生式方式為P，PVN，(VTVN)*開場符S至少必需在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。例，定義只含+，*的算術(shù)表達(dá)式的文法G=<{i，+，*，(，)}，{E}，E，P>，其中，P由以下產(chǎn)生式組成：EiEE+EEE*EE(E)定義：稱A直接推出，即A僅當(dāng)A是一個(gè)產(chǎn)生式，且，(VTVN)*。假設(shè)12n，那么我們稱這個(gè)序列是從1到n的一個(gè)推導(dǎo)。假設(shè)存在一個(gè)從1到n的推導(dǎo)，那么稱1可以推導(dǎo)出n。例：對文法(1)E(E)(E+E)(i+E)(i+i)通常，用表示：從1出發(fā)，經(jīng)過一步或假設(shè)干步，可以推出n。用表示：從1出發(fā)，經(jīng)過0步或假設(shè)干步，可以推出n。所以：即或定義：假定G是一個(gè)文法，S是它的開場符號(hào)。假設(shè)，那么稱是一個(gè)句型。僅含終結(jié)符號(hào)的句型是一個(gè)句子。文法G所產(chǎn)生的句子的全體是一個(gè)言語，將它記為L(G)。4.1語法分析器的功能語法分析的義務(wù)是分析一個(gè)文法的句子構(gòu)造。語法分析器的功能：按照文法的產(chǎn)生式(言語的語法規(guī)那么)，識(shí)別輸入符號(hào)串能否為一個(gè)句子(合式程序)。源程序單詞符號(hào)取下一單詞...語法分析樹詞法分析器語法分析器符號(hào)表編譯程序后續(xù)部分語法分析的方法：自下而上分析法(Bottom-up)根本思想：從輸入串開場，逐漸進(jìn)展“歸約〞，直到文法的開場符號(hào)。即從樹末端開場，構(gòu)造語法樹。所謂歸約，是指根據(jù)文法的產(chǎn)生式規(guī)那么，把產(chǎn)生式的右部交換成左部符號(hào)。算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合性質(zhì)進(jìn)展語法分析。適宜分析表達(dá)式。G(E)：Ei|E+E|E-E|E*E|E/E|(E)i*i+i E*i+i E*E+i E+i E+E Ei+*EiiEEEE自上而下分析法(Top-down)根本思想：它從文法的開場符號(hào)出發(fā)，反復(fù)運(yùn)用各種產(chǎn)生式，尋覓"匹配"的推導(dǎo)。遞歸下降分析法：對每一語法變量(非終結(jié)符)構(gòu)造一個(gè)相應(yīng)的子程序，每個(gè)子程序識(shí)別一定的語法單位，經(jīng)過子程序間的信息反響和結(jié)協(xié)作用實(shí)現(xiàn)對輸入串的識(shí)別。預(yù)測分析程序優(yōu)點(diǎn)：直觀、簡單和宜于手工實(shí)現(xiàn)。4.2自上而下分析面臨的問題自上而下就是從文法的開場符號(hào)出發(fā)，向下推導(dǎo)，推出句子。帶“回溯〞的不帶回溯的遞歸子程序(遞歸下降)分析方法。自上而下分析的主旨：對任何輸入串，試圖用一切能夠的方法，從文法開場符號(hào)(根結(jié)點(diǎn))出發(fā)，自上而下地為輸入串建立一棵語法樹?；蛘哒f，為輸入串尋覓一個(gè)最左推導(dǎo)。例3.4.1假定有文法G(S):(1)S→xAy(2)A→**|* 分析輸入串x*y(記為)。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy**Sx*yIPAxy**Sx*yIPAxy*Sx*yIPAxy*當(dāng)某個(gè)非終結(jié)符有多個(gè)產(chǎn)生式候選時(shí)，能夠帶來如下問題:1.分析過程中，當(dāng)一個(gè)非終結(jié)符用某一個(gè)候選匹配勝利時(shí)，這種匹配能夠是暫時(shí)的。出錯(cuò)時(shí)，不得不“回溯〞。2.文法左遞歸問題。一個(gè)文法是含有左遞歸的，假設(shè)存在非終結(jié)符P含有左遞歸的文法將使自上而下的分析墮入無限循環(huán)。4.3LL(1)分析法構(gòu)造不帶回溯的自上而下分析算法要消除文法的左遞歸性抑制回溯4.3.1左遞歸的消除直接消除見諸于產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符P的規(guī)那么為 P→P|其中不以P開頭。我們可以把P的規(guī)那么等價(jià)地改寫為如下的非直接左遞歸方式：P→P P→P|普通而言，假定P關(guān)于的全部產(chǎn)生式是 P→P1|P2|…|Pm|1|2|…|n其中，每個(gè)都不等于，每個(gè)都不以P開頭那么，消除P的直接左遞歸性就是把這些規(guī)那么改寫成： P→1P|2P|…|nP P→1P|2P|…|mP|例文法G(E):E→E＋T|TT→T*F|FF→(E)|i經(jīng)消去直接左遞歸后變成：E→TEE→+TE|T→FTT→*FT|F→(E)|i (4.2)例如文法G(S):S→Qc|cQ→Rb|bR→Sa|a (4.3)雖沒有直接左遞歸，但S、Q、R都是左遞歸的SQcRbcSabc一個(gè)文法消除左遞歸的條件：不含以為右部的產(chǎn)生式不含回路。消除左遞歸的算法:1.把文法G的一切非終結(jié)符按任一種順序陳列成P1，P2，…，Pn；按此順序執(zhí)行；2.FORi:=1TOnDOBEGINFORj:=1TOi-1DO把形如Pi→Pj的規(guī)那么改寫成Pi→1|2|…|k;(其中Pj→1|2|…|k是關(guān)于Pj的一切規(guī)那么)消除關(guān)于Pi規(guī)那么的直接左遞歸性END3.化簡由2所得的文法。去除那些從開場符號(hào)出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)那么。例思索文法G(S)S→Qc|cQ→Rb|bR→Sa|a令它的非終結(jié)符的排序?yàn)镽、Q、S。對于R，不存在直接左遞歸。把R代入到Q的有關(guān)候選后，把Q的規(guī)那么變?yōu)镼→Sab|ab|b如今的Q不含直接左遞歸，把它代入到S的有關(guān)候選后，S變成S→Sabc|abc|bc|c消除S的直接左遞歸后： S→abcS|bcS|cS S→abcS| Q→Sab|ab|b R→Sa|a關(guān)于Q和R的規(guī)那么已是多余的，化簡為： S→abcS|bcS|cS S→abcS|(4.4)留意，由于對非終結(jié)符排序的不同，最后所得的文法在方式上能夠不一樣。但不難證明，它們都是等價(jià)的。例如，假設(shè)對文法(4.3)的非終結(jié)符排序選為S、Q、R，那么，最后所得的無左遞歸文法是： S→Qc|c Q→Rb|b R→bcaR|caR|aR(4.5) R→bcaR| 文法(4.4)和(4.5)的等價(jià)性是顯然的。4.3.2消除回溯、提左因子為了消除回溯就必需保證：對文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時(shí)，可以根據(jù)它所面臨的輸入符號(hào)準(zhǔn)確地指派它的一個(gè)候選去執(zhí)行義務(wù)，并且此候選的任務(wù)結(jié)果應(yīng)是確信無疑的。A→1|2|…|nSa….IPA......令G是一個(gè)不含左遞歸的文法，對G的一切非終結(jié)符的每個(gè)候選定義它的終結(jié)首符集FIRST()為：特別是，假設(shè)，那么規(guī)定FIRST()。假設(shè)非終結(jié)符A的一切候選首符集兩兩不相交，即A的任何兩個(gè)不同候選i和jFIRST(i)∩FIRST(j)＝當(dāng)要求A匹配輸入串時(shí)，A就能根據(jù)它所面臨的第一個(gè)輸入符號(hào)a，準(zhǔn)確地指派某一個(gè)候選前去執(zhí)行義務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含a的。提取公共左因子:假定關(guān)于A的規(guī)那么是A→1|2|…|n|1|2|…|m (其中，每個(gè)不以開頭)那么，可以把這些規(guī)那么改寫成A→A|1|2|…|mA→1|2|…|n經(jīng)過反復(fù)提取左因子，就可以把每個(gè)非終結(jié)符(包括新引進(jìn)者)的一切候選首符集變成為兩兩不相交。假定S是文法G的開場符號(hào)，對于G的任何非終結(jié)符A，我們定義特別是，假設(shè)，那么規(guī)定＃FOLLOW(A)4.3.3LL(1)分析條件i+iIPEi+iIPETE’i+iIPETE’FT’i+iIPETE’FT’ii+iIPETE’FT’ii+iIPETE’FT’ii+iIPETE’FT’i+TE’i+iIPETE’FT’i+TE’i+iIPETE’FT’i+TE’FT’i+iIPETE’FT’i+TE’FT’ii+iIPETE’FT’i+TE’FT’iFIRST(i)∩FOLLOW(A)=FIRST(T)={(,i}A→1|2|…|n步驟 符號(hào)棧 輸入串 所用產(chǎn)生式T；FOLLOW(E)={),#}預(yù)測分析程序的總控程序：P，PVN，(VTVN)*decimal→[sign]integer.F→i|(E) (4.用上下文無關(guān)文法來描畫語法規(guī)那么。例如，假設(shè)對文法(4.ENDOFWHILE;5)的等價(jià)性是顯然的。FOLLOW(T)={+,),#}把文法G的一切非終結(jié)符按任一種順序陳列成P1，P2，…，Pn；i+iIPETE’FT’i+TE’FT’ii+iIPETE’FT’i+TE’FT’i構(gòu)造不帶回溯的自上而下分析的文法條件1.文法不含左遞歸，2.對于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，假設(shè)A→1|2|…|n那么FIRST(i)∩FIRST(j)＝ (ij)3.對文法中的每個(gè)非終結(jié)符A，假設(shè)它存在某個(gè)候選首符集包含，那么FIRST(i)∩FOLLOW(A)=i=1,2,...,n假設(shè)一個(gè)文法G滿足以上條件，那么稱該文法G為LL(1)文法。 對于一個(gè)滿足上述條件的文法，可以對其輸入串進(jìn)展有效的無回溯的自上而下分析。假設(shè)要用非終結(jié)符A進(jìn)展匹配，面臨的輸入符號(hào)為a，A的一切產(chǎn)生式為A→1|2|…|n1.假設(shè)aFIRST(i)，那么指派i執(zhí)行匹配義務(wù)；2.假設(shè)a不屬于任何一個(gè)候選首符集，那么：(1)假設(shè)屬于某個(gè)FIRST(i)且aFOLLOW(A)，那么讓A與自動(dòng)匹配。(2)否那么，a的出現(xiàn)是一種語法錯(cuò)誤。構(gòu)造FIRST()對每一文法符號(hào)XVT∪VN構(gòu)造FIRST(X)延續(xù)運(yùn)用下面的規(guī)那么，直至每個(gè)集合FIRST不再增大為止：1.假設(shè)XVT，那么FIRST(X)＝{X}。2.假設(shè)XVN，且有產(chǎn)生式X→a…，那么把a(bǔ)參與到FIRST(X)中；假設(shè)X→也是一條產(chǎn)生式，那么把也加到FIRST(X)中。3.假設(shè)X→Y…是一個(gè)產(chǎn)生式且YVN，那么把FIRST(Y)中的一切非-元素都加到FIRST(X)中；假設(shè)X→Y1Y2…Yk是一個(gè)產(chǎn)生式，Y1，…，Yi-1都是非終結(jié)符，而且，對于任何j，1ji-1，F(xiàn)IRST(Yj)都含有(即Y1…Yi-1)，那么把FIRST(Yi)中的一切非-元素都加到FIRST(X)中；特別是，假設(shè)一切的FIRST(Yj)均含有，j＝1，2，…，k，那么把加到FIRST(X)中。對文法G的任何符號(hào)串=X1X2…Xn構(gòu)造集合FIRST()。1.置FIRST()＝FIRST(X1)\{}；2.假設(shè)對任何1ji-1，F(xiàn)IRST(Xj)，那么把FIRST(Xi)\{}加至FIRST()中；特別是，假設(shè)一切的FIRST(Xj)均含有，1jn，那么把也加至FIRST()中。顯然，假設(shè)＝那么FIRST()＝{}。構(gòu)造FOLLOW(A)對于文法G的每個(gè)非終結(jié)符A構(gòu)造FOLLOW(A)的方法是，延續(xù)運(yùn)用下面的規(guī)那么，直至每個(gè)FOLLOW不再增大為止：1.對于文法的開場符號(hào)S，置＃于FOLLOW(S)中；2.假設(shè)A→B是一個(gè)產(chǎn)生式，那么把FIRST()\{}加至FOLLOW(B)中；3.假設(shè)A→B是一個(gè)產(chǎn)生式，或AB是一個(gè)產(chǎn)生式而(即FIRST())，那么把FOLLOW(A)加至FOLLOW(B)中。例4.6對于文法G(E)E→TEE→+TE|T→FTT→*FT|F→(E)|i 構(gòu)造每個(gè)非終結(jié)符的FIRST和FOLLOW集合： FIRST(E)={(,i}FIRST(E)={+,}FIRST(T)={(,i}FIRST(T)={*,}FIRST(F)={(,i} FOLLOW(E)={),#}FOLLOW(E)={),#}FOLLOW(T)={+,),#}FOLLOW(T)={+,),#}FOLLOW(F)={*,+,),#}4.4遞歸下降分析程序構(gòu)造構(gòu)造不帶回溯的自上而下分析程序要消除文法的左遞歸性抑制回溯構(gòu)造不帶回溯的自上而下分析器分析程序由一組遞歸過程組成，文法中每個(gè)非終結(jié)符對應(yīng)一個(gè)過程；所以這樣的分析程序稱為遞歸下降分析器。(由于文法的定義通常是遞歸的)幾個(gè)全局過程和變量：ADVANCE，把輸入串指示器IP指向下一個(gè)輸入符號(hào)，即讀入一個(gè)單字符號(hào)SYM，IP當(dāng)前所指的輸入符號(hào)ERROR，出錯(cuò)處置子程序例:文法G(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i 每個(gè)非終結(jié)符有對應(yīng)的子程序的定義，首先在分析過程中，當(dāng)需求從某個(gè)非終結(jié)符出發(fā)進(jìn)展展開(推導(dǎo))時(shí)，就調(diào)用這個(gè)非終結(jié)符對應(yīng)的子程序。對應(yīng)的遞歸下降子程序?yàn)?

PROCEDUREE；BEGIN T；EEND；

PROCEDURET；BEGIN F；TENDPROCEDUREE；IFSYM=‘+’THEN BEGIN ADVANCE；T；E ENDPROCEDURET；IFSYM=‘*’THENBEGINADVANCE；F；TEND；PROCEDUREF；IFSYM=‘i’THENADVANCEELSE IFSYM=‘(’THEN BEGIN ADVANCE; E； IFSYM=‘)’THENADVANCE ELSEERROR END ELSEERROR;假設(shè)X＝a‘＃’，那么把X從STACK棧頂逐出，讓a指向下一個(gè)輸入符號(hào)。ERROR二、分析表M[A，a]的構(gòu)造為了消除回溯就必需保證：對文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時(shí)，可以根據(jù)它所面臨的輸入符號(hào)準(zhǔn)確地指派它的一個(gè)候選去執(zhí)行義務(wù)，并且此候選的任務(wù)結(jié)果應(yīng)是確信無疑的。構(gòu)造FOLLOW(A)語法分析器的功能：按照文法的產(chǎn)生式(言語的語法規(guī)那么)，識(shí)別輸入符號(hào)串能否為一個(gè)句子(合式程序)。假設(shè)aFIRST(i)，那么指派i執(zhí)行匹配義務(wù)；2自上而下分析面臨的問題定義：假定G是一個(gè)文法，S是它的開場符號(hào)。VN：非終結(jié)符集合(非空)，且VTVN=不帶回溯的遞歸子程序(遞歸下降)分析方法。BEGIN假設(shè)A→B是一個(gè)產(chǎn)生式，或AB是一個(gè)產(chǎn)生式而(即FIRST())，PROCEDUREE；假設(shè)X→Y1Y2…Yk是一個(gè)產(chǎn)生式，Y1，…，Yi-1都是非終結(jié)符，而且，對于任何j，1ji-1，F(xiàn)IRST(Yj)都含有(即Y1…Yi-1)，那么把FIRST(Yi)中的一切非-元素都加到FIRST(X)中；主程序:PROGRAMPARSER;BEGINADVANCE;E;IFSYM<>’#’THENERROREND;對應(yīng)的遞歸下降子程序?yàn)?

E→TE|BCPROCEDUREE；BEGIN IFSYMFIRST(TE’) THEN T；E ELSEIFSYMFIRST(BC) THEN B;C ELSEERROREND；

E→TEE→+TE|T→FTT→*FT|F→(E)|I對應(yīng)的遞歸下降子程序?yàn)?

PROCEDUREE；BEGIN T；EEND；

PROCEDURET；BEGIN F；TEND對應(yīng)的遞歸下降子程序?yàn)?

PROCEDUREE；IFSYM=‘+’THEN BEGIN ADVANCE；T；E ENDELSEIFSYM<>‘#’ANDSYM<>’)’THENERROR對應(yīng)的遞歸下降子程序?yàn)?

PROCEDURET；IFSYM=‘*’THENBEGINADVANCE；F；TENDELSEIFSYM<>‘#’ANDSYM<>’)’ANDSYM<>’+’THENERRORPROCEDUREF；IFSYM=‘i’THENADVANCEELSE IFSYM=‘(’THEN BEGIN ADVANCE; E； IFSYM=‘)’THENADVANCE ELSEERROR END ELSEERROR;主程序:PROGRAMPARSER;BEGINADVANCE;EEND;在元符號(hào)“→〞和“|〞的根底上，擴(kuò)展幾個(gè)元言語符號(hào)：1.用花括號(hào){}表示閉包運(yùn)算*。2.用表示{}0n可恣意反復(fù)0次至n次，。3.用方括號(hào)[]表示{}01，即表示的出現(xiàn)可有可無(等價(jià)于|)。引入上述元符號(hào)的文法亦稱擴(kuò)展的巴科斯范式。文法的另一種表示法和轉(zhuǎn)換圖例如，通常的“實(shí)數(shù)〞可定義為：decimal→[sign]integer.{digit}[exponent]exponent→E[sign]integerinteger→digit{digit}sign→+|-用擴(kuò)展的巴科斯范式來描畫語法，直觀易懂，便于表示左遞歸消去和因子提取。例4.5文法E→T|E+TT→F|T*FF→i|(E)可表示成E→T{+T}T→F{*F}F→i|(E) (4.6)E→T{+T}T→F{*F}F→i|(E) (4.6)可以用語法圖來表示言語的文法。T+ETF*TFi)FE(可構(gòu)造一組遞歸下降分析程序：PROCEDUREE；BEGINT；WHILESYM=‘+’DOBEGINADVANCE；TENDEND；PROCEDURET；BEGINF；WHILESYM=‘*’DOBEGINADVANCE；FENDEND；PROCEDUREF；同前，見圖4.2。4.5預(yù)測分析程序一、預(yù)測分析程序任務(wù)原理預(yù)測分析程序或LL(1)分析法：總控程序分析表M[A，a]矩陣，AVN，aVT是終結(jié)符或‘?！?，分析棧STACK用于存放文法符號(hào)總控程序分析表X#輸入串分析棧STACKa1a2...ai…#預(yù)測分析程序的任務(wù)圖#Sa1a2...ai…#分析開場時(shí)：總控程序根據(jù)現(xiàn)行棧頂符號(hào)X和當(dāng)前輸入符號(hào)a，執(zhí)行以下三種動(dòng)作之一:1.假設(shè)X＝a＝‘?！?，那么宣布分析勝利，停頓分析。2.假設(shè)X＝a‘＃’，那么把X從STACK棧頂逐出，讓a指向下一個(gè)輸入符號(hào)。3.假設(shè)X是一個(gè)非終結(jié)符，那么查看分析表M。假設(shè)M[X，a]中存放著關(guān)于X的一個(gè)產(chǎn)生式，把X逐出STACK棧頂，把產(chǎn)生式的右部符號(hào)串按反序一一推進(jìn)STACK棧(假設(shè)右部符號(hào)為，那么意味不推什么東西進(jìn)棧)。在把產(chǎn)生式的右部符號(hào)推進(jìn)棧的同時(shí)應(yīng)做這個(gè)產(chǎn)生式相應(yīng)的語義動(dòng)作。假設(shè)M[X，a]中存放著“出錯(cuò)標(biāo)志〞，那么調(diào)用出錯(cuò)診察程序ERROR。預(yù)測分析程序的總控程序：BEGIN首先把‘?！缓蟀盐姆ㄩ_場符號(hào)推進(jìn)STACK棧；把第一個(gè)輸入符號(hào)讀進(jìn)a；FLAG:=TRUE;WHILEFLAGDO BEGIN把STACK棧頂符號(hào)上托出去并放在X中；IFXVTTHEN IFX=aTHEN把下一輸入符號(hào)讀進(jìn)a ELSEERROR

ELSEIFX=‘#’THEN IFX=aTHENFLAG:=FALSEELSEERRORELSEIFM[X,a]={X→X1X2…Xk}THEN 把Xk,Xk-1,…,X1一一推進(jìn)STACK棧 /*假設(shè)X1X2…Xk=，不推什么進(jìn)棧*/ELSEERRORENDOFWHILE;STOP/*分析勝利，過程終了*/END例4.6對于文法G(E)E→TEE→+TE|T→FTT→*FT|F→(E)|i 輸入串為i1*i2+i3，利用分析表進(jìn)展預(yù)測分析：步驟 符號(hào)棧 輸入串 所用產(chǎn)生式0 #E i1*i2+i3#1 #ET i1*i2+i3# E→TE2 #ETF i1*i2+i3# T→FT3 #ETi i1*i2+i3# F→i4 #ET *i2+i3#5 #ETF* *i2+i3# T→*FT6 #ETFi2+i3#7 #ETi i2+i3#F→i步驟 符號(hào)棧 輸入串 所用產(chǎn)生8 #ET +i3#9 #E +i3# T→10 #ET+ +i3# E→+TE11 #ET i3#12 #ETF i3# T→FT13 #ETi i3# F→i14 #ET #15 #E # T→16 # # E→二、分析表M[A，a]的構(gòu)造構(gòu)造FIRST()和FOLLOW(A)構(gòu)造分析表M[A，a]構(gòu)造FIRST()對每一文法符號(hào)XVT∪VN構(gòu)造FIRST(X)延續(xù)運(yùn)用下面的規(guī)那么，直至每個(gè)集合FIRST不再增大為止：1.假設(shè)XVT，那么FIRST(X)＝{X}。2.假設(shè)XVN，且有產(chǎn)生式X→a…，那么把a(bǔ)參與到FIRST(X)中；假設(shè)X→也是一條產(chǎn)生式，那么把也加到FIRST(X)中。3.假設(shè)X→Y…是一個(gè)產(chǎn)生式且YVN，那么把FIRST(Y)中的一切非-元素都加到FIRST(X)中；假設(shè)X→Y1Y2…Yk是一個(gè)產(chǎn)生式，Y1，…，Yi-1都是非終結(jié)符，而且，對于任何j，1ji-1，F(xiàn)IRST(Yj)都含有(即Y1…Yi-1)，那么把FIRST(Yi)中的一切非-元素都加到FIRST(X)中；特別是，假設(shè)一切的FIRST(Yj)均含有，j＝1，2，…，k，那么把加到FIRST(X)中。對文法G的任何符號(hào)串=X1X2…Xn構(gòu)造集合FIR