【正文】 αBβ是一個產(chǎn)生式而??FIRST(β) ＡＡ ?B ＡＡ ?$∈∈ FOLLOW(A)■*...A特殊地：若特殊地：若 S…… Aa…… ， a∈∈ T}A∈∈ N,S =例：求 First(BaB)Date 17信息學(xué)院 {d,ε}{e,ε}First(T)=注意：有 ε產(chǎn)生式時求 First集 ，別漏，別漏元素?。≡兀?！First(M)={e,a,d,b,→d|(4)→ Db|eT|(3)T→Ba |M→TBFIRST集合集合G:語法分析■孫麗云第 4章 ε}First(stmt)={s}解：解：■First(stmtseq’)={。stmtsequence|εstmt→ssequences)stmtsequence →stmt stmt seq’stmtseq’ → 。for語法分析3)求文法求文法 G的的 孫麗云第 4章 1(1) statement → ifstmt(2) statement → other(3) ifstmt → if (exp) statement elsepart(4) elsepart → else statement(5) elsepart → ε(6) exp → 0 (7) exp → 1First(statement)={if,other}First(ifstmt)={if}First(elsepart)={else,ε}First(exp)={0,1}解：解：■0ifstatement)statement → ifstmt | otherifstmt → if (exp) statement elsepartelsepart → else statement | εexpgrammarFIRST集合集合 (Left練習練習同例 1，僅符號不一樣而已Date 14信息學(xué)院 First(factor)={(,number} First(term)={(,number} →→ numberFirst(expr)={(,number}(9)factormulop→→ factor(6)termtermaddopaddopexpraddopexprgrammar)expr → expr addop term∣termaddop → +|term → term mulop factor ∣ factormulop →*factor → (expr)integer語法分析1)求文法求文法 G的的 孫麗云第 4章 →i■(10)F→/(8)mop→F(6)mopT→(4)aopE→TTE→EFIRST集合集合G:εDate 12信息學(xué)院 C?xy|B?bd|c|εC?xy|B?bd|c|εB?bd|c③③ A?Ba孫麗云■特別是 ,若所有的 FIRST(Yj , j=1,2,…,K) 均含有 ?,則把 ?加到FRIST(X)中 .■若 X??也是一條產(chǎn)生式 ,則把 ?也加到 FIRST(X)中 . X?Y… 是一個產(chǎn)生式且 Y?N,則把 FIRST(Y)中的所有非 ?元 素都加到 FIRST(X)中 。該集合稱為該集合稱為 α的頭符號集合的頭符號集合Date 10信息學(xué)院 ε， 則規(guī)定則規(guī)定 ε?=(T?N)* }α,β?Taβ， =|=語法分析First集合和 Follow集合■孫麗云第 4章 LL(1)文法文法LL(1)中的第一個 L表示從左到右掃描輸入串，第二個L表明分析過程中使用最左推導(dǎo)， 1表示分析時每一步只需向前看一個符號即可決定所選用的規(guī)則，而且這種選擇是準確無誤的。例：例： A?Bx B?x（ 2）相同左部的規(guī)則，其中某一右部能推出 ε串。例： 語法分析■孫麗云第 4章 例：例： A?252。term { addop term }252。exp addop term | term exp ?statement]exp ?statementifstatementifstmtexp )ifstatement(例：例： ifstmt ?語法分析（ 2）采用擴充 BNF表示法改寫含直接左遞歸的規(guī)則252。孫麗云第 4章 T/FT*FFT||→→ 左遞歸改成右遞歸左遞歸改成右遞歸 ———— 普通的直接左遞歸的消除普通的直接左遞歸的消除練習： 對文法 G:exp’exp’+exp’exp’→ 解：解： 消除消除左遞歸。termtermexptermexpexpε●A’α n…|α2A’→β m…|β2A’A|Aα2|→確定的自上而下分析法對文法要求： (1)無左遞歸； (2)無回溯Date 6信息學(xué)院 左遞歸的消除不改變語言，但是改變了文法和分析樹。消除左遞歸。termaddop termexp →|→→αA’|βA’A’ AAα|A左遞歸改成右遞歸左遞歸改成右遞歸 ———— 簡單直接左遞歸的消除簡單直接左遞歸的消除文法左遞歸的消除文法左遞歸的消除 自上而下分析法左遞歸導(dǎo)致無限遞歸循環(huán)；解決無限遞歸循環(huán)的方法： 消除左遞歸 。Date 5信息學(xué)院 G[Z]:E?cAd?cad建立了推導(dǎo)序列建立了推導(dǎo)序列 改選改選 A的第二右部的第二右部 即砍掉即砍掉 A的子樹的子樹 回溯回溯 但是還不能冒然宣布但是還不能冒然宣布 S?L(G[Z])c A da bZ完成進一步推導(dǎo)完成進一步推導(dǎo) A?abA有兩個右部有兩個右部 ,選第一個選第一個 語法分析3.孫麗云第 4章 S?L(G[Z])求解求解 語法分析例：已知符號串例：已知符號串 S=cad孫麗云第 4章 Sc A d■A→a 。A→ab 。自頂向下的分析自頂向下的分析例：設(shè)有文法 G： S→cAd 。Date 2信息學(xué)院 語法分析方法L:由左向右的處理輸入由左向右的處理輸入L:為輸入串構(gòu)造最左推導(dǎo)為輸入串構(gòu)造最左推導(dǎo)語法分析遞歸下降法遞歸下降法LL(1)分析法分析法回溯分析方法（不確定的分析法）回溯分析方法（不確定的分析法）預(yù)測分析方法預(yù)測分析方法(確定的分析法確定的分析法 )LR(0) parsingSLR(1) parsingLR(1) parsingLALR(1) parsing自頂向下分析方法自頂向下分析方法從根結(jié)點出發(fā)構(gòu)造從根結(jié)點出發(fā)構(gòu)造語法樹語法樹孫麗云第 4章 語法分析程序的輸入是單詞符號序列；輸出是語法樹。語法分析語法分析程序的功能是以詞法分析器生成的單詞符號序列作為輸入，根據(jù)語言的語法規(guī)則（文法），識別出各種語法成分，并在分析過程中進行語法檢查，檢查所給單詞符號序列是否是該語言的文法的一個句子。第 4章 若是，則以該句子的某種形式的語法樹作為輸出；若不是，則表明有錯誤，并指出錯誤的性質(zhì)和位置。Date 1信息學(xué)院 自底向上分析方法自底向上分析方法從從 葉葉 結(jié)點出發(fā)構(gòu)造結(jié)點出發(fā)構(gòu)造語法樹語法樹L:由左向右的處理輸入由左向右的處理輸入R:為輸入串構(gòu)造最右推導(dǎo)為輸入串構(gòu)造最右推導(dǎo)孫麗云第 4章 語法分析■識別串 w=cabd是否是該文法的句子。自底向上的分析自底向上的分析Sc A da bc da bc da bAc da bASDate 3信息學(xué)院 文法文法 G[Z]:Z→cAd A→ab|a 分析過程分析過程是設(shè)法建立一棵語法樹是設(shè)法建立一棵語法樹 ,使語法樹的末端結(jié)點與使語法樹的末端結(jié)點與給定符號串相匹配給定符號串相匹配 . :令令 Z為根結(jié)點為根結(jié)點 Z Z的右部的右部 ,符號串去匹配輸入串符號串去匹配輸入串 Zc A d完成一步推導(dǎo)完成一步推導(dǎo) Z?cAd檢查檢查 cc匹配匹配 A是非終結(jié)符是非終結(jié)符 ,將匹配任務(wù)交給將匹配任務(wù)交給 A回溯分析法 自上而下分析法Date 4信息學(xué)院 選用選用 A的右部符號串匹配輸入串的右部符號串匹配輸入串 檢查檢查 ,aa匹配匹配 ,bd不匹配不匹配 (失敗失敗 )4.Zc A daA?a檢查檢查 aa匹配匹配 dd匹配匹配建立語法樹建立語法樹 ,末端結(jié)點為末端結(jié)點為 cad與與 輸入輸入 cad相匹配相匹配 ,∴∴ cad?L(G(E))S=cadZ→cAd A→ab|a分析工作要部分析工作要部分地或全部地分地或全部地退回去重做叫退回去重做叫回溯回溯回溯分析法分析效率低，代價高，實際不常用。孫麗云第 4章 語法分析■（（ 1）） →β→→ε解解 ：： exp term exp’exp’ addop term exp’εε例：將文法例：將文法 G：： exp|消除左遞歸。左遞歸的消除不改變語言，但是改變了文法和分析樹。孫麗云第 4章 語法分析AAα 1|…Aα n|β1|β2|…|β m→β 1|A’|A’A’α 1|A’||Example將文法將文法 G：： →+||左遞歸。expterm→term|term|ε(1)ET*FT/FF→→ ||消除左遞歸Date 7信息學(xué)院 使用花括號 {a}表示符號串 a的出現(xiàn)可 0次或多次，即表示 a*。 ifexp )|(statement else?(exp)[else使用方括號 [a]表示 a的出現(xiàn)可有可無，它用來表示可供選擇的符號串。使用圓括號可在規(guī)則中提取因子。 xa1|xa2|…| xanA?x(a1|a2|…|an)Date 8信息學(xué)院 回溯的消除回溯的消除引起回溯的情況：（ 1）相同左部的規(guī)則，其右部左端第一個符號相同而引起回溯。Z→cAd A→ab|a 串。|ε■ P61Date 9信息學(xué)院 First集合集合定義：定義： FIRST(α){aα*a,?若若 α*FIRST(α)孫麗云第 4章 語法分析 X??,則 FIRST(X)={X} X?N,且有產(chǎn)生式 X?a… ，則把 a加入到 FIRST(X)中。若 X ? Y1Y2…Y K 是一個產(chǎn)生式 ,Y1,Y2,…,Y (i1)都是非終結(jié)符 ,而且 ,對于任何 j,1≤j ≤i1, FIRST(Yj)都含有 ? (即 Y1..Y(i1) =* ? ),則把FIRST(Yj)中的所有非 ?元素都加到 FIRST(X)中 。First集合算法集合算法 P67令 X為一個文法符號或 ?，則集合 First(X)由終結(jié)符組成，此外還可能有 ?，定義如下：Date 11信息學(xué)院 求求 First集合綜合舉例集合綜合舉例求下列各種情況下的求下列各種情況下的 First(A)(1)A∈∈ T(2)A∈∈ N例：例： ①① A?aB|ε②② A?BaB?bd|c|ε④④ A?BCaε⑤⑤ A?BCDεD?m|孫麗云第 4章 語法分析求文法求文法 G的的 (1) aop(2)(3)→+aop(5)→TFT(7)→*mop(9)→(E)F求求 First集合舉例集合舉例 1Date 13信息學(xué)院 FIRST集合集合 (Simpleexpression∣ number(1)→ exprterm(2)→ term(3)→ +(4)→ (5)→→ muloptermfactor(7)→→ *(8)→→ (expr)factor First(addop)={+,} First(mulop)={*}解：解：■孫麗云第 4章 語法分析2)求文法求文法 G的的 factoredof→|練習練習Date 15信息學(xué)院 FIRST集合集合 (Grammarstatement(1) stmtsequence → stmt stmtseq’(2) stmtseq’ → 。stmtsequence(3) stmtseq’ → ε(4) stmt→ sFirst(stmtsequence)={s},練習練習D