編譯原理4自頂向下的語法分析

1、Part4Part4語法分析語法分析授課：胡靜授課：胡靜語法分析器的作用語法分析器的作用以語法分析器為核心的編譯器模型以語法分析器為核心的編譯器模型語法分語法分析器析器詞法分詞法分析器析器中間代碼中間代碼生成器生成器語義分析器語義分析器一部分中一部分中間代碼間代碼輸入字輸入字符串符串程序入口程序入口初始化工作初始化工作語法分析器所處的位置語法分析器所處的位置語法分析的例子語法分析的例子語法分析的類比語法分析的類比針對(duì)自然語言的語法分析：針對(duì)自然語言的語法分析：識(shí)別一個(gè)句子是不是符合語法規(guī)范識(shí)別一個(gè)句子是不是符合語法規(guī)范&識(shí)別每一個(gè)成分識(shí)別每一個(gè)成分的功能。的功能。語法分析器的作用語法分

2、析器的作用接收詞法分析器提供的記號(hào)串接收詞法分析器提供的記號(hào)串檢查記號(hào)串是否能由源程序語言的文法產(chǎn)生檢查記號(hào)串是否能由源程序語言的文法產(chǎn)生用易于理解的方式提示語法錯(cuò)誤信息，并能從常見的用易于理解的方式提示語法錯(cuò)誤信息，并能從常見的錯(cuò)誤中恢復(fù)過來錯(cuò)誤中恢復(fù)過來語法分語法分析器析器詞法詞法分析器分析器符號(hào)表符號(hào)表前端的其前端的其余部分余部分源程序源程序記號(hào)記號(hào)取下一取下一個(gè)記號(hào)個(gè)記號(hào)語法樹語法樹中間表示中間表示語法分析器工作原理語法分析器工作原理語言的結(jié)構(gòu)是用上下文無關(guān)文法描述的，因此，語法分析器語言的結(jié)構(gòu)是用上下文無關(guān)文法描述的，因此，語法分析器的工作本質(zhì)上就是按照文法的產(chǎn)生式，識(shí)別輸入符號(hào)串是

3、否的工作本質(zhì)上就是按照文法的產(chǎn)生式，識(shí)別輸入符號(hào)串是否為一個(gè)句子。為一個(gè)句子。語法分析器是從左向右的掃描輸入字符串，每次讀入一個(gè)符語法分析器是從左向右的掃描輸入字符串，每次讀入一個(gè)符號(hào)，并判斷，看是否能從文法的開始符號(hào)出發(fā)推導(dǎo)出這個(gè)輸號(hào)，并判斷，看是否能從文法的開始符號(hào)出發(fā)推導(dǎo)出這個(gè)輸入串?；蛘?，從概念上講，就是要建立一棵與輸入串匹配的入串。或者，從概念上講，就是要建立一棵與輸入串匹配的語法分析樹。語法分析樹。語法分析器分類語法分析器分類 通用的語法分析方法，用來分析任何文法，生成編譯器時(shí)效率太通用的語法分析方法，用來分析任何文法，生成編譯器時(shí)效率太低低編譯器使用的語法分析方法編譯器使用的語法

4、分析方法處理文法的一些子類處理文法的一些子類自頂向下（建立分析樹）自頂向下（建立分析樹）LL文法，其分析器常用手工實(shí)現(xiàn)文法，其分析器常用手工實(shí)現(xiàn)自底向上（建立分析樹）自底向上（建立分析樹）LR文法，其分析器常利用自動(dòng)生成工文法，其分析器常利用自動(dòng)生成工具構(gòu)造具構(gòu)造自頂向下分析面臨的困難自頂向下分析面臨的困難自頂向下分析面臨的困難自頂向下分析面臨的困難 自頂向下分析的主旨是，對(duì)任何輸入串，試圖用一切自頂向下分析的主旨是，對(duì)任何輸入串，試圖用一切可能的辦法，從文法的開始符號(hào)（根結(jié)）出發(fā)，自頂可能的辦法，從文法的開始符號(hào)（根結(jié)）出發(fā)，自頂向下的為輸入串建立一棵語法樹。向下的為輸入串建立一棵語法樹。這

