工學第4章編譯原理課件

第4章語法分析—自上而下分析4.1語法分析器的功能4.2自上而下分析面臨的問題4.3LL（1）分析法4.4遞歸下降分析程序構(gòu)造4.5預測分析程序第4章語法分析—自上而下分析第4章語法分析—自上而下分析4.1語法分析器的功能內(nèi)容回顧句型、句子和語言的定義句型有文法G[S]，若S==*>α，且α∈Ｖ*,

則稱是α是文法G的一個句型句子有文法G[S]，若S==*>α，且α∈ＶT*,

則稱是α是文法G的一個句子語言由文法G產(chǎn)生的所有句子的集合

L(G)={α|S==+>α,且α∈ＶT*}內(nèi)容回顧內(nèi)容回顧句型、句子和語言的定義內(nèi)容回顧最左(最右)推導在推導的任何一步α==*>β(其中α和β是句型)，都對α中的最左(最右)非終結(jié)符進行替換句型分析(句子分析)識別一個符號串是否為某文法的句型(句子)的過程也就是某文法的某個推導的構(gòu)造過程設(shè)文法G為:E→E+T|TT→T*F|FF→(E)|i請問符號串i+i*i是否為該文法的句子?自上而下自下而上EE+TT*FFFTiii內(nèi)容回顧最左(最右)推導設(shè)文法G為:請問符號串i+i*i是自上術(shù)語解釋分析算法(分析器、識別算法)在語言的編譯實現(xiàn)中，把完成句型(句子)分析的程序稱為分析程序或識別程序從左到右的分析算法即總是從左到右地識別輸入符號串，首先識別符號串中的最左符號，進而依次識別右邊的一個符號內(nèi)容回顧術(shù)語解釋分析算法(分析器、識別算法)內(nèi)容回顧4.1語法分析器的功能任務(wù)分析并判定輸入的單詞符號串是否符合該語言的語法規(guī)則(上下文無關(guān)文法)實質(zhì)就是按照文法的產(chǎn)生式，識別輸入符號串是否為一個句子(合法程序，語句，表達式等)詞法掃描器語法分析器語義處理單詞符號語法樹4.1語法分析的功能4.1語法分析器的功能任務(wù)詞法掃描器語法分析器語義處理單詞符設(shè)計思想判斷是否能從文法的開始符號出發(fā)推導出這個輸入串或者,判斷能否建立一棵與輸入串匹配的語法分析樹輸入單詞符號串輸出語法分析樹格式化的程序合法的表達式、語句、函數(shù)出錯處理要求盡快發(fā)現(xiàn)錯誤，準確定位可能時進行恢復處理，繼續(xù)語法分析4.1語法分析的功能設(shè)計思想4.1語法分析的功能根據(jù)建立方法，語法分析算法可分為兩大類:自上而下分析法從文法的開始符號出發(fā)，反復使用各種產(chǎn)生式向下推導，尋找與輸入符號串匹配的推導自下而上分析法從輸入串開始，逐步進行歸約，直至歸約到文法的開始符號兩種方法反映了兩種不同的語法樹的構(gòu)造過程自上而下——從樹根推導到樹葉自下而上——從樹葉歸約到樹根4.1語法分析的功能根據(jù)建立方法，語法分析算法可分為兩大類:4.1語法分析的功能4.2自上而下分析面臨的問題基本方法對任何輸入串,試圖從文法的開始符號出發(fā)，自上而下地為輸入串建立一棵語法樹或者說，為輸入串尋找一個最左推導過程本質(zhì)是一種試探過程，是反復使用不同產(chǎn)生式謀求匹配輸入串的過程如何選擇哪個產(chǎn)生式進行推導?4.2自上而下分析面臨的問題4.2自上而下分析面臨的問題基本方法4.2自上而下分析面臨例文法G[S]S→xAyA→ab|a

判斷輸入串w=xay是否為該文法的句子？SxAy試探ab失敗回溯a試探成功分析結(jié)束SxAy==>xay==>問題產(chǎn)生回溯的原因是什么?4.2自上而下分析面臨的問題例文法G[S]S→xAyA→ab|aSxAy試探公共左因子——產(chǎn)生回溯例文法G:S→xAyA→ab|a無法確定非終結(jié)符A面臨輸入符號a時選用哪個關(guān)于A的候選式左遞歸——無限循環(huán)例文法G:S→Sa|abaw=abaaaSSaSa…無法確定何時用S→aba產(chǎn)生式進行推導某些文法導致自上而下分析具有不確定性4.2自上而下分析面臨的問題公共左因子——產(chǎn)生回溯w=abaaaSSaSa…無法確定4.3LL(1)分析法為了構(gòu)造不帶回溯的自上而下分析算法消除文法的左遞歸消除回溯、提取左因子LL(1)分析條件LL(1)文法4.3LL（1）分析法4.3LL(1)分析法為了構(gòu)造不帶回溯的自上而下分析算法4.3.1左遞歸的消除關(guān)于非終結(jié)符P的規(guī)則直接左遞歸定義：若P→Pα｜βα、β∈Ｖ*例如E→E+T｜T（含有E的左遞歸）

T→T*F｜F（含有T的左遞歸）

F→(E)｜i4.3LL（1）分析法4.3.1左遞歸的消除關(guān)于非終結(jié)符P的規(guī)則4.3LL（間接左遞歸定義：若P==+>Pαα∈Ｖ*例如間接左遞歸

S→AaA→Sb|bS==>Aa==>Sba即S==+>Sb用S的產(chǎn)生式右部替換A右部的S得：

A→Aab|b

變成A的產(chǎn)生式含有直接左遞歸4.3LL（1）分析法間接左遞歸定義：4.3LL（1）分析法消除直接左遞歸的方法改寫為等價的右遞歸形如：P→Pα｜β

α非ε，β不以P開始

改寫為：P→βP’（P’為新增加的非終結(jié)符）

P'→αP'｜ε改寫前產(chǎn)生式可產(chǎn)生短語P==>Pα==>βα

改寫后產(chǎn)生式可產(chǎn)生短語

P==>βP’

==>βαP'

==>βα

