編譯原理第4章 語法分析 自上而下

4.1語法分析——自上而下分析內(nèi)容語法分析的任務(wù)與分類自上而下分析面臨的問題遞歸下降分析程序構(gòu)造LL(1)分析法句型、句子、語言的定義句型有文法G，若Sx，且x∈V*，則稱x是文法G的句型。句子有文法G，若Sx，且x∈VT*，則稱x是文法G的句子。例：G：S→0S1，S→01S0S100S11000S11100001111上下文無關(guān)文法的句型的推導(dǎo)最左（最右）推導(dǎo)：在推導(dǎo)的任何一步αβ，其中α、β是句型，都是對(duì)α中的最左（右）非終結(jié)符進(jìn)行替換最右推導(dǎo)被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型句型的分析句型分析就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過程。在語言的編譯實(shí)現(xiàn)中，把完成句型分析的程序稱為分析程序或識(shí)別程序。分析算法又稱識(shí)別算法。從左到右的分析算法，即總是從左到右地識(shí)別輸入符號(hào)串，首先識(shí)別符號(hào)串中的最左符號(hào)，進(jìn)而依次識(shí)別右邊的一個(gè)符號(hào)。

語法分析的任務(wù)：

對(duì)任一給定w∈VT*，判斷w∈L（G）?

語法分析器：按照產(chǎn)生式規(guī)則，做識(shí)別w的工作詞法分析器語法分析器編譯程序后續(xù)部分符號(hào)表源程序單詞符號(hào)取下一個(gè)單詞符號(hào)語法分析語法分析器在編譯程序中的地位分析算法分類：自上而下分析法（自頂向下）：

從文法的開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找與輸入符號(hào)匹配的最左推導(dǎo)。自下而上分析法（自底向上）：

從輸入符號(hào)串開始，逐步進(jìn)行歸約（最右推導(dǎo)的逆過程），直至歸約到文法的開始符號(hào)。語法分析算法分類語法分析方法 遞歸子程序 自頂向下 預(yù)測(cè)分析(LL（1）分析器) 算符優(yōu)先 自底向上 LR(0)、SLR(1)，LR(1)、LALR（1）

自上而下語法分析的一般過程從文法的開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找與輸入符號(hào)匹配的最左推導(dǎo)。

如果能夠推導(dǎo)出，則該輸入串是給定文法的句子；

如果不能推導(dǎo)出，則該輸入串不是給定文法的句子。主旨：從文法開始符號(hào)出發(fā)，自上而下的為輸入串建立一棵語法樹自頂向下語法分析要解決的關(guān)鍵問題假定要被代換的最左非終結(jié)符號(hào)是B，且有n條規(guī)則：B→A1|A2|…|An，那么如何確定用哪個(gè)右部去替代B？例1：文法G(S)：S→pAS→qBA→cAdA→a輸入串W=pccadd相應(yīng)的語法樹：SpApcAdpccAddpccaddSPASPAcdAcdASPAcdAcdASPAcdAaS→pAS→qBA→cAdA→aW=pccadd文法G(S)：S→pAS→qBA→cAdA→a該文法的特點(diǎn)：（1）每個(gè)產(chǎn)生式的右部都由終結(jié)符號(hào)開始；（2）如果兩個(gè)產(chǎn)生式有相同的左部，則它們的右部由不同的終結(jié)符開始。對(duì)于這樣的文法，其推導(dǎo)過程可以根據(jù)當(dāng)前的輸入符號(hào)決定選擇哪個(gè)產(chǎn)生式往下推導(dǎo)，因此，分析過程是唯一確定的。ScAdabaS—＞cAdA—＞abA—＞a輸入串w:文法G:IP分析過程：1）w——輸入串；IP—>‘c’S——擴(kuò)充；cad2）α=cAd；與IP—>‘c’匹配；3）IP—>‘a(chǎn)’A擴(kuò)展，第一式ab,IP—>‘a(chǎn)’與ab匹配；IP—>‘d’,但d與b不匹配;4）報(bào)告失敗，撤銷A的子樹，回到A;指針回退到IP—>‘a(chǎn)’;A還有替換式未試過，而又可能匹配；語法樹的形成過程匹配結(jié)束，語法樹形成例：文法G為：S→xAy|z，A→**|*輸入串=#x*y#自上而下的分析過程：（1）S有兩個(gè)侯選式“xAy”和“z”，侯選式“xAy”與輸入串“x*y”相匹配，故推導(dǎo)：SxAy。 （2）非終極符A也有兩個(gè)侯選式“**”和“*”，若選第一個(gè)侯選式“**”對(duì)句型進(jìn)行推導(dǎo)，則得：SxAyx**y，不相匹；推導(dǎo)回溯到句型“xAy”；再用非終極符A的第二個(gè)侯選式“*”進(jìn)行推導(dǎo)，即：SxAyx*y。且都是終極符，輸入串“x*y”是所給文法的句子。過程調(diào)用示意圖描述句型的推導(dǎo)過程例4.1

