第四章語法分析(3)-展示頁
2025-07-31 09:44本頁面
【正文】 A b c b 7 Example S ? aABe ? aAde ? aAbcde ? abbcde 考慮文法 S ? aABe A ? Abc | b B ? d It follows that: A ? Abc is a handle of aAbcde in location 2. rm rm rm rm S a A B e d A b c 8 Example S ? aABe ? aAde ? aAbcde ? abbcde 考慮文法 S ? aABe A ? Abc | b B ? d It follows that: B ? d is a handle of aAde in location 3. rm rm rm rm S a A B e d 9 Example S ? aABe ? aAde ? aAbcde ? abbcde 考慮文法 S ? aABe A ? Abc | b B ? d It follows that: S ? aABe is a handle of aABe in location 1. rm rm rm rm S a A B e 10 ? 如果文法二義，那么句柄可能不唯一。 5 Handles ? 右句型 ?的句柄是產(chǎn)生式 A ? ?和 ?中的子串 ?，且用 A 代替 ?得到的仍是右句型 ? . A ? ? is a handle of ??? at the location immediately after the end of ?, if: ? 最左直接短語稱為句柄。1 自底向上語法分析 2 自底向上分析 ? 介紹一種常用的自底向上分析法－ 移進歸約分析法 (Shiftreduce parsing) ? 下一節(jié)討論最易于實現(xiàn)的移進歸約分析算法－ 算符優(yōu)先分析法 (Operatorprecedence parsing ) ? 下下一節(jié)討論一般的移進歸約法－ LR parsing – LR(0)、 SLR – LR(1)、 LALR ? LR分析法用于自動的語法分析器的生成器（ YACC） 3 例 考慮文法 S ? aABe A ? Abc | b B ? d 句子 abbcde的歸約步驟如下： abbcde aAbcde aAde aABe S 這些歸約對應(yīng)最右推導(dǎo)的逆過程： S ?rm aABe ?rm aAde ?rm aAbcde ?rm abbcde S a A B e d A b c b 4 句柄 (handles) ? 句柄是 最左直接短語 。 ? 句型的句柄是和某產(chǎn)生式右部匹配的子串，并且，把它歸約成該產(chǎn)生式左部的非終結(jié)符代表了最右推導(dǎo)過程的逆過程的一步。 ? 句柄的右邊僅含終結(jié)符。 ? 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中，句柄不唯一。 wS nrmrmrmrm ?????? ???? ?21013 例 右句型 句柄 歸約產(chǎn)生式 id1 ＋ id2 * id3 E ＋ id2 * id3 E ＋ E * id3 E ＋ E * E E ＋ E E id1 id2 id3 E * E E + E E ? id E ? id E ? id E ? E * E E ? E + E 14 分析過程的特點 1. 從輸入串的開頭依次讀入 (移進 )單詞。 3. 根據(jù)句柄對分析樹進行修剪子樹，剪去子樹的葉子。 5. 由于總是將句型的 最左邊的可歸約串 替換成非終結(jié)符號，該歸約方法通常得到是 最右推導(dǎo)的逆過程 。 ? 考察任意最右推導(dǎo)中連續(xù)兩步的可能形式： x y zB x y zB x A zSyzB y zAzSrmrmrmrmrmrm????? ? ????******??????20 yzB y zAzSrmrmrm? ? ????***???? 假設(shè)當前狀態(tài)格局為： 棧 輸入 $??? yz$ ? 把句柄 ?歸約為 B，達到 狀態(tài)格局： 棧 輸入 $??B yz$ ? 移進 y入棧中，達到格局： 棧 輸入 $??By z$ ? 棧頂形成句柄 ?By，歸約為 A，達到 狀態(tài)格局： 棧 輸入 $?A z$ 21 ? 假設(shè)當前狀態(tài)格局為： 棧 輸入 $?? xyz$ ? 把句柄 ?歸約為 B，達到 狀態(tài)格局： 棧 輸入 $?B xyz$ ? 移進 x, y入棧中，達到格局： 棧 輸入 $?Bxy z$ ? 棧頂句柄 y歸約為 A，達到 狀態(tài)格局： 棧 輸入 $?Bx z$ x y zB x y zB x A zSrmrmrm????***???22 活前綴 (Viable prefix) ? 出現(xiàn)在移進歸約分析器棧中的右句型的前綴集合稱為 活前綴 。 ? 活前綴后加上終結(jié)符可以得到右句型。 23 沖突 (Conflicts) ? 如果形成這樣的格局：根據(jù)棧中的內(nèi)容和下一個輸入符號不能決定是移進還是歸約（移進 ?歸約沖突），或 不能決定用那一條產(chǎn)生式進行歸約（ 歸約 ?歸約沖突）。 一般地，任何二義性文法都不是 LR(k)文法。 假設(shè)當前狀態(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為 算符文法 。 ? 在實際應(yīng)用時，不必太拘泥這個定義，只要相鄰終結(jié)符號之間的歸約關(guān)系是唯一的，就可以使用算符優(yōu)先分析法。 b”表示 a 的優(yōu)先級低于 b， a后于 b歸約； ? “ a 30 利用算符優(yōu)先關(guān)系確定右句型的句柄（可歸約串） 31 例：考慮文法 E ? E +E | E * E | ( E
外語相關(guān)推薦
鄂ICP備17016276號-1