等價4.3LL（1）分析法消除直接左遞歸的方法改寫為等價的右遞歸等價4.3LL（E→E+T｜TT→T*F｜FF→(E)｜iE→TE'E'→+TE'｜εT→FT'T'→*FT'｜εF→(E)｜i4.3LL（1）分析法E→E+T｜TE→TE'4.3LL（1）分消除多個直接左遞歸若有多個左遞歸的產(chǎn)生式如：P→Pα1|Pα2|…|Pαm|β1|β2|…|βn消除左遞歸后變?yōu)椋?/p>

P→β1P’|β2P’|…|βnP’ P’→α1P’|α2P’|…|αmP’|ε消除左遞歸要求文法：

1.無回路（A==*>A）

2.無空產(chǎn)生式（A→ε）4.3LL（1）分析法消除多個直接左遞歸若有多個左遞歸的產(chǎn)生式如：消除左遞歸后變?yōu)榫毩暲缬形姆ǎ?/p>

K→Ka|Kb|Kc|d|e

消除左遞歸后變?yōu)椋?/p>

K→dK’|eK’

K’→aK’|bK’|cK’|ε4.3LL（1）分析法練習例如有文法：消除左遞歸后變?yōu)椋?.3LL（1）分析法間接左遞歸消除舉例S→Qc｜cQ→Rb｜b

R→Sa｜aS=>Qc=>Rbc=>Sabc

是間接左遞歸消除方法1：將非終結(jié)符排序：

RQS將R的右部代入Q，S：

Q→Sab｜ab｜bS→Qc｜c（不變）將Q的右部代入S：

S→Sabc｜abc｜bc｜c消除S的直接左遞歸：

S→abcS’｜bcS’|cS’S’→abcS’|εQ→Sab｜ab|bR→Sa｜a整理化簡：刪除Q，R（無用）消除左遞歸后得：

S→abcS’｜bcS’|cS’S’→abcS’|ε4.3LL（1）分析法間接左遞歸消除舉例S→Qc｜c將Q的右部代入S：4.

S→Qc｜cQ→Rb｜b

R→Sa｜a消除方法2：將非終結(jié)符排序：

SQR將S的右部代入Q，R：

Q→Rb｜b（不變）

R→Qca｜ca|a將Q的右部代入R：

R→Rbca｜bca|ca|a消除R的直接左遞歸：

R→bcaR’｜caR’|aR’

R’→bcaR’|ε

整理化簡：S，Q（有用）消除左遞歸后得：

S→Qc｜cQ→Rb｜bR→bcaR’｜caR’|aR’R’→bcaR’|ε4.3LL（1）分析法S→Qc｜c將Q的右部代入R：4.3LL（1）分消除左遞歸算法1.以某種S順序?qū)⑽姆ǖ姆墙K結(jié)符排列

P1，P2，…,Pn

2.FORi:=1TOnDOBEGINFORj:=1TOi-1DO

把形如Pi→Pjγ的規(guī)則改寫成

Pi→δ1γ|δ2γ|…|δkγ,其中

Pj→δ1|δ2|…|γ是關(guān)于Pj的所有規(guī)則;

消除Pi的直接左遞歸

END3.化簡由2所得的文法，即去除那些從開始符號出發(fā)永遠無法到達的非終結(jié)符的產(chǎn)生式當非終結(jié)符的排列順序不同時，變換后的文法形式可能不同，但是它們都和原文法是等價的4.3LL（1）分析法消除左遞歸算法1.以某種S順序?qū)⑽姆ǖ姆墙K結(jié)符排列當非終結(jié)符4.3.2消除回溯、提左因子消除回溯目的對文法的任何非終結(jié)符，當它去匹配輸入串時，能夠根據(jù)輸入符號，準確地選擇合適的候選式去匹配若需要非終結(jié)符A去匹配輸入串，A的候選式為A→α1|α2|…|αn

，

A所面臨的第一個輸入符號為a時，A能準確地選擇αi去執(zhí)行匹配任務(wù)，則無需回溯4.3LL（1）分析法4.3.2消除回溯、提左因子消除回溯目的4.3LL（1提取公共左因子方法對于所有形如A→αβ1｜αβ2｜...｜αβn｜γ的規(guī)則其中，α為左因子，γ不以α開頭改寫為A→αA'｜γ其中A’為新增加的非終結(jié)符

A'→β1｜β2｜...｜βn例如

S→xAyA→ab|a提左因子后變換為

S→xAy

A→aA’

A’