文法G41=({P,U},{a},{P→aU,U→P|},P)，L(G41)={an|n≥1}例4.2

文法G42=({P,B},{a},{P→B|a,B→Pa},P)，L(G42)=L(G41)例4.3

文法G43=({P},{a},{P→aP|a},P)，L(G43)=L(G41)G41過程調(diào)用圖

輸入串為#aa#文法G42=({P,B},{a},{P→B|a,B→Pa},P)

過程調(diào)用圖--輸入串為#aa#

首先，是文法的左遞歸問題。一個(gè)文法是含有左遞歸的，如果存在非終結(jié)符P的產(chǎn)生式P?Pα含有左遞歸的文法將使上述的自上而下的分析過程陷入無限循環(huán)。即，當(dāng)試圖用P去匹配輸入串時(shí)，我們會(huì)發(fā)現(xiàn)，在沒有識(shí)別任何輸入符號(hào)的情況下，又得重新要求P去進(jìn)行新的匹配。因此，使用自上而下分析法必須消除文法的左遞歸性。自上而下分析面臨的問題其次，由于回溯，如果走了一大段錯(cuò)路，最后必須回頭，那么，就應(yīng)把已經(jīng)做的一大堆語義工作（指中間代碼產(chǎn)生工作和各種表格的簿記工作）推倒重來?；厮輹?huì)引起時(shí)間和空間的大量消耗應(yīng)設(shè)法消除回溯。最后，如果被識(shí)別的語句是錯(cuò)的，算法無法指出錯(cuò)誤的確切位置。問題解決--消除左遞歸1.一個(gè)文法含有下列形式的產(chǎn)生式時(shí)，a)AAAVN,V*b)ABBAA,BVN,

，V*

稱為左遞歸文法。其中a)是直接遞歸，b)是間接遞歸。如果一個(gè)文法是左遞歸時(shí)，則不能采用自頂向下分析法。例：文法SSaSb是直接左遞歸所產(chǎn)生的語言是：L＝{ban|n≥0}例：文法為：AaBABbBAcBd是間接左遞歸※消除左遞歸的方法：(1)消除直接左遞歸：方法：改為右遞歸。保持其語言不變。直接左遞歸的消除候選式：A->Aα|βββαβααβααα……A->βA’A’->αA’|ε消去直接左遞歸后：E—＞TE′ E′—＞+TE′|ε T—＞FT′ T′—＞*FT′|ε F—＞（E）|i例4.2文法： E—＞E+T|TT—＞T*F|FF—＞（E）|i消除方法：若：A—＞Aα|β

，修改為

：

A—＞βA′A′—＞αA′|ε一般地，若文法的產(chǎn)生式為：P→P1|P2|……|Pn|1|2|……|m其中：j不以P打頭，i非空（1≤j≤m，1≤i≤n）；消除左遞歸后，為：P→1P'|2P'|……|mP'P'→1P'|2P'|……|nP'|

