第四章語法分析(3)(編輯修改稿)
2025-08-18 09:44 本頁面
【文章內(nèi)容簡介】 id id * + * * id id $ $ + $ accept id + * $ id + * $ 33 應(yīng)用下面的過程發(fā)現(xiàn)句柄： ? 從左端開始掃描串，直至遇到第一個 ， 最靠棧頂?shù)慕K結(jié)符號 當(dāng)前的輸入符號 。 ? 向左掃描，跳過所有的 =，直至遇到第一個 ? 句柄包括從 的右部開始直到第一個 之間的所有符號，包括介于其間或兩邊的非終結(jié)符。 ? 非終結(jié)符不會影響語法分析。 34 分析棧 輸入串 動作 $ id + id * id$ 移進(jìn) $id + id * id$ 歸約 , E ? id $E + id * id$ 移進(jìn) $E+ id * id$ 移進(jìn) $E+id * id$ 歸約， E ? id $E+E * id$ 移進(jìn) $E+E* id$ 移進(jìn) $E+E*id $ 歸約， E ? id $E+E*E $ 歸約 , E ? E * E $E+E $ 歸約 , E ? E + E $E $ 接受 將非終結(jié)符保留在棧中 ,作為屬性的占位符 . 35 i t e $ i = t ? = ? e ? ? ? $ ? acc 例： 文法 S ? i E t Se S | i E t S 中，終結(jié)符號之間的歸約優(yōu)先關(guān)系： 36 算符優(yōu)先分析法的思想源于表達(dá)式的分析，即利用相鄰終結(jié)符號之間的關(guān)系來尋找可歸約串。 顯然，在一個符號串中，任意兩個相鄰終結(jié)符號 a和b之間，只可能存在以下四種歸約關(guān)系： (1) 同屬一個可歸約串，記作 a = b。 (2) a應(yīng)先于 b歸約，記作 a ? b。 (3) a應(yīng)后于 b歸約，記作 a ? b。 (4) a與 b不可能相鄰，即此符號串不是句型 (出錯 )。 如果以上四種關(guān)系中的任意兩種都不會同時成立，則可以根據(jù)終結(jié)符號之間的歸約關(guān)系進(jìn)行語法分析。 37 算法 算符優(yōu)先分析法 輸入： 輸入符號串 w$和一張優(yōu)先關(guān)系表。 輸出： 若 w是句子，則輸出 w的推導(dǎo)步驟 (或 w的分析樹基架 )；否則輸出錯誤信息。 方法： 初始時，分別置放 $到棧中和 w$到輸入緩沖區(qū)中。 38 令 ip指向 w$的第一個符號； repeat forever if $在棧頂并且 ip指向 $ then return /* accept */ else begin 令 a是最靠棧頂?shù)慕K結(jié)符號，且 b是 ip所指向的符號 if ab 或 a=b then begin 將 b入棧； ip指向下一個輸入符號； end else if ab then begin /*歸約 */ repeat 從棧內(nèi)彈出符號 until 棧頂終結(jié)符與最近彈出的符號滿足 關(guān)系； else error()。 end 39 算符優(yōu)先關(guān)系表的構(gòu)造 ? 利用算符之間的優(yōu)先級和結(jié)合律 – 如果操作符 ?1比 ?2優(yōu)先級高，則 ?1?2 且?2 ?1； – 如果 ?1和 ?2優(yōu)先級相同，則當(dāng)滿足左結(jié)合律時， ?1 ?2 和 ?2 ?1成立；當(dāng)滿足右結(jié)合律時， ?1 ?2 和 ?2 ?1成立； – 對應(yīng)所有操作符 ?， ? id、 id ?、 ? (、( ?、 ) ?、 ? ) 、 ? $、 $ ?均成立。 40 算符優(yōu)先關(guān)系表的構(gòu)造 ? 利用產(chǎn)生式的特點 若 A ? ?a?b? (或 A ? ?ab? )，則 a=b。 若 A ? ?b? 且 ? ?+…a 或 ? ?+...aB，則a b。 若 A ? ?a? 且 ? ?+b... 或 ? ?+Bb...，則a b。 41 例 構(gòu)造文法 的算符優(yōu)先關(guān)系表。 E ? E + E | E E | E * E | E / E | E ? E | (E) | E | id 設(shè)文法的算符優(yōu)先關(guān)系滿足： 1. ?有最高優(yōu)先級， 并且是右結(jié)合的。 2. * 和 / 有次優(yōu)先級，并且是左結(jié)合的。 3. + 和 有最低優(yōu)先級，并且是左結(jié)合的。 42 + * / ? id ( ) $+*/?id()$? ? ? ? ? ? ?? ?? ? ? ? ? ? ?? ? ? ?? ? ? ? ?? ? ? ?? ? ? ? ?? ? ? ? ? ? ?? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ?
外語相關(guān)推薦
鄂ICP備17016276號-1