語法分析自上而下分析

語法分析自上而下分析第1頁，課件共113頁，創(chuàng)作于2023年2月課程安排內(nèi)容講授課時(shí)實(shí)驗(yàn)課時(shí)第一章引論2第二章高級(jí)程序語言及其語法描述2第三章詞法分析實(shí)驗(yàn)一詞法分析器（第6、7、8、9周）108第四章語法分析----自上而下分析8第五章語法分析----自下而上分析實(shí)驗(yàn)二語法分析器（第13、14、15、16周）88第六章屬性文法和語法制導(dǎo)翻譯8第七章語義分析及中間代碼產(chǎn)生8第八章優(yōu)化2合計(jì)4816第2頁，課件共113頁，創(chuàng)作于2023年2月實(shí)驗(yàn)時(shí)間：實(shí)驗(yàn)一詞法分析：第6、7、8、9周實(shí)驗(yàn)二語法分析：第13、14、15、16周實(shí)驗(yàn)地點(diǎn)：計(jì)算機(jī)系實(shí)驗(yàn)中心（5教910、911）指導(dǎo)教師：楊健、張謙實(shí)驗(yàn)安排楊健謙箱：bigjordon@126.com地點(diǎn)：五教8層802圖像處理研究室第3頁，課件共113頁，創(chuàng)作于2023年2月數(shù)字媒體制作實(shí)驗(yàn)室910計(jì)11-12

軟件開發(fā)實(shí)驗(yàn)室911計(jì)11-34

第6、7、8、9周，都是周二1,2節(jié)實(shí)驗(yàn)一詞法分析器（第6、7、8、9周）第4頁，課件共113頁，創(chuàng)作于2023年2月第四章語法分析-自上而下分析4.1語法分析器的功能4.2自上而下分析面臨的問題4.3LL(1)分析法4.4遞歸下降分析程序構(gòu)造4.5預(yù)測(cè)分析程序第5頁，課件共113頁，創(chuàng)作于2023年2月第四章語法分析-自上而下分析了解：語法分析器的功能。熟悉：預(yù)測(cè)分析程序、遞歸下降分析程序的設(shè)計(jì)方法。掌握：LL(1)分析法的條件，消除左遞歸的算法，預(yù)測(cè)分析表的構(gòu)造。第6頁，課件共113頁，創(chuàng)作于2023年2月第四章語法分析-自上而下分析作業(yè)：

4.1，4.2第7頁，課件共113頁，創(chuàng)作于2023年2月4.1考慮下面文法G1:

S→a∣∧∣(T) T→T,S∣S（1）消去G1的左遞歸。然后對(duì)每個(gè)非終結(jié)符，寫出不帶回溯的遞歸子程序。（2）經(jīng)改寫后的文法是否是LL(1)的？給出它的預(yù)測(cè)分析表。第四章語法分析-自上而下分析第8頁，課件共113頁，創(chuàng)作于2023年2月4.2對(duì)下面的文法G： E→TE E→+E∣ε T→FT T→T∣ε F→PF F→*F∣ε P→(E)∣a∣b∣∧（1）計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST和FOLLOW。（2）證明這個(gè)文法是LL(1)的。（3）構(gòu)造它的預(yù)測(cè)分析表。（4）構(gòu)造它的遞歸下降分析程序。第9頁，課件共113頁，創(chuàng)作于2023年2月第三章詞法分析實(shí)驗(yàn)一詞法分析器

每次實(shí)驗(yàn)結(jié)束都必須寫出實(shí)驗(yàn)報(bào)告，報(bào)告內(nèi)容包括：實(shí)驗(yàn)題目、實(shí)驗(yàn)?zāi)康暮鸵?，?shí)驗(yàn)的實(shí)現(xiàn)（包括主要設(shè)計(jì)思想、實(shí)現(xiàn)算法、主要技術(shù)問題的處理方法，及實(shí)驗(yàn)結(jié)果），結(jié)論分析。實(shí)驗(yàn)二語法分析器第10頁，課件共113頁，創(chuàng)作于2023年2月實(shí)驗(yàn)二

語法分析器構(gòu)造一、目的和要求借助于詞法分析程序提供的分析結(jié)果，編寫一個(gè)算符優(yōu)先語法分析程序，程序能進(jìn)行語法結(jié)構(gòu)分析和錯(cuò)誤檢查并產(chǎn)生相應(yīng)的歸約信息。同時(shí)給出出錯(cuò)信息和錯(cuò)誤類型，從而加深對(duì)語法分析的理解。二、實(shí)驗(yàn)內(nèi)容給定文法G和算符優(yōu)先分析法，構(gòu)造其算符優(yōu)先分析程序。文法G：語句→賦值語句｜條件語句｜轉(zhuǎn)移語句｜帶標(biāo)號(hào)的賦

值語句帶標(biāo)號(hào)的賦值語句→<標(biāo)號(hào)><賦值語句>賦值語句→變量=算術(shù)表達(dá)式條件語句→

IF<布爾表達(dá)式>THEN語句｜IF

<布爾表達(dá)式>THEN語句ELSE語句第11頁，課件共113頁，創(chuàng)作于2023年2月實(shí)驗(yàn)二