（2）消除隱含的左遞歸要求文法中不含回路，即無AA的推導(dǎo)①給文法VN中的符號(hào)一個(gè)排序：A1,A2,…,An；for(i=1;i<=n;i++){for(j=1;j<=i-1;j++){把形如Ai→Aj的規(guī)則改成 Ai→1|2|…|k 其中：Aj→1|2|…|k是關(guān)于Aj的所有規(guī)則；}/*替換為直接左遞歸*/ 消除關(guān)于Ai規(guī)則的直接左遞歸； }； 化簡所得到的文法（去掉無用產(chǎn)生式），結(jié)束。＋例子G46:S→Qc|cQ→Rb|bR→Sa|a有推導(dǎo)：S?Qc?Rbc?Sabc,存在左遞歸。按R、Q、S排序，執(zhí)行算法①得：i=1，j從1至0，R的產(chǎn)生式R→Sa|a無直接左遞歸，無需消除直接左遞歸。i=2，j從1至1，R的產(chǎn)生式代入Q的產(chǎn)生式得：Q→Sab|ab|b，無直接左遞歸。i=3，j從1至2，j=1，S的候選式不含R，所以無需替換；j=2，S的候選式含Q，將Q→Sab|ab|b代入S的候選式得： S→Sabc|abc|bc|c再消除直接左遞歸得： S→abcS'|bcS'|cS' S'→abcS'|ε消除無用產(chǎn)生式：Q→Sab|ab|b，R→Sa|a，得文法G47： S→abcS'|bcS'|cS' S'→abcS'|ε 文法G47對(duì)應(yīng)的正規(guī)式：V1=(abc|bc|c)(abc)*。S→Qc|cQ→Rb|bR→Sa|a消除隱含的左遞歸算法與非終極符排序方法無關(guān)；例如，文法G46按S、Q、R排序所得文法對(duì)應(yīng)正規(guī)式相同?！?.=bc(abc)*(abc)|c(abc)*(abc)|(abc)*(abc)|bc|c=bc(abc)+|c(abc)+|(abc)(abc)*|bc(abc)0|c(abc)0=bc((abc)+|(abc)0)|c((abc)+|(abc)0)

|(abc)(abc)*=bc(abc)*|c(abc)*|(abc)(abc)*=(abc|bc|c)(abc)*=V1例如，有產(chǎn)生式： 語句->if條件then語句else語句 |while條件do語句 |begin語句表end

若要尋找一個(gè)語句，那么關(guān)鍵字if，while，begin就提示某個(gè)替換式是唯一的替換式。2、消除回溯、提左公因子回溯原因

若當(dāng)前符號(hào)=a，下一步要展開A，而A->α1|α2|…|αm，那么，要知道哪一個(gè)αi是獲得以a開頭的串的式。怎樣選擇αi？ ①以a為頭的αi如果只有一個(gè)，則替換唯一；

②若以a為頭有多個(gè)αi的，則替換不唯一，需要回溯，這是文法的問題，應(yīng)該變換文法。解決辦法--提取左公因子

要求文法的任一非終極符的侯選式之間無左公因子，使相匹的侯選式是唯一的，提取左公因子的方法是增加非終結(jié)符，改寫文法。提取左公因子--例如：S→ifBthenSelseS|ifBthenS其中，S表示語句，if、then、else為終極符。提取左公因子，增加非終結(jié)符S3，產(chǎn)生式改成：S→ifBthenSS3S3→elseS|經(jīng)過反復(fù)提取左因子，就能夠把每個(gè)非終結(jié)符（包括新引進(jìn)者）的所有候選首符號(hào)變成為兩兩不相交。為此付出的代價(jià)是，大量引進(jìn)新的非終結(jié)符和ε-產(chǎn)生式。4.1.2遞歸下降分析程序構(gòu)造 在不含左遞歸和每個(gè)非終結(jié)符的所有候選式的終結(jié)首符集都兩兩不相交條件下，構(gòu)造一個(gè)不帶回溯的自上而下分析程序，該分析程序由一組遞歸過程組成，每個(gè)過程對(duì)應(yīng)文法的一個(gè)非終結(jié)符。這樣的一個(gè)分析程序稱為遞歸下降分析器。遞歸下降分析器