→b|ε4.3LL（1）分析法提取公共左因子方法對于所有形如提左因子后變換為4.3L4.3.3LL(1)分析條件FIRST集合的定義FOLLOW集合的定義LL(1)分析條件LL(1)文法的定義4.3LL（1）分析法4.3.3LL(1)分析條件FIRST集合的定義4.3FIRST(α)集合的定義設(shè)G=(ＶT，ＶN，S，P）α∈Ｖ*

FIRST(α)={a|α==*>a…，a∈ＶT}若α==*>ε，則ε∈FIRST(α)FIRST(α)是α的所有可能推導的首遇終結(jié)符號或ε，是選擇產(chǎn)生式的依據(jù)αa……

E→TE'E'→+TE'｜εT→FT'T'→*FT'｜εF→(E)｜iFIRST((E))={(}（E）==0>（E）FIRST（TE’）={（，i}TE’==>FT’E’==>（E）T’E’TE’==>FT’E’==>iT’E’4.3LL（1）分析法FIRST(α)集合的定義設(shè)G=(ＶT，ＶN，S，P）α∈FOLLOW(A)集合的定義A∈ＶN

FOLLOW(A)={a｜S==*>…Aa…，a∈ＶT}若S==*>…A，則#∈FOLLOW（A）#—輸入串的結(jié)束符也可看作是句子的括號#S#FOLLOW(A)表示了句型中可能緊跟在A后面的終結(jié)符號S…Aa…E→TE'E'→+TE'｜εT→FT'T'→*FT'｜εF→(E)｜i

）∈FOLLOW（E）S==>TE’==>FT’E’==>（E）T’E’

+

∈FOLLOW（T）S==>TE’==>T+TE’

#∈FOLLOW（E）S==0>E4.3LL（1）分析法FOLLOW(A)集合的定義A∈ＶNS…Aa…E→消除回溯的條件非終結(jié)符A的所有候選首符集兩兩不相交，即A的任何兩個不同候選α和β，滿足：

FIRST(α)∩FIRST(β)=φ

當要求A

匹配輸入串時，A就能根據(jù)它所面臨的第一個輸入符號a，準確地指派某一個候選去執(zhí)行任務(wù)，這個候選就是那個終結(jié)首符集含a的α4.3LL（1）分析法消除回溯的條件非終結(jié)符A的所有候選首符集兩兩不相交，4.3非終結(jié)符A的自動匹配當非終結(jié)符A面臨輸入符號a，但a不屬于A

的任何候選首符集，如果A有候選式A→ε(A

的某個候選首符集包含ε)，可以讓A自動得到匹配，即A匹配于空字ε，但輸入符號不讀進要想讓A自動匹配成功，需要考察FOLLOW(A)4.3LL（1）分析法非終結(jié)符A的自動匹配當非終結(jié)符A面臨輸入符號a，但a不屬i+i#的推導過程設(shè)有文法GE→TE’

E’→+TE’|ε

T→FT’

T’→*FT’|ε

F→(E)|i

i∈FIRST(i)+∈FIRST(+TE’)+∈FOLLOW(T’)#∈FOLLOW(E’)#∈FOLLOW(T’)ＥＴＥ’ＦＴ’iε＋ＴＥ’ＦＴ’iεε生成語法分析樹4.3LL（1）分析法i+i#的推導過程設(shè)有文法GＥＴＥ’ＦＴ’iε＋ＴＥ推導過程的分析輸入輸出輸入：符號串(有序的)輸出：結(jié)構(gòu)化的符號串(樹結(jié)構(gòu))產(chǎn)生式的選擇根據(jù)當前符號（單詞）語法分析樹的表示按照使用序列排列的產(chǎn)生式序列4.3LL（1）分析法推導過程的分析輸入輸出4.3LL（1）分析法無回溯的自上而下分析的文法的條件文法不含左遞歸對于文法的每個非終結(jié)符A的任何兩個不同的產(chǎn)生式A→α|β 1)FIRST(α)∩FIRST(β)=φ 2)α==*>和β==*>不能同時成立

3)如果β==*>，則

FISRT(α/A)∩FOLLOW(A)=φ滿足以上條件的文法稱為LL(1)文法4.3LL（1）分析法無回溯的自上而下分析的文法的條件文法不含左遞歸4.3LLLL(1)分析含義第一個L表示從左向右掃描輸入符號串第二個L表示生成最左推導1表示讀入一個符號可確定下一步推導對于LL（1）文法，可以對輸入串進行有效的無回溯的自上而下分析。對于文法G，當面臨的輸入符號為a，要用非終結(jié)符A進行匹配時，假設(shè)A的所有產(chǎn)生式為A→α1|α2|…|αn 1)若a∈FIRST(αi

)，則指派αi去執(zhí)行任務(wù)

2)若a不屬于任何候選首符集，則： ①若ε屬于某個FIRST(αi

)且

a∈FOLLOW(A)，則讓A與ε自動匹配 ②否則，a的出現(xiàn)是一種語法錯誤4.3LL（1）分析法LL(1)分析含義4.3LL（1）分析法4.4遞歸下降分析程序構(gòu)造不帶回溯的自上而下分析程序分析程序一組遞歸過程每個非終結(jié)符一個子過程LL（1）文法構(gòu)造分析程序從開始符號所對應(yīng)的過程開始運行子過程的功能：對相應(yīng)非終結(jié)符產(chǎn)生式右部進行語法分析4.4遞歸下降分析程序構(gòu)造4.4遞歸下降分析程序構(gòu)造不帶回溯的自上而下分析程序分析例表達式文法的遞歸下降分析器消除左遞歸后的表達式文法G為：

E→TE' E'→+TE’|ε T→FT' T'→*FT’|ε F→(E)|i可以證明

G是一個LL（1）文法E()E’()T()T’()F()5個非終結(jié)符構(gòu)造5個子過程4.4遞歸下降分析程序構(gòu)造例表達式文法的遞歸下降分析器消除左遞歸后的表達式文法G為：遞歸下降分析器構(gòu)造說明C語言

E（）

{ T;E’; }E’TE（1）E（）：完成對E→TE’的右部分析PASCAL語言 procedureE; begin T;E’; end;右部有非終結(jié)符時，調(diào)用該非終結(jié)符對應(yīng)的子過程來完成遞歸下降分析器構(gòu)造說明C語言 E’TE（1）E（）：完成對E’(){ if(c==‘+’){p++;T;E’;}}E’TE’（2）E’（）：完成對E→+TE’|ε的右部分析procedureE’; ifsym=‘+’thenbeginadvance;T;E’;end；+其它非+字符自動匹配εadvance：把輸入指針ip下移一位sym：當前所面臨的輸入符號4.4遞歸下降分析程序構(gòu)造E’()E’TE’（2）E’（）：完成對E→+TE’|C語言練習T(){ F;

T’;}(3)T():T→FT’procedureT; begin