5、種分析過程本質(zhì)上是一種試探過程，是反復(fù)使用不這種分析過程本質(zhì)上是一種試探過程，是反復(fù)使用不同產(chǎn)生式謀求匹配輸入串的過程。同產(chǎn)生式謀求匹配輸入串的過程。 自頂向下分析的一般方法是帶自頂向下分析的一般方法是帶“回溯回溯”的。的。自頂向下分析方法的特點(diǎn)自頂向下分析方法的特點(diǎn)自頂向下分析存在的問題自頂向下分析存在的問題左遞歸文法：左遞歸文法：有如下文法：有如下文法：令令P是文法的任一非終結(jié)符，文法中有規(guī)則是文法的任一非終結(jié)符，文法中有規(guī)則PP或或者者P=+P，這個(gè)文法是左遞歸的。，這個(gè)文法是左遞歸的。自頂向下分析的基本缺點(diǎn)是：不能處理具有左遞歸的自頂向下分析的基本缺點(diǎn)是：不能處理具有左遞歸的文法。文法

6、。？自頂向下分析存在的問題自頂向下分析存在的問題假定文法假定文法GS，以及輸入串，以及輸入串x*y（記為（記為）。）。SxAyA*|*初始化：初始化：第一步擴(kuò)展第一步擴(kuò)展Sx*yIPSx*yIPyAx自頂向下分析的困難自頂向下分析的困難假定文法假定文法GS，以及輸入串，以及輸入串x*y（記為（記為）。）。SxAyA*|*第二步擴(kuò)展：第二步擴(kuò)展：回溯回溯x*yIPSx*yIPyAx*SyAx*遞歸下降分析程序構(gòu)造遞歸下降分析程序構(gòu)造前面的巴科斯范式只用到了兩個(gè)元符號(hào)前面的巴科斯范式只用到了兩個(gè)元符號(hào)“”和和“|” 擴(kuò)充的巴科斯范式加入幾個(gè)元語言符號(hào)：擴(kuò)充的巴科斯范式加入幾個(gè)元語言符號(hào)：用花括號(hào)用

7、花括號(hào)表示閉包運(yùn)算表示閉包運(yùn)算*。用用n0表示表示可任意重復(fù)可任意重復(fù)0次至次至n次。次。00=0=.用方括號(hào)用方括號(hào)表示表示10，即表示，即表示的出現(xiàn)可有可無（等價(jià)于的出現(xiàn)可有可無（等價(jià)于 |）。）。 例如，通常的例如，通常的“實(shí)數(shù)實(shí)數(shù)”可定義為：可定義為：decimalsigninteger.digitexponentexponentEsignintegerintegerdigitdigitsign+ | -遞歸下降分析程序的構(gòu)造遞歸下降分析程序的構(gòu)造當(dāng)文法滿足上述兩個(gè)文法條件時(shí)，我們就可以為它構(gòu)當(dāng)文法滿足上述兩個(gè)文法條件時(shí)，我們就可以為它構(gòu)造一個(gè)不帶回溯的自頂向下分析程序，這個(gè)分析程序造

8、一個(gè)不帶回溯的自頂向下分析程序，這個(gè)分析程序是由一組遞歸過程組成的。每個(gè)過程對(duì)應(yīng)文法的一個(gè)是由一組遞歸過程組成的。每個(gè)過程對(duì)應(yīng)文法的一個(gè)非終結(jié)符。這樣的一個(gè)分析程序稱為遞歸下降分析器。非終結(jié)符。這樣的一個(gè)分析程序稱為遞歸下降分析器。 EE+T | TTT*F | FF(E) | iET+TTF*FF(E) | i遞歸下降分析程序構(gòu)造遞歸下降分析程序構(gòu)造ET+TTF*FF(E) | iPROCEDURE E;BEGINT;WHILE SYM = + DOBEGIN ADVANCE; T ENDENDPROCEDURE T;BEGINF;WHILE SYM = * DOBEGIN ADVANCE;

9、 F ENDENDLL(1)LL(1)分析法分析法消除直接左遞歸消除直接左遞歸改寫成右遞歸改寫成右遞歸直接左遞歸的消除直接左遞歸的消除PP | PPPP | EE+T | TTT*F | FF(E) | iETEE+TE | TFTT*FT | F(E) | i消除左遞歸的一般算法消除左遞歸的一般算法如果一個(gè)文法不含回路（形如如果一個(gè)文法不含回路（形如P=+P的推導(dǎo)），也的推導(dǎo)），也不含以不含以為右部的產(chǎn)生式，那么執(zhí)行下述算法將保證為右部的產(chǎn)生式，那么執(zhí)行下述算法將保證消除左遞歸（但改寫后的文法可能含有消除左遞歸（但改寫后的文法可能含有為右部的產(chǎn)為右部的產(chǎn)生式）。生式）。 消除左遞歸的算法消除

