【正文】 需要對(duì) G的每個(gè)非終結(jié)符 P構(gòu)造兩個(gè)集合FIRSTVT(P)和 LASTVT(P)： F I R S T V T P a P a P Qa a V Q VT N( ) { | , , }? ? ? ? ?? ?? ?或 而},|{)( NT VQVaaQPaPaPL AS T VT ????? ?? 而或 ??國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ?有了這兩個(gè)集合之后，就可以通過(guò)檢查每所有終結(jié)符對(duì)。 3. G是算符優(yōu)先文法嗎 ? 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 + * ? ( ) iE √ √ √ √ √T √ √ √ √F √ √ √P √ √}{ ( ,)(}(,*,{)(}(,{)(}(,{ *,)(iPF I R ST V TiEF I R ST V TiFF I R ST V TiTF I R ST V T????????+ * ? ( ) iE √ √ √ √ √T √ √ √ √F √ √ √P √ √}{ ) ,)(}),*,{)(}),{)(}),{ *,)(iPL A ST V TiEL A ST V TiFL A ST V TiTL A ST V T????????國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 + * ? ( ) i+*?()i?結(jié)論 : G是算符優(yōu)先文法 ? G的算符優(yōu)先關(guān)系表 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 算符優(yōu)先分析算法 ? 可歸約串，句型，短語(yǔ)，直接短語(yǔ)，句柄，規(guī)范歸約。由于非終結(jié)符對(duì)歸約沒(méi)有影響，因此，非終結(jié)符根本可以不進(jìn)符號(hào)棧 S。 ? 至于 a b和 a b的情形，只須證明其一。A 5. E→aA ? 構(gòu)成識(shí)別一個(gè)文法活前綴的 DFA的項(xiàng)目集(狀態(tài) )的全體稱(chēng)為文法的 LR(0)項(xiàng)目集規(guī)范族 。cB B→ ?也屬于 CLOSURE(I)； 3. 重復(fù)執(zhí)行上述兩步驟直至 CLOSURE(I) 不再增大為止。d} )=I 2 GO(I0, b)= closure(J)=closure ({E →}) ={E →, B→.cB, B→.d}= I 3 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ?構(gòu)造文法 G的拓廣文法 G?的 LR(0)項(xiàng)目集規(guī)范族算法： PROCEDURE ITEMSETS(G?)； BEGIN C:={CLOSURE({S??A A→ 屬于 Ik，則置 ACTION[k,]為 “ acc”。 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 構(gòu)造 SLR(1)分析表方法 : ? 首先把 G拓廣為 G?，對(duì) G?構(gòu)造 LR(0)項(xiàng)目集規(guī)范族 C和活前綴識(shí)別自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換函數(shù) GO. ? 然后使用 C和 GO，按下面的算法構(gòu)造 SLR分析表： ?令每個(gè)項(xiàng)目集 Ik的下標(biāo) k作為分析器的狀態(tài)，包含項(xiàng)目 S?→F F→T T→S S→L L→?, a1a2…a k], ???，搜索符串 a1a2…a k 沒(méi)有作用。 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 令 I是一個(gè)項(xiàng)目集， X是一個(gè)文法符號(hào)，函數(shù) GO(I， X)定義為： GO(I， X)＝ CLOSURE(J) 其中 J＝ {任何形如 [A→ ?X ? 使用這種分析表的分析器叫做一個(gè) 規(guī)范的LR分析器 。, ] 屬于 Ik，則置 ACTION[k, ]為 “ acc”。 2. 若項(xiàng)目 [A→ ?項(xiàng)目中的 a1a2…a k 稱(chēng)為它的 向前搜索符串 (或 展望串 )。*R L→ I11: F→(E)F F→E+T E→B2→ ?a ?屬于 Ik且 GO(Ik, a)＝ Ij， a為終結(jié)符，則置 ACTION[k,a] 為“ sj”。B B→} = I 1 GO(I0, a)= closure(J)=closure({E→a 那么 ， 我們稱(chēng) G?是 G的 拓廣文法 。B B→ 17. B→ (?必為終結(jié)符串 ) ? 對(duì)于一個(gè)文法 G, 可以構(gòu)造一個(gè) DFA,它能識(shí)別 G的所有活前綴 . 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 文法 G的每個(gè)產(chǎn)生式的右部添加一個(gè)圓點(diǎn)稱(chēng)為 G的 LR(0)項(xiàng)目 ? 如 :A?XYZ有四個(gè)項(xiàng)目： A?.XYZ A? A? A?XYZ. ?A?? . 稱(chēng)為 歸約項(xiàng)目 ?歸約項(xiàng)目 S??? . 稱(chēng)為 接受項(xiàng)目 ?A?? .a? (a?VT) 稱(chēng)為 移進(jìn)項(xiàng)目 ? A?? .B? (B?VN) 稱(chēng)為 待約項(xiàng)目 . 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ?文法 G(S?) S?→E E→aA|bB A→cA|d B→cB|d ? 該文法的項(xiàng)目有： 1. S?→ 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 現(xiàn)在必須證明：若 a b，則 f(a)＝ g(b)；若 a b，則 f(a) g(b)；若 a b，則 f(a) g(b)。 15 IF S[j] a OR S[j] a THEN 16 BEGIN k:=k+1。 FIRSTVT(P)＝ {a | F[P， a]=TRUE} ? 同理，可構(gòu)造計(jì)算 LASTVT的算法。對(duì)于任何一對(duì)終結(jié)符 a、 b，我們說(shuō)： 1. a b 當(dāng)且僅當(dāng)文法 G中含有形如P→…ab… 或 P→…aQb… 的產(chǎn)生式； ? 如果一個(gè)算符文法 G中的任何終結(jié)符對(duì) (a，b)至多只滿(mǎn)足下述三關(guān)系之一： a b， a b， a b 則稱(chēng) G是一個(gè) 算符優(yōu)先文法 。 核心問(wèn)題：識(shí)別可歸約串 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 規(guī)范歸約 ? 定義：令 G是一個(gè)文法， S是文法的開(kāi)始符號(hào)，假定 ???是文法 G的一個(gè)句型，如果有 且 ?? AS *? ???A則 ?稱(chēng)是句型 ???相對(duì)于非終結(jié)符 A的 短語(yǔ) 。 ? 基本思想：用一個(gè)寄存符號(hào)的先進(jìn)后出棧，把輸入符號(hào)一個(gè)一個(gè)地移進(jìn)到棧里，當(dāng)棧頂形成某個(gè)產(chǎn)生式的候選式時(shí)，即把棧頂?shù)倪@一部分替換成 (歸約 為 )該產(chǎn)生式的左部符號(hào)。 國(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… 則我們稱(chēng)該文法為 算符文法 。對(duì)于每個(gè)形如 P→Q… 的產(chǎn)生式，若 F[P， a]為假，則變其值為真且將 (P， a)推進(jìn) STACK棧。 9 IF S[j1]?VT THEN j:=j1 ELSE j:=j2 10 UNTIL S[j] Q。賦給 fa的數(shù)作為 f(a)，賦給 ga的數(shù)作為 g(a)。 ? 定義：一個(gè)文法，如果能用一個(gè)每步頂多向前檢查 k個(gè)輸入符號(hào)的 LR分析器進(jìn)行分析，則這個(gè)文法就稱(chēng)為 LR(k)文法 . ? 非 LR結(jié)構(gòu) ?LR文法不是二義的，二義文法肯定不會(huì)是 LR的。 14. B→cA A→ 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 結(jié)論 : 若項(xiàng)目 A?? .B?對(duì)活前綴 ?=??是有效的且 B ? ?是一個(gè)產(chǎn)生式，則項(xiàng)目 B ? .?對(duì) ?=??也是有效的。aA, E→B B→ 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 構(gòu)造 LR(0)分析表的算法 ? 令每個(gè)項(xiàng)目集 Ik的下標(biāo) k作為分析器的狀態(tài)，包含項(xiàng)目 S?→a 1?1，A2→ ? ? 每個(gè) SLR(1)文法都是無(wú)二義的。E+T E→+T I9: E→E+T I4： L→* 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 規(guī)范 LR分析表的構(gòu)造 ? 我們需要重新定義項(xiàng)目，使得每個(gè)項(xiàng)目都附帶有 k個(gè)終結(jié)符。 ?, b]對(duì) ?也是有效的。 2. 若項(xiàng)目 [A→ ? 特別是，如果有 A??,則稱(chēng) ?是句型 ???相對(duì)于規(guī)則 A? ?的 直接短語(yǔ) 。S ， ]})}。 ? 我們只對(duì) k?1的情形感興趣，向前搜索 (展望 )一個(gè)符號(hào)就多半可以確定“移進(jìn)”或“歸約”。 I9： S→L=R*R L→(E) F→ E→Ea ?屬于 Ik且 GO(Ik,a)=Ij， a為終結(jié)符，則置 ACTION[k,a]為 “ sj”； 2. 若項(xiàng)目 A→ ? 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? LR(0)分析表為 ACTI ON GO TO狀態(tài) a b c d E A B0 s2 s3 11 acc2 s4 s10 63 s5 s11 74 s4 s10 85 s5 s116 r1 r1 r1 r1 r1 97 r2 r2 r2 r2 r28 r3 r3 r3 r3 r39 r5 r5 r5 r5 r510 r4 r4 r4 r4 r411 r6 r6 r6 r6 r6國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 例 : 按上表對(duì) acccd進(jìn)行分析 ? 步驟 狀態(tài) 符號(hào) 輸入串 1 0 acccd 2 02 a cccd 3 024 ac ccd 4 0244 acc cd 5 02444 accc d 6 0244410 acccd 7 024448 acccA 8 02448 accA 9 0248 acA 10 026 aA 11 01 E 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 SLR分析表的構(gòu)造 ? LR(0)文法太簡(jiǎn)單， 沒(méi)有實(shí)用價(jià)值 . ? 假定一個(gè) LR(0)規(guī)范族中含有如下的一個(gè)項(xiàng)目集(狀態(tài) )I＝ {X→ ? d 8: A→cAE E→函數(shù)值 GO(I，X)定義為： GO(I， X)＝ CLOSURE(J) 其中 J＝ {任何形如 A→ ?X 7: E→bBaA E→A 8. A→cA因此，