詞法分析與語(yǔ)法分析(二)?語(yǔ)法分析概要?上下文無(wú)關(guān)文法?自頂向下的語(yǔ)法分析算法?自底向上的語(yǔ)法分析算法?詞法分析和語(yǔ)法分析的實(shí)踐技術(shù)提綱描述分析?程序設(shè)計(jì)語(yǔ)言源程序的構(gòu)成：語(yǔ)法結(jié)構(gòu)引言O(shè)position=initial+rate*60<id,1>

<=,>

<id,2>

<+,>

<id,3>

<*,>

<number,4>一個(gè)實(shí)例語(yǔ)法分析?文法：一種用于描述程序設(shè)計(jì)語(yǔ)言語(yǔ)法的表示方法，能夠自然地描述程序設(shè)計(jì)語(yǔ)言構(gòu)造的層次化語(yǔ)法結(jié)構(gòu)O

文法給出了一個(gè)程序設(shè)計(jì)語(yǔ)言的精確易懂的語(yǔ)法規(guī)約O

可以基于文法構(gòu)造語(yǔ)法分析器，幫助確定源程序的語(yǔ)法結(jié)構(gòu)O

語(yǔ)法結(jié)構(gòu)有助于把源程序翻譯為正確的目標(biāo)代碼 O

文法的擴(kuò)展性，有助于迭代的語(yǔ)言演化引言?輸入：詞法分析器輸出的詞法單元序列?輸出：語(yǔ)法樹(shù)表示?語(yǔ)法分析器功能：O

驗(yàn)證輸入源程序的合法性，輸出良構(gòu)程序的語(yǔ)法結(jié)構(gòu)O

對(duì)于病構(gòu)的程序，能夠報(bào)告語(yǔ)法錯(cuò)誤，進(jìn)行錯(cuò)誤恢復(fù)?語(yǔ)法分析器的類型：

從左到右掃描字符

O

通用型

O

自頂向下：通常處理LL文法O

自底向上：通常處理LR文法語(yǔ)法分析器?類型檢查，語(yǔ)義分析，翻譯生成中間代碼等往往和語(yǔ)法分析過(guò)程交錯(cuò)完成，實(shí)踐中往往和語(yǔ)法分析放入一個(gè)模塊，圖上用“前端的其余部分”表示上述活動(dòng)語(yǔ)法分析器?錯(cuò)誤難以避免?編譯器需要具有處理錯(cuò)誤的能力?程序中可能存在不同層次的錯(cuò)誤O

詞法錯(cuò)誤O

語(yǔ)法錯(cuò)誤O

語(yǔ)義錯(cuò)誤O

邏輯錯(cuò)誤?語(yǔ)法錯(cuò)誤相對(duì)容易發(fā)現(xiàn)，語(yǔ)義和邏輯錯(cuò)誤較難精確的檢測(cè)到?語(yǔ)法分析器中錯(cuò)誤處理程序的設(shè)計(jì)目標(biāo)O

清晰準(zhǔn)確地報(bào)告出現(xiàn)錯(cuò)誤，并指出錯(cuò)誤的位置O

能從當(dāng)前錯(cuò)誤中恢復(fù)，以繼續(xù)檢測(cè)后面的錯(cuò)誤O

盡可能減少處理正確程序的開(kāi)銷語(yǔ)法錯(cuò)誤的處理?錯(cuò)誤恢復(fù)O

當(dāng)預(yù)測(cè)分析器報(bào)錯(cuò)時(shí)，表示輸入的串不是句子O

對(duì)于使用者而言，希望預(yù)測(cè)分析器能夠進(jìn)行恢復(fù)處理后繼續(xù)語(yǔ)法分析過(guò)程，以便在一次分析中找到更多的語(yǔ)法錯(cuò)誤O

但是有可能恢復(fù)得并不成功，之后找到的語(yǔ)法錯(cuò)誤有可能是假的O

進(jìn)行錯(cuò)誤恢復(fù)時(shí)可用的信息：棧里面的符號(hào)，待分析的符號(hào)?兩類錯(cuò)誤恢復(fù)方法O

恐慌模式O

短語(yǔ)層次的恢復(fù)預(yù)測(cè)分析中的錯(cuò)誤恢復(fù)?基本思想O

語(yǔ)法分析器忽略輸入中的一些符號(hào)，直到出現(xiàn)由設(shè)計(jì)者選定的某個(gè)同步詞法單元O

解釋?語(yǔ)法分析過(guò)程總是試圖在輸入的前綴中找到和某個(gè)非終結(jié)符號(hào)對(duì)應(yīng)的串；出現(xiàn)錯(cuò)誤表明現(xiàn)在已經(jīng)不可能找到這個(gè)非終結(jié)符號(hào)(程序結(jié)構(gòu))的串?如果編程錯(cuò)誤僅僅局限于這個(gè)程序結(jié)構(gòu)，那么我們可以考慮跳過(guò)這個(gè)程序結(jié)構(gòu)，假裝已經(jīng)找到了這個(gè)結(jié)構(gòu)；然后繼續(xù)進(jìn)行語(yǔ)法分析處理 O

同步詞法單元就是這個(gè)程序結(jié)構(gòu)結(jié)束的標(biāo)志恐慌模式?在預(yù)測(cè)語(yǔ)法分析表的空白條目中插入錯(cuò)誤處理例程的函數(shù)指針?例程可以改變、插入或刪除輸入中的符號(hào)；發(fā)出適當(dāng)?shù)腻e(cuò)誤消息短語(yǔ)層次的恢復(fù)LL類文法

(無(wú)左遞歸)

自頂向下分析LR文法類

自底向上分析代表性文法?語(yǔ)法分析概要?上下文無(wú)關(guān)文法?自頂向下的語(yǔ)法分析算法?自底向上的語(yǔ)法分析算法?詞法分析和語(yǔ)法分析的實(shí)踐技術(shù)提綱?上下文無(wú)關(guān)文法(ContextFreeGrammar,CFG)?上下文無(wú)關(guān)文法是一種能夠很好描述程序設(shè)計(jì)語(yǔ)言的表示方法stmt

t

if(expr)stmt

else

stmtexpr

t……stmt

t……上下文無(wú)關(guān)文法?一個(gè)CFG由以下幾個(gè)部分構(gòu)成O

終結(jié)符號(hào)?組成串的基本符號(hào)，與“詞法單元名字”同義O

非終結(jié)符號(hào)?語(yǔ)法變量，表示特定串的集合?給出了語(yǔ)言的層次結(jié)構(gòu)，這種層次結(jié)構(gòu)是語(yǔ)法分析和翻譯的關(guān)鍵O

一個(gè)開(kāi)始符號(hào)?某個(gè)特定的非終結(jié)符號(hào)，其表示的串集合是這個(gè)文法生成的語(yǔ)言O(shè)

一組產(chǎn)生式?描述將終結(jié)符號(hào)和非終結(jié)符號(hào)組合成串的方法?產(chǎn)生式左部(頭)是一個(gè)非終結(jié)符號(hào)?符號(hào)“→”?一個(gè)由零個(gè)或多個(gè)終結(jié)符號(hào)與非終結(jié)符號(hào)組成的產(chǎn)生式右部(體)上下文無(wú)關(guān)文法的定義?什么是上下文？O

在應(yīng)用一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)時(shí)，前后已經(jīng)推導(dǎo)出的部分結(jié)果就是上下文；O