10、左遞歸的算法消除左遞歸的例子消除左遞歸的例子RSa | aQRb | bSQc |cRSa |aQSab | ab | bSSabc | abc | bc | cSabcS | bcS | cSSabcS | RSa |aQSab | ab | bSabcS | bcS | cSSabcS | SQc | cQRb | bRbcaR |caR | aRRbcaR | 回溯問題回溯問題消除回溯、提取左因子消除回溯、提取左因子令是一個(gè)不含左遞歸的文法，對(duì)令是一個(gè)不含左遞歸的文法，對(duì)G的所有非終結(jié)符的每個(gè)候的所有非終結(jié)符的每個(gè)候選選定義它的終結(jié)首符集定義它的終結(jié)首符集FIRST()為：為：FIRST

11、()=a | =*a, aVT 若若=*，則規(guī)定，則規(guī)定FIRST()FIRST()是是的所有可能推導(dǎo)的開頭終結(jié)符或可能的的所有可能推導(dǎo)的開頭終結(jié)符或可能的 如果非終結(jié)符的所有候選首符集兩兩不相交，即的任何如果非終結(jié)符的所有候選首符集兩兩不相交，即的任何兩個(gè)不同候選兩個(gè)不同候選i和和FIRST(i) FIRST(j)=那么當(dāng)要求匹配輸入串時(shí)，就能根據(jù)它所面臨的第一個(gè)那么當(dāng)要求匹配輸入串時(shí)，就能根據(jù)它所面臨的第一個(gè)輸入符號(hào)，準(zhǔn)確的指派某一個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候輸入符號(hào)，準(zhǔn)確的指派某一個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含的選就是那個(gè)終結(jié)首符集含的。 消除回溯、提取左因子消除回溯、提

12、取左因子提取左因子的方法提取左因子的方法假定的規(guī)則是：假定的規(guī)則是：1 |2 | |n |1 |2 | |m（其中，每個(gè)（其中，每個(gè)不以不以開頭）開頭）那么這些規(guī)則可以改寫為：那么這些規(guī)則可以改寫為：AA |1 |2 | |mA1 |2 | |n經(jīng)過反復(fù)提取左因子，就能夠把每個(gè)非終結(jié)符（包括新引進(jìn)經(jīng)過反復(fù)提取左因子，就能夠把每個(gè)非終結(jié)符（包括新引進(jìn)者）的所有候選首符集便成為兩兩不相交。我們?yōu)榇艘冻稣撸┑乃泻蜻x首符集便成為兩兩不相交。我們?yōu)榇艘冻龅拇鷥r(jià)是大量引進(jìn)新的非終結(jié)符和的代價(jià)是大量引進(jìn)新的非終結(jié)符和產(chǎn)生式。產(chǎn)生式。 消除回溯、提取左因子消除回溯、提取左因子提取左因子的方法提取左因子的

13、方法假定的規(guī)則是：假定的規(guī)則是：1 |2 | |n |1 |2 | |m（其中，每個(gè)（其中，每個(gè)不以不以開頭）開頭）那么這些規(guī)則可以改寫為：那么這些規(guī)則可以改寫為：AA |1 |2 | |mA1 |2 | |n經(jīng)過反復(fù)提取左因子，就能夠把每個(gè)非終結(jié)符（包括新引進(jìn)經(jīng)過反復(fù)提取左因子，就能夠把每個(gè)非終結(jié)符（包括新引進(jìn)者）的所有候選首符集便成為兩兩不相交。我們?yōu)榇艘冻稣撸┑乃泻蜻x首符集便成為兩兩不相交。我們?yōu)榇艘冻龅拇鷥r(jià)是大量引進(jìn)新的非終結(jié)符和的代價(jià)是大量引進(jìn)新的非終結(jié)符和產(chǎn)生式。產(chǎn)生式。 LL(1)LL(1)分析條件分析條件ETEE+TE | TFTT*FT | F(E) | i對(duì)輸入串對(duì)輸

14、入串i+i進(jìn)行自頂向下分析進(jìn)行自頂向下分析Ei + iIPTEiFIRST(TE)Ei + iIPTEiFIRST(FT)FTEi + iIPTEiFIRST(i)FTiLL(1)LL(1)分析條件分析條件ETEE+TE | TFTT*FT | F(E) | i對(duì)輸入串對(duì)輸入串i+i進(jìn)行自頂向下分析進(jìn)行自頂向下分析Ei + iIPTE+不屬于不屬于T的任一候選式的首符集的任一候選式的首符集FTiETEFTi+TEFTiLL(1)LL(1)分析條件分析條件如果如果A的某個(gè)候選首符集中包含的某個(gè)候選首符集中包含怎么辦？怎么辦？假定假定S是文法是文法G的開始符號(hào)，對(duì)于的開始符號(hào)，對(duì)于G的任何非終結(jié)符

