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