上下文無(wú)關(guān)的意思的，只要文法的定義里有某個(gè)產(chǎn)生式，不管一個(gè)非終結(jié)符前后的串是什么，就可以應(yīng)用相應(yīng)的產(chǎn)生式進(jìn)行推導(dǎo)?文法的分類：O

上下文有關(guān)文法O

上下文無(wú)關(guān)文法上下文有關(guān)文法與上下文無(wú)關(guān)文法?一個(gè)簡(jiǎn)單的上下文無(wú)關(guān)文法例子O

Sent->S

V

OO

S->人|天O

V->吃|

下O

O->雨|雪

|飯|肉其中英文字母都是非終結(jié)符(SVO

分別表示主謂

賓)，漢字都是終結(jié)符。上下文有關(guān)文法與上下文無(wú)關(guān)文法?一個(gè)簡(jiǎn)單的上下文無(wú)關(guān)文法例子O

Sent->S

V

OO

S->人|天O

V->吃|

下O

O->雨|雪

|飯|肉上下文有關(guān)文法與上下文無(wú)關(guān)文法?這個(gè)文法可以生成多少個(gè)句子？?一個(gè)簡(jiǎn)單的上下文無(wú)關(guān)文法例子O

Sent->S

V

OO

S->人|天O

V->吃|

下O

O->雨|雪

|飯|肉?“天吃肉”。其(最左)推導(dǎo)過(guò)程為：Sent->SVO->天VO->天吃O(shè)->天吃肉上下文有關(guān)文法與上下文無(wú)關(guān)文法?一個(gè)簡(jiǎn)單的上下文有關(guān)文法例子O

Sent->S

V

OO

S->人|天O

人V->人吃O(shè)

天V->天下O

下O->下雨

|下雪O

吃O(shè)->吃飯

|吃肉其中英文字母都是非終結(jié)符(SVO

分別表示主謂

賓)，漢字都是終結(jié)符。上下文有關(guān)文法與上下文無(wú)關(guān)文法?一個(gè)簡(jiǎn)單的上下文有關(guān)文法例子O

Sent->S

V

OO

S->人|天O

人V->人吃O(shè)

天V->天下O

下O->下雨

|下雪O

吃O(shè)->吃飯

|吃肉上下文有關(guān)文法與上下文無(wú)關(guān)文法?這個(gè)文法可以生成多少個(gè)句子？?一個(gè)簡(jiǎn)單的上下文有關(guān)文法例子O

Sent->S

V

OO

S->人|天O

人V->人吃O(shè)

天V->天下O

下O->下雨

|下雪O

吃O(shè)->吃飯

|吃肉?Sent->SVO->人VO->人吃O(shè)->人吃飯其中第三步推導(dǎo)是這樣的：非終結(jié)符V

的上文是“人”，因此可以應(yīng)用“人V->人吃”這條產(chǎn)生式，得到“人VO->人吃O(shè)”。

第四步也類似。

上下文有關(guān)文法與上下文無(wú)關(guān)文法用于描述算術(shù)表達(dá)式的文法定義?終結(jié)符號(hào)：ab+3id…?非終結(jié)符號(hào):A

B

C…,

S,

stmt?文法符號(hào):X

Y…?終結(jié)符號(hào)串:u

v

w…?文法符號(hào)串:α

β

…?不同可選體:α

1

α2

α3

…?開(kāi)始符號(hào):

S符號(hào)表示約定?產(chǎn)生式又可稱為重寫(xiě)規(guī)則(Rewritingrule)?推導(dǎo)O

將待處理的串中的某個(gè)非終結(jié)符號(hào)替換為這個(gè)非終結(jié)符號(hào)的某個(gè)產(chǎn)生式的體O

從開(kāi)始符號(hào)出發(fā)，不斷進(jìn)行上面的替換，就可以得到文法的不同句型?推導(dǎo)的實(shí)例O

文法:E

→-E|E+E|E*E|(E)|idO從E到-(id)的推導(dǎo)序列：E=>-E=>-(E)=>-(id)推導(dǎo)?推導(dǎo)的一般性定義O

如果A→γ是一個(gè)產(chǎn)生式，那么αAβ

αγβ?經(jīng)過(guò)零步或者多步推導(dǎo)出：O

對(duì)于任何串α,ααO

如果αβ且βγ，那么αγ?經(jīng)過(guò)一步或者多步推導(dǎo)出：O

αβ且α不等于β等價(jià)于αβ?最左(右)推導(dǎo)推導(dǎo)?符號(hào)：?文法實(shí)例E

t

E+E|E*E|-E|(E)|

id

從上述文法推導(dǎo)出串–(id+id)推導(dǎo)的例子?句型(sentential

form)：O

如果Sα，那么α就是文法的一個(gè)句型O

可能既包含非終結(jié)符，又包含終結(jié)符號(hào)；可以是空串?句子(sentence)O

文法的句子就是不包含非終結(jié)符號(hào)的句型?語(yǔ)言O(shè)

文法G的語(yǔ)言就是G的句子的集合，記為L(zhǎng)(G)O

ω在L(G)中當(dāng)且僅當(dāng)ω是G的句子，即S

ω句型/句子/語(yǔ)言?從推導(dǎo)的角度看，語(yǔ)法分析的任務(wù)是：接受一個(gè)終結(jié)符號(hào)串作為輸入，找出從文法的開(kāi)始符號(hào)推導(dǎo)出這個(gè)串的方法E

t

E+E|E*E|-E|(E)|

id推導(dǎo)出串–(id+id*id)推導(dǎo)的問(wèn)題?推導(dǎo)中可能遇到的兩個(gè)問(wèn)題O

每一步替換哪個(gè)非終結(jié)符號(hào)？O

若以這個(gè)非終結(jié)符號(hào)為頭的產(chǎn)生式有多個(gè)，用哪個(gè)產(chǎn)生式的右部替換？E

t

E+E|E*E|-E|(E)|

id推導(dǎo)出串–(id+id*id)推導(dǎo)的問(wèn)題?通常使用兩種方式進(jìn)行推導(dǎo)O

最左推導(dǎo)：總是選擇每個(gè)句型的最左非終結(jié)符號(hào)。記作O

最右推導(dǎo)：總是選擇最右邊的非終結(jié)符號(hào)。記作?每個(gè)最左推導(dǎo)步驟可以寫(xiě)成

，,應(yīng)用產(chǎn)生式:?最左句型：S是文法G的識(shí)別符號(hào)，如果

G的最左句型非終結(jié)符號(hào)的替換順序?如果經(jīng)過(guò)最左推導(dǎo)得到，記作，則是?推導(dǎo)的圖形表示形式O

根結(jié)點(diǎn)的標(biāo)號(hào)是文法的開(kāi)始符號(hào)O

每個(gè)葉子結(jié)點(diǎn)的標(biāo)號(hào)是非終結(jié)符號(hào)、終結(jié)符號(hào)或εO

每個(gè)內(nèi)部節(jié)點(diǎn)的標(biāo)號(hào)是非終結(jié)符號(hào)O