15、的任何非終結(jié)符A，我們定義我們定義FOLLOW(A)=a | S=*Aa，aVTFOLLOW(A)是所有句型中出現(xiàn)在緊接是所有句型中出現(xiàn)在緊接A之后的終結(jié)之后的終結(jié)符或符或“#”。 開始符號(hào)的開始符號(hào)的FOLLOW集初始化時(shí)加入集初始化時(shí)加入“#”。當(dāng)非終結(jié)符當(dāng)非終結(jié)符A面臨輸入符號(hào)面臨輸入符號(hào)a，且，且a不屬于不屬于A的任意候的任意候選首符集但選首符集但A的某個(gè)候選首符集包含的某個(gè)候選首符集包含時(shí)，只有當(dāng)時(shí)，只有當(dāng)aFOLLOW(A)時(shí)，才可能允許時(shí)，才可能允許A自動(dòng)匹配。自動(dòng)匹配。 LL(1)LL(1)分析條件分析條件通過上面的討論，我們可以找出滿足構(gòu)造不帶回溯的自頂向通過上面的討論，我們

16、可以找出滿足構(gòu)造不帶回溯的自頂向下分析的文法條件。下分析的文法條件。 文法不含左遞歸文法不含左遞歸對(duì)于文法中每一個(gè)非終結(jié)符對(duì)于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若不相交。即，若A1 |2 | |n，則，則FIRST(i)FIRST(j)=(ij)對(duì)文法中的每個(gè)非終結(jié)符對(duì)文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)候選首符集包含，若它存在某個(gè)候選首符集包含，則，則，F(xiàn)IRST(A)FOLLOW(A)=如果一個(gè)文法如果一個(gè)文法G滿足以上條件，則稱該文法滿足以上條件，則稱該文法G為為L(zhǎng)L(1)文法。文法。這里這里L(fēng)L(1)中的第一個(gè)中的第一個(gè)L表示從左

17、到右掃描輸入串，第二個(gè)表示從左到右掃描輸入串，第二個(gè)L表示最左推導(dǎo)，表示最左推導(dǎo)，1表示分析時(shí)每一步只需向前查看一個(gè)符號(hào)。表示分析時(shí)每一步只需向前查看一個(gè)符號(hào)。 LL(1)LL(1)分析條件分析條件對(duì)于一個(gè)對(duì)于一個(gè)LL(1)文法，可以對(duì)其輸入串進(jìn)行有效的無文法，可以對(duì)其輸入串進(jìn)行有效的無回溯的自頂向下分析?；厮莸淖皂斚蛳路治?。假設(shè)要用非終結(jié)符假設(shè)要用非終結(jié)符A進(jìn)行匹配，面臨的輸入符號(hào)為進(jìn)行匹配，面臨的輸入符號(hào)為a，A的所有產(chǎn)生式為的所有產(chǎn)生式為A1 |2 | |n若若aFIRST(i)，則指派，則指派i去執(zhí)行匹配任務(wù)。去執(zhí)行匹配任務(wù)。若若a不屬于任何一個(gè)候選首字符集，則：不屬于任何一個(gè)候選首字

18、符集，則：若若屬于某個(gè)屬于某個(gè)FIRST(i)，且，且aFOLLOW(A)，則讓，則讓A與與自動(dòng)匹配；自動(dòng)匹配；否則，否則，a的出現(xiàn)是一種語法錯(cuò)誤。的出現(xiàn)是一種語法錯(cuò)誤。根據(jù)根據(jù)LL(1)文法的條件，每一步這樣的工作都是確信文法的條件，每一步這樣的工作都是確信無疑的無疑的 LL(1)LL(1)分析法分析法預(yù)測(cè)分析程序工作過程預(yù)測(cè)分析程序工作過程實(shí)現(xiàn)實(shí)現(xiàn)LL(1)分析的一種有效方法是使用一張分析表和一個(gè)棧進(jìn)分析的一種有效方法是使用一張分析表和一個(gè)棧進(jìn)行聯(lián)合控制。下面要介紹的預(yù)測(cè)分析程序就是屬于這種類型行聯(lián)合控制。下面要介紹的預(yù)測(cè)分析程序就是屬于這種類型的的LL(1)分析器。分析器。 預(yù)測(cè)分析表預(yù)