F;T’; end;T’FT4.4遞歸下降分析程序構(gòu)造C語言練習(3)T():T→FT’procedure(4)T’():T’→*FT’|εC語言練習T’(){ if(c==‘*’)

{p++;F;T’;}

}procedureT’; ifsym=‘*’thenbeginadvance;F;T’;end；T’F*其它非*字符自動匹配εT’4.4遞歸下降分析程序構(gòu)造(4)T’():T’→*FT’|εC語言練習proce(5)F():F→(E)|iprocedureF;beginifsym='('thenbeginadvance;E;ifsym=‘)’thenadvanceelseerror{括號不匹配}endelseifsym=‘i’thenadvance elseerror{F面臨非（，i輸入符號，語法錯誤}endEF()i其它非(,i字符出現(xiàn)語法錯誤4.4遞歸下降分析程序構(gòu)造(5)F():F→(E)|iprocedureF;Ｆ的子程序F(){ if(c==‘(‘){p++;E;if(c==‘)’)p++;elseerror;}/*括號不匹配*/

elseif(c==‘i’)p++;elseerror;/*F面臨非(,i輸入符號，語法錯誤*/

}EF()i其它非(,i字符出現(xiàn)法錯誤4.4遞歸下降分析程序構(gòu)造Ｆ的子程序EF()i其它非(,i字符出現(xiàn)法錯誤4.4遞i+i的遞歸下降分析過程ＥＴＥ’ＦＴ’Ｔ＋Ｅ’iεＦＴ’iεε生成語法分析樹i+i#匹配成功返回，指針下移自動匹配，返回自動匹配，返回自動匹配，返回匹配成功繼續(xù)，指針下移匹配成功返回，指針下移分析成功結(jié)束4.4遞歸下降分析程序構(gòu)造i+i的遞歸下降分析過程ＥＴＥ’ＦＴ’Ｔ＋Ｅ’iεＦＴ’i遞歸下降分析程序優(yōu)缺點分析優(yōu)點：1）直觀、簡單、可讀性好2）便于擴充缺點：1)遞歸算法的實現(xiàn)效率低2)處理能力相對有限3)通用性差，難以自動生成4.4遞歸下降分析程序構(gòu)造遞歸下降分析程序優(yōu)缺點分析優(yōu)點：4.4遞歸下降分析程序構(gòu)

遞歸下降分析程序課堂練習文法G為：

S→(T)|a+S|a

T

→T,S|S

消除左遞歸：

S→(T)|a+S|a

T→ST’

T’

→，ST’|ε提取左因子：

S→(T)|aS’

S’→+S|ε

T→ST’T’→，ST’|ε4個子程序：

S（）S’（）

T（）T’（）

BEGIN4.4遞歸下降分析程序構(gòu)造遞歸下降分析程序課堂練習文法G為：消除左遞歸：提取左因

遞歸下降分析程序課堂練習答案（1）S→(T)|aS’S(){if(c=‘(‘)/*匹配第一候選式*/{p++;T;if(c=‘)’)p++;elseerror;/*括號不匹配*/}elseif(c=‘a(chǎn)’){p++;S’;}/*匹配第二候選式*/elseerror;/*語法錯誤*/}4.4遞歸下降分析程序構(gòu)造遞歸下降分析程序課堂練習答案（1）S→(T)|aS’(2)S’→+S|εS’(){if(c=‘+‘){p++;

S;}}(3)T→ST’T(){S;T’;}(4)T’→,ST’|εT’(){if(c=‘,’){p++;

S;T’;}}4.4遞歸下降分析程序構(gòu)造(2)S’→+S|ε(3)T→ST’(4)T’→,ST’4.5預測分析程序?qū)崿F(xiàn)LL(1)分析的另一種有效方法使用一張二維分析表（預測分析表）和一個分析棧（文法符號棧）聯(lián)合進行控制來實現(xiàn)自上而下分析技術(shù)4.5預測分析程序4.5預測分析程序?qū)崿F(xiàn)LL(1)分析的另一種有效方法使用

預測分析表說明預測分析表實際上是一個矩陣M[A,a]M[A，a]=A→αi當A面臨a時所應(yīng)選用的候選式空(error)A不可能與a匹配出現(xiàn)語法錯誤待匹配棧頂非終結(jié)符所面臨輸入符號4.5.1預測分析程序工作過程預測分析表說明預測分析表實際上是一個矩陣M[A,a]M[A表達式文法的預測分析表M[E’，+]=E’→+TE’E’面臨+時選用E’→+TE’M[T’，)]=T’→εT’面臨）時選用T’→εM[F，*]=errorF面臨*時出現(xiàn)語法錯誤表達式文法的預測分析表M[E’，+]=E’→+TE’E分析棧的說明分析棧用于存放分析過程中的文法符號topstack棧頂指針分析棧初始化時：棧底壓入一個‘#’底頂#Stoptop次棧底壓入文法開始符S入棧操作push出棧操作poptop分析棧的說明分析棧用于存放分析過程中的文法符號topstac

預測分析器模型

輸入緩沖區(qū):…a…#

X┆#

棧總控制程序預測分析表輸出所選用產(chǎn)生式序列查找4.5預測分析程序預測分析器模型輸入緩沖區(qū):…a…#總控制程序預總控程序執(zhí)行時可能動作對于任何（X，a）X是棧頂符號a是面臨輸入符號(1)X∈ＶT

且X＝a＝‘#’，分析成功結(jié)束，輸入串是一個合法句子(2)X∈ＶT

且X＝a≠‘#’，X出棧，輸入指針指向下一輸入符號(3)X∈ＶN，查分析表M[X，a]

若M[X，a]=X→αi，X出棧，αi逆序入棧，輸入指針不動若M[X，a]=空，則調(diào)用error程序，進行錯誤處理4.5預測分析程序總控程序執(zhí)行時可能動作對于任何（X，a）X是棧頂符號a是執(zhí)行例子：i*i+i分析過程

棧輸入緩沖區(qū)所用產(chǎn)生式0#E

i*i+i#E→TE'E'T入棧1#E'Ti*i+i#T→FT'2#E'T'F

i*i+i#F→i3#E'T'ii*i+i#i出棧，a下移4#E'T'

*i+i#T'→*FT'5#E'T'F**i+i#*出棧，a下移6#E'T'F

i+i#F→i

7#E'T'ii+i#i出棧，a下移4.5預測分析程序執(zhí)行例子：i*i+i分析過程棧輸入i*i+i分析

過程續(xù)

棧輸入緩沖區(qū)所用產(chǎn)生式8#E'T'

+i#T'→ε9#E'+i#E'→+TE'10#E'T+

+i#11#E'Ti#T→FT'12#E'T'F

i#F→i13#E'T'ii#14#E'T'

#T'→ε15#E'#E'→ε16#

##=#分析成功結(jié)束輸出的產(chǎn)生式序列形成了按最左推導生成的語法分析樹4.5預測分析程序i*i+i分析

過程續(xù)棧輸入緩沖區(qū)課堂練習一：i+i分析過程棧輸入緩沖區(qū)所用產(chǎn)生式0#E

i+i#E→TE'1#E'Ti+i#T→FT' 2#E'T'F

i+i#F→i3#E'T'ii+i# 4#E'T'+i#T'→ε5#E'+i#E'→+TE'6#E'T+

+i# 7#E'Ti#T→FT'4.5預測分析程序課堂練習一：i+i分析過程棧輸入緩沖區(qū)i+i分析

過程

續(xù)棧輸入緩沖區(qū)所用產(chǎn)生式8#E'T'F

i#F→i9#E'T'ii#10#E'T'

#T'→ε11#E'#E'→ε12#

##=#分析成功4.5預測分析程序i+i分析

過程

續(xù)棧輸入緩沖區(qū)所用課堂練習二：i+i*i分析過程棧輸入緩沖區(qū)所用產(chǎn)生式0#Ei+i*i#E→TE'1#E'T

i+i*i# T→FT'2#E'T'Fi+i*i#F→i3#E'T'i

i+i*i# 4#E'T'+i*i#T'→ε5#E'

+i*i#E'→+TE'6#E'T++i*i#7#E'T

i*i#T→FT'4.5預測分析程序課堂練習二：i+i*i分析過程棧輸入緩沖i+i*i分析

過程

續(xù)棧輸入緩沖區(qū)所用產(chǎn)生式8#E'T'Fi*i#F→i9#E'T'ii*i#10#E'T'*i#T'→*FT'11#E'T'F**i#12#E'T'Fi#F→i13#E'T'ii#14#E'T'#T'→ε15#E'#E'→ε16##4.5預測分析程序i+i*i分析

過程

續(xù)棧輸入緩沖區(qū)總控程序?qū)崿F(xiàn)算法描述BEGINPUSH(STACK,’#’)；PUSH(STACK,開始符號);a=第一個輸入符號；

FLAG:=TRUE；

WHILEFLAGDOBEGINX=POP(STACK);IFX∈ＶTTHENIFX=aTHENa=下一個符號{終結(jié)符匹配}ELSEERROR{與當前輸入符號不匹配}4.5預測分析程序總控程序?qū)崿F(xiàn)算法描述BEGIN4.5預測分析程序ELSEIFX=‘#’THENIFX=aFLAG:=FALSEELSEERRORX=a=‘#’