文法G消除左遞歸得：E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i給出#i+i*i#的最左推導(dǎo)：過程調(diào)用程序示意圖

E=>TE'=>FT'E'=>iT'E'=>iE'=>i+TE'=>i+FT'E'=>i+iT'E'=>i+i*FT'E'=>i+i*iT'E'=>i+i*iE'=>i+i*i當(dāng)前句型應(yīng)選候選式當(dāng)前輸入符號(hào)余下的符號(hào)ETE’ii+i*i上述分析方法的實(shí)現(xiàn)：

①每一非終結(jié)符對(duì)應(yīng)一個(gè)遞歸子程序；在只生成有限個(gè)串的文法，過程是無須遞歸的，而對(duì)生成無數(shù)個(gè)串的文法，遞歸是不可避免的；

②遞歸子程序：是一個(gè)過程，一旦發(fā)現(xiàn)它的某個(gè)候選式與輸入串匹配，它就按此式擴(kuò)充（語法樹），指針移過已匹配子串。否則，返回error，保持原來的（語法樹）和指針不變。使用記號(hào)：sym存放讀單詞子程序讀來的單詞，稱為當(dāng)前輸入符號(hào)，進(jìn)入程序前，輸入串的第一個(gè)符號(hào)應(yīng)讀入sym中；使用過程：advance()將讀單詞子程序的單詞指針下移一個(gè)單詞位置，且讀出指針?biāo)傅膯卧~，存入sym。

將過程調(diào)用示意圖寫成程序，程序稱為遞歸下降分析器。E'→+TE'|

voidE'(void){if(sym=='+'){advance();T();E'();}}F→(E)|i

voidF(void){if(sym=='i')advance();

else

if(sym=='('){advance();E();if(sym=')')advance();

elseerror();}

elseerror();}sym存放讀單詞子程序讀來的單詞，稱為當(dāng)前輸入符號(hào)；advance將指針下移一個(gè)單詞位置，且讀出單詞，存入sym。過程調(diào)用程序示意圖

問題：用遞歸子程序描寫遞歸下降分析 器，要求實(shí)現(xiàn)該編譯系統(tǒng)的語言允 許遞歸。改進(jìn)：使用一張分析表和一個(gè)棧同樣可實(shí)現(xiàn)遞歸下降分析，用這種方法實(shí)現(xiàn)的語法分析程序叫預(yù)測(cè)分析程序。4.3.1LL（1）分析器LL(1)分析法LL(1)分析法又稱預(yù)測(cè)分析法,是一種不帶回溯的非遞歸自上而下分析法。

LL(1)的含義:第一個(gè)L表明自左至右掃描輸入串;第二個(gè)L表明最左推導(dǎo);1表明向右查看一個(gè)符號(hào)。類似地,可有LL(k)文法,即向前查看k個(gè)符號(hào)才能確定選用哪個(gè)產(chǎn)生式,不過LL(k)(k>1)在實(shí)際中極少使用。LL（1）分析器LL(1)分析法的基本思想:

根據(jù)輸入串的當(dāng)前輸入符確定選用某一個(gè)產(chǎn)生式進(jìn)行推導(dǎo),當(dāng)該輸入符與推導(dǎo)的第一個(gè)符號(hào)相同時(shí)，再取輸入串的下一個(gè)符號(hào),繼續(xù)確定下一個(gè)推導(dǎo)應(yīng)選的產(chǎn)生式,如此下去,直到推出被分析的輸入串為止。

LL(1)分析器組成：一張LL(1)分析表(預(yù)測(cè)分析表)

一個(gè)分析棧(后進(jìn)先出)