19、測(cè)分析表預(yù)測(cè)分析表示一個(gè)預(yù)測(cè)分析表示一個(gè)MA,a形式的矩陣。其中形式的矩陣。其中A為非終結(jié)符，為非終結(jié)符，a是是終結(jié)符或終結(jié)符或# 。矩陣元素矩陣元素MA,a中存放著一條關(guān)于中存放著一條關(guān)于A的產(chǎn)生式，指出當(dāng)?shù)漠a(chǎn)生式，指出當(dāng)A面臨輸面臨輸入符號(hào)入符號(hào)a時(shí)所應(yīng)采用的候選。時(shí)所應(yīng)采用的候選。MA,a中也可能存放一個(gè)中也可能存放一個(gè)“出錯(cuò)標(biāo)志出錯(cuò)標(biāo)志”，指出，指出A根本不該面臨根本不該面臨輸入符號(hào)輸入符號(hào)a。 i+*()#EETEETEEE+TEEETTFTTFTTTT*FTTTFFiF(E)預(yù)測(cè)分析過程概述預(yù)測(cè)分析過程概述預(yù)測(cè)分析程序的總控程序在任何時(shí)候都是按預(yù)測(cè)分析程序的總控程序在任何時(shí)候都是按

20、STACK棧頂符號(hào)棧頂符號(hào)X和當(dāng)前的輸入符號(hào)和當(dāng)前的輸入符號(hào)a行事的。如下圖所示，對(duì)于任何行事的。如下圖所示，對(duì)于任何(X,a)，總控程序每次都執(zhí)行下述三種可能的動(dòng)作之一：總控程序每次都執(zhí)行下述三種可能的動(dòng)作之一：若若X = a = #，則宣布分析成功，停止分析過程。，則宣布分析成功，停止分析過程。若若X = a #，則把，則把X從從STACK棧頂彈出，讓棧頂彈出，讓a指向下一個(gè)輸入符指向下一個(gè)輸入符號(hào)。號(hào)。若若X是一個(gè)非終結(jié)符，則查看分析表是一個(gè)非終結(jié)符，則查看分析表M。若若MX,a中存放著關(guān)于中存放著關(guān)于X的一個(gè)產(chǎn)生式，那么，先把的一個(gè)產(chǎn)生式，那么，先把X彈出彈出STACK棧頂，然后把產(chǎn)生

21、式的右部符號(hào)串按反序一一推進(jìn)棧頂，然后把產(chǎn)生式的右部符號(hào)串按反序一一推進(jìn)STACK棧（若棧（若右部符號(hào)為右部符號(hào)為，則意味著不推什么東西進(jìn)棧）。，則意味著不推什么東西進(jìn)棧）。在把產(chǎn)生式的右部符號(hào)退進(jìn)棧的同時(shí)應(yīng)該做這個(gè)產(chǎn)生式對(duì)應(yīng)的語義在把產(chǎn)生式的右部符號(hào)退進(jìn)棧的同時(shí)應(yīng)該做這個(gè)產(chǎn)生式對(duì)應(yīng)的語義動(dòng)作（目前暫且不管）。動(dòng)作（目前暫且不管）。若若MX,a中存放著中存放著“出錯(cuò)標(biāo)志出錯(cuò)標(biāo)志”，則調(diào)用出錯(cuò)診斷程序，則調(diào)用出錯(cuò)診斷程序ERROR。 預(yù)測(cè)分析預(yù)測(cè)分析過程舉例過程舉例i+*()#EETEETEEE+TEEETTFTTFTTTT*FTTTFFiF(E)i1*i2+i3步驟步驟符號(hào)棧符號(hào)棧輸入串輸入串

22、所用產(chǎn)生式所用產(chǎn)生式0#Ei*i+i#1#ETi*i+i#ETE2#ETFi*i+i#TFTTFT3#ETii*i+i#Fi4#ET *i+i#5#ETF* *i+i#T*FT6#ETF i+i#7#ETi i+i#Fi8#ET +i#9#E +i#T10#ET+ +i#E+TE11#ET i#12#ETF i#TFT13#ETi i#Fi14#ET #15#E #T16# #E預(yù)測(cè)分析表的構(gòu)造預(yù)測(cè)分析表的構(gòu)造FIRSTFIRST集合和集合和FOLLOWFOLLOW集合的定義集合的定義FIRSTFIRST集合的構(gòu)造算法集合的構(gòu)造算法分析表的構(gòu)造分析表的構(gòu)造分析表的構(gòu)造分析表的構(gòu)造分析表的構(gòu)造分