分析成功結(jié)束ELSEIFM[A，a]={X→X1X2…Xk}

把Xk…X2X1一一推進STACK棧]ELSEERRORENDOFWHILESTOP{分析成功,過程完畢}END4.5預測分析程序ELSEIFX=‘#’THENX=a=‘#’分析成4.5.2預測分析表的構(gòu)造設(shè)有文法G，預測分析表構(gòu)造過程：計算所有候選式α的首符集

FIRST（α）計算所有非終結(jié)符A的后繼符集

FOLLOW（A）構(gòu)造預測分析表

M4.5預測分析程序4.5.2預測分析表的構(gòu)造設(shè)有文法G，預測分析表構(gòu)造過程：FIRST(α)的計算法FIRST(α)={a｜α==*>a

…，a∈ＶT}若α==*>ε，則ε∈FIRST(α)計算文法符號X的FIRST（X）計算文法符號串α=X1X2…Xn的FIRST(α)4.5預測分析程序FIRST(α)的計算法FIRST(α)={a｜α==*FIRST(X)的計算法重復以下計算，直到FIRST（X）不再增大為止：1)若X∈ＶT，則FIRST(X)={X}。例FIRST（+）={+}FIRST（i）={i}2)若X∈ＶN，若有X→a…，則將a加入FIRST(X)；例E'→+TE'+∈FIRST（E’）

F→（E）|i

（，i∈FIRST（F）若有X→ε，則將ε加入FIRST(X)。例E’→εε∈FIRST（E’）4.5預測分析程序FIRST(X)的計算法重復以下計算，直到FIRST（X若有X→Y1…Yi-1Yi…Yk

，并對于某個i， 有1≤j≤i-1，ε∈FIRST（Yj），即Y1，…，Yi-1==*>ε，則將所有FIRST(Yj)-{ε}∪FIRST(Yi)-{ε}

加入FIRST(X)中；-{ε}-{ε}3)若有X→Y…，且Y∈ＶN

，則FIRST(Y)-{ε}加入FIRST(X);例F→(E)|iFIRST(F)={（，i}T→FT'FIRST(T)=FIRST(F)-{ε}={（，i}若所有Y1,…,Yk==*>ε，則將ε加入到FIRST(

X

)。-{ε}-{ε}3)若有X→Y…，且Y∈ＶN，例計算X→Y1…Yi-1Yi…YkFIRST(X)集舉例若有文法G為：

X→Y1Y2Y3

Y4Y5

Y1→a｜εY2→b｜ε

Y3

→c｜εY4→d｜εY5→e｜fFIRST集Y1Y2Y3Y4Y5Xa，εb，εc，εd，εe，fa,b,c,d,e,fεε

因為Y5==*>ε，所以ε∈FIRST（X）ε==*>ε==*>ε因為Y5==*>ε，所以ε∈FIRST（X）4.5預測分析程序計算X→Y1…Yi-1Yi…YkFIRST(X)集舉例若有計算表達式文法FIRST(X)集舉例文法G為：