語法分析器構(gòu)造轉(zhuǎn)移語句→GOTO標(biāo)號(hào)變量→標(biāo)識(shí)符標(biāo)識(shí)符→字母｜<標(biāo)識(shí)符><數(shù)字>字母→A｜B｜…｜Z｜a｜b｜…｜z數(shù)字→0｜1｜…｜9算術(shù)表達(dá)式→項(xiàng)｜算術(shù)表達(dá)式+項(xiàng)｜算術(shù)表達(dá)式-項(xiàng)項(xiàng)→因子｜項(xiàng)*因子｜項(xiàng)/因子｜因子↑項(xiàng)因子→變量｜常數(shù)｜(表達(dá)式)布爾表達(dá)式→<算術(shù)表達(dá)式><關(guān)系符><算術(shù)表達(dá)式>關(guān)系符→>｜<｜>=｜<=｜=｜<>標(biāo)號(hào)→常數(shù)常數(shù)→數(shù)字｜<常數(shù)><數(shù)字>第12頁，課件共113頁，創(chuàng)作于2023年2月實(shí)驗(yàn)二

語法分析器構(gòu)造三、說明和提示1.本實(shí)驗(yàn)的優(yōu)先表可以手工先設(shè)計(jì)好。2.本實(shí)驗(yàn)要求中提出的“產(chǎn)生相應(yīng)的歸約信息”意指在語法分析的過程中，一旦產(chǎn)生歸約，在程序上產(chǎn)生并最終輸出歸約產(chǎn)生式序號(hào)。3.出錯(cuò)類型的產(chǎn)生可預(yù)先對(duì)應(yīng)優(yōu)先表中出錯(cuò)欄列表說明其出錯(cuò)類型，并分別編序，當(dāng)分析中產(chǎn)生錯(cuò)誤時(shí)以字符串輸出相應(yīng)表中錯(cuò)誤信息。4.算法采用一個(gè)符號(hào)棧的數(shù)據(jù)結(jié)構(gòu)，既用它存放終結(jié)符，也用它存放非終結(jié)符。第13頁，課件共113頁，創(chuàng)作于2023年2月第四章語法分析-自上而下分析4.1語法分析器的功能4.2自上而下分析面臨的問題4.3LL(1)分析法4.4遞歸下降分析程序構(gòu)造4.5預(yù)測(cè)分析程序第14頁，課件共113頁，創(chuàng)作于2023年2月中間代碼單詞符號(hào)語法單位中間代碼目標(biāo)代碼詞法分析器語法分析器語義分析與中間代碼產(chǎn)生器優(yōu)化器源程序表格管理出錯(cuò)處理目標(biāo)代碼生成器編譯程序總框第15頁，課件共113頁，創(chuàng)作于2023年2月本章主要介紹語法分析的處理要進(jìn)行語法分析，必須對(duì)語言的語法結(jié)構(gòu)進(jìn)行描述。采用正規(guī)式和有限自動(dòng)機(jī)可以描述和識(shí)別語言的單詞符號(hào)；用上下文無關(guān)文法來描述語法規(guī)則。第四章語法分析-自上而下分析第16頁，課件共113頁，創(chuàng)作于2023年2月形式化定義：一個(gè)上下文無關(guān)文法是一個(gè)四元式（VT,VN,S,Ｐ）VT是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符號(hào)；VN是一個(gè)非空有限集，它的每個(gè)元素稱為非終結(jié)符號(hào)，VT∩VN=ф；S是一個(gè)非終結(jié)符號(hào)，稱為開始符號(hào)；S∈VN。Ｐ是一個(gè)產(chǎn)生式集合（有限），每個(gè)產(chǎn)生式的形式是P→а。其中，P∈VN，а∈(VT∪VN)＊。開始符號(hào)S必須至少在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。P→а1|а2|…|аn。其中，аi稱為是P的一個(gè)候選式?！x作“定義”，直豎讀為“或”,它是元語言符號(hào)。2.3.1上下文無關(guān)文法第17頁，課件共113頁，創(chuàng)作于2023年2月2.3.1上下文無關(guān)文法定義：稱A直接推出，即A

僅當(dāng)A是一個(gè)產(chǎn)生式，且，(VT

VN)*

。如果1

2

n，則我們稱這個(gè)序列是從1到n的一個(gè)推導(dǎo)。若存在一個(gè)從1到n的推導(dǎo)，則稱1可以推導(dǎo)出n

。對(duì)文法G(E)：Ei|E+E|E*E|(E)E(E)(E+E)(i+E)(i+i)第18頁，課件共113頁，創(chuàng)作于2023年2月

用表示：從1出發(fā)，經(jīng)過0步或若干步，可以推出n。

所以：即或定義：假定G是一個(gè)文法，S是開始符號(hào)。如果，則稱是一個(gè)句型。僅含終結(jié)符號(hào)的句型是一個(gè)句子。文法G所產(chǎn)生的句子的全體是一個(gè)語言，將它記為L(zhǎng)(G)。通常，用

表示：從1出發(fā)，經(jīng)過一步或若干步，可以推出n。第19頁，課件共113頁，創(chuàng)作于2023年2月例：(i*i+i)是文法G(E)：Ei|E+E|E*E|(E)的一個(gè)句子。證明：

E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)

E，(E)，(E+E)，(E*E+E)，…，(i*i+i)是句型。2.3.1上下文無關(guān)文法第20頁，課件共113頁，創(chuàng)作于2023年2月第四章語法分析-自上而下分析4.1語法分析器的功能4.2自上而下分析面臨的問題4.3LL(1)分析法4.4遞歸下降分析程序構(gòu)造4.5預(yù)測(cè)分析程序第21頁，課件共113頁，創(chuàng)作于2023年2月4.1語法分析器的功能語法分析的任務(wù)是分析一個(gè)文法的句子結(jié)構(gòu)。語法分析器的功能：按照文法的產(chǎn)生式，識(shí)別輸入符號(hào)串是否為一個(gè)句子。策略：自上而下分析法，自下而上分析法。

