[理學(xué)]第四章2自下而上語法分析-在線瀏覽
2024-12-03 22:57本頁面
【正文】 約 )—— 文法按 一定原則規(guī)定文法符號的優(yōu)先關(guān)系 ②算符優(yōu)先分析法 (不規(guī)范歸約 )—— 規(guī)定 算符 之間的優(yōu)先關(guān)系 ③ LR分析法（規(guī)范歸約） —— LR(0)、LR(1)、 SLR(1)和 LALR(1) 語法分析樹的生成演示 a b b c d e A A B S A→b A→Abc B→d S→aABe (1)S ? aABe (2)A ? b (3)A ? Abc (4)B ? d S ? aABe ? aAde ? aAbcde ? abbcde 規(guī)范歸約相關(guān)概念復(fù)習(xí) ? 有文法 G，開始符號為 S, 如果有 S=xβ y,則 xβ y是文法 G的 句型 ， x,y是任意的符號串 ? 如果有 S=xAy, 且有 A=β ,則 β 是句型 xβ y相對于非終結(jié)符 A的 短語 ? 如果有 S=xAy, 且有 Aβ ,則 β 是句型 xβ y相對于Aβ 的 直接短語 ? 位于 一個 句型最左邊的直接短語稱為 句柄 . ? 句型 短語 直接短語 句柄 * * + * 注 : 每次歸約的部分就是分析為 句柄 的字符串 (最右推導(dǎo) )。 句型 歸約規(guī)則 abbcde (1)S ? aABe (2)A ? b (3)A ? Abc (4)B ? d (2) A?b (3)A ? Abc aAbcde aAde (4)B ? d (1)S ? aABe aABe S 練習(xí)：有文法如下 (1)EE+T|T (2)TT*F|F (3)F(E)|id 1）寫出輸入串 id1+id2*id3 的規(guī)范歸約過程； 2）給出該文法“移進(jìn) 歸約”語法分析的過程。 ? 2) 歸約 歸約沖突 – 存在兩個可選的句柄，可對棧頂符號進(jìn)行歸約 – 例如上述第 13)步，可以用 T→F 進(jìn)行歸約，又可以按 T→T*F 進(jìn)行歸約。 ? 將句型中的終結(jié)符號當(dāng)作 “ 算符 ” ，借助于算符之間的優(yōu)先關(guān)系確定句柄。 (2) a優(yōu)先性高于 b， 記作 a b。 (4) a與 b不可能相鄰，即此符號串不是句型 (出錯 )。 ? :一個上下無關(guān)文法 G,如果沒有 P?,且沒有 P...QR...(P,Q,R屬于非終結(jié)符 ),則 G是一個 算符文法。 因?yàn)椋?E→E+E ， E?E*E 則有 + * 又因?yàn)椋?E→E*E, E?E+E 則有 + * 所以不是算符優(yōu)先文法 。 算符優(yōu)先關(guān)系表 的構(gòu)造 ? 用表格形式來表示各終結(jié)符號的優(yōu)先關(guān)系，這種表稱為優(yōu)先表。 終結(jié)符 +?‘ 終結(jié)符 +?‘ 對于結(jié)束符 和其它終結(jié)符 a有關(guān)系 : a 。 ? a,b之間未必有優(yōu)先關(guān)系 ( , , ) 算符優(yōu)先關(guān)系表的構(gòu)造算法 ? – 定義： 對每個非終結(jié)符 P, FIRSTVT(P)={a|P=a...或 P=Qa...,a為終結(jié)符 ,P， Q為非終結(jié)符 } + + 由優(yōu)先性低于的定義和 FIRSTVT集合的定義可以得出： 若存在某個產(chǎn)生式： …aP… ，對所有： b∈ firstVT(P) 都有： a b。步驟： ? 先用第一條規(guī)則進(jìn)行初始化 ? 使用第二條規(guī)則對數(shù)組 F進(jìn)行修改， 修改方法是： – (1) 用一個棧，將所有 F數(shù)組中值為真的元素 F[P,a]的符號對 (P,a)壓入堆棧； – (2) 對棧施行如下操作：若棧不空，將棧頂符號對出棧，記為 (Q,a)，檢查所有的產(chǎn)生式，若有形為： P?Q… 的產(chǎn)生式，且 F[P,a]為假，則使 F[P,a]為真，且將 (P,a)壓入堆棧； – (3) 重復(fù)這一過程，直到棧空 求文法各非終結(jié)符的 firstVT： ? 定義數(shù)組： + * ( ) i E 1 T 1 F 1 1 E?E+T | T T?T*F | F F?(E) | i 1 1 1 1 1 從而得到： FirstVT(E) = { +, *,(, I} FirstVT(T) = {*,(,I} FirstVT(F) = {(,I} Begin For 對每個非終結(jié)符 P和終結(jié)符 a do F[P,a] = false For 對每個形如 P?a… 或 P?Qa… 的產(chǎn)生式 do Insert(P,a) While stack 非空 Begin 把棧頂項(xiàng)出棧，記為 (Q,a) For 對每條形如 P?Q… 的產(chǎn)生式 do insert(P,a) End。 IF not F[P,a] then begin f[p,a] = true。 對數(shù)組初始化 應(yīng)用規(guī)則 1 應(yīng)用規(guī)則 2 ? 2. 求 LASTVT集 – 定義： LASTVT(P)={a|P = ...a或 P =... aQ,a為終結(jié)符 ,P， Q為非終結(jié)符 } + + ?構(gòu)造
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1