自底向上優(yōu)先分析法-文庫(kù)吧資料
2025-05-21 08:00本頁(yè)面
【正文】 能為力。 B 是 是 否 否 例 子 1 b ? ( aa)b 移入 2 b( ? a a)b 移入 3 b(a ? a )b 歸約 4 b(M = a )b 移入 5 b(Ma = ) b 移入 7 b(L ? b 歸約 8 bM = b 移入 9 bMb ? 歸約 10 Z 接受 0 ? b (aa)b 移入 步驟 棧 關(guān)系 Next 余下部分 動(dòng)作 6 b(Ma) ? b 歸約 簡(jiǎn)單優(yōu)先技術(shù)的局限性 ? 文法的適用范圍小。 此時(shí)找到右部為該句柄的規(guī)則進(jìn)行歸約 。 如果 S ? a表示已經(jīng)碰到了一個(gè)句柄的尾 。 已經(jīng)掃描或歸約得到的符號(hào)被存放在一個(gè)棧中 。比如四則運(yùn)算表達(dá)式的文法。 S0? Sj1Sj Sj+1Sj+2?? Si1Si Si+1? Sn U 應(yīng)用優(yōu)先技術(shù)的困難與克服 ? 簡(jiǎn)單優(yōu)先技術(shù)只適應(yīng)于簡(jiǎn)單優(yōu)先文法。 –句柄只能歸約到確定的非終結(jié)符號(hào)。 –在歸約過(guò)程 2中 ， 當(dāng)首次有句柄 1(包括 Sj1和Si+1)中間的某個(gè)符號(hào) St作為句柄 （ 句柄 2） 的一部分被歸約的時(shí)候 ， 我們可以考慮以下的情況： （ 下一頁(yè) ） 定理 (續(xù) ) ? 如果 t=j1，那么 , 由句柄 1， Sj1 ? Sj； 由句柄 2， Sj1 = Sj 或者 Sj1 ? Sj；矛盾！ ? 如果 t=i+1，由句柄 1， Si ? Si+1； 由句柄 2， Si ? Si+1 或者 Si = Si+1。 定理 ? 首先用反證法證明任何句型的句柄是唯一的 。 ? 第一點(diǎn)保證可以識(shí)別出句柄 . ? 第二點(diǎn)保證可以確定歸約到哪個(gè)非終結(jié)符號(hào) 。 –任何兩個(gè)規(guī)則式的右部不相同 。 Sj1 Si1 Si2 ? Sin ? ? ? Sj2 ? ? ? ? Sjm ? ? ? = 簡(jiǎn)單優(yōu)先關(guān)系矩陣（表） 文法： S→bAb A→(B | a B→Aa) HEAD(A)={ ( a } HEAD(B)={ ( a A } TAIL(A)= { a ) B } S A B a b ( ) S A = = B ? ? a ? ? ( ? = ? ? b = ? ? ) ? ? 優(yōu)先關(guān)系的沖突 ? 當(dāng)優(yōu)先矩陣中出現(xiàn)值不唯一的元素時(shí)，文法不適合使用優(yōu)先識(shí)別技術(shù)來(lái)識(shí)別句型。 Sj Si1 Si2 ? Sin ? ? ? （ 3） ?關(guān)系的構(gòu)造：由定義， Sj ?Si 表示 : 存在規(guī)則 U → ? VW? 其中 V = W + TAIL (V)＝ {Sl | V == ? Sl } ＝ { Sj1, Sj2, ? , Sjm }。 (1) =的構(gòu)造：直接對(duì)每個(gè)規(guī)則右部處理，對(duì)所有右部 X1X2? Xn，都有 Xi = Xi+1。 b A b a S b?a a?b b A b S ( B b? ( ( 〓 B B?b 優(yōu)先矩陣 ? 可以將優(yōu)先關(guān)系填寫(xiě)到一個(gè)矩陣，得到優(yōu)先矩陣。 優(yōu)先關(guān)系的定義 ? Sj = Si：當(dāng)且僅當(dāng) G中有規(guī)則 U → ? SjSi ? ? Sj ? Si：當(dāng)且僅當(dāng) U → ? SjV? ，且 + V == Si? ； ? Sj ? Si：當(dāng)且僅當(dāng) U → ? VW? ， 其中 V和 W分別滿足 + V == ? Sj * W == Si ? 且 Si為終結(jié)符號(hào)。 簡(jiǎn)單優(yōu)先分析技術(shù) (思路續(xù)） ? 我們要通過(guò)兩個(gè)相鄰符號(hào) SiSi+1之間的關(guān)系來(lái)找到句柄： – SiSi+1在句柄內(nèi)：必然有規(guī)則 U→ ? SiSi+1? – Si在句柄內(nèi)部 ， 但是 Si+1在句柄之后：必然有規(guī)則 U→ ? Si， 且存在規(guī)范句型 ? USi+1? 。 等同： Si 〓 Sj 先于： Si ?Sj
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1