每個(gè)內(nèi)部結(jié)點(diǎn)表示某個(gè)產(chǎn)生式的一次應(yīng)用?內(nèi)部結(jié)點(diǎn)的標(biāo)號(hào)為產(chǎn)生式頭，結(jié)點(diǎn)的子結(jié)點(diǎn)從左到右是產(chǎn)生式的體?有時(shí)允許樹(shù)的根不是開(kāi)始符號(hào)(對(duì)應(yīng)于某個(gè)短語(yǔ))?樹(shù)的葉子組成的序列是根的文法符號(hào)的句型?一棵分析樹(shù)可對(duì)應(yīng)多個(gè)推導(dǎo)序列，但是分析樹(shù)和最左(右)推導(dǎo)序列之間具有一一對(duì)應(yīng)關(guān)系語(yǔ)法分析樹(shù)?推導(dǎo)的圖形表示形式，樹(shù)上看不出來(lái)推導(dǎo)的順序?能夠反映串的語(yǔ)法層次結(jié)構(gòu)?語(yǔ)法分析樹(shù)O

內(nèi)部節(jié)點(diǎn)：對(duì)應(yīng)于一個(gè)非終結(jié)

符號(hào)O

子節(jié)點(diǎn)：對(duì)應(yīng)于其父節(jié)點(diǎn)為頭

的產(chǎn)生式體O

葉子節(jié)點(diǎn)：可以是終結(jié)符號(hào)或

非終結(jié)符號(hào)，從左到右排列可

以得到一個(gè)句型，稱為這棵樹(shù)

的結(jié)果語(yǔ)法分析樹(shù)?對(duì)于推導(dǎo)中的每個(gè)句型i

，我們都可以構(gòu)

造出一個(gè)結(jié)果為i

的語(yǔ)法樹(shù)O

構(gòu)造過(guò)程是對(duì)i的一次歸納過(guò)程O(píng)

在推導(dǎo)的第i步，對(duì)i

應(yīng)用規(guī)則推導(dǎo)和語(yǔ)法樹(shù)O

假設(shè)已經(jīng)構(gòu)造出?假設(shè)有推導(dǎo)序列：O

A=>α1=>α2

=>…=>

αn?算法：O

初始化：α1的分析樹(shù)是標(biāo)號(hào)為A的單個(gè)結(jié)點(diǎn)O

假設(shè)已經(jīng)構(gòu)造出αi-1=X1X2

…Xk的分析樹(shù)，且αi-1

到αi的推導(dǎo)是將Xj替換為β，那么在當(dāng)前分析樹(shù)中找出第j個(gè)非ε結(jié)點(diǎn)，向這個(gè)結(jié)點(diǎn)增加構(gòu)成β的子結(jié)點(diǎn)。(如果β=ε，則增加一個(gè)標(biāo)

號(hào)為ε的子結(jié)點(diǎn))從推導(dǎo)序列構(gòu)造分析樹(shù)推導(dǎo)與語(yǔ)法樹(shù)的例子?如果一個(gè)文法可以為一個(gè)句子生成多棵不同的語(yǔ)法分析樹(shù)，則該文法為二義性文法?通常情況下，我們需要無(wú)二義性的文法二義性文法?程序設(shè)計(jì)語(yǔ)言的文法通常都應(yīng)該是無(wú)二義性的O

否則就會(huì)導(dǎo)致一個(gè)程序有多種“正確”的解釋。O

比如文法：E

→-E|E+E|E*E|(E)|

id的句子a+b*c?但有些二義性的情況可以方便文法或語(yǔ)法分析器的設(shè)計(jì)O

需要消二義性規(guī)則來(lái)剔除不要的語(yǔ)法分析樹(shù)O

比如：先乘除后加減二義性?例子：stmt

→if

expr

then

stmt|if

expr

then

stmt

else

stmt|other?if

E1

then

if

E2

then

S1

else

S2

的兩棵語(yǔ)法樹(shù)?這個(gè)文法是可以被改造成等價(jià)的無(wú)二義性的文法文法的二義性?語(yǔ)言是由文法的開(kāi)始符號(hào)出發(fā)，能夠推導(dǎo)得到的所有句子的集合?文法G:

S

→

aS|a|b,

L(G)={ai(a|b),

i>=0}?文法G：S

→

aSb|abL(G)={anbn,

n>=1}?文法G：S

→

(S)S|εL(G)={所有具有對(duì)稱括號(hào)對(duì)的串}文法及其生成的語(yǔ)言?驗(yàn)證文法G生成語(yǔ)言L可以幫助我們了解文法可以生成什么樣的語(yǔ)言?基本步驟：O

首先證明L(G)L：G生成的每個(gè)串都在L中O

然后證明L

L(G)：L的每個(gè)串都能由G生成O

一般使用數(shù)學(xué)歸納法?證明L(G)L：按照推導(dǎo)序列長(zhǎng)度進(jìn)行數(shù)學(xué)歸納?證明L

L(G)：按照符號(hào)串的長(zhǎng)度來(lái)構(gòu)造推導(dǎo)序列?實(shí)例：文法G：S→(S)S|ε,L(G)={所有具有對(duì)稱括號(hào)對(duì)

的串}驗(yàn)證文法生成的語(yǔ)言?程序設(shè)計(jì)語(yǔ)言所需要的文法O

上下文無(wú)關(guān)文法足夠用來(lái)描述語(yǔ)法嗎？?標(biāo)識(shí)符必須先聲明后使用O

語(yǔ)法分析器能夠完全按照上下文無(wú)關(guān)文法來(lái)構(gòu)造嗎？?二義性、左遞歸的文法可能給語(yǔ)法分析器造成很大麻煩?可以怎么做？O

改造語(yǔ)法分析器，添加語(yǔ)義規(guī)則，使它可以做得更多O

改造上下文無(wú)關(guān)文法，消除二義性和左遞歸文法的設(shè)計(jì)?在進(jìn)行高效的語(yǔ)法分析之前，需要對(duì)文法做以下處理O

消除二義性?文法的二義性：文法可以為一個(gè)句子生成多顆不同的

樹(shù)O

消除左遞歸?左遞歸：文法中一個(gè)非終結(jié)符號(hào)A使得對(duì)某個(gè)串α，存在一個(gè)推導(dǎo)，則稱這個(gè)文法是左遞歸的O

提取左公因子很重要文法的設(shè)計(jì)?一些二義性文法可以被改成等價(jià)的無(wú)二義性的文法?例子：stmt

→if

expr

then

stmt|if

expr

then

stmt

else

stmt

|other?if

E1

then

if

E2

then

S1

else

S2

的兩棵語(yǔ)法樹(shù)消除文法的二義性?改寫(xiě)文法，基本思想:在一個(gè)then和一個(gè)else之間出現(xiàn)的語(yǔ)句必須是“已匹配的”。也就是說(shuō)then和else中間的語(yǔ)句不能以一個(gè)尚未匹配的then結(jié)尾?解決方案：引入新的非終結(jié)符號(hào)matched_stmt，用來(lái)區(qū)分是否是成對(duì)的then/else消除文法的二義性(續(xù))?通常并不是通過(guò)改變文法來(lái)消除二義性?二義性的消除方法沒(méi)有規(guī)律可循消除文法的二義性(續(xù))?左遞歸的定義O

文法中一個(gè)非終結(jié)符號(hào)A使得對(duì)某個(gè)串α，存在一個(gè)推導(dǎo)，則稱這個(gè)文法是左遞歸的?立即左遞歸O

如果存在A→

Aα,則稱為立即左遞歸?為什么要消除左遞歸？O

自頂向下的語(yǔ)法分析技術(shù)不能處理左遞歸的文法?立即左遞歸的消除實(shí)例：A