23、析表的構(gòu)造FIRSTFIRST集合構(gòu)造的例子集合構(gòu)造的例子FIRST(E)=+,FIRST(T)=*,FIRST(F)=( , iFIRST(T)=( , iFIRST(E)=( , iETEE+TE | TFTT*FT | F(E) | iFOLLOWFOLLOW集合構(gòu)造的例子集合構(gòu)造的例子FOLLOW(E)=),#FOLLOW(E)=),#FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=*,+,),#ETEE+TE | TFTT*FT | F(E) | iFIRST(E)=+,FIRST(T)=*,FIRST(F)=( , iFIRST(T)=( , iFI

24、RST(E)=( , ii+*()#EETEETEEE+TEEETTFTTFTTTT*FTTTFFiF(E)LL(1)LL(1)文法文法LL(1)LL(1)分析中的錯(cuò)誤處理分析中的錯(cuò)誤處理 錯(cuò)誤的出現(xiàn)及基本做法錯(cuò)誤的出現(xiàn)及基本做法棧頂?shù)慕K結(jié)符與當(dāng)前的輸入符號(hào)不匹配。棧頂?shù)慕K結(jié)符與當(dāng)前的輸入符號(hào)不匹配。非終結(jié)符非終結(jié)符A處于棧頂，面臨的輸入符號(hào)為處于棧頂，面臨的輸入符號(hào)為a，但分析，但分析表表M中中MA,a為空。為空。 基本的做法就是跳過輸入串中的一些符號(hào)直至遇到基本的做法就是跳過輸入串中的一些符號(hào)直至遇到“同步符號(hào)同步符號(hào)”為止。這種做法的效果有賴于同步符為止。這種做法的效果有賴于同步符號(hào)集的

25、選擇。號(hào)集的選擇。 同步符號(hào)集的選擇同步符號(hào)集的選擇 把把FOLLOW(A)中的所有符號(hào)放入非終結(jié)符中的所有符號(hào)放入非終結(jié)符A的同步符號(hào)集。的同步符號(hào)集。如果我們跳讀一些輸入符號(hào)直至出現(xiàn)如果我們跳讀一些輸入符號(hào)直至出現(xiàn)FOLLOW(A)中的同步中的同步符號(hào)，把符號(hào)，把A從棧中彈出來，這樣就可能使分析繼續(xù)下去。從棧中彈出來，這樣就可能使分析繼續(xù)下去。對(duì)于非終結(jié)符對(duì)于非終結(jié)符A來說，只用來說，只用FOLLOW(A)作為它的同步符號(hào)作為它的同步符號(hào)集是不夠的。例如，如果分號(hào)作為語句的終結(jié)符，那么作為集是不夠的。例如，如果分號(hào)作為語句的終結(jié)符，那么作為語句開頭的關(guān)鍵字就可能不在產(chǎn)生表達(dá)式的非終結(jié)符的語句開頭的關(guān)鍵字就可能不在產(chǎn)生表達(dá)式的非終結(jié)符的FOLLOW集合中。這樣，在一個(gè)賦值語句后少一個(gè)分號(hào)就集合中。這樣，在一個(gè)賦值語句后少一個(gè)分號(hào)就可能導(dǎo)致作為下一個(gè)語句開頭的關(guān)鍵字被跳過可能導(dǎo)致作為下一個(gè)語句開頭的關(guān)鍵字被跳過如果把如果把FIRST(A)中的符號(hào)加入非終結(jié)符中的符號(hào)加入非終結(jié)符A的同步符號(hào)集，那的同步符號(hào)集，那么當(dāng)么當(dāng)FIRST(A)中的一個(gè)符號(hào)在輸入中出現(xiàn)時(shí)，可以根據(jù)中的一個(gè)符號(hào)在輸入中出現(xiàn)時(shí)，可以根據(jù)A恢恢復(fù)語法分析復(fù)語法分析同步符號(hào)集的選擇同步符號(hào)集的選擇 如果一個(gè)非終結(jié)符產(chǎn)生空串，那么推導(dǎo)如果一個(gè)非終結(jié)符產(chǎn)生空串，那么推導(dǎo)的產(chǎn)生式可以作為的產(chǎn)生式可以作