自底向上優(yōu)先分析法(編輯修改稿)
2025-06-18 08:00 本頁面
【文章內(nèi)容簡介】 簡單優(yōu)先文法 。 ? 第一點保證可以識別出句柄 . ? 第二點保證可以確定歸約到哪個非終結(jié)符號 。 定理 ? 一個簡單優(yōu)先文法是無二義性的，且其任何一個句型 Sm? Sn的唯一句柄是滿足條件： Sj1 ? Sj = Sj+1 = Sj+2 = … = Si1 = Si ? Si+1 的最左子符號串 SjSj+1Sj+2 ? Si1Si。 定理 ? 首先用反證法證明任何句型的句柄是唯一的 。 –句型必然有句柄 ， 且這個句柄必然滿足 Sj1 ? Sj = Sj+1 = Sj+2 = ? = Si1 = Si ? Si+1 (句柄 1) –如果還有另外一個語法樹 ， 那么它對應(yīng)的歸約 （ 稱為歸約過程 2） 必然不是把上面的句柄作為一個整體歸約的 。 –在歸約過程 2中 ， 當首次有句柄 1(包括 Sj1和Si+1)中間的某個符號 St作為句柄 （ 句柄 2） 的一部分被歸約的時候 ， 我們可以考慮以下的情況： （ 下一頁 ） 定理 (續(xù) ) ? 如果 t=j1，那么 , 由句柄 1， Sj1 ? Sj； 由句柄 2， Sj1 = Sj 或者 Sj1 ? Sj；矛盾！ ? 如果 t=i+1，由句柄 1， Si ? Si+1； 由句柄 2， Si ? Si+1 或者 Si = Si+1。 ? 如果 i= t = j；那么 – Sj在句柄中： – Si在句柄中： – Sj和 Si都不在句柄中： 定理 (續(xù) ) ? 簡單優(yōu)先文法的無二義性是顯而易見的： –每個句型只有一個句柄。 –句柄只能歸約到確定的非終結(jié)符號。 ? 該證明的實質(zhì)就是：句柄 1和句柄 2相互交錯，交錯的邊緣必然有多重定義的優(yōu)先關(guān)系。 S0? Sj1Sj Sj+1Sj+2?? Si1Si Si+1? Sn U 應(yīng)用優(yōu)先技術(shù)的困難與克服 ? 簡單優(yōu)先技術(shù)只適應(yīng)于簡單優(yōu)先文法。實際上，一般的程序設(shè)計語言的文法都不是簡單優(yōu)先文法。比如四則運算表達式的文法。 ? 可能的解決辦法是：分離法（成層法） 簡單優(yōu)先分析技術(shù)的實現(xiàn) ? 識別過程 :從左到右地掃描輸入符號 。 已經(jīng)掃描或歸約得到的符號被存放在一個棧中 。 ? 每次掃描的時候 ， 將當前符號 a和棧頂符號 S相比較 。 如果 S ? a表示已經(jīng)碰到了一個句柄的尾 。 然后在棧里面向前 （ 下 ）找 ， 直到找到句柄的頭 。 此時找到右部為該句柄的規(guī)則進行歸約 。 簡單優(yōu)先分析技術(shù)流程圖 開始 初始化 R=下一個輸入符號 棧頂 Si?R? 把 R入棧 找出棧中第一個滿足 Sj1 ? Sj的值 A B 否 是 簡單優(yōu)先分析技術(shù)流程圖 (續(xù) ) A 尋找其右部和句柄匹配的規(guī)則 存在這樣的規(guī)則 是句子？ 出錯處理 停止 將句柄中的符號退去，將規(guī)則的左部入棧。 B 是 是 否 否 例 子 1 b ? ( aa)b 移入 2 b( ? a a)b 移入 3 b(a ? a )b 歸約 4 b(M = a )b 移入 5 b(Ma = ) b 移入 7 b(L ? b 歸約 8 bM = b 移入 9 bMb ? 歸約 10 Z 接受 0 ? b (aa)b 移入 步驟 棧 關(guān)系 Next 余下部分 動作 6 b(Ma) ? b 歸約 簡單優(yōu)先技術(shù)的局限性 ? 文法的適用范圍小。 ? 雖然使用成層法可以使一些文法變成簡單優(yōu)先文法，但是 –成層法的技術(shù)非常復(fù)雜。 –當兩個關(guān)系既有 ?又有 ?時，成層法無能為力。 ? 如果使用高階矩陣，將使得算法的內(nèi)存需求更加大。 算符優(yōu)先分析法 ? 簡單優(yōu)先技術(shù)對字匯表中的所有符號之間建立優(yōu)先關(guān)系 。 但是 ， 有些情況下 ， 不需要對所有兩個符號之間建立優(yōu)先關(guān)系 。 ? 算符優(yōu)先分析技術(shù)只在部分符號 （ 終結(jié)符 ）之間建立優(yōu)先關(guān)系 。 算符優(yōu)先分析技術(shù)基本思想 ? 對于算術(shù)表達式 ， 只需要按照操作符之間的優(yōu)先關(guān)系 ， 就可以確定運算的順序 。不需要考慮操作數(shù)就可以對表達式進行分析 。 ? 例如： E+T*F。 只需要知道 *的優(yōu)先級高于 +， 就可以知道 T*F時句柄 。 ? 在一般的文法中 ， 終結(jié)符的地位相當于操作符 。 算符文法 ? 定義 ：如果文法中沒有形狀如 U::= ? VW? 的規(guī)則，則該文法稱為算符文法。 其中， U， V和 W均為非終結(jié)符。 算符文法的性質(zhì) ? 定理 對于算符文法 ， 不存在包含有相鄰兩個非
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1