兩種方法反映了兩種語法樹的構(gòu)造過程。第22頁，課件共113頁，創(chuàng)作于2023年2月源程序單詞符號(hào)取下一單詞符號(hào)...語法分析樹詞法分析器語法分析器符號(hào)表編譯程序后續(xù)部分圖4.1語法分析器在編譯程序中的地位4.1語法分析器的功能第23頁，課件共113頁，創(chuàng)作于2023年2月語法分析的方法-自上而下分析法(Top-down)基本思想：它從文法的開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找“匹配”的推導(dǎo)。從樹根到葉子來建立語法樹。遞歸下降分析法：對(duì)每個(gè)非終結(jié)符號(hào)構(gòu)造一個(gè)相應(yīng)的子程序，每個(gè)子程序識(shí)別一定的語法單位，通過子程序間的信息反饋和聯(lián)合作用實(shí)現(xiàn)對(duì)輸入串的識(shí)別。預(yù)測(cè)分析程序優(yōu)點(diǎn)：直觀、簡(jiǎn)單和宜于手工實(shí)現(xiàn)。第24頁，課件共113頁，創(chuàng)作于2023年2月語法分析的方法-自下而上分析法(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á)式。LR分析法：規(guī)范歸約第25頁，課件共113頁，創(chuàng)作于2023年2月

G(E)：Ei|E+E|E-E|E*E|E/E|(E)

給出i*i+i的語法樹。i*i+i E*i+i E*E+i E+i E+E Ei+*EiiEEEE第26頁，課件共113頁，創(chuàng)作于2023年2月第四章語法分析-自上而下分析4.1語法分析器的功能4.2自上而下分析面臨的問題4.3LL(1)分析法4.4遞歸下降分析程序構(gòu)造4.5預(yù)測(cè)分析程序第27頁，課件共113頁，創(chuàng)作于2023年2月4.2自上而下分析面臨的問題自上而下就是從文法的開始符號(hào)出發(fā)，向下推導(dǎo)，推出句子。自上而下分析的主旨：對(duì)任何輸入串，試圖用一切可能的辦法，從文法開始符號(hào)(根結(jié)點(diǎn))出發(fā)，自上而下地為輸入串建立一棵語法樹?；蛘哒f，為輸入串尋找一個(gè)最左推導(dǎo)。第28頁，課件共113頁，創(chuàng)作于2023年2月例文法G(E):

EiEE+EEE*EE(E)對(duì)句子(i+i)最左推導(dǎo)E(E)(E+E)(i+E)(i+i)4.2自上而下分析面臨的問題第29頁，課件共113頁，創(chuàng)作于2023年2月例假定有文法G(S):(1)S→xAy(2)A→**|* 分析輸入串x*y序號(hào)指示器IP指向語法樹最左推導(dǎo)說明

x*yS根結(jié)S,當(dāng)前符x①x*y③x得匹配,移動(dòng)IPSx

A

ySxAy用S→xAy展開S欲用xAy匹配輸入串SxAy

②x*y第30頁，課件共113頁，創(chuàng)作于2023年2月序號(hào)IP指向語法樹最左推導(dǎo)說明Sx*yx

A

y試用A→**展開ASxAyx**y④**x*y⑤*得匹配,移動(dòng)IP,但y得不到匹配Sx

A

y*

*用A→**展開失敗,回溯,回到第③步⑥Sx

A

ySxAyx*y第31頁，課件共113頁，創(chuàng)作于2023年2月

序號(hào)IP指向語法樹最左推導(dǎo)說明x*ySx

A

y試用A→*展開ASxAyx*y⑦*

x*y⑧*得匹配,移動(dòng)IPSx

A

y*

A完成匹配,y得匹配,移動(dòng)IP,輸入串匹配成功,結(jié)束⑨Sx

A

ySxAyx*yx*y*

第32頁，課件共113頁，創(chuàng)作于2023年2月存在回溯的原因文法中非終結(jié)符A的產(chǎn)生式右部稱為A的候選式，如果有多個(gè)候選式左端第一個(gè)符號(hào)相同，則語法分析程序無法根據(jù)當(dāng)前輸入符號(hào)選擇產(chǎn)生式，只能試探。例假定有文法G(S):(1)S→xAy(2)A→**|* 分析輸入串x*y第33頁，課件共113頁，創(chuàng)作于2023年2月自上而下分析方法的步驟：（帶回溯的試探過程）⑴遇非終結(jié)符,