→

β

A’A’

→

αA’

|

ε消除左遞歸A

→

Aα

|

β首先對(duì)A產(chǎn)生式分組(所有αi不等于ε，βi不

以A開(kāi)頭)可以替換為?由A生成的串總是以某個(gè)βi開(kāi)頭，

然后跟上零個(gè)或者多個(gè)αi的重復(fù)?假設(shè)非終結(jié)符號(hào)A存在立即左遞歸的情形，假設(shè)以A為左部的規(guī)則有：立即左遞歸的消除?替換A

→

β1

A’|β2

A’|…|βn

A’A’→

α1

A’|α2

A’|…|αm

A’

|ε?A

→Aα1

|Aα2

|…|Aαm

|β1

|β2

|…|βn?分組消除立即左遞歸Aα1

|Aα2

|…|

Aαmβ1

|β2

|…|βnA

→|立即左遞歸消除示例?消除立即左遞歸的方法并不能消除因?yàn)閮刹交蚨嗖酵茖?dǎo)而產(chǎn)生的左遞歸?文法：S→Aa|b,A→Ac|Sd|ε?S=>Aa=>Sda?如何消除？消除多步左遞歸?輸入：沒(méi)有環(huán)Ai

Ai和A→ε?輸出：一個(gè)等價(jià)的無(wú)左遞歸的文法?算法原理：O

給非終結(jié)符號(hào)排序，A1

,A2,

…,AnO

如果只有Ai

Aj

(i<j)，則不會(huì)有左遞歸O

如果發(fā)現(xiàn)Ai

Aj

(i>j)，代入

Aj

的當(dāng)前產(chǎn)生式，若替換后有Ai

的直接左遞歸，再消除消除算法?輸入：沒(méi)有環(huán)和ε產(chǎn)生式的文法G?輸出：等價(jià)的無(wú)左遞歸的文法?步驟：將文法的非終結(jié)符號(hào)任意排序?yàn)锳1,A2,…,Anfor

i=1to

n

do

{forj=1toi-1do{將形如Ai

→Ajγ的產(chǎn)生式替換為Ai

→61γ|62γ|…|6kγ，

其中Aj

→61

|62

|…|6k是以Aj為左部的所有產(chǎn)生式；

}消除Ai

的立即左遞歸；

}

通用的左遞歸消除方法1.內(nèi)層循環(huán)的每一次迭代保證了Ai

的產(chǎn)生式的右部首符號(hào)都比Aj更加靠后2.

當(dāng)內(nèi)層循環(huán)結(jié)束時(shí)，Ai

的產(chǎn)生式的右部首符號(hào)不先于Ai3.消除立即左遞歸就保證了Ai

的產(chǎn)生式的右部首符號(hào)必然比Ai后。(不能有環(huán)和ε產(chǎn)生式)4.當(dāng)外層循環(huán)結(jié)束時(shí)，所有的產(chǎn)生式都是如此。使

用這些產(chǎn)生式當(dāng)然不會(huì)產(chǎn)生左遞歸的情形通用的左遞歸消除方法(續(xù))?S→Aa|b,A→Ac|Sd|ε?排序：SA?替換：O

i=1，沒(méi)有處理O

i=2,替換A→Sd

中的S

，得到A→Ac|Aad|bd|ε?消除立即左遞歸消除算法(示例)?在推導(dǎo)的時(shí)候，不知道該如何選擇(自頂向下算法會(huì)詳細(xì)描述)A

→

αA’A’→β1

|

β2A→αβ1

|

αβ2提取左公因子?輸入：文法G?輸出：一個(gè)等價(jià)的提取了左公因子的文法?方法：對(duì)于每個(gè)非終結(jié)符號(hào)A，找出它的兩個(gè)或多個(gè)可選項(xiàng)之間的最長(zhǎng)公共前綴α，且α≠

ε，那么將A所有的產(chǎn)生式A→αβ1

|αβ2

|...|αβn

|

γ替換為A→αA’|γA’→β1

|β2

|...|

βn提取左公因子算法對(duì)于S而言，最長(zhǎng)的前綴是i

E

t

S，因此：提取左公因子?抽象語(yǔ)言L1={wcw|w在(a|b)*中}?這個(gè)語(yǔ)言不是上下文無(wú)關(guān)的語(yǔ)言?它抽象地表示了C或者Java中“標(biāo)識(shí)符先聲明后使用”的規(guī)則O

說(shuō)明了C/Java這些語(yǔ)言不是上下文無(wú)關(guān)語(yǔ)言，不能使用上下文無(wú)關(guān)文法描述。O

通常用上下文無(wú)關(guān)文法描述其基本結(jié)構(gòu)，不能用文法描述的特性在語(yǔ)義分析階段完成。原因是上下文無(wú)關(guān)文法具有高效的處理算法。非上下文無(wú)關(guān)語(yǔ)言的構(gòu)造?語(yǔ)法分析概要?上下文無(wú)關(guān)文法?自頂向下的語(yǔ)法分析算法?自底向上的語(yǔ)法分析算法?詞法分析和語(yǔ)法分析的實(shí)踐技術(shù)提綱?自頂向下分析可以被看作是為輸入串構(gòu)造語(yǔ)法分析樹(shù)的問(wèn)題，也可以看作一個(gè)尋找輸入串的最左推導(dǎo)的過(guò)程?問(wèn)題O

在推導(dǎo)的每一步，對(duì)非終結(jié)符號(hào)A，應(yīng)用哪個(gè)產(chǎn)生式，以可能產(chǎn)生于輸入串相匹配的終結(jié)符號(hào)串自頂向下分析技術(shù)id+id*id的自頂向下分析?問(wèn)題：對(duì)于非終結(jié)符號(hào)A，選擇哪一個(gè)產(chǎn)生式?一種通用的遞歸下降分析框架O

由一組過(guò)程組成，每個(gè)非終結(jié)符號(hào)對(duì)應(yīng)一個(gè)過(guò)程O(píng)

程序的執(zhí)行從開(kāi)始符號(hào)對(duì)應(yīng)的過(guò)程開(kāi)始O

每個(gè)過(guò)程的功能是：選擇一個(gè)產(chǎn)生式體，掃描相應(yīng)的句子。若遇到非終結(jié)符號(hào)，調(diào)用該符號(hào)對(duì)應(yīng)的過(guò)程自頂向下語(yǔ)法分析遞歸下降分析過(guò)程示例O

S

→

cAdO

A

→

ab

|

a?輸入串w

=

c

a

d?文法：?輸入串w

=

c

a

d?文法：遞歸下降分析過(guò)程示例O

S

→

cAdO

A

→

ab

|

a?輸入串w

=

c

a

d?文法：遞歸下降分析過(guò)程示例O

S

→

cAdO

A

→

ab

|

a匹配成功！遞歸下降分析過(guò)程示例O

S

→

cAdO

A

→

ab

|

a?輸入串w

=

c

a

d?文法：?可能需要回溯，或者說(shuō)，可能需要重復(fù)掃描輸入?“在回到A時(shí)，我們必須把輸入指針重新設(shè)置到位置2，即我們第一次嘗試展開(kāi)A時(shí)該指針指向的位置。這意味著A的過(guò)程必須將輸入指針存放在一個(gè)局部變量中?！?如果文法中存在左遞歸……?回溯(窮試?)顯然是笨辦法遞歸下降過(guò)程示例(續(xù))?試圖從開(kāi)始符號(hào)推導(dǎo)出輸入符號(hào)串?以開(kāi)始符號(hào)作為初始的當(dāng)前句型?每次為最左邊的非終結(jié)符號(hào)選擇適當(dāng)?shù)漠a(chǎn)生式O

