第四章++語(yǔ)法分析(3)-全文預(yù)覽
【正文】 id * id$ + id * id$ id * id$ * id$ * id$ id$ $ $ $ $ $ STACK INPUT Remark $ + ? b ”表示 a應(yīng)當(dāng)先于 b歸約；“ a ?? err id = ?? ? * ? ?? b ”表示 a 的優(yōu)先級(jí)高于 b， a先于 b歸約； ? “ a = b”表示 a 的優(yōu)先級(jí)等于 b， a應(yīng)當(dāng)與 b同時(shí)歸約。 ? 所有產(chǎn)生式的右部都不是 ?或兩個(gè)相鄰的非終結(jié)符。 24 移進(jìn) ?歸約沖突 例 stmt ? if expr then stmt | if expr then stmt else stmt | other 存在 移進(jìn) 歸約沖突 。 ? 活前綴是右句型的前綴， 不含右句柄之后的任何符號(hào)。 4. 若最終能歸約成文法的開始符號(hào)，則分析成功。 E ?rm E * E ?rm E * id3 ?rm E + E * id3 ?rm E + id2 * id3 ?rm id1 + id2 * id3 12 句柄剪枝 (Handle Pruning) ? A rightmost derivation in reverse can be obtained by “handlepruning.” ? 從被分析的終結(jié)符號(hào)串 w開始，如果 w是文法的句子，那么記 w=?n，其中 ?n是最右推導(dǎo)的第 n步句型： ? 構(gòu)造最右推導(dǎo)的逆過(guò)程，在 ?n中找句柄進(jìn)行歸約得到右句型 ?n1。 5 Handles ? 右句型 ?的句柄是產(chǎn)生式 A ? ?和 ?中的子串 ?，且用 A 代替 ?得到的仍是右句型 ? . A ? ? is a handle of ??? at the location immediately after the end of ?, if: ? 最左直接短語(yǔ)稱為句柄。 ? 句型的句柄是和某產(chǎn)生式右部匹配的子串，并且，把它歸約成該產(chǎn)生式左部的非終結(jié)符代表了最右推導(dǎo)過(guò)程的逆過(guò)程的一步。 ? Right sentential forms of a nonambiguous grammar have one unique handle. 11 例 E ? E + E | E * E | (E ) | id E ?rm E + E ?rm E + E * E ?rm E + E * id3 ?rm E + id2 * id3 ?rm id1 + id2 * id3 在句型 E + E * id3中，句柄不唯一。 3. 根據(jù)句柄對(duì)分析樹進(jìn)行修剪子樹，剪去子樹的葉子。 ? 考察任意最右推導(dǎo)中連續(xù)兩步的可能形式： x y zB x y zB x A zSyzB y zAzSrmrmrmrmrmrm????? ? ????******??????20 yzB y zAzSrmrmrm? ? ????***???? 假設(shè)當(dāng)前狀態(tài)格局為： 棧 輸入 $??? yz$ ? 把句柄 ?歸約為 B，達(dá)到 狀態(tài)格局： 棧 輸入 $??B yz$ ? 移進(jìn) y入棧中，達(dá)到格局： 棧 輸入 $??By z$ ? 棧頂形成句柄 ?By，歸約為 A，達(dá)到 狀態(tài)格局： 棧 輸入 $?A z$ 21 ? 假設(shè)當(dāng)前狀態(tài)格局為： 棧 輸入 $?? xyz$ ? 把句柄 ?歸約為 B，達(dá)到 狀態(tài)格局： 棧 輸入 $?B xyz$ ? 移進(jìn) x, y入棧中，達(dá)到格局： 棧 輸入 $?Bxy z$ ? 棧頂句柄 y歸約為 A，達(dá)到 狀態(tài)格局： 棧 輸入 $?Bx z$ x y zB x y zB x A zSrmrmrm????***???22 活前綴 (Viable prefix) ? 出現(xiàn)在移進(jìn)歸約分析器棧中的右句型的前綴集合稱為 活前綴 。 23 沖突 (Conflicts) ? 如果形成這樣的格局：根據(jù)棧中的內(nèi)容和下一個(gè)輸入符號(hào)不能決定是移進(jìn)還是歸約（移進(jìn) ?歸約沖突），或 不能決定用那一條產(chǎn)生式進(jìn)行歸約（ 歸約 ?歸約沖突）。 假設(shè)當(dāng)前狀態(tài)格局為： 棧 輸入 … id(id , id …$ Reduce/Reduce Conflict … what to do? (it really depends on what is A, an array? or a procedure? 27 算符優(yōu)先分析法 (OperatorPrecedence Parsing) ? 如果文法 G中不存在形為 A??和 A??BC?的產(chǎn)生式 (A, B, C?VN, ?, ??(VT?VN)*)，則稱 G為 算符文法 。 b”表示 a 的優(yōu)先級(jí)低于 b， a后于 b歸約； ? “ a 構(gòu)造相鄰終結(jié)符號(hào)之間的關(guān)系： + * ( ) id + ? ? ?? err ? err 這里，“ a id id + + id id ? 向左掃描，跳過(guò)所有的 =，直至遇到第一個(gè) ? 非終結(jié)符不會(huì)影響語(yǔ)法分析。 顯然，在一個(gè)符號(hào)串中，任意兩個(gè)相鄰終結(jié)符號(hào) a和b之間，只可能存在以下四種歸約關(guān)系： (1) 同屬一個(gè)可歸約串，記作 a = b。 b。 輸出： 若 w是句子，則輸出 w的推導(dǎo)步驟 (或 w的分析樹基架 )；否則輸出錯(cuò)誤信息。b then begin /*歸約 */ repeat 從棧內(nèi)彈出符號(hào) until 棧頂終結(jié)符與最近彈出的符號(hào)滿足 ?1； – 如果 ?1和 ?2優(yōu)先級(jí)相同，則當(dāng)滿足左結(jié)合律時(shí)， ?1 ?1成立； – 對(duì)應(yīng)所有操作符 ?， ? ?、 ) ?均成立。 若 A ? ?a? 且 ? ?+b... 或 ? ?+Bb...，則a 2. * 和 / 有次優(yōu)先級(jí)，并且是左結(jié)合的。 172。 ? 成立，否則 172。比 amp。Eamp。E。 (2)若 a = b，則 f(a) = g(b)。 46 + * / ? ( ) id $ f g 2 1 2 1 4 3 4 3 4 5
外語(yǔ)相關(guān)推薦
鄂ICP備17016276號(hào)-1