就試圖用某個(gè)候選式展開,期望此候選能匹配輸入串,若不能匹配,則要回溯。⑵遇終結(jié)符，就進(jìn)行匹配，然后移動(dòng)輸入串指針I(yè)P指向下一個(gè)符號(hào)?；厮菔且豁?xiàng)復(fù)雜而費(fèi)時(shí)的工作，須廢棄已做的許多工作，恢復(fù)到前面的某一情況，效率很低。4.2自上而下分析面臨的問題第34頁，課件共113頁，創(chuàng)作于2023年2月當(dāng)某個(gè)非終結(jié)符有多個(gè)產(chǎn)生式候選時(shí)，可能帶來如下問題:1.分析過程中，當(dāng)一個(gè)非終結(jié)符用某一個(gè)候選匹配成功時(shí)，這種匹配可能是暫時(shí)的。出錯(cuò)時(shí)，不得不“回溯”。2.文法左遞歸問題。一個(gè)文法是含有左遞歸的，如果存在非終結(jié)符P含有左遞歸的文法將使自上而下的分析陷入無限循環(huán)。4.2自上而下分析面臨的問題第35頁，課件共113頁，創(chuàng)作于2023年2月第四章語法分析-自上而下分析4.1語法分析器的功能4.2自上而下分析面臨的問題4.3LL(1)分析法4.4遞歸下降分析程序構(gòu)造4.5預(yù)測(cè)分析程序第36頁，課件共113頁，創(chuàng)作于2023年2月4.3LL(1)分析法構(gòu)造不帶回溯的自上而下分析算法要消除文法的左遞歸性克服回溯第37頁，課件共113頁，創(chuàng)作于2023年2月4.3LL(1)分析法4.3.1左遞歸的消除4.3.2消除回溯、提左因子4.3.3LL(1)分析條件第38頁，課件共113頁，創(chuàng)作于2023年2月4.3.1左遞歸的消除直接消除見諸于產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符P的產(chǎn)生式為

P→P|其中不以P開頭，不等于?？梢园裀的產(chǎn)生式等價(jià)地改寫為如下的非直接左遞歸形式：

P→P

P→P|左遞歸變右遞歸第39頁，課件共113頁，創(chuàng)作于2023年2月例文法G(E):E→E＋T|TT→T*F|FF→(E)|i經(jīng)消去直接左遞歸后變成：E→TEE→+TE|

T→FTT→*FT|F→(E)|i

第40頁，課件共113頁，創(chuàng)作于2023年2月一般而言，假定P的產(chǎn)生式是 P→P1|P2|…|Pm

|1|2|…|n其中，每個(gè)都不等于，每個(gè)都不以P開頭。那么，消除P的直接左遞歸性就是將產(chǎn)生式改寫成：P→1P|2P|…|nP P→1P|2P|…|mP|左遞歸變右遞歸4.3.1左遞歸的消除第41頁，課件共113頁，創(chuàng)作于2023年2月例如文法G(S):S→Qc|cQ→Rb|bR→Sa|a 雖沒有直接左遞歸，但S、Q、R都是左遞歸的SQcRbcSabc一個(gè)文法消除左遞歸的條件：不含以為右部的產(chǎn)生式不含回路。4.3.1左遞歸的消除第42頁，課件共113頁，創(chuàng)作于2023年2月消除左遞歸的算法:（1）把文法G的所有非終結(jié)符按任一種順序排列成P1，P2，…，Pn；按此順序執(zhí)行；（2）FORi:=1TOnDOBEGIN

FORj:=1TOi-1DO把形如Pi→Pj的產(chǎn)生式改寫成Pi→1|2|…|k;(其中Pj→1|2|…|k是Pj的產(chǎn)生式)消除Pi產(chǎn)生式的直接左遞歸性

END（3）化簡(jiǎn)由（2）所得的文法。去除那些從開始符號(hào)出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生式。為非終結(jié)符編號(hào)，再采用代入法將間接左遞歸變?yōu)橹苯幼筮f歸，消除直接左遞歸。第43頁，課件共113頁，創(chuàng)作于2023年2月例考慮文法G(S)S→Qc|cQ→Rb|bR→Sa|a令它的非終結(jié)符的排序?yàn)镽、Q、S。

對(duì)于R，不存在直接左遞歸。

把R代入到Q的有關(guān)候選后，把Q的產(chǎn)生式變?yōu)镼→Sab|ab|b

現(xiàn)在的Q不含直接左遞歸，把它代入到S的有關(guān)候選后，S變成S→Sabc|abc|bc|c

消除S的直接左遞歸后：

S→abcS|bcS|cS

S→abcS|

Q→Sab|ab|b

R→Sa|aQ和R的規(guī)則已是多余的，化簡(jiǎn)為： S→abcS|bcS|cS S→abcS|

文法(4.4)第44頁，課件共113頁，創(chuàng)作于2023年2月注意，由于對(duì)非終結(jié)符排序的不同，最后所得的文法在形式上可能不一樣。但不難證明，它們都是等價(jià)的。例如，若對(duì)文法非終結(jié)符排序選為S、Q、R，那么，最后所得的無左遞歸文法是： S→Qc|c Q→Rb|b

文法(4.5) R→bcaR|caR|aR

R→bcaR|

文法(4.4)和(4.5)的等價(jià)性是顯然的。消除左遞歸前后，文法的開始符號(hào)不變。4.3.1左遞歸的消除第45頁，課件共113頁，創(chuàng)作于2023年2月例考慮文法G(S)S→Qc|cQ→Rb|bR→Sa|a令它的非終結(jié)符的排序?yàn)镾、Q、R。

對(duì)于S和Q都不存在直接左遞歸。

把S代入到R的有關(guān)候選后，把R的產(chǎn)生式變?yōu)镽→Qca|ca|a

把Q代入到R的有關(guān)候選后，R變成R→Rbca|bca|ca|a

消除R的直接左遞歸后：

R→bcaR|caR|aR

R→bcaR|

最后所得的無左遞歸文法是：

S→Qc|c