一個(gè)控制程序(表驅(qū)動(dòng)程序)組成。a1a2…ai…an#分析表M控制程序輸入串：棧頂#x1…xj輸出分析棧LL(1)分析器表項(xiàng)：M[A,a]A的產(chǎn)生式待分析的符號(hào)串,它以“#”作為結(jié)束標(biāo)志。存放分析過程中的文法符號(hào)。分析開始時(shí)棧底先放一個(gè)“#”對(duì)LL(1)分析器說明如下：

(1)輸入串是待分析的符號(hào)串,它以“#”作為結(jié)束標(biāo)志。

(注:#∈VT但不是文法符號(hào),是由分析程序自動(dòng)添加的)(2)分析棧STACK存放分析過程中的文法符號(hào)。分析開始時(shí)棧底先放一個(gè)“#”,再壓入文法開始符;當(dāng)分析棧中僅?！?”且輸入串指針指向串尾的“#”時(shí),分析成功。

(3)分析表用一個(gè)矩陣M(二維數(shù)組)表示,它概括了文法的全部信息。矩陣的每一行與文法的一個(gè)非終結(jié)符相關(guān)聯(lián),而每一列與文法的一個(gè)終結(jié)符或“#”關(guān)聯(lián)(見表4－2)。分析表元素M[A,a]中的內(nèi)容為

一條A的產(chǎn)生式（比如：A→aB)表明當(dāng)A面臨輸入符a時(shí)應(yīng)采用的候選式;當(dāng)元素內(nèi)容為空時(shí),表明A不應(yīng)面臨輸入符a,即輸入串含語法錯(cuò)誤。(4)總控程序根據(jù)分析棧棧頂符號(hào)x和當(dāng)前輸入符a查表決定分析器的動(dòng)作:①若x＝a＝“#”,即STACK棧頂符號(hào)為“#”，當(dāng)前輸入符號(hào)為“#”，則分析成功。②若x＝a≠“#”,即棧頂符號(hào)x與當(dāng)前輸入符a匹配,則將x從棧頂彈出,輸入串指針后移,讀入下一個(gè)符號(hào)存入a，繼續(xù)對(duì)下一個(gè)字符進(jìn)行分析。

③若x為非終結(jié)符A,則查分析表M[A,a]:i.若M[A,a]為一產(chǎn)生式,則A自棧頂彈出,M[A,a]中產(chǎn)生式的右部符號(hào)逆序壓棧;若M[A,a]為A→ε,則只將A自棧頂彈出。ii.若M[A,a]為空,則發(fā)現(xiàn)語法錯(cuò)誤,調(diào)用出錯(cuò)處理程序進(jìn)行處理?？刂瞥绦蛎枋鋈缦?1.將“#”和文法開始符依次入棧Stack;2.把第一個(gè)輸入符讀入a;do{pop(Stack,x)//彈出棧頂放入x中;

if(x∈VT){

if(x＝＝a)//x＝a≠“#”,將下一輸入符讀入a;

elseerror();}

elseif(M[x,a]＝＝“x→y1y2…yk”){把y1y2…yk按逆序入棧;若M[x,a]為X->ε,ε不入棧;輸出“x→y1y2…yk”;}

