【正文】 它包含了整個(gè) G， 但它引進(jìn)了一個(gè)不出現(xiàn)在 G中的非終結(jié)符 S?，并加進(jìn)一個(gè)新產(chǎn)生式 S?→S ， 而這個(gè) S?是G?的開始符號(hào) 。 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 結(jié)論 : 若項(xiàng)目 A?? .B?對(duì)活前綴 ?=??是有效的且 B ? ?是一個(gè)產(chǎn)生式，則項(xiàng)目 B ? .?對(duì) ?=??也是有效的。 c c b E a d A c c d d d B A B 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 有效項(xiàng)目 ? 我們說(shuō)項(xiàng)目 A? ?1.?2對(duì)活前綴 ??1是有效的，其條件是存在規(guī)范推導(dǎo) ?????? 21R*RAS ????在任何時(shí)候，分析棧中的活前綴 X1X2 … Xm的有效項(xiàng)目集正是棧頂狀態(tài) Sm所代表的那個(gè)集合。 6: E→aA 7: E→bBd 11: B→dB B→cB B→ 3: E→bcA A→d 2: E→aA A→aA E→ 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 6 7 8 9 10 4 5 3 1 2 11 12 13 14 15 16 18 17 ? ? ? ? ? ? ? a ? ? ? A E b B B c A c d 識(shí)別活前綴的 NFA 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 識(shí)別活前綴的 DFA 0: S?→ ? 把識(shí)別文法所有活前綴的 NFA確定化。d 18. B→dB 16. B→cB 14. B→bB 12. E→bd 10. A→dA 8. A→cA 6. A→aA 4. E→aE 2. S?→E即，對(duì)于規(guī)范句型 ???， ?為句柄，如果 ??=u1u2…u r，則符號(hào)串 u1u2…u i(1?i?r)是 ???的 活前綴 。 ? 定義：一個(gè)文法，如果能用一個(gè)每步頂多向前檢查 k個(gè)輸入符號(hào)的 LR分析器進(jìn)行分析，則這個(gè)文法就稱為 LR(k)文法 . ? 非 LR結(jié)構(gòu) ?LR文法不是二義的，二義文法肯定不會(huì)是 LR的。因此，不存在優(yōu)先函數(shù) f和 g。 ?我們將指出，如果 f(a)＝ g(b)，則根本不存在優(yōu)先函數(shù)。因此，f(a)? g(b)。 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 如果 a b，則有從 fa到 gb的弧。所以， fa和 gb所能到達(dá)的結(jié)是全同的。 ? 第一個(gè)關(guān)系可從函數(shù)的構(gòu)造直接獲得。若沒(méi)有矛盾，則 f和 g就是要求的優(yōu)先函數(shù)，若有矛盾，則不存在優(yōu)先函數(shù)。賦給 fa的數(shù)作為 f(a)，賦給 ga的數(shù)作為 g(a)。如果 a b，則從 fa畫一條弧至 gb，如果 a b，則畫一條弧從 gb至 fa 。要進(jìn)行一些特殊的判斷。 ?用于分析各類表達(dá)式 ?ALGOL 60 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 優(yōu)先函數(shù) ? 把每個(gè)終結(jié)符 ?與兩個(gè)自然數(shù) f(?)與 g(?)相對(duì)應(yīng)，使得 若 ?1 ?2，則 f(?1) g(?2) 若 ?1 ?2，則 f(?1) = g(?2) 若 ?1 ?2，則 f(?1) g(?2) f稱為入棧優(yōu)先函數(shù)， g稱為比較優(yōu)先函數(shù)。 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 算符優(yōu)先分析一般并不等價(jià)于規(guī)范歸約。 ? 算法的第 11行中的 N是指那樣一個(gè)產(chǎn)生式的左部符號(hào)，此產(chǎn)生式的右部和S[j+1]…S[k] 構(gòu)成如下一一對(duì)應(yīng)關(guān)系：自左至右，終結(jié)符對(duì)終結(jié)符，非終結(jié)符對(duì)非終結(jié)符，而且對(duì)應(yīng)的終結(jié)符相同。S[k]:=a END 17 ELSE ERROR /*調(diào)用出錯(cuò)診察程序 */ 18 UNTIL a=?? 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 在算法的工作過(guò)程中，若出現(xiàn) j減 1后的值小于等于 0時(shí)，則意味著輸入串有錯(cuò)。 13 S[k]:=N 14 END OF WHILE。 9 IF S[j1]?VT THEN j:=j1 ELSE j:=j2 10 UNTIL S[j] Q。 2 REPEAT 3 把下一個(gè)輸入符號(hào)讀進(jìn) a中； 4 IF S[k]?VT THEN j:=k ELSE j:=k1。 1 k:=1。 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 考慮下面的文法 G(E)： (1) E→E+T | T (2) T→T*F | F (3) F→P ? F | P (4) P→(E) | i E E F + * T i F T F T P + E T P 句型： T+F*P+i 短語(yǔ)： T+F*P+i, T, F， P, F*P, i, T+F*P 直接短語(yǔ)： T, F, P, i 句柄： T 素短語(yǔ)： F*P, i 最左素短語(yǔ)： F*P 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 算符優(yōu)先文法句型 (括在兩個(gè)＃之間 )的一般形式寫成： N1a1N2a2…N nanNn+1 其中，每個(gè) ai都是終結(jié)符， Ni是可有可無(wú)的非終結(jié)符。 ? 一個(gè)文法 G的句型的 素短語(yǔ) 是指這樣一個(gè)短語(yǔ)，它至少含有一個(gè)終結(jié)符，并且，除它自身之外不再含任何更小的素短語(yǔ)。 2. 構(gòu)造優(yōu)先關(guān)系表 。 ? 使用每個(gè)非終結(jié)符 P的 FIRSTVT(P)和LASTVT(P)，就能夠構(gòu)造文法 G的優(yōu)先表。 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 如果把這個(gè)算法稍為形式化一點(diǎn)，我們可得如下所示的一個(gè)程序 (包括一個(gè)過(guò)程和主程序 )： PROCEDURE INSERT(P， a)； IF NOT F[P， a] THEN BEGIN F[P， a]:=TRUE； 把 (P， a)下推進(jìn) STACK棧 END； 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 主程序： BEGIN FOR 每個(gè)非終結(jié)符 P和終結(jié)符 a DO F[P， a]:=FALSE； FOR 每個(gè)形如 P→a… 或 P→Qa… 的產(chǎn)生式 DO INSERT(P， a)； WHILE STACK 非空 DO BEGIN 把 STACK的頂項(xiàng)，記為 (Q， a)，上托出去； FOR 每條形如 P→Q… 的產(chǎn)生式 DO INSERT(P， a)； END OF WHILE； END 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 這個(gè)算法的工作結(jié)果得到一個(gè)二維數(shù)組 F，從它可得任何非終結(jié)符 P的 FIRSTVT。對(duì)于每個(gè)形如 P→Q… 的產(chǎn)生式，若 F[P， a]為假，則變其值為真且將 (P， a)推進(jìn) STACK棧。 ?棧 STACK，把所有初值為真的數(shù)組元素 F[P，a]的符號(hào)對(duì) (P， a)全都放在 STACK之中。 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 數(shù)據(jù)結(jié)構(gòu)： ?布爾數(shù)組 F[P， a]，使得 F[P， a]為真的條件是，當(dāng)且僅當(dāng) a?FIRSTVT(P)。 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 首先討論構(gòu)造集合 FIRSTVT(P)的算法。 ?假定有個(gè)產(chǎn)生式的一個(gè)候選形為 …aP… 那么，對(duì)任何 b?FIRSTVT(P)，有 a b。 ? 通過(guò)檢查 G的每個(gè)產(chǎn)生式的每個(gè)候選式，可找出所有滿足 a b的終結(jié)符對(duì)。 2. a b 當(dāng)且僅當(dāng) G中含有形如 P→…aR…的產(chǎn)生式， 而 R b… 或 R Qb… ； ????3. a b 當(dāng)且僅當(dāng) G中含有形如 P→…Rb…的產(chǎn)生式，而 R …a 或 R …aQ 。 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 假定 G是一個(gè)不含 ?產(chǎn)生式的算符文法。 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 首先必須定義任何兩個(gè)可能相繼出現(xiàn)的終結(jié)符 a與 b的優(yōu)先關(guān)系 三種關(guān)系 a b a的優(yōu)先級(jí)低于 b a b a的優(yōu)先級(jí)等于 b a b a的優(yōu)先級(jí)高于 b ? 注意：與數(shù)學(xué)上的 =不同， a b并不意味著 b a 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 算符優(yōu)先文法及優(yōu)先表構(gòu)造 ? 一個(gè)文法，如果它的任一產(chǎn)生式的右部都不含兩個(gè)相繼 (并列 )的非終結(jié)符，即不含如下形式的產(chǎn)生式右部： …QR… 則我們稱該文法為 算符文法 。 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 起決定作用的是相鄰的兩個(gè)算符之間的優(yōu)先關(guān)系 。歸約順序不同，則計(jì)算的順序也不同，結(jié)果也不一樣。 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 算符優(yōu)先分析 ? 四則運(yùn)算的優(yōu)先規(guī)則： 先乘除后加減，同級(jí)從左到右 ? 考慮二義文法文法 G(E)： G(E)： E ? i| E+E|EE|E*E|E/E|(E) ? 它的句子有幾種 不同的規(guī)范規(guī)約 。 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 把上例倒過(guò)來(lái)寫，則得到： S ? aAcBe? aAcde ? aAbcde ? abbcde 顯然這是一個(gè)最右推導(dǎo)。 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 在一個(gè)句型對(duì)應(yīng)的語(yǔ)法樹中，以某非終結(jié)符為根的兩代以上的子樹的所有末端結(jié)點(diǎn)從左到右排列就是相對(duì)于該非終結(jié)符的一個(gè)短語(yǔ)，如果子樹只有兩代，則該短語(yǔ)就是直接短語(yǔ)。 特別是，如果有 A??,則稱 ?是句型 ???相對(duì)于規(guī)則 A? ?的 直接短語(yǔ) 。 自下而上分析過(guò)程：邊輸入單詞符號(hào)，邊歸約。 ? 基本思想：用一個(gè)寄存符號(hào)的先進(jìn)后出棧，把輸入符號(hào)一個(gè)一個(gè)地移進(jìn)到棧里，當(dāng)棧頂形成某個(gè)產(chǎn)生式的候選式時(shí)，即把棧頂?shù)倪@一部分替換成 (歸約 為 )該產(chǎn)生式的左部符號(hào)。適合分析表達(dá)式。所謂歸約，是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號(hào)。國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 第五章 語(yǔ)法分析 ——自下而上分析 ? 自上而下分析法 (Topdown) ? 自下而上分析法 (Bottomup) 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ?語(yǔ)法分析的方法： ?自下而上分析法 (Bottomup) 基本思想：從輸入串開始，逐步進(jìn)行 “ 歸約 ” ，直到文法的開始符號(hào)。即從樹末端開始，構(gòu)造語(yǔ)法樹。 算符優(yōu)先分析法：