Q→Rb|b

文法(4.5)

R→bcaR|caR|aR

R→bcaR|

第46頁，課件共113頁，創(chuàng)作于2023年2月4.3LL(1)分析法4.3.1左遞歸的消除4.3.2消除回溯、提左因子4.3.3LL(1)分析條件第47頁，課件共113頁，創(chuàng)作于2023年2月回溯問題什么是回溯?分析工作要部分地或全部地退回去重做叫回溯。造成回溯的條件：

文法中，對(duì)于某個(gè)非終結(jié)符號(hào)的產(chǎn)生式右部有多個(gè)選擇，并根據(jù)所面臨的輸入符號(hào)不能準(zhǔn)確地確定所要的選擇時(shí)，就可能出現(xiàn)回溯?；厮輲淼膯栴}：嚴(yán)重的低效率，只有在理論上的意義而無實(shí)際意義。例假定有文法G(S):(1)S→xAy(2)A→**|* 分析輸入串x*y第48頁，課件共113頁，創(chuàng)作于2023年2月4.3.2消除回溯、提左因子為了消除回溯就必須保證：對(duì)文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時(shí)，能夠根據(jù)它所面臨的輸入符號(hào)準(zhǔn)確地指派它的一個(gè)候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無疑的。A→1|2|…|nSa….IPA......第49頁，課件共113頁，創(chuàng)作于2023年2月令G是一個(gè)不含左遞歸的文法，對(duì)G的所有非終結(jié)符的每個(gè)候選定義它的終結(jié)首符集FIRST()為：

特別是，若，則規(guī)定FIRST()。若非終結(jié)符A的所有候選終結(jié)首符集兩兩不相交，即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的。FIRST()是的所有可能推導(dǎo)的開頭終結(jié)符或可能的ε。第50頁，課件共113頁，創(chuàng)作于2023年2月提取公共左因子:

假定關(guān)于A的產(chǎn)生式是A→1|2|…|n|1|2|…|m (其中，每個(gè)

不以開頭)那么，可以把產(chǎn)生式改寫成A→A|1|2|…|mA→1|2|…|n經(jīng)過反復(fù)提取左因子，就能夠把每個(gè)非終結(jié)符(包括新引進(jìn)者)的所有候選首符集變成為兩兩不相交。第51頁，課件共113頁，創(chuàng)作于2023年2月52文法

SiBtSeS|iBtS|aBb

提取公共左因子改寫文法。

提取公共左因子，將文法改寫為

SiBtSS|aS

eS|εB

b4.3.2消除回溯、提左因子第52頁，課件共113頁，創(chuàng)作于2023年2月一個(gè)文法不含左遞歸，且所有候選式首符集兩兩不相交，但帶ε產(chǎn)生式，在自上而下分析又帶來新問題：這就引出自動(dòng)匹配問題。當(dāng)非終結(jié)符A面臨輸入符號(hào)a，且a不屬于A的任意候選首符集，但A的某個(gè)候選首符集包含時(shí)，就一定可以使A自動(dòng)匹配。這是一種錯(cuò)誤。4.3.2消除回溯、提左因子第53頁，課件共113頁，創(chuàng)作于2023年2月4.3LL(1)分析法4.3.1左遞歸的消除4.3.2消除回溯、提左因子4.3.3LL(1)分析條件文法是LL(1)的第一個(gè)L從左到右掃描輸入串第二個(gè)L生成的是最左推導(dǎo)

1向前看一個(gè)輸入符號(hào)（lookahead)第54頁，課件共113頁，創(chuàng)作于2023年2月E→TEE→+TE|T→FTT→*FT|F→(E)|ii+i4.3.3LL(1)分析條件例文法G(E):E→E＋T|TT→T*F|FF→(E)|i經(jīng)消去直接左遞歸后變成：E→TEE→+TE|

T→FTT→*FT|F→(E)|i

第55頁，課件共113頁，創(chuàng)作于2023年2月i+iIPEG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第56頁，課件共113頁，創(chuàng)作于2023年2月i+iIPETEG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第57頁，課件共113頁，創(chuàng)作于2023年2月i+iIPETEFTG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第58頁，課件共113頁，創(chuàng)作于2023年2月i+iIPETEFTiG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第59頁，課件共113頁，創(chuàng)作于2023年2月i+iIPETEFTiG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第60頁，課件共113頁，創(chuàng)作于2023年2月i+iIPETEFTiG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第61頁，課件共113頁，創(chuàng)作于2023年2月i+iIPETEFTi+TEG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第62頁，課件共113頁，創(chuàng)作于2023年2月i+iIPETEFTi+TEG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第63頁，課件共113頁，創(chuàng)作于2023年2月i+iIPETEFTi+TEFTG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第64頁，課件共113頁，創(chuàng)作于2023年2月i+iIPETEFTi+TEFTiG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第65頁，課件共113頁，創(chuàng)作于2023年2月i+iIPETEFTi+TEFTiG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第66頁，課件共113頁，創(chuàng)作于2023年2月i+iIPETEFTi+TEFTiG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第67頁，課件共113頁，創(chuàng)作于2023年2月i+iIPETEFT’i+TEFTiG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|iS…T+…第68頁，課件共113頁，創(chuàng)作于2023年2月假定S是文法G的開始符號(hào)，對(duì)于G的任何非終結(jié)符A，我們定義

若