elseerror();

}while(x!=“#”)3.分析成功，完畢！//x＝a＝“#”分析表格式i+*()#EE—＞TE′E—＞TE′E’E′—＞+TE′E′—＞εE′—＞εTT—＞FT′T—＞FT′T’T′—＞εT′—＞*FT′T′—＞εT′—＞εFF—＞iF—＞(E)E—＞TE′ E′—＞+TE′|εT—＞FT′ T′—＞*FT′|εF—＞（E）|i返回

i+i*i的最左推導(dǎo)：E=>TE’=>FT’E’=>iT’E’=>iE’=>i+TE’=>i+TE’=>i+FT’E’=>i+iT’E’=>i+i*FT’E’=>…i+i*iE—＞TE′ E′—＞+TE′|εT—＞FT′ T′—＞*FT′|εF—＞（E）|i例按LL(1)分析法，分析句子＃i+i*i＃棧輸入輸出1#Ei+i*i#2#E′Ti+i*i#E—＞TE′3#E′T′Fi+i*i#T—＞FT′4#E′T′ii+i*i#F—＞i5#E′T′+i*i#6#E′+i*i#T′—＞ε7#E′T′++i*i#E′—＞+TE′#E′T′i*i##E′T′Fi*i#T—＞FT′M[E,i]=E—＞TE′M[T,i]=T—＞FT′左部出棧，右部反序壓棧!M[F,i]=F—＞i匹配，i出棧輸入串指針后移XaEiTiFiii棧輸入輸出10#E′T′ii*i#F—＞i11#E′T′*i#12#E′T′F**i#T′—＞*FT′13#E′T′Fi#14#E′T′ii#F—＞i15#E′T′#16#E′#T′—＞ε##E′—＞ε

有:X=a=#，分析成功。

iiXaT

′i**FiiiT’#E’###結(jié)論：①輸出的產(chǎn)生式就是最左推導(dǎo)的產(chǎn)生式。棧中存放產(chǎn)生式右部，等待與α匹配；②當(dāng)棧頂X＝a時(shí)，表指出如何擴(kuò)充語法樹，出錯(cuò)能馬上發(fā)現(xiàn)。實(shí)質(zhì)：棧：部分句型，句型右部，還未得到推導(dǎo)的 表：指出VN按哪一條擴(kuò)充，依賴于VTF—＞(E)F—＞iFT′—＞εT′—＞εT′—＞*FT′T′—＞εT′T—＞FT′T—＞FT′TE′—＞εE′—＞εE′—＞+TE′E′E—＞TE′E—＞TE′E#)(*+ii+i*i#：+E?TFT?*FT?iiεεETE?FT?iε上述分析過程生成的語法樹：分析表的構(gòu)造分析表格式：i+*()#EE—＞TE′E—＞TE′E′E′—＞+TE′E′—＞

εE′—＞

εTT—＞FT′T—＞FT′T′T′—＞

εT′—＞*FT′T′—＞

εT′—＞

εFF—＞iF—＞(E)思路：

1）把產(chǎn)生式填到何處？

2）按A?

將產(chǎn)生式分為兩種： 一種是：Aa…

另種是：Aε2.LL(1)分析表的構(gòu)造

LL(1)分析器中除分析表因文法的不同而不同外,分析棧、控制程序都相同。因此構(gòu)造一個(gè)LL(1)分析器實(shí)際上就是構(gòu)造文法的LL(1)分析表。構(gòu)造分析表M,需預(yù)先定義FIRST集和FOLLOW集。假定是文法任一符號(hào)串,(VT∪VN)*

先要構(gòu)造兩個(gè)與G有關(guān)的集合：FIRST(α)和FOLLOW(A)；

1）若有文法G，α∈V*，S，A∈VN定義4.1FIRST(α)={a|αa…,a∈VT}

特別的，若α

ε，規(guī)定ε∈FIRST(α)定義4.2FOLLOW(A)={a|S

αAaβ，a∈VT，α,β∈V

*}若S…A成立，則規(guī)定句子的右界符#∈FOLLOW(A)2）構(gòu)造FIRST(α)先構(gòu)造FIRST(X),X∈V。

連續(xù)使用以下規(guī)則，直至再無終結(jié)符，或ε加入任一FIRST集為止①若X∈VT，則FIRST(X)＝{X}②若X∈VN,且X->aα，則FIRST(X)＝{a}∪FIRST(X)

X->ε，則FIRST(X)＝{ε}∪FIRST(X)③若X∈VN,X->Y…,Y∈VN,則FIRST(Y)\{ε}FIRST(X)進(jìn)而：若X->Y1Y2…Yi-1Yi…Yk,Yj∈VN,1≤j≤i-1

ε∈FIRST(Yj)，即Y1Y2…Yi-1

ε，則特別，若Y1Y2…Ykε，則ε∈FIRST(x)。

2）先構(gòu)造FIRST(X),X∈V。若x∈(VN∪VT)*，不妨設(shè)x=x1x2x3…xn

①FIRST(X1)的非ε終結(jié)符加入FIRST(α)FIRST(x)=FIRST(x1)-{ε}；

②若ε∈FIRST(X1)， 則FIRST(X2)的所有非ε終結(jié)符加入FIRST(α)③若ε∈FIRST(X1),ε∈FIRST(X2)， 則FIRST(X3)的所有非ε終結(jié)符加入FIRST(α)最后，若ε∈FIRST(Xi),i=1..n，則{ε}加入FIRST(α)即：例如，已知文法的產(chǎn)生式為： X→Y1Y2Y3Y4Y5 Y1→a|ε Y2→b|ε Y3→c|ε Y4→d|ε Y5→e|ε求FIRST(X)的過程如下：（1）FIRST(X)={};（2）for(i=1;I<=5;I++) FIRST(X)=FIRST(X)∪FIRST(Yi)\{ε};（3）if(Y1Y2Y3Y4Y5ε)FIRST(X)=FIRST(X)∪{ε};計(jì)算結(jié)果：FIRST(X)={a，b，c，d，e，ε}3）構(gòu)造FOLLOW(A)①置初值：對(duì)任一A∈VN，置FOLLOW(A):={}；若A是文法的開始符號(hào)，則置FOLLOW(A):={#}，“#”是句子右界符；②若有A→αBβ，B∈VN，則置FOLLOW(B)=FOLLOW(B)∪FIRST(β)-{ε}；③若有產(chǎn)生式A→αB或A→αBβ，且有βε，則置FOLLOW(B)=FOLLOW(B)∪FOLLOW(A)；④重復(fù)②、③，直至每個(gè)FOLLOW(A)不擴(kuò)大為止。4）例4.6已知文法G：E—＞TE′ T′—＞*FT′|εE′—＞+TE′|εF—＞（E）|iT—＞FT′求它的FIRST(α),FOLLOW(A)FIRST集的構(gòu)造：FIRST(E)=FIRST(T)=FIRST(F)={(,i}FIRST(E’)={+,ε}FIRST(T’)={*,ε}①#屬于FOLLOW(S)②若存在A->αBβ，則FIRST(β)FOLLOW(B),除ε外由①得：FOLLOW(E)={#}由②得：E—＞TE′則FIRST(E’)\{ε}FOLLOW(T)， 即FOLLOW(T)={+}T—＞FT′則FIRST(T’)\{ε}FOLLOW(F), 即FOLLOW(F)={*}F—＞（E）則FIRST())∈FOLLOW(E), 即FOLLOW(E)={#,)}

FOLLOW集的構(gòu)造：FIRST(T’)={*,ε}FIRST(E’)={+,ε}即FOLLOW(F)={*,,,}③若有A->αB，或A->αBβ且ε∈FIRST(β),則FOLLOW(B)FOLLOW(A)FOLLOW(E)={),#}FOLLOW(T)={+}FOLLOW(F)={*}由③得：E—＞TE′得FOLLOW(E)FOLLOW(E’)，即FOLLOW(E’)={,})

#

E—＞TE′且E’—>ε得FOLLOW(E)FOLLOW(T)，即FOLLOW(T)={+,,})

#

T—＞FT′得FOLLOW(T)FOLLOW(T’),即FOLLOW(T’)={,,}T—＞FT′且T’—>ε得FOLLOW(T)

FOLLOW(F),)