通過(guò)查看下一個(gè)輸入符號(hào)來(lái)選擇這個(gè)產(chǎn)生式O

有多個(gè)可能的產(chǎn)生式時(shí)預(yù)測(cè)分析法無(wú)能為力?比如文法：E

→+EE

|-EE|id；輸入為+id-id

id?當(dāng)兩個(gè)產(chǎn)生式具有相同的前綴時(shí)無(wú)法預(yù)測(cè)O文法：stmt

→if

expr

then

stmt

else

stmt|if

expr

then

stmtO輸入：if

a

then…O新文法：stmt

→ifexprthen

stmt

elsePartO

elsePart

→else

stmt

|ε?需要提取公因子預(yù)測(cè)分析法簡(jiǎn)介?一種確定性的、無(wú)回溯的分析技術(shù)?在每一步選擇正確的產(chǎn)生式

例1：文法G(S)：S→

pAS→qBA→cAdA→a

輸入串

W=pccadd消除二義性

消除左遞歸

提取左公因子預(yù)測(cè)分析技術(shù)

例2：文法G(S)為：S

→Ap

S

→

Bq

A

→a∣cA

B→

b∣dB

輸入W=ccap預(yù)測(cè)分析技術(shù)(續(xù))?通過(guò)在輸入中向前看固定多個(gè)符號(hào)來(lái)選擇正確的產(chǎn)生式?通常情況下，我們只需要向前看一個(gè)符號(hào)O

遞歸下降分析一般只適合于每個(gè)子表達(dá)式的第一個(gè)終結(jié)符能夠?yàn)楫a(chǎn)生式選擇提供足夠信息的那些文法?給出兩個(gè)與文法相關(guān)的兩個(gè)函數(shù)O

FIRSTO

FOLLOW?基于上述兩個(gè)函數(shù)，可以根據(jù)下一個(gè)輸入符號(hào)來(lái)選擇應(yīng)用哪個(gè)產(chǎn)生式預(yù)測(cè)分析技術(shù)(續(xù))?在自頂向下的分析技術(shù)中，通常使用向前看幾個(gè)符號(hào)來(lái)唯一地確定產(chǎn)生式(這里假定只看一個(gè)符

號(hào))?當(dāng)前句型是xAβ，而輸入是xa…。那么選擇產(chǎn)生式A→α的必要條件是下列之一：O

Αε，且β以a開(kāi)頭；也就是說(shuō)在某個(gè)句型中a跟在A之后；O

Α

a…；O

如果按照這兩個(gè)條件選擇時(shí)能夠保證唯一性，那么我們就可以避免回溯。?因此，我們定義FIRST和FOLLOWFIRST和FOLLOW(1)很重要?FIRST(α)：O

可以從α推導(dǎo)得到的串

的首符號(hào)的集合；O

如果αε，那么ε也在FIRST(α)中；?

FOLLOW(A)：O

可能在某些句型中緊跟

在A右邊的終結(jié)符號(hào)的

集合。FIRST和FOLLOW(2)?定義：可從α推導(dǎo)得到的串的首符號(hào)的集合，其中α是任意的文法符號(hào)串。如果α

ε，那么ε也在FIRST(α)中?FIRST函數(shù)的意義O

如果兩個(gè)A產(chǎn)生式A

→

α

|

β，其中First(α)和

First(β)是不相交的集合。下一個(gè)輸入符號(hào)是a

，

若a∈First(α)，則選擇A

→

α

，若a∈First(β)，則選擇A

→

βO

用于預(yù)測(cè)產(chǎn)生式的選擇FIRST(α)?對(duì)于文法符號(hào)X的FIRST(X)，通過(guò)不斷應(yīng)用下

列規(guī)則，直到?jīng)]有新的終結(jié)符號(hào)或者ε可以加入到任何FIRST集合為止O

如果X是終結(jié)符號(hào)，那么FIRST(X)={X}O

如果X是非終結(jié)符號(hào)，且有規(guī)則X

t

a…,那么將a添加到FIRST(X)中;如果X

t

c，那么c也在FIRST(X)中O

對(duì)于規(guī)則X

t

Y1Y2

…Yn

，把FIRST(Y1)中的非c符號(hào)添加到FIRST(X)中。如果c在FIRST(Y1)中，把FIRST(Y2)中

的非c符號(hào)添加到FIRST(X)中…；如果c在FIRST(Yn)中，

把c添加到FIRST(X)中First的計(jì)算?對(duì)于文法符號(hào)串X1X2

…Xn

的First集合O

向First(X1X2

…Xn)加入First(X1)中所有的非ε符號(hào)。O

如果ε在First(X1)中，再加入First(X2)中的所有非ε符號(hào)。如果ε在First(X1)和First(X2)中，再加入First(X3)中的所有非ε符號(hào)。依次類推。O

如果對(duì)所有的i

(1到n)，ε都在First(Xi)中，則

ε加入First(X1X2

…Xn)中。First的計(jì)算(續(xù))?

First(F)=First(T)=First(E)={(,id}?

First(E’)={+,ε}?

First(T’)={*,ε}?First(TE’)=First(T)={(,id}?First(+TE’)={+}?……First的計(jì)算示例

First(S)

={a,

b,

c}

First(A)

=

{a,

ε

}

First(B)

=

First(C)

=

{c}

First(D)

=

ecmqsy8O

S

→

AB

|

CDO

A

→aD

|

εO

C

→cDO

B

→bCO

D

→d?文法G[S],

輸入bcd一個(gè)實(shí)例D

→d?對(duì)于非終結(jié)符號(hào)A

，F(xiàn)OLLOW(A)定義為可能在某些句型中緊跟在A右邊的終結(jié)符號(hào)的集合O

例如SαAaβ，終結(jié)符號(hào)a∈Follow(A)?如果A是某些句型的最右符號(hào)，那么$∈Follow(A)。$是

特殊的輸入串“結(jié)束標(biāo)記”?FOLLOW函數(shù)的意義：O

如果A→α，當(dāng)α→c或αc時(shí)，F(xiàn)OLLOW(A)可以幫助我們做出選擇恰當(dāng)?shù)漠a(chǎn)生式O

例如：如果A→α,b屬于FOLLOW(A)，如果α

c，則若當(dāng)前輸入符號(hào)是b，可以選擇A→α，因?yàn)锳最終到達(dá)了c，而且后面跟著b文法G[S],

輸入bcdS

→

AB|CD

A

→aD|

εC

→cDB

→bCFOLLOW函數(shù)?計(jì)算各個(gè)非終結(jié)符號(hào)A的FOLLOW(A)集合，

不斷應(yīng)用下列規(guī)則，直到?jīng)]有新的終結(jié)符號(hào)可以被加入到任意FOLLOW集合中O

將$放入FOLLOW(S)，S是開(kāi)始符號(hào)，而$是輸入串的結(jié)束標(biāo)記O

如果存在產(chǎn)生式A

→

αBβ，那么First(β)中除ε之外的所有符號(hào)都在Follow(B)中O

如果存在一個(gè)產(chǎn)生式A