,則規(guī)定＃FOLLOW(A)4.3.3LL(1)分析條件即FOLLOW(A)是所有句型中緊跟在A之后的終結(jié)符或#。第69頁，課件共113頁，創(chuàng)作于2023年2月構(gòu)造不帶回溯的自上而下分析的文法條件1.文法不含左遞歸。2.對(duì)于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若A→1|2|…|n則FIRST(i)∩FIRST(j)＝ (ij)3.對(duì)文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)候選首符集包含，當(dāng)ε∈FIRST(αj)時(shí)，則FOLLOW(A)∩FIRST(αi)=Φ如果一個(gè)文法G滿足以上條件，則稱該文法G為L(zhǎng)L(1)文法。 第70頁，課件共113頁，創(chuàng)作于2023年2月對(duì)于一個(gè)滿足上述條件的文法，可以對(duì)其輸入串進(jìn)行有效的無回溯的自上而下分析。假設(shè)要用非終結(jié)符A進(jìn)行匹配，面臨的輸入符號(hào)為a，A的所有產(chǎn)生式為A→1|2|…|n1.若aFIRST(i)，則指派i執(zhí)行匹配任務(wù)；2.若a不屬于任何一個(gè)候選首符集，則：(1)若屬于某個(gè)FIRST(i)且aFOLLOW(A)，則讓A與自動(dòng)匹配。(2)否則，a的出現(xiàn)是一種語法錯(cuò)誤。第71頁，課件共113頁，創(chuàng)作于2023年2月第四章語法分析-自上而下分析4.1語法分析器的功能4.2自上而下分析面臨的問題4.3LL(1)分析法4.4遞歸下降分析程序構(gòu)造4.5預(yù)測(cè)分析程序第72頁，課件共113頁，創(chuàng)作于2023年2月4.4遞歸下降分析程序構(gòu)造構(gòu)造不帶回溯的自上而下分析程序要消除文法的左遞歸性克服回溯第73頁，課件共113頁，創(chuàng)作于2023年2月當(dāng)一個(gè)文法滿足LL(1)條件時(shí)，我們就可以為它構(gòu)造一個(gè)不帶回溯的自上而下分析程序，這個(gè)分析程序是由一組遞歸過程組成的，每個(gè)過程對(duì)應(yīng)文法的一個(gè)非終結(jié)符。這樣的一個(gè)分析程序稱為遞歸下降分析器。4.4遞歸下降分析程序構(gòu)造如果用某種高級(jí)語言寫出所有遞歸過程，那就可以用這個(gè)語言的編譯系統(tǒng)來產(chǎn)生整個(gè)的語法分析程序。幾個(gè)全局過程和變量：ADVANCE，讀入IP指向的輸入符號(hào)到SYM中，把輸入串指示器IP指向下一個(gè)輸入符號(hào)。SYM，IP當(dāng)前所指的輸入符號(hào)。ERROR，出錯(cuò)處理程序。第74頁，課件共113頁，創(chuàng)作于2023年2月例:文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i 非終結(jié)符號(hào)的分析子程序的功能是：用產(chǎn)生式右部符號(hào)串來匹配輸入串。每個(gè)非終結(jié)符都有對(duì)應(yīng)的遞歸過程，在分析過程中，當(dāng)需要從某個(gè)非終結(jié)符出發(fā)進(jìn)行展開(推導(dǎo))時(shí)，就調(diào)用這個(gè)非終結(jié)符對(duì)應(yīng)的子程序。第75頁，課件共113頁，創(chuàng)作于2023年2月假定在開始工作前，輸入串指示器IP指向第一個(gè)輸入符號(hào)。當(dāng)每個(gè)子程序工作完畢之后，IP總是指向下一個(gè)未處理的符號(hào)。E→+TE|E

只有兩個(gè)候選，第一個(gè)候選的開頭終結(jié)符為+，第二個(gè)候選為。當(dāng)E

面臨輸入符號(hào)+時(shí)，就令第一個(gè)候選進(jìn)入工作，當(dāng)面臨任何其它輸入符號(hào)時(shí)，E就自動(dòng)認(rèn)為獲得了匹配（這時(shí)，更精確的做法是判斷該輸入符號(hào)是否屬于FOLLOW(E)）。4.4遞歸下降分析程序構(gòu)造第76頁，課件共113頁，創(chuàng)作于2023年2月//將ε看成與任一符號(hào)匹配例:文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i對(duì)應(yīng)的遞歸下降子程序?yàn)?

PROCEDUREE；BEGIN T；EEND；

PROCEDUREE；IFSYM=‘+’THEN BEGIN ADVANCE；T；E

END；第77頁，課件共113頁，創(chuàng)作于2023年2月PROCEDURET；BEGIN F；TEND；PROCEDURET；IFSYM=‘*’THENBEGINADVANCE；F；TEND；例:文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i對(duì)應(yīng)的遞歸下降子程序?yàn)?

第78頁，課件共113頁，創(chuàng)作于2023年2月例:文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i對(duì)應(yīng)的遞歸下降子程序?yàn)?

PROCEDUREF；IFSYM=‘i’THEN

ADVANCEELSE

IFSYM=‘(’THEN

BEGIN

ADVANCE;

E；

IFSYM=‘)’THEN

ADVANCE ELSEERROR