E→TE’ E'→+TE'｜ε T→FT' T'→*FT'｜ε F→(E)｜i先找以終結(jié)符開頭的產(chǎn)生式FIRST(F)={(,i}FIRST(E')={+，ε}FIRST(T')={*,ε}再找右部以非終結(jié)符開頭的產(chǎn)生式FIRST(T)=FIRST(F)FIRST(E)=FIRST(T)={(,i}4.5預測分析程序計算表達式文法FIRST(X)集舉例文法G為：先找以終結(jié)符開計算FIRST(X)集合課堂練習={a，c，d，q}文法G為：

S→Ap｜Bq

A→a｜cA B→dB｜ε先找以終結(jié)符開頭的產(chǎn)生式FIRST(A)={a

,c

}FIRST(B)={d

,ε}再找右部以非終結(jié)符開頭的產(chǎn)生式FIRST(S)=FIRST(A)-{ε}∪FIRST(B)-{ε}因為B==>εε∈FIRST(S),因為S==*>ε∪FIRST(q)4.5預測分析程序計算FIRST(X)集合課堂練習={a，c，d，q}計算表達式文法候選式FIRST(α)集舉例候選式的FIRST集FIRST(TE’)=FIRST(T)={(,i}FIRST(+TE’)={+}FIRST(FT’)=FIRST(F)={(,i}FIRST(*FT’)={*}FIRST((E))={(}FIRST(i)={i}FIRST(ε)={ε}文法G為：

E→TE’

E'→+TE’|ε

T→FT’

T'→*FT’|ε

F→(E)|i非終結(jié)符的FIRST集FIRST(E)={(,i}FIRST(E')={+,ε}FIRST(T)={(,i}FIRST(T')={*,ε}FIRST(F)={(,i}4.5預測分析程序計算表達式文法候選式FIRST(α)集舉例候選式的FIRST計算FIRST(α)集合課堂練習文法G為：S→Ap｜Bq

A→a｜cA

B→

dB｜ε非終結(jié)符的FIRST集FIRST(S)={a,c,d,q}FIRST(A)={a,c}FIRST(B)={d,ε}候選式的FIRST集FIRST(Ap)=FIRST(A)={a,c}FIRST(Bq)=FIRST(B)-{ε}∪FIRST(q)={d,q}FIRST(a)={a}FIRST(cA)={c}FIRST(dB)=xntrdxfFIRST(ε)={ε}4.5預測分析程序計算FIRST(α)集合課堂練習文法G為：非終結(jié)符的FIRSFOLLOW(A)的計算法FOLLOW(A)={a｜S==*>…Aa…，a∈ＶT}若S==*>…A，則#∈FOLLOW（A）重復以下計算，直到每個FOLLOW(A)不再增大為止：1)將#加入到FOLLOW(S)中例#

∈FOLLOW(E)2)若A→αBβ,

則將FIRST(β)-{ε}加入FOLLOW(B)例E→TE’

FIRST(E’)-{ε}加入FOLLOW(T)

T→FT’

FIRST(T’)-{ε}加入FOLLOW(F)4.5預測分析程序FOLLOW(A)的計算法FOLLOW(A)={a｜S==3)若A→αB

，或A→αBβ，且β==*>ε，即ε∈FIRST(β)，A≠B

則將FOLLOW(A)所有元素加入FOLLOW(B)ε例E→TE’FOLLOW(E)加入FOLLOW(E’)E→T

E’E'→εFOLLOW(E)加入FOLLOW(T)T→FT’FOLLOW(T)加入FOLLOW(T’)T→F

T’FOLLOW(T)加入FOLLOW(F)T'→ε4.5預測分析程序3)若A→αB，或A→αBβ，ε例E→T計算表達式文法的FOLLOW集舉例#∈FOLLOW（開始符號）對每個非終結(jié)符查看其在產(chǎn)生式右邊的出現(xiàn)G：E→TE’

E'→+TE’|εT→FT’

T'→*FT’|εF→(E)|i#∈FOLLOW(E)=FIRST(E’)-{ε}FOLLOW(T)∪FOLLOW(E)={+,),#}FOLLOW(F)=FIRST(T’)-{ε}∪FOLLOW(T)={*,+,),#}FOLLOW(E)={),#}FOLLOW(E')=FOLLOW(E)={),#}FOLLOW(T')=FOLLOW(T)={+,),#}相同不需處理計算表達式文法的FOLLOW集舉例#∈FOLLOW（開始符號計算FOLLOW(A)集合課堂練習文法G為：S→Ap｜Bq A→a｜cA B→dB｜ε非終結(jié)符的FIRST集FIRST(S)={a,c,d,q}FIRST(A)={a,c}FIRST(B)={d,ε}

非終結(jié)符FOLLOW集FOLLOW(S)={#}FOLLOW(A)=FIRST(p)-{ε}={p}FOLLOW(B)=FIRST(q)-{ε}={q}4.5預測分析程序計算FOLLOW(A)集合課堂練習文法G為：非終結(jié)符的FIR表達式文法是LL(1)文法滿足條件（3）：

E’→εFIRST(+TE’)={+}FOLLOW(E’)={),#}φ

T’→εFIRST(*FT’)={*}FOLLOW(T’)={+,),#}φ文法G是LL（1）文法滿足條件（1）：已消除左遞歸滿足條件（2）：FIRST(+TE’)={+}FIRST(ε)={ε}

φFIRST(*FT’)={*}

FIRST(ε)={ε}

φFIRST((E))={(}

FIRST(i)={i}φ

文法G：E→TE'E'→+TE'

|ε

T→FT'T'→*FT'

|ε

F→(E)｜i表達式文法是LL(1)文法滿足條件（3）：滿足條件（1）預測分析表的構(gòu)造算法(4)把所有無定義的M[A,a]標上“出錯標志”(1)對文法G的每個產(chǎn)生式A→α，執(zhí)行(2)和(3)(2)對每個終結(jié)符a∈FIRST(α)，

把A→α填入M[A,a](3)若ε∈FIRST(α)，則對任何b∈FOLLOW(A)

把A→α填入M[A,b]4.5預測分析程序預測分析表的構(gòu)造算法(4)把所有無定義的M[A,a]標上“預測分析表的構(gòu)造算法舉例E→TE’

FIRST(TE’)={(,i}M[E,(]=E→TE’M[E,i]=E→TE’

E’→+TE’

FIRST(+TE’)={+}M[E’,+]=E’→+TE’E’→ε

FOLLOW(E’)={),#}M[E’,)]=E’→εM[E’,#]=E’→εF→(E)|i

M[F,(]=F→(E)M[F,i]=F→i若文法G的分析表不含多重入口，則G是LL(1)文法4.5預測分析程序預測分析表的構(gòu)造算法舉例E→TE’FIRST(TE’)預測分析法（狀態(tài)矩陣法）1)編寫文法，消除二義性；2)消除左遞歸、提取左因子；3)求FIRST集合和FOLLOW集合4）檢查是不是LL(1)文法若不是LL(1),說明文法的復雜性超過自上而下方法的分析能力5）按照LL(1)文法構(gòu)造預測分析表6）實現(xiàn)預測分析器4.5預測分析程序預測分析法（狀態(tài)矩陣法）1)編寫文法，消除二義性；4.5LL（1）分析中的錯誤處理語法錯誤：棧頂終結(jié)符與當前輸入符不匹配棧頂非終結(jié)符A面臨輸入符a，但分析表M中M[A,a]為空解決方法：跳過輸入串中的符號直至遇到“同步符號”4.5預測分析程序LL（1）分析中的錯誤處理語法錯誤：4.5預測分析程序預測分析程序課堂綜合練習文法G為：S→aBc｜bABA→aAb｜bB→b｜ε1.非終結(jié)符的FIRST集FIRST(S)={a,b}FIRST(A)={a,b}FIRST(B)={b,ε}2.非終結(jié)符FOLLOW集FOLLOW(S)={#}FOLLOW(A)=FIRST(b)∪FIRST(B)-{ε}∪FOLLOW(S)={b,#}FOLLOW(B)=FIRST(c)∪FOLLOW(S)={c,#}問題：構(gòu)造預測分析表，并分析符號串baabbb是否為該文法的句子？S→bABB==>εS→bAB預測分析程序課堂綜合練習文法G為：1.非終結(jié)符的FIRST集文法G為：S→aBc｜bABA→aAb｜bB→b｜εFOLLOW(B)={c,#}SABabc#S→aBcS→bABA→aAbA→bB→bB→εB→ε3.構(gòu)造預測分析表若分析表無多重入口，則G是LL(1)文法4.5預測分析程序文法G為：S→aBc｜bABA→aAb｜bB→b｜ε綜

合

練

習

續(xù)

符號棧輸入緩沖區(qū)所用產(chǎn)生式0#S

baabbb#S→bAB1#BAb

baabbb#移進b 2#BA

aabbb#A→aAb3#BbAa

aabbb#移進a4#BbA

abbb#A→aAb5#BbbAa

abbb#移進a6#BbbA

bbb#A→b7#Bbbb

bbb#移進b8#Bbb

bb#移進b9#Bb

b#移進b10#B

#B→ε11##分析成功結(jié)束4.b

a

a

b

b

b

分

析

過

程綜

合

練

習

續(xù)符號棧輸入緩沖區(qū)所用產(chǎn)作業(yè)：P8123、文法G[A]如下：4、已知文法G[S]如下：A→BaC|CbB

S→aABbcd|εB→Ac|cA→ASd|εC→Bb|bB→SAh|eC|ε

消除其左遞歸C→Sf|Cg|εD→aBD|ε

求每一非終結(jié)符的FIRST

集合和FOLLOW集合，該文法是LL（1）文法嗎？為什么？作業(yè)作業(yè)：P812作業(yè)第4章語法分析—自上而下分析4.1語法分析器的功能4.2自上而下分析面臨的問題4.3LL（1）分析法4.4遞歸下降分析程序構(gòu)造4.5預測分析程序第4章語法分析—自上而下分析第4章語法分析—自上而下分析4.1語法分析器的功能內(nèi)容回顧句型、句子和語言的定義句型有文法G[S]，若S==*>α，且α∈Ｖ*,

則稱是α是文法G的一個句型句子有文法G[S]，若S==*>α，且α∈ＶT*,

則稱是α是文法G的一個句子語言由文法G產(chǎn)生的所有句子的集合

L(G)={α|S==+>α,且α∈ＶT*}內(nèi)容回顧內(nèi)容回顧句型、句子和語言的定義內(nèi)容回顧最左(最右)推導在推導的任何一步α==*>β(其中α和β是句型)，都對α中的最左(最右)非終結(jié)符進行替換句型分析(句子分析)識別一個符號串是否為某文法的句型(句子)的過程也就是某文法的某個推導的構(gòu)造過程設(shè)文法G為:E→E+T|TT→T*F|FF→(E)|i請問符號串i+i*i是否為該文法的句子?自上而下自下而上EE+TT*FFFTiii內(nèi)容回顧最左(最右)推導設(shè)文法G為:請問符號串i+i*i是自上術(shù)語解釋分析算法(分析器、識別算法)在語言的編譯實現(xiàn)中，把完成句型(句子)分析的程序稱為分析程序或識別程序從左到右的分析算法即總是從左到右地識別輸入符號串，首先識別符號串中的最左符號，進而依次識別右邊的一個符號內(nèi)容回顧術(shù)語解釋分析算法(分析器、識別算法)內(nèi)容回顧4.1語法分析器的功能任務(wù)分析并判定輸入的單詞符號串是否符合該語言的語法規(guī)則(上下文無關(guān)文法)實質(zhì)就是按照文法的產(chǎn)生式，識別輸入符號串是否為一個句子(合法程序，語句，表達式等)詞法掃描器語法分析器語義處理單詞符號語法樹4.1語法分析的功能4.1語法分析器的功能任務(wù)詞法掃描器語法分析器語義處理單詞符設(shè)計思想判斷是否能從文法的開始符號出發(fā)推導出這個輸入串或者,判斷能否建立一棵與輸入串匹配的語法分析樹輸入單詞符號串輸出語法分析樹格式化的程序合法的表達式、語句、函數(shù)出錯處理要求盡快發(fā)現(xiàn)錯誤，準確定位可能時進行恢復處理，繼續(xù)語法分析4.1語法分析的功能設(shè)計思想4.1語法分析的功能根據(jù)建立方法，語法分析算法可分為兩大類:自上而下分析法從文法的開始符號出發(fā)，反復使用各種產(chǎn)生式向下推導，尋找與輸入符號串匹配的推導自下而上分析法從輸入串開始，逐步進行歸約，直至歸約到文法的開始符號兩種方法反映了兩種不同的語法樹的構(gòu)造過程自上而下——從樹根推導到樹葉自下而上——從樹葉歸約到樹根4.1語法分析的功能根據(jù)建立方法，語法分析算法可分為兩大類:4.1語法分析的功能4.2自上而下分析面臨的問題基本方法對任何輸入串,試圖從文法的開始符號出發(fā)，自上而下地為輸入串建立一棵語法樹或者說，為輸入串尋找一個最左推導過程本質(zhì)是一種試探過程，是反復使用不同產(chǎn)生式謀求匹配輸入串的過程如何選擇哪個產(chǎn)生式進行推導?4.2自上而下分析面臨的問題4.2自上而下分析面臨的問題基本方法4.2自上而下分析面臨例文法G[S]S→xAyA→ab|a

判斷輸入串w=xay是否為該文法的句子？SxAy試探ab失敗回溯a試探成功分析結(jié)束SxAy==>xay==>問題產(chǎn)生回溯的原因是什么?4.2自上而下分析面臨的問題例文法G[S]S→xAyA→ab|aSxAy試探公共左因子——產(chǎn)生回溯例文法G:S→xAyA→ab|a無法確定非終結(jié)符A面臨輸入符號a時選用哪個關(guān)于A的候選式左遞歸——無限循環(huán)例文法G:S→Sa|abaw=abaaaSSaSa…無法確定何時用S→aba產(chǎn)生式進行推導某些文法導致自上而下分析具有不確定性4.2自上而下分析面臨的問題公共左因子——產(chǎn)生回溯w=abaaaSSaSa…無法確定4.3LL(1)分析法為了構(gòu)造不帶回溯的自上而下分析算法消除文法的左遞歸消除回溯、提取左因子LL(1)分析條件LL(1)文法4.3LL（1）分析法4.3LL(1)分析法為了構(gòu)造不帶回溯的自上而下分析算法4.3.1左遞歸的消除關(guān)于非終結(jié)符P的規(guī)則直接左遞歸定義：若P→Pα｜βα、β∈Ｖ*例如E→E+T｜T（含有E的左遞歸）

T→T*F｜F（含有T的左遞歸）

F→(E)｜i4.3LL（1）分析法4.3.1左遞歸的消除關(guān)于非終結(jié)符P的規(guī)則4.3LL（間接左遞歸定義：若P==+>Pαα∈Ｖ*例如間接左遞歸

S→AaA→Sb|bS==>Aa==>Sba即S==+>Sb用S的產(chǎn)生式右部替換A右部的S得：

A→Aab|b

變成A的產(chǎn)生式含有直接左遞歸4.3LL（1）分析法間接左遞歸定義：4.3LL（1）分析法消除直接左遞歸的方法改寫為等價的右遞歸形如：P→Pα｜β

α非ε，β不以P開始

改寫為：P→βP’（P’為新增加的非終結(jié)符）

P'→αP'｜ε改寫前產(chǎn)生式可產(chǎn)生短語P==>Pα==>βα

改寫后產(chǎn)生式可產(chǎn)生短語

P==>βP’

==>βαP'

==>βα

等價4.3LL（1）分析法消除直接左遞歸的方法改寫為等價的右遞歸等價4.3LL（E→E+T｜TT→T*F｜FF→(E)｜iE→TE'E'→+TE'｜εT→FT'T'→*FT'｜εF→(E)｜i4.3LL（1）分析法E→E+T｜TE→TE'4.3LL（1）分消除多個直接左遞歸若有多個左遞歸的產(chǎn)生式如：P→Pα1|Pα2|…|Pαm|β1|β2|…|βn消除左遞歸后變?yōu)椋?/p>

P→β1P’|β2P’|…|βnP’ P’→α1P’|α2P’|…|αmP’|ε消除左遞歸要求文法：

1.無回路（A==*>A）

2.無空產(chǎn)生式（A→ε）4.3LL（1）分析法消除多個直接左遞歸若有多個左遞歸的產(chǎn)生式如：消除左遞歸后變?yōu)榫毩暲缬形姆ǎ?/p>

K→Ka|Kb|Kc|d|e

消除左遞歸后變?yōu)椋?/p>

K→dK’|eK’

K’→aK’|bK’|cK’|ε4.3LL（1）分析法練習例如有文法：消除左遞歸后變?yōu)椋?.3LL（1）分析法間接左遞歸消除舉例S→Qc｜cQ→Rb｜b

R→Sa｜aS=>Qc=>Rbc=>Sabc

是間接左遞歸消除方法1：將非終結(jié)符排序：

RQS將R的右部代入Q，S：

Q→Sab｜ab｜bS→Qc｜c（不變）將Q的右部代入S：

S→Sabc｜abc｜bc｜c消除S的直接左遞歸：

S→abcS’｜bcS’|cS’S’→abcS’|εQ→Sab｜ab|bR→Sa｜a整理化簡：刪除Q，R（無用）消除左遞歸后得：

S→abcS’｜bcS’|cS’S’→abcS’|ε4.3LL（1）分析法間接左遞歸消除舉例S→Qc｜c將Q的右部代入S：4.

S→Qc｜cQ→Rb｜b

R→Sa｜a消除方法2：將非終結(jié)符排序：

SQR將S的右部代入Q，R：

Q→Rb｜b（不變）

R→Qca｜ca|a將Q的右部代入R：

R→Rbca｜bca|ca|a消除R的直接左遞歸：

R→bcaR’｜caR’|aR’

R’→bcaR’|ε

整理化簡：S，Q（有用）消除左遞歸后得：

S→Qc｜cQ→Rb｜bR→bcaR’｜caR’|aR’R’→bcaR’|ε4.3LL（1）分析法S→Qc｜c將Q的右部代入R：4.3LL（1）分消除左遞歸算法1.以某種S順序?qū)⑽姆ǖ姆墙K結(jié)符排列

P1，P2，…,Pn

2.FORi:=1TOnDOBEGINFORj:=1TOi-1DO

把形如Pi→Pjγ的規(guī)則改寫成

Pi→δ1γ|δ2γ|…|δkγ,其中

Pj→δ1|δ2|…|γ是關(guān)于Pj的所有規(guī)則;

消除Pi的直接左遞歸

END3.化簡由2所得的文法，即去除那些從開始符號出發(fā)永遠無法到達的非終結(jié)符的產(chǎn)生式當非終結(jié)符的排列順序不同時，變換后的文法形式可能不同，但是它們都和原文法是等價的4.3LL（1）分析法消除左遞歸算法1.以某種S順序?qū)⑽姆ǖ姆墙K結(jié)符排列當非終結(jié)符4.3.2消除回溯、提左因子消除回溯目的對文法的任何非終結(jié)符，當它去匹配輸入串時，能夠根據(jù)輸入符號，準確地選擇合適的候選式去匹配若需要非終結(jié)符A去匹配輸入串，A的候選式為A→α1|α2|…|αn

，

A所面臨的第一個輸入符號為a時，A能準確地選擇αi去執(zhí)行匹配任務(wù)，則無需回溯4.3LL（1）分析法4.3.2消除回溯、提左因子消除回溯目的4.3LL（1提取公共左因子方法對于所有形如A→αβ1｜αβ2｜...｜αβn｜γ的規(guī)則其中，α為左因子，γ不以α開頭改寫為A→αA'｜γ其中A’為新增加的非終結(jié)符

A'→β1｜β2｜...｜βn例如

S→xAyA→ab|a提左因子后變換為

S→xAy

A→aA