→

αB，或存在產(chǎn)生式A

→

αBβ且First(β)包含ε，那么Follow(A)中的所有符號(hào)都在Follow(B)中FOLLOW計(jì)算?將$放入FOLLOW(S)

，S是開(kāi)始符號(hào)，而$是輸入串的結(jié)束標(biāo)記?如果存在產(chǎn)生式A

t

αBβ，那么First(β)中除ε之外的所有符號(hào)都在

Follow(B)中

?如果存在一個(gè)產(chǎn)生式A

t

αB，或存在產(chǎn)生式A

t

αBβ且First(β)包含ε

，

那么Follow(A)中的所有符號(hào)都在Follow(B)中

FOLLOW(E)={)

，

$}

FOLLOW(E’)={)

，

$}

FOLLOW(T)={+

，)

，$}

FOLLOW(T’)={+

，)

，$}

FOLLOW(F)=(*

，+

，)

，$)←

FIRST(

)

)

U

{S}←

FOLLOW(E)←

FIRST(E’)

U

FOLLOW(E’)

←

FOLLOW(T)

←

FIRST(T’)

U

FOLLOW(T)

文法E

t

T

E’T’

t

*F

T’

|

cFollow的計(jì)算示例E’

t

+T

E’

|

cF

t

(

E

)

|

iT

t

F

T’?有如下文法：O

E

→

id

XO

X

→

ε

|

(A)

|

[E]O

A

→

EYO

Y

→

ε

|

;A?給出各個(gè)非終結(jié)符號(hào)的First集和Follow集課堂練習(xí)。合?提取左公因子?求First和Follow集合LL(1)文法

的預(yù)測(cè)分析思考：為什么?消除左遞歸?消除二義性改造文法?LL(1)文法，第一個(gè)L表示自左向右掃描，

第二個(gè)L指產(chǎn)生最左推導(dǎo)，而1則表示向前

看一個(gè)輸入符號(hào)?LL(1)文法可以利用不回溯的確定性的預(yù)測(cè)分析技術(shù)，因?yàn)橹恍枰獧z查當(dāng)前輸入符號(hào)就可以為一個(gè)非終結(jié)符號(hào)選擇正確的產(chǎn)生式LL(1)文法(1)?定義:對(duì)于文法的任意兩個(gè)不同的產(chǎn)生式A→α|βO

不存在終結(jié)符號(hào)a使得α和β都可以推導(dǎo)出以a開(kāi)頭的串O

α和β最多只有一個(gè)可以推導(dǎo)出空串O

如果β可以推導(dǎo)出空串，那么α不能推導(dǎo)出以FOLLOW

中任何終結(jié)符號(hào)開(kāi)頭的串；?等價(jià)于：O

FIRST(α)FIRST(β)=Φ;(條件一、二)O

如果ε∈FIRST(β)，那么FIRST(α)

FOLLOW(A)=Φ；反之亦然。(條件三)LL(1)文法(2)?思考：對(duì)于一個(gè)LL(1)文法，我們期望從A推導(dǎo)出以終結(jié)符號(hào)a開(kāi)頭的符號(hào)串O

我們?nèi)绾芜x擇產(chǎn)生式？O

有多個(gè)選擇嗎？LL(1)文法(3)?對(duì)于LL(1)文法，可以在自頂向下分析過(guò)程中，根據(jù)當(dāng)前輸入符號(hào)來(lái)確定使用的產(chǎn)生式?例如：O

產(chǎn)生式：stmt

t

if(exp)stmt

else

stmt|while(exp)stmt

|aO

輸入：if(exp)while(exp)

a

else

aO

首先選擇產(chǎn)生式stmt

t

if(exp)stmt

else

stmt

得到句型if

(exp)stmt

else

stmtO

然后發(fā)現(xiàn)要把句型中的第一個(gè)stmt展開(kāi)，選擇產(chǎn)生式stmt

t

while(exp)stmt，得到句型if(exp)while(exp)stmt

else

stmt

。O

然后再展開(kāi)第一個(gè)stmt，得到if(exp)while(exp)

a

else

stmtO

…LL(1)文法(4)?LL(1)文法==>預(yù)測(cè)分析表?將First和Follow集合中的信息放入一個(gè)預(yù)測(cè)分析表M[A,a]，該預(yù)測(cè)表告訴我們當(dāng)非終結(jié)符號(hào)為A

，當(dāng)前輸入符號(hào)為a時(shí)，要選擇哪條產(chǎn)生式?預(yù)測(cè)分析表的構(gòu)造O

若當(dāng)前輸入符號(hào)a在First(α)中，選擇產(chǎn)生式A→αO

若αc，如果a在Follow(A)中，選擇產(chǎn)生式A→αO

如果當(dāng)前符號(hào)a是$，且$在Follow(A)中，則選擇產(chǎn)生式A→α

LL(1)文法的預(yù)測(cè)分析技術(shù)?輸入：文法G?輸出：預(yù)測(cè)分析表M?方法：對(duì)于文法G的每個(gè)產(chǎn)生式A

→α，進(jìn)行如下處理O

對(duì)于First(α)中的每個(gè)終結(jié)符號(hào)a，將A

→α加入到M[A,a]O

如果c在First(α)中，那么對(duì)于Follow(A)中的每個(gè)終結(jié)符號(hào)b，將A

→α加入到M[A,b]中O

如果c在First(α)中，且$在Follow(A)中，將A

→

α加入到M[A,$]中?完成上述操作后，若M[A,a]中沒(méi)有產(chǎn)生式，填為Error預(yù)測(cè)分析表構(gòu)造?文法：O

E→TE’E’→+TE’|εO

T→FT’T’→*FT’|εO

F→(E)|id?FIRST集：O

F

：{(,id}；E,T

：{(,id}；?FOLLOW集：O

E

：{$,)};E’：{$,)};這個(gè)例子恰巧使得每個(gè)產(chǎn)生式的右部的

第一個(gè)符號(hào)的FIRST集合就等于產(chǎn)生式

右部的FIRST集合。但是在一般情況下

不總是這樣的。E’：{+,ε};T’：{*,ε}T,T’：{+,),$};F

：{+,*,),$}預(yù)測(cè)分析表的例子?對(duì)于任何文法G，都可以構(gòu)造預(yù)測(cè)分析表?對(duì)于LL(1)文法，預(yù)測(cè)表中每個(gè)條目都唯一地指定了一個(gè)產(chǎn)生式，或者標(biāo)明Error預(yù)測(cè)分析方法?對(duì)于某些文法，表中可能會(huì)有一些多重定義的條目，比如左遞歸或二義性文法。–FIRST(eS)={e}，使得S’→eS在M[S’,e]中；

–FOLLOW(S’)={$,e}使得S’→

ε也在M[S’,e]中二義性文法的預(yù)測(cè)分析表?設(shè)計(jì)文法(保證描述能力，且適用于自頂向下分析)O

消除二義性O(shè)

消除左遞歸O

提取左公因子?自頂向下分析O

遞歸下降分析(通用的可能需要回溯)O

預(yù)測(cè)分析?LL(1)文法及其預(yù)測(cè)分析文法和自頂向下分析?在自頂向下分析的過(guò)程中，我們總是O

匹配掉句型中左邊的所有終結(jié)符號(hào)O

對(duì)于最左邊的非終結(jié)符號(hào)，我們選擇適當(dāng)?shù)漠a(chǎn)生式展開(kāi)O