END ELSEERROR;第79頁，課件共113頁，創(chuàng)作于2023年2月第四章語法分析-自上而下分析4.1語法分析器的功能4.2自上而下分析面臨的問題4.3LL(1)分析法4.4遞歸下降分析程序構(gòu)造4.5預(yù)測(cè)分析程序第80頁，課件共113頁，創(chuàng)作于2023年2月4.5預(yù)測(cè)分析程序4.5.1預(yù)測(cè)分析程序工作過程4.5.2預(yù)測(cè)分析表的構(gòu)造本節(jié)要重點(diǎn)掌握:1.對(duì)給定文法構(gòu)造符號(hào)串的FIRST集合和非終結(jié)符的FOLLOW集合。

2.構(gòu)造預(yù)測(cè)分析表的方法。第81頁，課件共113頁，創(chuàng)作于2023年2月4.5.1預(yù)測(cè)分析程序工作過程預(yù)測(cè)分析程序或LL(1)分析法：總控程序分析表M[A，a]矩陣，AVN，aVT是終結(jié)符或‘?！?，分析棧STACK用于存放文法符號(hào)第82頁，課件共113頁，創(chuàng)作于2023年2月總控程序分析表X#輸入串分析棧STACKa1a2...ai…#預(yù)測(cè)分析器模型#Sa1a2...ai…#分析開始時(shí)：輸出第83頁，課件共113頁，創(chuàng)作于2023年2月總控程序根據(jù)現(xiàn)行棧頂符號(hào)X和當(dāng)前輸入符號(hào)a，執(zhí)行下列三種動(dòng)作之一:（1）若X＝a＝‘?！瑒t宣布分析成功，停止分析過程。（2）若X＝a‘?！瑒t把X從STACK棧頂逐出，讓a指向下一個(gè)輸入符號(hào)。匹配成功4.5.1預(yù)測(cè)分析程序工作過程第84頁，課件共113頁，創(chuàng)作于2023年2月4.5.1預(yù)測(cè)分析程序工作過程（3）若X是一個(gè)非終結(jié)符，則查看分析表M。若M[X，a]中存放著關(guān)于X的一個(gè)產(chǎn)生式，首先將X彈出STACK棧頂，把產(chǎn)生式的右部符號(hào)串按反序一一推進(jìn)STACK棧(若右部符號(hào)為，則意味不推任何東西進(jìn)棧)。在把產(chǎn)生式的右部符號(hào)推進(jìn)棧的同時(shí)應(yīng)做這個(gè)產(chǎn)生式相應(yīng)的語義動(dòng)作（目前暫不管）。若M[X，a]中存放著“出錯(cuò)標(biāo)志”，則調(diào)用出錯(cuò)診察程序ERROR。推導(dǎo)第85頁，課件共113頁，創(chuàng)作于2023年2月例對(duì)于文法G(E)E→TEE→+TE|T→FT

T→*FT|F→(E)|i 輸入串為i1*i2+i3，利用分析表進(jìn)行預(yù)測(cè)分析：分析表矩陣元素M[A,a]指出非終結(jié)符A，面臨輸入符號(hào)a時(shí)，應(yīng)選用的候選式（或產(chǎn)生式）。若A不該面臨a，則放一出錯(cuò)標(biāo)志。注：矩陣元素空白表示ERROR第86頁，課件共113頁，創(chuàng)作于2023年2月步驟

