程序設(shè)計語言與編譯原理-自上而下的語法分析課件

語法分析對無關(guān)文法G=(VT，VN，S，P)及符號串ω，判斷ω是否是文法G的一個合法句子。即

S*=>w？

語法分析對無關(guān)文法G=(VT，VN，S，P)及符號串ω，判斷符號串（二元式流）正確句子的語法樹報告語法錯誤語法分析程序第七章自上而下的語法分析第一節(jié)引言一.語法分析的功能符號串（二元式流）正確句子的語法樹報告語法錯誤語法分析程序第語法分析:自上而下(自頂而下)

自下而上(自底而上)二.語法分析方法的分類自上而下語法分析法:或從開始符號出發(fā),找最左推導(dǎo);或從根開始,構(gòu)造推導(dǎo)樹。自下而上語法分析法:從輸入串開始,歸約,直至文法開始符。語法分析:自上而下(自頂而下)二.語法分析方法的分類自自上而下的語法分析分析過程從文法開始符出發(fā)，能否找到一個最左推導(dǎo)序列，使得S=>*w

；或者從根結(jié)點(diǎn)S開始，根據(jù)最左推導(dǎo)，能否構(gòu)造一棵語法樹，使得該語法樹的葉結(jié)點(diǎn)自左至右的連接正好是ω。給定文法G=(VT,

VN,S，P)以及輸入串wVT*,自上而下的語法分析分析過程給定文法G=(VT,VN,S，自下而上的語法分析分析過程從ω出發(fā)，能否找到一個最左規(guī)約（最右推導(dǎo)的逆過程）序列，逐步向上規(guī)約，直至文法的開始符S；或者對生成ω的語法樹，按最左規(guī)約對語法樹進(jìn)行剪枝，能否最后只剩下根結(jié)點(diǎn)S。給定文法G=(VT,

VN,S，P)以及輸入串wVT*,自下而上的語法分析分析過程給定文法G=(VT,VN,S，自上而下的語法分析可分為不確定和確定的兩類。回溯分析法是不確定的分析方法。遞歸下降分析法和預(yù)測分析法屬于確定的分析方法。自上而下的語法分析可分為不確定和確定的兩類。第二節(jié)回溯分析法一.一個實(shí)例S→xAyA→ab│a輸入串為xay,說明分析過程。xAyabSxAyaS從文法的開始符號S出發(fā)，選取S的候選式進(jìn)行推導(dǎo)，接著按最左推導(dǎo)進(jìn)行下去；如果推導(dǎo)失敗，再換用其他的候選式；若窮盡所有的候選式都失敗，則表明w不是G的句子，w存在語法錯語。第二節(jié)回溯分析法一.一個實(shí)例S→xAyxAya

(1)公共左因子的存在

A→1|2(2)左遞歸

A→Aα或AAα+二.存在的問題—回溯直接左遞歸間接左遞歸(3)ε產(chǎn)生式可能產(chǎn)生回溯的原因有+二.存在的問題—回溯直接左遞歸間接左遞歸(3(1)公共左因子公共左因子，是指在文法的產(chǎn)生式集合中，某個非終結(jié)符的多個候選式具有相同的前綴。一般，公共左因子的產(chǎn)生式為

A→αβ1│αβ2(1)公共左因子公共左因子，是指在文法的產(chǎn)生式集合中，某個存在公共左因子采取試探的方法來分析每一個候選式，分析的過程很可能產(chǎn)生回溯。若所有的候選式都沒有公共左因子就可以選擇惟一匹配的候選式，不會產(chǎn)生回溯。

存在公共左因子采取試探的方法來分析每一個候選式，分析的過程很(2)左遞歸左遞歸的形式為

A=>+Aβ特別地

A=>Aβ

就是直接左遞歸(2)左遞歸左遞歸的形式為例子:S→SaS→b文法G(s)：符合串baa的推導(dǎo)過程。SbSaSbaSaSSb例子:S→Sa文法G(s)：符合串baa的推導(dǎo)過程。Sε產(chǎn)生式S→aASS→bA→bASA→ε文法G(S)：輸入串a(chǎn)b的推導(dǎo)過程。SAaSAbSSAaSεbε產(chǎn)生式S→aAS文法G(S)：輸入串a(chǎn)b的推導(dǎo)過程。S

例：將文法S→xAyA→ab│a改造成：S→xAyA→aBB→b│xay的推導(dǎo)過程如右圖SxAyaB

三.解決回溯：提取公共左因子例：將文法SxAyaB三

一般方法A→1|2|…|n|δ提取公共左因子A→B|δB→1|2|…|n產(chǎn)生式：一般方法A→1|2|…|n|δ提取公共左因子

四.消除左遞歸1.消除直接左遞歸改寫為PPα|Pβ|γPγP’P’αP’|βP’|P→P’P’→αP’│εP→Pα│β改寫為PPα|β|γ改寫為P

βP’|γP’P’αP’|四.消除左遞歸1.消除直接左遞歸改寫為PPα|Pβ|γP一般地:

A→A1|A2|…|Am|1|2|…|n

（iε，j不以A開頭）改寫為:A→1P’│2P’│...│nP’P’→1P’│2P’│...│mP’│ε

一般地:A→A1|A2|…|Am|1|2|…|一般而言，假定P相關(guān)的全部產(chǎn)生式是

P→P1|P2|…|Pm|1|2|…|n其中，每個都不等于，每個都不以P開頭那么，消除P的直接左遞歸性就是把這些規(guī)則改寫成：

P→1P|2P|…|nP P→1P|2P|…|mP|左遞歸變右遞歸一般而言，假定P相關(guān)的全部產(chǎn)生式是左遞歸變右遞歸例文法G(E):E→E＋T|TT→T*F|FF→(E)|i經(jīng)消去直接左遞歸后變成：

E→TEE→+TE|

T→FTT→*FT|F→(E)|i (4.2)P→P1|P2|…|Pm

|1|2|…|nP→1P|2P|…|nPP→1P|2P|…|mP|例文法G(E):(4.2)P→P1|P2|…例如文法G(S):S→Qc|cQ→Rb|bR→Sa|a (4.3)雖沒有直接左遞歸，但S、Q、R都是左遞歸的SQcRbcSabc例：設(shè)文法G(A):A→Ac|Aad|bd|e消去直接左遞歸：A→bdA’|eA’A’→cA’|adA’|例如文法G(S):例：設(shè)文法G(A):

2.間接左遞歸的消除PPα+例子：A→Bc│aB→AbA→Abc│aA→aP’P’→bcP’│ε改為：2.間接左遞歸的消除PPα+例子：A→Abc

算法1.將文法G的所有非終結(jié)符按任一順序排列，設(shè)為A1,…,An2.執(zhí)行下面算法，消除可能的左遞歸：fori:=1tondoforj:=1toi-1dobegin

把一個形如AiAj的產(chǎn)生式改寫為

Aiδ1|δ2|…|δk

其中Ajδ1|δ2|…|δk是Aj的所有產(chǎn)生式;

消除Ai產(chǎn)生式的直接左遞歸;end3.化簡：刪除多余產(chǎn)生式，即在從文法開始符號的

任何推導(dǎo)中都不會出現(xiàn)的非終結(jié)符的產(chǎn)生式；算法1.將文法G的所有非終結(jié)符按任一順序排列，設(shè)為A1,…以S→Qc│cQ→Rb│bR→Sa│a為例,按S,Q,R排列,或R,Q,S排列以S→Qc│c

S→Qc|cQ→Rb|bR→Sa|a步驟：1.將非終結(jié)符按R，Q，S排列2.執(zhí)行算法i=1沒有操作i=2,j=1，Ai=Q,Aj=R,有Q→Rb|b把R→Sa|a代入上式得:Q→Sab|ab|b該式無直接左遞歸i=3,j=2，Ai=S,Aj=Q，S→Qc|c將上面得到的Q的產(chǎn)生式代入得：S→Sabc|abc|bc|c消除上式的直接左遞歸得：

S→abcS’|bcS’|cS’S’→abcS’|i=3,j=1，Ai=S,Aj=R，無相應(yīng)產(chǎn)生式，沒有操作3.化簡：經(jīng)過上述算法，Q和R的產(chǎn)生式為多余的產(chǎn)生式，可刪除。最后得：S→abcS’|bcS’|cS’S’→abcS’|S→Qc|c步驟：1.將非終結(jié)符按R，Q，S排列2.執(zhí)行算1.按R、Q、S排列,代入后

R→Sa│aQ→Sab│ab│bS→Sabc│abc│bc│cS→Qc│cQ→Rb│bR→Sa│a2.消除S中的直接左遞歸文法產(chǎn)生的語言:(abc|bc|c)(abc)*S→abcS’│bcS’│cS’S’→abcS’│

1.按R、Q、S排列,代入后S→Qc│c2.消除S中的直接1.按S、Q、R排列,代入后

S→Qc│cQ→Rb│bR→Qca│ca│aR→Rbca│bca│ca│aS→Qc│cQ→Rb│bR→Sa│a2.消除R中的直接左遞歸

R→bcaR’│caR’│aR’R’→bcaR’│文法產(chǎn)生的語言:(bca|ca|a)(bca)*bc|bc|c

1.按S、Q、R排列,代入后S→Qc│c2.消除R中的直接文法產(chǎn)生的語言:(bca|ca|a)(bca)*bc|bc|c文法產(chǎn)生的語言:(abc|bc|c)(abc)*

文法產(chǎn)生的語言:(bca|ca|a)(bca)*bc|bc|對于文法G=（{a,b,c,d,},{S,A},S,P）;其中P為:S→Aa|Ac|bcA→Ad|Sbc|d請先提取文法G的公共左因子，再消除左遞歸。練習(xí)對于文法G=（{a,b,c,d,},{S,A},S,P）;練提取公共左因子S→AB|bcB→a|cA→Ad|Sbc|d

S→Aa|Ac|bcA→Ad|Sbc|d直接左遞歸S→AB|bcB→a|cA→SbcP|dPP→dP|間接左遞歸S→AB|bcB→a|cA→ABbcP|bcbcP|dPP→dP|間接左遞歸S→AB|bcB→a|cA→bcbcPQ|dPQQ→BbcPQ|P→dP|提取公共左因子S→Aa|Ac|bc直接左遞歸間接左遞歸回顧

1.語法分析功能2.兩大類3.回溯分析1.自上而下(自頂而下)2.自下而上(自底而上)a.公共左因子b.左遞歸c.空產(chǎn)生式回顧1.語法分析功能2.兩大類3.回溯分析1.自上而下(自

當(dāng)文法改造為無公共左因子,無左遞歸時,讓每個非終結(jié)符對應(yīng)一個過程，該過程對相應(yīng)的非終結(jié)符產(chǎn)生式的右部短語進(jìn)行語法分析，這種分析方法稱為遞歸下降分析法。這樣的分析程序稱為遞歸下降分析器。第三節(jié)遞歸下降分析法當(dāng)文法改造為無公共左因子,無左遞歸時,讓每個非終結(jié)符對應(yīng)一例:G(E)E→E+T│TT→T*F│FF→(E)│i消除左遞歸:E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│i

一.分析方法例:G(E)E→E+T│T消除左遞歸:E→T過程advance:匹配并把輸入串指針后移一位變量sym:輸入指針指向的符號Error():出錯處理函數(shù)

procedureadvance(t:token);beginifsym==tthensym=nexttokenelseerror（）end;

過程advance:匹配并把輸入串指針后移一位procedureE;beginT;E’end;procedureT;beginF;T’end;E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iprocedureE’;ifsym=‘+’thenbeginadvance(‘+’);T;E’end;procedureT’;ifsym=‘*’thenbeginadvance(‘*’);F;T’end;

procedureE;procedureT;E→TE’E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iprocedureF;ifsym=‘i’thenadvance(‘i’)elseifsym=‘(’thenbegin

advance(‘(’);E;ifsym=‘)’thenadvance(‘)’)elseerror()endelseerror();

E→TE’E’→+TE’│εprocedi+i*i#的遞歸下降分析過程E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iETTiiiii+++++**######FM(i)FM(i)FM(i)E’M(+)T’M()E’M()#T’M()#T’M(*)M()

i+i*i#的遞歸下降分析過程E→TE’ETTiiiii++

二.擴(kuò)充的BNF用花括號{α}表示閉包運(yùn)算α*;α可以重復(fù)任意多次用{α}表示α可任意重復(fù)0次至n次

{α}=α0=ε;用[α]表示{α},即[α]表示α的出現(xiàn)可有可無(等價于α│ε)；1.表示形式n00010二.擴(kuò)充的BNF用花括號{α}表示閉包運(yùn)算α*;1.表示例一：標(biāo)識符的定義利用擴(kuò)充BNF表示為E→T{+T}T→F{*F}F→i|(E)E→E+T│TT→T*F│FF→(E)│i例二：文法I→L│LSS→T│STT→L│DL→a│b│...│zD→0│1│2│...│9I→L{L|D}L→a|b|…|zD→0|1|…|9

例一：標(biāo)識符的定義利用擴(kuò)充BNF表示為E→T{+T}E→E+

decimal→[sign]integer.{digit}[exponent]exponent→E[sign]integerinteger→digit{digit}sign→+│-digit→0│1│…│9例三：實(shí)數(shù)可定義為

例三：實(shí)數(shù)可定義為p→x│y│…│z│pv改寫成:p→(x│y│…│z){v}2.左遞歸的消除

p→x│y│…│z│pv2.左遞歸的消除3.文法的轉(zhuǎn)換圖表示E→T{+T}T→F{*F}F→i|(E)E→E+T│TT→T*F│FF→(E)│i+012T關(guān)于E的轉(zhuǎn)換圖012F*關(guān)于T的轉(zhuǎn)換圖013（）i2E關(guān)于F的轉(zhuǎn)換圖

3.文法的轉(zhuǎn)換圖表示E→T{+T}E→E+T│T+012TprocedureE;BeginT;whilesym=’+’dobeginadvance(‘+’);TendendE→T{+T}+012T關(guān)于E的轉(zhuǎn)換圖E→T{+T}T→F{*F}F→i|(E)三.改進(jìn)的遞歸下降分析法F

procedureE;E→T{+T}+012T關(guān)于E的轉(zhuǎn)procedureT;beginF;whilesym=’*’dobeginadvance(‘*’);Fendend;T→F{*F}012F*關(guān)于T的轉(zhuǎn)換圖

procedureT;T→F{*F}012F*關(guān)于T的轉(zhuǎn)procedureF;ifsym=‘i’thenadvance(‘i’)elseifsym=‘(’thenbeginadvance(‘(’);E;ifsym=‘)’thenadvance(‘)’)elseerrorendelseerror；013（）i2E關(guān)于F的轉(zhuǎn)換圖F→i|(E)

procedureF;013（）i2E關(guān)于F的轉(zhuǎn)換圖F→ii+i*i#的遞歸下降分析過程E→T{+T}T→F{*F}F→(E)│iETTFFFiii++i##i*M(i)M(*)M(i)M(+)M(i)

i+i*i#的遞歸下降分析過程E→T{+T}ETTFFFii

第四節(jié)預(yù)測分析法

預(yù)測分析（LL(1)分析法）是一種表驅(qū)動方法，由下推棧、預(yù)測分析表和控制程序組成。它實(shí)際上一種下推自動機(jī)的實(shí)現(xiàn)模型。第四節(jié)預(yù)測分析法預(yù)測分析（LL(1)分析法）是一種LL(1)分析法是一種不帶回溯的非遞歸自上而下分析法。

LL(1)的含義:

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

LL(1)分析法的基本思想:

根據(jù)輸入串的當(dāng)前輸入符確定選用某一個產(chǎn)生式進(jìn)行推導(dǎo),當(dāng)該輸入符與推導(dǎo)的第一個符號相同時，再取輸入串的下一個符號,繼續(xù)確定下一個推導(dǎo)應(yīng)選的產(chǎn)生式,如此下去,直到推出被分析的輸入串為止。一個LL(1)分析器由一張LL(1)分析表(預(yù)測分析表)、一個先進(jìn)后出分析棧和一個控制程序(表驅(qū)動程序)組成。程序設(shè)計語言與編譯原理_自上而下的語法分析課件a1a2…ai…an#分析表M控制程序輸入串：棧頂#x1…xj輸出分析棧圖LL(1)分析器a1a2…ai…an#分析表M控制程序輸入串：棧頂#x1…x對圖

的LL(1)分析器說明如下：

(1)輸入串是待分析的符號串,它以“#”作為結(jié)束標(biāo)志。(注:#∈VT但不是文法符號,是由分析程序自動添加的)(2)分析棧存放分析過程中的文法符號。分析開始時棧底先放一個“#”,再壓入文法開始符;當(dāng)分析棧中僅?！?”且輸入串指針指向串尾的“#”時,分析成功。對圖的LL(1)分析器說明如下：

(3)分析表用一個矩陣M(二維數(shù)組)表示,它概括了文法的全部信息。矩陣的每一行與文法的一個非終結(jié)符相關(guān)聯(lián),而每一列與文法的一個終結(jié)符或“#”關(guān)聯(lián)。分析表元素M[A,a]中的內(nèi)容為一條A的產(chǎn)生式,表明當(dāng)A面臨輸入符a時應(yīng)采用的候選式;當(dāng)元素內(nèi)容為空時,表明A不應(yīng)面臨輸入符a,即輸入串含語法錯誤。(3)分析表用一個矩陣M(二維數(shù)組)表示,它(4)控制程序根據(jù)分析棧棧頂符號x和當(dāng)前輸入符a決定分析器的動作:①若x＝a＝“#”,則分析成功。②若x＝a≠“#”,即棧頂符號x與當(dāng)前輸入符a匹配,則將x從棧頂彈出,輸入串指針后移,繼續(xù)對下一個字符進(jìn)行分析。③若x為非終結(jié)符A,則查分析表M[A,a]:i.若M[A,a]為一產(chǎn)生式,則A自棧頂彈出,M[A,a]中產(chǎn)生式的右部符號逆序壓棧;若M[A,a]為A→ε,則只將A自棧頂彈出。

ii.若M[A,a]為空,則發(fā)現(xiàn)語法錯誤,調(diào)用出錯處理程序進(jìn)行處理。(4)控制程序根據(jù)分析棧棧頂符號x和當(dāng)控制程序描述如下:

將“#”和文法開始符依次入棧;

把第一個輸入符讀入a;do{把棧頂符號彈出并放入x中;if(x∈VT){if(x＝＝a)將下一輸入符讀入a;elseerror();}elseif(M[x,a]＝＝“x→y1y2…yk”){把y1y2…yk按逆序入棧;

輸出“x→y1y2…yk”;}elseerror();}while(x!=“#”)控制程序描述如下:一.預(yù)測分析過程1.預(yù)測分析表形式:M[A,a]矩陣,AVN,aVT{#}

內(nèi)容:A→α或出錯標(biāo)志(空白表示)

一.預(yù)測分析過程1.預(yù)測分析表預(yù)測分析表EE’TT’Fi+*()#E→TE’E→TE’E’→+TE’T→FT’T→FT’T’→*FT’F→iF→(E)E’→εE’→εT’→εT’→εT’→εE→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│i

預(yù)測分析表EE’TT’Fi+*()#E→TE’E→TE’E’2.分析方法初始時,#和開始符入棧,輸入指針指向第一個符號,然后根據(jù)下推棧棧頂符x和當(dāng)前輸入符a進(jìn)行工作:①x=a=#,成功②x=a#,匹配③xVN,查表并把產(chǎn)生式右部符號按逆序推進(jìn)棧

2.分析方法初始時,#和開始符入棧,輸入指針指向第一個符號,例：文法G2’E→TE’E’→+TE’|T→FT’T’→*FT’|F→(E)|i如何對輸入串i+i*i按照預(yù)測分析法進(jìn)行語法分析?

例：文法G2’如何對輸入串i+i*i按照預(yù)測分析法進(jìn)行語法分下推棧輸入串查分析表i+i*i##E#E’T#E’T’F#E’T’#E’T’i#E’#E’T#E’T+i+i*i#+i*i#i+i*i#i+i*i#+i*i#+i*i#i*i#E→TE’T→FT’T→FT’F→iT’→εE’→+TE’

匹配匹配下推棧輸入串查分析表i+i*i##E#E’T#E’T’F#E#E’T’Fi*i##E’T’i#E’T’#E’T’F*#E’T’i#E’T’F#E’T’##E’*i#i#*i#i####T’→*FT’結(jié)束F→iT’→εi*i#F→iE’→ε

匹配匹配匹配#E’T’Fi*i##E’T’i#E’T’#E’T’例7

一個文法的LL(1)分析表如下所示,

試給出輸入串a(chǎn)adl的分析過程。輸入串a(chǎn)adl的分析過程如下:例7一個文法的LL(1)分析表如下所示,輸入串a(chǎn)adl的符號棧當(dāng)前輸入符輸入串說明

#Aaadl#彈出棧頂符,將A→aA'右部反序壓棧

#A'aaadl#匹配,彈出棧頂符a,讀出下一輸入符a

#A'a

dl#彈出棧頂符,將A'→ABl右部反序壓棧

#lBAa

dl#彈出棧頂符,將A→aA'右部反序壓棧#lBA'aa

dl#匹配,彈出棧頂符a,讀出下一輸入符d

#lBA'd

l#由A'→ε僅彈出棧頂符號A'

#lBd

l#彈出棧頂符,將B→dB'右部反序壓棧

#lB'dd

l#匹配,彈出棧頂符d,讀出下一輸入符l

#lB'l

#由B'→ε僅彈出棧頂符號B'

#ll

#匹配,彈出棧頂符l,讀出下一輸入符#

##

匹配,分析成功符號棧當(dāng)前輸入符輸入串說明#Aaadl#內(nèi)容回顧預(yù)測分析

1.下推堆棧2.總控程序3.預(yù)測分析表總控程序①x=a=#,成功②x=a#,匹配③xVN,查表內(nèi)容回顧預(yù)測分析1.下推堆棧2.總控程序3.預(yù)測分析表總控6363基本思想是:當(dāng)文法中某一非終結(jié)符呈現(xiàn)在棧頂時,根據(jù)當(dāng)前的輸入符號,分析表應(yīng)指示要用該非終結(jié)符里的哪一條規(guī)則取匹配輸入串(即進(jìn)行下一步最左推導(dǎo))

根據(jù)這個思想,我們不難把構(gòu)造分析表算法構(gòu)造出來!終結(jié)符號非終結(jié)符號分析表M[A，a]的構(gòu)造6363基本思想是:終結(jié)符號非終結(jié)符號分析表M[A，a]的分析表M[A，a]的構(gòu)造構(gòu)造FIRST()和FOLLOW(A)構(gòu)造分析表M[A，a]分析表M[A，a]的構(gòu)造構(gòu)造FIRST()和FOLLOW(二.FIRST集和FOLLOW集1.FIRST集定義:假定是文法任一符號串,對α(VTVN)*,有

FIRST（α）＝{a|αa...,aVT}.

若αε,則εFIRST(α）**即FIRST()是的所有可能推出的首終結(jié)符或可能的ε組成的集合。*二.FIRST集和FOLLOW集1.FIRST集定義:假

FIRST集的構(gòu)造方法對每個文法符號XVTVN，連續(xù)使用入下規(guī)則，直到每個FIRST(X)不再增大XVT,則FIRST(X)={X};XVN,分三種情形:1.Xa…2.XY…3.XY1Y2…YkFIRST集的構(gòu)造方法對每個文法符號XVTVN，連續(xù)使1.若有X→a…,把a(bǔ)加入FIRST(X);

若有X→ε,把ε加入FIRST(X);2.若有X→Y…,Y∈VN,把FIRST(Y)的

所有非ε元素都加入FIRST(X);3.若有X→Y1Y2…Yk,而Y1~Yi?1都有ε,

則把FIRST(Yj)(j=1,2,…,i)的所有非

ε元素都加入FIRST(X);

特別地,若Y1～Yk均有ε產(chǎn)生式,

則把ε也加入到FIRST(X)。1.若有X→a…,把a(bǔ)加入FIRST(X);

首先把FIRST(X1)-{}加入FIRST()；若對任何1ji-1,FIRST(Xi),則把FIRST(Xi)加入FIRST()中；如果所有FIRST(Xi)均包含，則把加入FIRST()中=X1X2…XnXiV,i=1,2,3,...n首先把FIRST(X1)-{}加入FIRST()；=例:G(E)E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iEE’TT’FFIRST(i(i(i+*

FIRST(E')={+,ε};FIRST(T')={*,ε};FIRST(F)＝{(,i};

由T→F…知,把FIRST(F)的所有非ε元素加入FIRST(T),故FIRST(T)={(,i};

由E→T…知,把FIRST(T)的所有非ε元素加入FIRST(E),故FIRST(E)={(,i}例:G(E)E→TE’EE’TT’FFIRST(FIRST(Y1)={y1,}FIRST(Y2)={y2,}FIRST(A)={a}FIRST(X)={y1,y2,a}例子：XY1Y2AY1y1│Y2y2│Aa

FIRST(Y1)={y1,}例子：XY1Y2A

定義:對AVN,有

FOLLOW(A)={a│S...Aa...,aVT}

若S...A,則規(guī)定#FOLLOW(A),其中S為開始符號.**2.Follow集FOLLOW(A)是所有句型中出現(xiàn)在緊隨A之后的終結(jié)符或#。定義:對AVN,有**2.Follow集FOL#FOLLOW(S)A→αBβ:將FIRST()-{}加入FOLLOW(B)A→αB:將FOLLOW(A)加入FOLLOW(B)A→αBβ且βε:將FOLLOW(A)加入FOLLOW(B)*求法注意:求FOLLOW(B)實(shí)際上是考察B在產(chǎn)生式右端的每一次出現(xiàn)

#FOLLOW(S)*求法注意:求FOLLOW(B)FOLLOW(X)={#}FOLLOW(Y1)={y2,a}FOLLOW(Y2)={a}FOLLOW(A)={#}例子：XY1Y2AY1y1│Y2y2│Aa

FOLLOW(X)={#}例子：XY1Y2A例:G(E)E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iEE’TT’FFIRST(i(i(i+*

例:G(E)E→TE’EE’TT’FFIRST(試構(gòu)造文法G[E]的FOLLOW集。解:1)FOLLOW(E)={#};2)由E→TE'知,FIRST(E')\{ε}屬于FOLLOW(T),

即FOLLOW(T)＝{+};{由E'→+TE'|ε,FIRST(E')\{ε}屬于…}

由T→FT'知,FIRST(T')\{ε}屬于FOLLOW(F),

即FOLLOW(F)＝{*};{由T'→*FT'|ε知,FIRST(T')\{ε}屬于…}

由F→(E)|i知,FIRST(')')屬于FOLLOW(E),

即FOLLOW(E)＝{),#};試構(gòu)造文法G[E]的FOLLOW集。3)由E→TE'知,FOLLOW(E)屬于FOLLOW(E'), 即FOLLOW(E')＝{),#};

由E→TE'且E'→ε知, FOLLOW(E)屬于FOLLOW(T),

即FOLLOW(T)＝{+,),#};

{由E'→+TE'知,FOLLOW(E')屬于FOLLOW(E')}{由E'→+TE'且E'→ε知,FOLLOW(E')屬于FOLLOW(T)}3)由E→TE'知,

由T→FT'知,FOLLOW(T)屬于FOLLOW(T')，

即FOLLOW(T')＝{+,),#};

由T→FT'且T'→ε知,FOLLOW(T)屬于FOLLOW(F),

即FOLLOW(F)＝{*,+,),#}；

{由T'→*FT'

知,FOLLOW(T')屬于FOLLOW(T')}{由T'→*FT'且T'→ε知,FOLLOW(T')屬于FOLLOW(F)}{考慮F→(E)|i}由T→FT'知,例:G(E)E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iEE’TT’FFIRSTFOLLOW(i(i(i+*)#)#+)#+)#*+)#

例:G(E)E→TE’EE’TT’FFIRSTFOL練習(xí):S->ABA->Ab|εB->a|ε試求出S、A、B的FIRST和FOLLOW集。SABFIRSTFOLLOWaba

b#b##練習(xí):S->ABSABFIRSTFOLLOWab練習(xí):G=（{a,b,c,（,）},{S,A,B},S,P）,P為S->bAbA->(B|a|εB->Aa)|Ac)練習(xí):G=（{a,b,c,（,）},{S,A,B},S,P設(shè)上下文無關(guān)文法G的產(chǎn)生式形如A→1|2|…|n,當(dāng)G滿足下述條件時則稱為LL(1)文法:①FIRST(i)FIRST(j)=Φ,ij,i,j=1,2,...,n②若i,則FIRST(j)FOLLOW(A)=Φ,ji，j=1,2,...,n

于是,在自頂向下分析時,可根據(jù)當(dāng)前輸入符號a選擇aFIRST(i)的A→i。*三.LL(1)文法

設(shè)上下文無關(guān)文法G的產(chǎn)生式形如A→1|2|…|n,當(dāng)在自上而下分析時，若當(dāng)前輸入字符為a,分析棧待匹配的非終結(jié)符為A，A→1|2|…|n，則當(dāng):aFIRST(i)，或若i,aFOLLOW(A)則A→i便是惟一與a匹配的產(chǎn)生式，即LL（1）文法中的兩個條件保證了自上而下匹配的唯一性。LL(1)文法與自上而下分析法的關(guān)系LL(1)文法與自上而下分析法的關(guān)系①對aFIRST(α),將A→α記入M[A,a]中;②若εFIRST(α),對bFOLLOW(A),

將A→α記入M[A,b]中;③凡未被定義的M[A,a]項(xiàng)中標(biāo)以出錯標(biāo)志。四.預(yù)測分析表的構(gòu)造1.構(gòu)造算法對每個產(chǎn)生式A→α

①對aFIRST(α),將A→α記入M[A,a]中;四.例:G(E)E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iEE’TT’FFIRSTFOLLOW(i(i(i+*)#)#+)#+)#*+)#

構(gòu)造過程：1）求FIRST：2）求FOLLOW3）構(gòu)造分析表例:G(E)E→TE’EE’TT’FFIRSTFOLE’→εT’→εi+*()#EE’TT’FE→TE’E→TE’E’→+TE’E’→εT→FT’T→FT’T’→εT’→*FT’T’→εF→iF→(E)注意:用上述算法可以構(gòu)造出任意給定文法的分析表,但不是所有文法都能構(gòu)造出上述那種形狀的分析表即M[A,a]=一條的規(guī)則或Error。對于能用上述算法構(gòu)造分析表的文法我們稱為LL(1)文法

3）構(gòu)造分析表FIRST(F)={(,i}FIRST(T’)={*,ε}FIRST(T)=={(,i}FIRST(E’)={+,ε}FIRST(E)=={(,i}E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iFOLLOW(E)={#,)}FOLLOW(E’)={#,)}FOLLOW(T)={+,),#}FOLLOW(T’)={+,),#}FOLLOW(F)={*,+,),#}E’→εT’→εi+*()#EE’TT’FE→TE’E→TE①M(fèi)[A,a]中只記產(chǎn)生式右部;②對α=x1x2...xn,在[M,a]中記xnxn-1...x1;③當(dāng)xnxn-1...x1的x1VT時,x1必為a,x1無須入棧,只移動輸入指針。2.預(yù)測分析表的改進(jìn)

①M(fèi)[A,a]中只記產(chǎn)生式右部;2.預(yù)測分析表的改進(jìn)

非LL(1)文法并非所有文法G都可以改寫成LL(1)文法，即使提取左公因子和消除左遞歸后，也不是LL(1)文法.例：文法G4S→iCtS|iCtSeS|aC→b提取左因子S→iCtSS’|aS’eS|C→b求FIRST和FOLLOWFIRST(S)={i,a}FIRST(S’)={e,}FIRST(C)=FOLLOW(S)=FOLLOW(S’)={e,#}FOLLOW(C)={t}求預(yù)測分析表abeit#SSaSiCtSS’S’S’eSS’S’CCb預(yù)測分析表非LL(1)文法例：文法G4提取左因子S→iCtSS’|a內(nèi)容回顧預(yù)測分析表

1.First集合2.Follow集合算First集算Follow集LL(1)文法①FIRST(i)FIRST(j)=Φ,ij,i,j=1,2,...,n②若i,則FIRST(j)FOLLOW(A)=Φ,ji，j=1,2,...,n內(nèi)容回顧預(yù)測分析表1.First集合2.Follow集合算

作業(yè)必做題：7.2，7.3，7.5作業(yè)必做題：7.2，7.3，7.5語法分析對無關(guān)文法G=(VT，VN，S，P)及符號串ω，判斷ω是否是文法G的一個合法句子。即

S*=>w？

語法分析對無關(guān)文法G=(VT，VN，S，P)及符號串ω，判斷符號串（二元式流）正確句子的語法樹報告語法錯誤語法分析程序第七章自上而下的語法分析第一節(jié)引言一.語法分析的功能符號串（二元式流）正確句子的語法樹報告語法錯誤語法分析程序第語法分析:自上而下(自頂而下)

自下而上(自底而上)二.語法分析方法的分類自上而下語法分析法:或從開始符號出發(fā),找最左推導(dǎo);或從根開始,構(gòu)造推導(dǎo)樹。自下而上語法分析法:從輸入串開始,歸約,直至文法開始符。語法分析:自上而下(自頂而下)二.語法分析方法的分類自自上而下的語法分析分析過程從文法開始符出發(fā)，能否找到一個最左推導(dǎo)序列，使得S=>*w

；或者從根結(jié)點(diǎn)S開始，根據(jù)最左推導(dǎo)，能否構(gòu)造一棵語法樹，使得該語法樹的葉結(jié)點(diǎn)自左至右的連接正好是ω。給定文法G=(VT,

VN,S，P)以及輸入串wVT*,自上而下的語法分析分析過程給定文法G=(VT,VN,S，自下而上的語法分析分析過程從ω出發(fā)，能否找到一個最左規(guī)約（最右推導(dǎo)的逆過程）序列，逐步向上規(guī)約，直至文法的開始符S；或者對生成ω的語法樹，按最左規(guī)約對語法樹進(jìn)行剪枝，能否最后只剩下根結(jié)點(diǎn)S。給定文法G=(VT,

VN,S，P)以及輸入串wVT*,自下而上的語法分析分析過程給定文法G=(VT,VN,S，自上而下的語法分析可分為不確定和確定的兩類。回溯分析法是不確定的分析方法。遞歸下降分析法和預(yù)測分析法屬于確定的分析方法。自上而下的語法分析可分為不確定和確定的兩類。第二節(jié)回溯分析法一.一個實(shí)例S→xAyA→ab│a輸入串為xay,說明分析過程。xAyabSxAyaS從文法的開始符號S出發(fā)，選取S的候選式進(jìn)行推導(dǎo)，接著按最左推導(dǎo)進(jìn)行下去；如果推導(dǎo)失敗，再換用其他的候選式；若窮盡所有的候選式都失敗，則表明w不是G的句子，w存在語法錯語。第二節(jié)回溯分析法一.一個實(shí)例S→xAyxAya

(1)公共左因子的存在

A→1|2(2)左遞歸

A→Aα或AAα+二.存在的問題—回溯直接左遞歸間接左遞歸(3)ε產(chǎn)生式可能產(chǎn)生回溯的原因有+二.存在的問題—回溯直接左遞歸間接左遞歸(3(1)公共左因子公共左因子，是指在文法的產(chǎn)生式集合中，某個非終結(jié)符的多個候選式具有相同的前綴。一般，公共左因子的產(chǎn)生式為

A→αβ1│αβ2(1)公共左因子公共左因子，是指在文法的產(chǎn)生式集合中，某個存在公共左因子采取試探的方法來分析每一個候選式，分析的過程很可能產(chǎn)生回溯。若所有的候選式都沒有公共左因子就可以選擇惟一匹配的候選式，不會產(chǎn)生回溯。

存在公共左因子采取試探的方法來分析每一個候選式，分析的過程很(2)左遞歸左遞歸的形式為

A=>+Aβ特別地

A=>Aβ

就是直接左遞歸(2)左遞歸左遞歸的形式為例子:S→SaS→b文法G(s)：符合串baa的推導(dǎo)過程。SbSaSbaSaSSb例子:S→Sa文法G(s)：符合串baa的推導(dǎo)過程。Sε產(chǎn)生式S→aASS→bA→bASA→ε文法G(S)：輸入串a(chǎn)b的推導(dǎo)過程。SAaSAbSSAaSεbε產(chǎn)生式S→aAS文法G(S)：輸入串a(chǎn)b的推導(dǎo)過程。S

例：將文法S→xAyA→ab│a改造成：S→xAyA→aBB→b│xay的推導(dǎo)過程如右圖SxAyaB

三.解決回溯：提取公共左因子例：將文法SxAyaB三

一般方法A→1|2|…|n|δ提取公共左因子A→B|δB→1|2|…|n產(chǎn)生式：一般方法A→1|2|…|n|δ提取公共左因子

四.消除左遞歸1.消除直接左遞歸改寫為PPα|Pβ|γPγP’P’αP’|βP’|P→P’P’→αP’│εP→Pα│β改寫為PPα|β|γ改寫為P

βP’|γP’P’αP’|四.消除左遞歸1.消除直接左遞歸改寫為PPα|Pβ|γP一般地:

A→A1|A2|…|Am|1|2|…|n

（iε，j不以A開頭）改寫為:A→1P’│2P’│...│nP’P’→1P’│2P’│...│mP’│ε

一般地:A→A1|A2|…|Am|1|2|…|一般而言，假定P相關(guān)的全部產(chǎn)生式是

P→P1|P2|…|Pm|1|2|…|n其中，每個都不等于，每個都不以P開頭那么，消除P的直接左遞歸性就是把這些規(guī)則改寫成：

P→1P|2P|…|nP P→1P|2P|…|mP|左遞歸變右遞歸一般而言，假定P相關(guān)的全部產(chǎn)生式是左遞歸變右遞歸例文法G(E):E→E＋T|TT→T*F|FF→(E)|i經(jīng)消去直接左遞歸后變成：

E→TEE→+TE|

T→FTT→*FT|F→(E)|i (4.2)P→P1|P2|…|Pm

|1|2|…|nP→1P|2P|…|nPP→1P|2P|…|mP|例文法G(E):(4.2)P→P1|P2|…例如文法G(S):S→Qc|cQ→Rb|bR→Sa|a (4.3)雖沒有直接左遞歸，但S、Q、R都是左遞歸的SQcRbcSabc例：設(shè)文法G(A):A→Ac|Aad|bd|e消去直接左遞歸：A→bdA’|eA’A’→cA’|adA’|例如文法G(S):例：設(shè)文法G(A):

2.間接左遞歸的消除PPα+例子：A→Bc│aB→AbA→Abc│aA→aP’P’→bcP’│ε改為：2.間接左遞歸的消除PPα+例子：A→Abc

算法1.將文法G的所有非終結(jié)符按任一順序排列，設(shè)為A1,…,An2.執(zhí)行下面算法，消除可能的左遞歸：fori:=1tondoforj:=1toi-1dobegin

把一個形如AiAj的產(chǎn)生式改寫為

Aiδ1|δ2|…|δk

其中Ajδ1|δ2|…|δk是Aj的所有產(chǎn)生式;

消除Ai產(chǎn)生式的直接左遞歸;end3.化簡：刪除多余產(chǎn)生式，即在從文法開始符號的

任何推導(dǎo)中都不會出現(xiàn)的非終結(jié)符的產(chǎn)生式；算法1.將文法G的所有非終結(jié)符按任一順序排列，設(shè)為A1,…以S→Qc│cQ→Rb│bR→Sa│a為例,按S,Q,R排列,或R,Q,S排列以S→Qc│c

S→Qc|cQ→Rb|bR→Sa|a步驟：1.將非終結(jié)符按R，Q，S排列2.執(zhí)行算法i=1沒有操作i=2,j=1，Ai=Q,Aj=R,有Q→Rb|b把R→Sa|a代入上式得:Q→Sab|ab|b該式無直接左遞歸i=3,j=2，Ai=S,Aj=Q，S→Qc|c將上面得到的Q的產(chǎn)生式代入得：S→Sabc|abc|bc|c消除上式的直接左遞歸得：

S→abcS’|bcS’|cS’S’→abcS’|i=3,j=1，Ai=S,Aj=R，無相應(yīng)產(chǎn)生式，沒有操作3.化簡：經(jīng)過上述算法，Q和R的產(chǎn)生式為多余的產(chǎn)生式，可刪除。最后得：S→abcS’|bcS’|cS’S’→abcS’|S→Qc|c步驟：1.將非終結(jié)符按R，Q，S排列2.執(zhí)行算1.按R、Q、S排列,代入后

R→Sa│aQ→Sab│ab│bS→Sabc│abc│bc│cS→Qc│cQ→Rb│bR→Sa│a2.消除S中的直接左遞歸文法產(chǎn)生的語言:(abc|bc|c)(abc)*S→abcS’│bcS’│cS’S’→abcS’│

1.按R、Q、S排列,代入后S→Qc│c2.消除S中的直接1.按S、Q、R排列,代入后

S→Qc│cQ→Rb│bR→Qca│ca│aR→Rbca│bca│ca│aS→Qc│cQ→Rb│bR→Sa│a2.消除R中的直接左遞歸

R→bcaR’│caR’│aR’R’→bcaR’│文法產(chǎn)生的語言:(bca|ca|a)(bca)*bc|bc|c

1.按S、Q、R排列,代入后S→Qc│c2.消除R中的直接文法產(chǎn)生的語言:(bca|ca|a)(bca)*bc|bc|c文法產(chǎn)生的語言:(abc|bc|c)(abc)*

文法產(chǎn)生的語言:(bca|ca|a)(bca)*bc|bc|對于文法G=（{a,b,c,d,},{S,A},S,P）;其中P為:S→Aa|Ac|bcA→Ad|Sbc|d請先提取文法G的公共左因子，再消除左遞歸。練習(xí)對于文法G=（{a,b,c,d,},{S,A},S,P）;練提取公共左因子S→AB|bcB→a|cA→Ad|Sbc|d

S→Aa|Ac|bcA→Ad|Sbc|d直接左遞歸S→AB|bcB→a|cA→SbcP|dPP→dP|間接左遞歸S→AB|bcB→a|cA→ABbcP|bcbcP|dPP→dP|間接左遞歸S→AB|bcB→a|cA→bcbcPQ|dPQQ→BbcPQ|P→dP|提取公共左因子S→Aa|Ac|bc直接左遞歸間接左遞歸回顧

1.語法分析功能2.兩大類3.回溯分析1.自上而下(自頂而下)2.自下而上(自底而上)a.公共左因子b.左遞歸c.空產(chǎn)生式回顧1.語法分析功能2.兩大類3.回溯分析1.自上而下(自

當(dāng)文法改造為無公共左因子,無左遞歸時,讓每個非終結(jié)符對應(yīng)一個過程，該過程對相應(yīng)的非終結(jié)符產(chǎn)生式的右部短語進(jìn)行語法分析，這種分析方法稱為遞歸下降分析法。這樣的分析程序稱為遞歸下降分析器。第三節(jié)遞歸下降分析法當(dāng)文法改造為無公共左因子,無左遞歸時,讓每個非終結(jié)符對應(yīng)一例:G(E)E→E+T│TT→T*F│FF→(E)│i消除左遞歸:E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│i

一.分析方法例:G(E)E→E+T│T消除左遞歸:E→T過程advance:匹配并把輸入串指針后移一位變量sym:輸入指針指向的符號Error():出錯處理函數(shù)

procedureadvance(t:token);beginifsym==tthensym=nexttokenelseerror（）end;

過程advance:匹配并把輸入串指針后移一位procedureE;beginT;E’end;procedureT;beginF;T’end;E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iprocedureE’;ifsym=‘+’thenbeginadvance(‘+’);T;E’end;procedureT’;ifsym=‘*’thenbeginadvance(‘*’);F;T’end;

procedureE;procedureT;E→TE’E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iprocedureF;ifsym=‘i’thenadvance(‘i’)elseifsym=‘(’thenbegin

advance(‘(’);E;ifsym=‘)’thenadvance(‘)’)elseerror()endelseerror();

E→TE’E’→+TE’│εprocedi+i*i#的遞歸下降分析過程E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iETTiiiii+++++**######FM(i)FM(i)FM(i)E’M(+)T’M()E’M()#T’M()#T’M(*)M()

i+i*i#的遞歸下降分析過程E→TE’ETTiiiii++

二.擴(kuò)充的BNF用花括號{α}表示閉包運(yùn)算α*;α可以重復(fù)任意多次用{α}表示α可任意重復(fù)0次至n次

{α}=α0=ε;用[α]表示{α},即[α]表示α的出現(xiàn)可有可無(等價于α│ε)；1.表示形式n00010二.擴(kuò)充的BNF用花括號{α}表示閉包運(yùn)算α*;1.表示例一：標(biāo)識符的定義利用擴(kuò)充BNF表示為E→T{+T}T→F{*F}F→i|(E)E→E+T│TT→T*F│FF→(E)│i例二：文法I→L│LSS→T│STT→L│DL→a│b│...│zD→0│1│2│...│9I→L{L|D}L→a|b|…|zD→0|1|…|9

例一：標(biāo)識符的定義利用擴(kuò)充BNF表示為E→T{+T}E→E+

decimal→[sign]integer.{digit}[exponent]exponent→E[sign]integerinteger→digit{digit}sign→+│-digit→0│1│…│9例三：實(shí)數(shù)可定義為

例三：實(shí)數(shù)可定義為p→x│y│…│z│pv改寫成:p→(x│y│…│z){v}2.左遞歸的消除

p→x│y│…│z│pv2.左遞歸的消除3.文法的轉(zhuǎn)換圖表示E→T{+T}T→F{*F}F→i|(E)E→E+T│TT→T*F│FF→(E)│i+012T關(guān)于E的轉(zhuǎn)換圖012F*關(guān)于T的轉(zhuǎn)換圖013（）i2E關(guān)于F的轉(zhuǎn)換圖

3.文法的轉(zhuǎn)換圖表示E→T{+T}E→E+T│T+012TprocedureE;BeginT;whilesym=’+’dobeginadvance(‘+’);TendendE→T{+T}+012T關(guān)于E的轉(zhuǎn)換圖E→T{+T}T→F{*F}F→i|(E)三.改進(jìn)的遞歸下降分析法F

procedureE;E→T{+T}+012T關(guān)于E的轉(zhuǎn)procedureT;beginF;whilesym=’*’dobeginadvance(‘*’);Fendend;T→F{*F}012F*關(guān)于T的轉(zhuǎn)換圖

procedureT;T→F{*F}012F*關(guān)于T的轉(zhuǎn)procedureF;ifsym=‘i’thenadvance(‘i’)elseifsym=‘(’thenbeginadvance(‘(’);E;ifsym=‘)’thenadvance(‘)’)elseerrorendelseerror；013（）i2E關(guān)于F的轉(zhuǎn)換圖F→i|(E)

procedureF;013（）i2E關(guān)于F的轉(zhuǎn)換圖F→ii+i*i#的遞歸下降分析過程E→T{+T}T→F{*F}F→(E)│iETTFFFiii++i##i*M(i)M(*)M(i)M(+)M(i)

i+i*i#的遞歸下降分析過程E→T{+T}ETTFFFii

第四節(jié)預(yù)測分析法

預(yù)測分析（LL(1)分析法）是一種表驅(qū)動方法，由下推棧、預(yù)測分析表和控制程序組成。它實(shí)際上一種下推自動機(jī)的實(shí)現(xiàn)模型。第四節(jié)預(yù)測分析法預(yù)測分析（LL(1)分析法）是一種LL(1