匹配成功的終結(jié)符號(hào)不會(huì)再被考慮，因此我們只需要記住句型的余下部分，以及尚未匹配的輸入終結(jié)符號(hào)串O

由于展開(kāi)的動(dòng)作總是發(fā)生在余下部分的左端，我們可以用棧來(lái)存放這些符號(hào)非遞歸的預(yù)測(cè)分析(1)?分析處理過(guò)程O(píng)

初始化時(shí)，棧中僅包含開(kāi)始符號(hào)O

如果棧頂元素是終結(jié)符號(hào)，那么進(jìn)行匹配O

如果棧頂元素是非終結(jié)符號(hào)?

使用預(yù)測(cè)分析表來(lái)選擇適當(dāng)?shù)漠a(chǎn)生式?

在棧頂用產(chǎn)生式右部替換產(chǎn)生式左部?對(duì)所有文法的預(yù)測(cè)分析都可以共用同樣的驅(qū)動(dòng)程序非遞歸的預(yù)測(cè)分析(2)O

在任何時(shí)刻，棧頂符號(hào)X與當(dāng)前輸入符號(hào)a決定了控制程序所應(yīng)執(zhí)行的分析動(dòng)作。四種可能的動(dòng)作?如果X=a=$，則分析成功結(jié)束?如果X=a≠$，則從棧中退去X，并把輸入指針推進(jìn)到指向下一個(gè)輸入符號(hào)?如果X是一個(gè)非終結(jié)符號(hào)，且分析表A的元素A[X][a]=“X

→X1X2

…Xk”，則把棧頂?shù)腦替換為XkX2

…X1

(反向下推入棧，使得X1在棧頂)?除上述情況外的其它情況，調(diào)用出錯(cuò)程序?文法符號(hào)棧?輸入緩沖區(qū)?控制程序非遞歸的預(yù)測(cè)分析技術(shù)?性質(zhì)1：如果棧中的符號(hào)序列為α，而w是已經(jīng)被讀入的部分輸入，

w’是尚未處理的輸入；那么O

S推導(dǎo)出wαO

我們?cè)噲D從α推導(dǎo)出余下的輸入終結(jié)符號(hào)串w’?預(yù)測(cè)分析程序使用M[X,a]

來(lái)擴(kuò)展X，將此產(chǎn)生式的右部按倒序壓入棧中?請(qǐng)注意：這樣的操作使得分析過(guò)程中性質(zhì)1得到

保持。分析表驅(qū)動(dòng)的預(yù)測(cè)分析器

w

w’

?

輸入：一個(gè)串w，文法G的預(yù)測(cè)分析表M。?

輸出：如果w在L(G)中，輸出w的一個(gè)最左推導(dǎo)；否則報(bào)錯(cuò)。?方法：初始化輸入緩沖區(qū)為w$,棧頂是G的開(kāi)始符號(hào)S

，下面是$

。表驅(qū)動(dòng)的非遞歸的預(yù)測(cè)語(yǔ)法分析分析表驅(qū)動(dòng)預(yù)測(cè)分析的例子已經(jīng)匹配部分加上棧中符號(hào)必然是一個(gè)最左句型?文法4.28，輸入：id+id*id;?文法：S→aSa|aa

生成了所有由a組成

的長(zhǎng)度為偶數(shù)的串?？梢詾檫@個(gè)文法設(shè)計(jì)一個(gè)帶回溯的遞歸下降分析器。如果我們選擇先使用產(chǎn)生式S

→aa展開(kāi)，那么只能識(shí)別到串a(chǎn)a。因此，任何合理的遞歸下降分析器將首先嘗試S→aSa

。?說(shuō)明這個(gè)遞歸下降分析器不能識(shí)別aaaaaa。習(xí)題21S4

→aaaaaaaa$匹配成功，返回調(diào)用上一層；22S3

→aSaaaaaaa$匹配成功，返回調(diào)用上一層；23S2

→aSaaaaaaa$匹配失敗，換產(chǎn)生式；24S2

→aaaaaaaa$匹配成功；25S2

→aaaaaaaa$匹配成功，返回調(diào)用上一層；26S1

→aSaaaaaaa$匹配成功；27隱藏符號(hào)$aaaaaa$匹配失敗，換產(chǎn)生式；28S1

→aaaaaaaa$匹配成功；29S1

→aaaaaaaa$匹配成功；30隱藏符號(hào)$aaaaaa$匹配失敗，程序結(jié)束，識(shí)別失敗；若要正確識(shí)別6個(gè)a，則應(yīng)依次使用產(chǎn)生式S1

→aSa，S2

→aSa以及S3

→aa。但是

根據(jù)分析過(guò)程發(fā)現(xiàn)，第22步時(shí)使用產(chǎn)生式S3

→aSa

，a成功匹配后返回調(diào)用上一

層。當(dāng)?shù)?3步發(fā)現(xiàn)S2

→aSa中a不能匹配時(shí)，實(shí)際上是S3

→aSa這個(gè)產(chǎn)生式用錯(cuò)了，但是程序此時(shí)不會(huì)嘗試(也無(wú)法嘗試)使用S3

→aa，只會(huì)嘗試使用S2

→aa。

因此導(dǎo)致最后錯(cuò)誤發(fā)生。

?S→

aSa|aaSa

S

aa

aa

S

aa

S

a21S4

→aaaaaaaa$匹配成功，返回調(diào)用上一層；22S3

→aSaaaaaaa$匹配成功，返回調(diào)用上一層；23S2

→aSaaaaaaa$匹配失敗，換產(chǎn)生式；24S2

→aaaaaaaa$匹配成功；25S2

→aaaaaaaa$匹配成功，返回調(diào)用上一層；26S1

→aSaaaaaaa$匹配成功；27隱藏符號(hào)$aaaaaa$匹配失敗，換產(chǎn)生式；28S1

→aaaaaaaa$匹配成功；29S1

→aaaaaaaa$匹配成功；30隱藏符號(hào)$aaaaaa$匹配失敗，程序結(jié)束，識(shí)別失??；層。當(dāng)?shù)?3步發(fā)現(xiàn)S2

→aSa中a不能匹配時(shí)，實(shí)際上是S3

→aSa這個(gè)產(chǎn)生式用錯(cuò)關(guān)鍵的一步

了，但是程序此時(shí)不會(huì)嘗試(也無(wú)法嘗回

了

試)使用S3

→aa，只會(huì)嘗試使用S2

→aa。

因此導(dǎo)致最后錯(cuò)誤發(fā)生。

式畢生完產(chǎn)行他執(zhí)其數(shù)試函嘗，續(xù)功繼成去配不匹若要正確識(shí)別6個(gè)a，則應(yīng)依次使用產(chǎn)生式S1

→aSa，S2

→aSa以及S3

→aa。但是

根據(jù)分析過(guò)程發(fā)現(xiàn)，第22步時(shí)使用產(chǎn)生式S3

→aSa

，a成功匹配后返回調(diào)用上一?S→

aSa|aaSa

S

aa

S

aa

S

aa

S

a

若要正確識(shí)別6個(gè)a，則應(yīng)依次使用產(chǎn)生a

S

a

式S1

→aSa

，S2

→aSa以及S3

→aa。但是根據(jù)分析過(guò)程發(fā)現(xiàn)，第22步時(shí)使用產(chǎn)生式S3