符號(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→i推導(dǎo)第87頁，課件共113頁，創(chuàng)作于2023年2月步驟

符號(hào)棧

輸入串

所用產(chǎn)生式4 #ET *i2+i3#5 #ETF* *i2+i3# T→*FT6 #ETFi2+i3#7 #ETi i2+i3#F→i推導(dǎo)推導(dǎo)第88頁，課件共113頁，創(chuàng)作于2023年2月步驟

符號(hào)棧

輸入串

所用產(chǎn)生式8 #ET +i3#9 #E +i3# T→10 #ET+ +i3# E→+TE11 #ET i3#推導(dǎo)推導(dǎo)第89頁，課件共113頁，創(chuàng)作于2023年2月步驟

符號(hào)棧

輸入串

所用產(chǎn)生式12 #ETF i3# T→FT13 #ETi i3# F→i14 #ET #15 #E # T→16 # # E→推導(dǎo)第90頁，課件共113頁，創(chuàng)作于2023年2月輸出的產(chǎn)生式序列對(duì)應(yīng)最左推導(dǎo)的過程，同時(shí)對(duì)應(yīng)相應(yīng)的分析樹。最左推導(dǎo)過程：

ETE'FT'E'iT'E'i*FT'E'

i*iT'E'i*iE'i*i+TE'i*i+FT'E'i*i+iT'E'i*i+iE'i*i+i第91頁，課件共113頁，創(chuàng)作于2023年2月4.5預(yù)測(cè)分析程序4.5.1預(yù)測(cè)分析程序工作過程4.5.2預(yù)測(cè)分析表的構(gòu)造第92頁，課件共113頁，創(chuàng)作于2023年2月4.5.2預(yù)測(cè)分析表的構(gòu)造構(gòu)造FIRST()和FOLLOW(A)構(gòu)造分析表M[A，a]第93頁，課件共113頁，創(chuàng)作于2023年2月構(gòu)造FIRST()對(duì)每一文法符號(hào)XVT∪VN構(gòu)造FIRST(X)。連續(xù)使用下面的規(guī)則，直至每個(gè)FIRST集合不再增大為止：（1）若XVT，則FIRST(X)＝{X}。（2）若XVN，且有產(chǎn)生式X→a…，則把a(bǔ)加入到FIRST(X)中；若X→也是一條產(chǎn)生式，則把也加到FIRST(X)中。（3）若X→Y…是一個(gè)產(chǎn)生式且YVN，則把FIRST(Y)中的所有非-元素都加到FIRST(X)中；若X→Y1Y2…Yk是一個(gè)產(chǎn)生式，Y1，…，Yi-1都是非終結(jié)符，而且，對(duì)于任何j，1ji-1，F(xiàn)IRST(Yj)都含有，則把FIRST(Yi)中的所有非-元素都加到FIRST(X)中；特別是，若所有的FIRST(Yj)均含有，j＝1,2,…,k，則把加到FIRST(X)中。第94頁，課件共113頁，創(chuàng)作于2023年2月對(duì)文法G的任何符號(hào)串=X1X2…Xn構(gòu)造集合FIRST()。（1）置FIRST()＝FIRST(X1)\{}；（2）若對(duì)任何1ji-1，F(xiàn)IRST(Xj)，則把FIRST(Xi)\{}加至FIRST()中；特別是，若所有的FIRST(Xj)均含有，1jn，則把也加至FIRST()中。顯然，若＝則FIRST()＝{}。構(gòu)造FIRST()第95頁，課件共113頁，創(chuàng)作于2023年2月構(gòu)造FOLLOW(A)對(duì)于文法G的每個(gè)非終結(jié)符A構(gòu)造FOLLOW(A)的辦法是，連續(xù)使用下面的規(guī)則，直至每個(gè)FOLLOW不再增大為止：（1）對(duì)于文法開始符號(hào)S，置＃于FOLLOW(S)中；（2）若A→B是一個(gè)產(chǎn)生式，則把FIRST()\{}加至FOLLOW(B)中；（3）若A→B是一個(gè)產(chǎn)生式，或AB是一個(gè)產(chǎn)生式而(即FIRST())，則把FOLLOW(A)

加至FOLLOW(B)中。第96頁，課件共113頁，創(chuàng)作于2023年2月例對(duì)于文法G(E)E→TEE→+TE|T→FT

T→*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)={*,+,),#}第97頁，課件共113頁，創(chuàng)作于2023年2月在對(duì)文法G的每個(gè)非終結(jié)符A及其任意候選都構(gòu)造出FIRST()和FOLLOW(A)之后，現(xiàn)在可以用它們來構(gòu)造G的分析表M[A，a]。（1）對(duì)文法G的每個(gè)產(chǎn)生式A→執(zhí)行第2步和第3步；（2）

對(duì)每個(gè)終結(jié)符aFIRST()，把A→加至M[A，a]中；（3）

若FIRST()，則對(duì)任何bFOLLOW(A)，把A→加至M[A，b]中。（4）把所有無定義的M[A，a]標(biāo)上“出錯(cuò)標(biāo)志”。第98頁，課件共113頁，創(chuàng)作于2023年2月第99頁，課件共113頁，創(chuàng)作于2023年2月對(duì)產(chǎn)生式ETE由于FIRST(TE)=FIRST(T)={(,i}故應(yīng)把ETE放入M[E,(]和M[E,i]中。對(duì)于產(chǎn)生式E+TE由于FIRST(+TE)={+}所以，應(yīng)把E+TE放入M[E,+]中。對(duì)于產(chǎn)生式E由于FOLLOW(E)={),#}故應(yīng)把E放入M[E,)]和M[E,#]中。第100頁，課件共113頁，創(chuàng)作于2023年2月如果G是左遞歸或二義的，那么，M至少含有一個(gè)多重定義入口。因此，消除左遞歸和提取左因子將有助于獲得無多重定義的分析表M?？梢宰C明，一個(gè)文法G的預(yù)測(cè)分析表M不含多重定義入口，當(dāng)且僅當(dāng)該文法為L(zhǎng)L(1)的。4.5.2預(yù)測(cè)分析表的構(gòu)造LL(1)的含義：第一個(gè)L表示從左至右掃描輸入符號(hào)串第二個(gè)L表示生成輸入串的一個(gè)最左推導(dǎo)1表示在決定分析器的每步動(dòng)作時(shí)，向前看一個(gè)符號(hào)。第101頁，課件共113頁，創(chuàng)作于2023年2月（2）若β=>ε,則FIRST(α)∩FOLLOW(A)=*LL(1)文法定義：一個(gè)文法G，其分析表M不含多重定義入口(即分析表中無二條以上產(chǎn)生式)，則稱它是一個(gè)LL(1)文法。定理：文法G是LL(1)文法的充分必要條件是：對(duì)于G的每一個(gè)非終結(jié)符A的產(chǎn)生式A|,下列條件成立：（1）FIRST(α)∩FIRST(β)=第102頁，課件共113頁，創(chuàng)作于2023年2月試證明文法G是LL(1)文法。證明：

E

→+TE|FIRST(+TE)=｛+｝

FOLLOW(E)=｛)，#｝

T→*FT|FIRST(*FT)=｛*｝

FOLLOW(T)=｛+,)，#｝

F→(E)|iFIRST((E))=｛(｝

FIRST(i)=｛i｝所以G(E)是LL(1)文法。第103頁，課件共113頁，創(chuàng)作于2023年2月G(S): SiCtS|iCtSeS|a Cb提取左因子之后，改寫成：G(S): SiCtSS|a SeS| Cb最近匹配原則FIRST(S)={i,a}FIRST(S)={e,