#

+

)

#

+

FIRST(E)=FIRST(T)=FIRST(F)={(,i}FIRST(E’)={+,ε}FIRST(T’)={*,ε}FOLLOW(E)=FOLLOW(E’)={),#}FOLLOW(T)=FOLLOW(T’)={+，)，#}FOLLOW(F)={*,+,),#}最終構(gòu)造結(jié)果：注意：FIRST集針對(duì)終結(jié)符，非終結(jié)符，候選式而構(gòu)造；FOLLOW集只對(duì)非終結(jié)符構(gòu)造。Follow(S)=Follow(A)=Follow(B)=Follow(C)=Follow(D)=文法為：SAB|bCAε|bBε|aDCAD|bDaS|c思考：求FOLLOW集SAB

BbBAAaDFollow(S)={#}Follow(A)={a，#，c}Follow(B)={#}Follow(C)={#}Follow(D)={#}文法為：SAB|bCAε|bBε|aDCAD|bDaS|cS為開始符號(hào)，加入#SABA

AABAaDbCbADbAc69693構(gòu)造分析表基本思想是:當(dāng)文法中某一非終結(jié)符呈現(xiàn)在棧頂時(shí),根據(jù)當(dāng)前的輸入符號(hào),分析表應(yīng)指示要用該非終結(jié)符里的哪一條規(guī)則去匹配輸入串(即進(jìn)行下一步最左推導(dǎo))根據(jù)這個(gè)思想,不難把構(gòu)造分析表算法構(gòu)造出來.終結(jié)符號(hào)非終結(jié)符號(hào)i+i*i的最左推導(dǎo)：E=>TE’=>FT’E’=>iT’E’=>iE’=>i+TE’=>i+TE’=>i+FT’E’=>i+iT’E’=>i+i*FT’E’=>…i+i*i構(gòu)造分析表算法：輸入——G文法，輸出——分析表M①對(duì)文法的每一個(gè)A->α,做②和③；②對(duì)于任a∈FIRST(α),把A->α加進(jìn)M[A，a]③若ε∈FIRST(α)，則把A->α加進(jìn)M[A,b],b∈FOLLOW(A)；

④若M[A，a]為空時(shí)，則填ERROR。上述方法構(gòu)造的分析表稱為LL(1)分析表。若LL(1)分析表無重復(fù)定義（即任一M[A，a]值唯一），則相應(yīng)的文法為LL(1)文法。例：

E—＞TE′填法：∵ FIRST(TE′)=FIRST(T)={(,i}∴ M[E,(]={E—＞TE′} M[E,i]={E—＞TE′}

E—＞+TE′填法：

M[E,+]={E—＞+TE′}E′—＞ε填法：∵ FOLLOW(E′)={),#}∴ M[E′,)]={E′—＞ε} M[E,#]={E′—＞ε}定理4.1、LL（1）文法的條件LL（1）文法一個(gè)文法G，若它的分析表M不含多重定義入口，則稱它是一個(gè)LL（1）文法。（1）FIRST(α）∩FIRST(β)=φ（2）若βε，則FIRST（α）∩FOLLOW（A）=Φ

文法G是LL(1)的，則對(duì)于G的每一個(gè)非終結(jié)符A的任何兩個(gè)不同產(chǎn)生式A->α|β,有：說明： 使用LL(1)文法，一定可以實(shí)現(xiàn)不帶回溯的自上而下分析；①對(duì)A->α|β，若條件（1）不成立， 則 FIRST(α）∩FIRST(β)≠φ，假設(shè)，F(xiàn)IRST(α）∩FIRST(β)={a}

那么，當(dāng)A面臨輸入符號(hào)a，而a同時(shí)屬于FIRST(α）和FIRST(β)，則分析無法繼續(xù)進(jìn)行下去，因?yàn)椴荒艽_定用哪一個(gè)候選式可以保證一定能夠得到匹配而不進(jìn)行回溯。

實(shí)質(zhì)就是分析表的M[A,a]中包含兩條候選式 A->α A->β反之，分析表的M[A,a]中只包含一條候選式則意味著可以進(jìn)行確定性的無回溯的分析。②對(duì)A->α|β，若βε，且條件（2）不成立， 則 FIRST（α）∩FOLLOW（A）≠Φ假設(shè)，F(xiàn)IRST(α）∩FOLLOW(A)={a} 那么，當(dāng)A面臨輸入符號(hào)a時(shí)， 若選候選式A->α，則由于a∈FIRST(α）可以使a一定得到匹配；同時(shí)，若選候選式A->β也可以滿足要求，