→aSa

，a成功匹配后返回調(diào)用上一

層。當(dāng)?shù)?3步發(fā)現(xiàn)S2

→aSa中a不能匹配時(shí)，實(shí)際上是S3

→aSa這個(gè)產(chǎn)生式用錯(cuò)了，但是程序此時(shí)不會(huì)嘗試(也無(wú)法嘗試)使用S3

→aa，只會(huì)嘗試使用S2

→aa。

因此導(dǎo)致最后錯(cuò)誤發(fā)生。

21S4

→aaaaaaaa$匹配成功，返回調(diào)用上一層；22S3

→aSaaaaaaa$匹配成功，返回調(diào)用上一層；23S2

→aSaaaaaaa$匹配失敗，換產(chǎn)生式；24S2

→aaaaaaaa$匹配成功；25S2

→aaaaaaaa$匹配成功，返回調(diào)用上一層；26S1

→aSaaaaaaa$匹配成功；27隱藏符號(hào)$aaaaaa$匹配失敗，換產(chǎn)生式；28S1

→aaaaaaaa$匹配成功；29S1

→aaaaaaaa$匹配成功；30隱藏符號(hào)$aaaaaa$匹配失敗，程序結(jié)束，識(shí)別失??；?S→

aSa|aaSa

S

a

若要正確識(shí)別6個(gè)a，則應(yīng)依次使用產(chǎn)生a

a

式S1

→aSa，S2

→aSa以及S3

→aa。但是根據(jù)分析過(guò)程發(fā)現(xiàn)，第22步時(shí)使用產(chǎn)生式S3

→aSa

，a成功匹配后返回調(diào)用上一

層。當(dāng)?shù)?3步發(fā)現(xiàn)S2

→aSa中a不能匹配時(shí)，實(shí)際上是S3

→aSa這個(gè)產(chǎn)生式用錯(cuò)了，但是程序此時(shí)不會(huì)嘗試(也無(wú)法嘗試)使用S3

→aa，只會(huì)嘗試使用S2

→aa。

因此導(dǎo)致最后錯(cuò)誤發(fā)生。

21S4

→aaaaaaaa$匹配成功，返回調(diào)用上一層；22S3

→aSaaaaaaa$匹配成功，返回調(diào)用上一層；23S2

→aSaaaaaaa$匹配失敗，換產(chǎn)生式；24S2

→aaaaaaaa$匹配成功；25S2

→aaaaaaaa$匹配成功，返回調(diào)用上一層；26S1

→aSaaaaaaa$匹配成功；27隱藏符號(hào)$aaaaaa$匹配失敗，換產(chǎn)生式；28S1

→aaaaaaaa$匹配成功；29S1

→aaaaaaaa$匹配成功；30隱藏符號(hào)$aaaaaa$匹配失敗，程序結(jié)束，識(shí)別失??；?S→

aSa|aaSa

S

a

若要正確識(shí)別6個(gè)a，則應(yīng)依次使用產(chǎn)生a

a

式S1

→aSa，S2

→aSa以及S3

→aa。但是根據(jù)分析過(guò)程發(fā)現(xiàn)，第22步時(shí)使用產(chǎn)生式S3

→aSa

，a成功匹配后返回調(diào)用上一

層。當(dāng)?shù)?3步發(fā)現(xiàn)S2

→aSa中a不能匹配時(shí)，實(shí)際上是S3

→aSa這個(gè)產(chǎn)生式用錯(cuò)了，但是程序此時(shí)不會(huì)嘗試(也無(wú)法嘗試)使用S3

→aa，只會(huì)嘗試使用S2

→aa。

因此導(dǎo)致最后錯(cuò)誤發(fā)生。

21S4

→aaaaaaaa$匹配成功，返回調(diào)用上一層；22S3

→aSaaaaaaa$匹配成功，返回調(diào)用上一層；23S2

→aSaaaaaaa$匹配失敗，換產(chǎn)生式；24S2

→aaaaaaaa$匹配成功；25S2

→aaaaaaaa$匹配成功，返回調(diào)用上一層；26S1

→aSaaaaaaa$匹配成功；27隱藏符號(hào)$aaaaaa$匹配失敗，換產(chǎn)生式；28S1

→aaaaaaaa$匹配成功；29S1

→aaaaaaaa$匹配成功；30隱藏符號(hào)$aaaaaa$匹配失敗，程序結(jié)束，識(shí)別失?。?S→

aSa|aaSa

S

a

若要正確識(shí)別6個(gè)a，則應(yīng)依次使用產(chǎn)生式S1

→aSa，S2

→aSa以及S3

→aa。但是

根據(jù)分析過(guò)程發(fā)現(xiàn)，第22步時(shí)使用產(chǎn)生式S3

→aSa

，a成功匹配后返回調(diào)用上一

層。當(dāng)?shù)?3步發(fā)現(xiàn)S2

→aSa中a不能匹配時(shí)，實(shí)際上是S3

→aSa這個(gè)產(chǎn)生式用錯(cuò)了，但是程序此時(shí)不會(huì)嘗試(也無(wú)法嘗試)使用S3

→aa，只會(huì)嘗試使用S2

→aa。

因此導(dǎo)致最后錯(cuò)誤發(fā)生。

21S4

→aaaaaaaa$匹配成功，返回調(diào)用上一層；22S3

→aSaaaaaaa$匹配成功，返回調(diào)用上一層；23S2

→aSaaaaaaa$匹配失敗，換產(chǎn)生式；24S2

→aaaaaaaa$匹配成功；25S2

→aaaaaaaa$匹配成功，返回調(diào)用上一層；26S1

→aSaaaaaaa$匹配成功；27隱藏符號(hào)$aaaaaa$匹配失敗，換產(chǎn)生式；28S1

→aaaaaaaa$匹配成功；29S1

→aaaaaaaa$匹配成功；30隱藏符號(hào)$aaaaaa$匹配失敗，程序結(jié)束，識(shí)別失?。?S→

aSa|aaS?語(yǔ)法分析概要?上下文無(wú)關(guān)文法?自頂向下的語(yǔ)法分析算法?自底向上的語(yǔ)法分析算法?詞法分析和語(yǔ)法分析的實(shí)踐技術(shù)提綱?為一個(gè)輸入串構(gòu)造語(yǔ)法分析樹(shù)的過(guò)程；?從葉子(輸入串中的終結(jié)符號(hào)，將位于分析樹(shù)的底端)開(kāi)始，向上到達(dá)根結(jié)點(diǎn)?重要的自底向上語(yǔ)法分析的通用框架O

移入-歸約?LR：最大的可以構(gòu)造出移入-歸約語(yǔ)法分析器的語(yǔ)法類自底向上的語(yǔ)法分析?Bottom-UpParsing

自底向上語(yǔ)法分析概述-歸約?Bottom-up

parsing–將一個(gè)串w歸約為文

法符號(hào)的過(guò)程?在每一步的歸約中，一個(gè)與某產(chǎn)生式體相匹配的特定子串被替換為該產(chǎn)生式頭部的非終結(jié)符號(hào)，一次歸約實(shí)質(zhì)上是一個(gè)推導(dǎo)的反向操作自底向上語(yǔ)法分析概述-歸約?id*id的歸約過(guò)程O(píng)id*id，F(xiàn)*id，T*id，T*F

，T

，E?對(duì)于句型T*id，有兩個(gè)子串