第四章語法分析(3)-在線瀏覽
2024-09-01 09:44本頁面
【正文】 ) | id 的分析。構(gòu)造相鄰終結(jié)符號(hào)之間的關(guān)系： + * ( ) id + ?? ?? ( ? ? ) ? err ? ? err 這里，“ a b”表示a應(yīng)當(dāng)后于 b歸約；“ a = b”表示 a應(yīng)當(dāng)與 b同時(shí)歸約。 id id id id id + + * + id id $ + 最靠棧頂?shù)慕K結(jié)符號(hào) ? 向左掃描，跳過所有的 =，直至遇到第一個(gè) 的右部開始直到第一個(gè) ? 非終結(jié)符不會(huì)影響語法分析。 = ? $ ? 顯然，在一個(gè)符號(hào)串中，任意兩個(gè)相鄰終結(jié)符號(hào) a和b之間，只可能存在以下四種歸約關(guān)系： (1) 同屬一個(gè)可歸約串，記作 a = b。? b。 b。 如果以上四種關(guān)系中的任意兩種都不會(huì)同時(shí)成立，則可以根據(jù)終結(jié)符號(hào)之間的歸約關(guān)系進(jìn)行語法分析。 輸出： 若 w是句子，則輸出 w的推導(dǎo)步驟 (或 w的分析樹基架 )；否則輸出錯(cuò)誤信息。 38 令 ip指向 w$的第一個(gè)符號(hào)； repeat forever if $在棧頂并且 ip指向 $ then return /* accept */ else begin 令 a是最靠棧頂?shù)慕K結(jié)符號(hào)，且 b是 ip所指向的符號(hào) if ab then begin /*歸約 */ repeat 從棧內(nèi)彈出符號(hào) until 棧頂終結(jié)符與最近彈出的符號(hào)滿足 end 39 算符優(yōu)先關(guān)系表的構(gòu)造 ? 利用算符之間的優(yōu)先級(jí)和結(jié)合律 – 如果操作符 ?1比 ?2優(yōu)先級(jí)高，則 ?1 ?1； – 如果 ?1和 ?2優(yōu)先級(jí)相同，則當(dāng)滿足左結(jié)合律時(shí)， ?1 ?1成立；當(dāng)滿足右結(jié)合律時(shí)， ?1 ?1成立； – 對(duì)應(yīng)所有操作符 ?， ? ?、 ? ?、 ) ) 、 ? ?均成立。 若 A ? ?b? 且 ? ?+…a 或 ? ?+...aB，則a 若 A ? ?a? 且 ? ?+b... 或 ? ?+Bb...，則a 41 例 構(gòu)造文法 的算符優(yōu)先關(guān)系表。 2. * 和 / 有次優(yōu)先級(jí)，并且是左結(jié)合的。 42 + * / ? id ( ) $+*/?id()$? ? ? ? ? ? ?? ?? ? ? ? ? ? ?? ? ? ?? ? ? ? ?? ? ? ?? ? ? ? ?? ? ? ? ? ? ?? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? =? ? ? ? ? ? ? ? 文法的優(yōu)先關(guān)系如表所示 43 id * (id?id) – id / id的分析過程 分析棧 輸入串 動(dòng)作 $ id * ( id ? id ) id / id$ $id, 移進(jìn) $id * ( id ? id ) id / id$ id *, 歸約 , E ? id $E * ( id ? id ) id / id$ $ *, 移進(jìn) $E* ( id ? id ) id / id$ * (, 移進(jìn) $E*( id ? id ) id / id$ ( id, 移進(jìn) $E*(id ? id ) id / id$ id ? , 歸約 , E ? id $E*(E ? id ) id / id$ ( ?, 移進(jìn) $E*(E ? id ) id / id$ ? id, 移進(jìn) $E*(E ? id ) id / id$ id ),歸約 , E ? id $E*(E ? E ) id / id$ ? ), 歸約 , E ? E ? E $E*(E ) id / id$ ( = ), 移進(jìn) $E*(E) id / id$ ) , 歸約 $E*E id / id$ * , 歸約 $E id / id$ $ , 移進(jìn) … … … 44 處理一元算符 ? 設(shè) 172。 172。優(yōu)先級(jí)比 ?高，則 172。 ? 成立，否則 172。 ?成立。比 amp。滿足左結(jié)合律，那么Eamp。Eamp。 (172。E。 ? 若定義在算符文法 G的終結(jié)符號(hào)集合上的函數(shù) f和 g f, g： VT ? N(整數(shù) ) 滿足 (1)若 a (2)若 a = b，則 f(a) = g(b)。 b，則 f(a) g(b)。 46 + * / ? ( ) id $ f g 2 1 2 1 4 3 4 3 4 5 0 5 6 0 6 5 0 0 例 上表 所對(duì)應(yīng)的優(yōu)先函數(shù)可定義為： 47 算法 構(gòu)造優(yōu)先函數(shù) 輸入 ：算符優(yōu)先關(guān)系表。 方法 ： 1. ?a?VT?{$} ，建立兩個(gè)符號(hào) fa和 ga。 3. 以 (2)建立的組為結(jié)點(diǎn)， ?a,b?VT?{$}，若 ab，則從 fa所在的組畫一弧到 gb所在的組。 4
外語相關(guān)推薦
鄂ICP備17016276號(hào)-1