自底向上優(yōu)先分析法-資料下載頁
2025-05-13 08:00本頁面
【正文】 +)T(≡) 算符優(yōu)先文法 ? 定義 ：設有算符文法 G， 如果在其任意兩個終結符之間 ， 算符優(yōu)先關系最多只有一種關系成立 ， 那么該文法 G稱為算符優(yōu)先文法 。 算符優(yōu)先文法句型的識別 ? 由于算符優(yōu)先分析技術在分析的過程中 ，非終結符是 “ 不可見 ” 的 。 因此 ， 對于單規(guī)則 ， 算符優(yōu)先技術無法處理 。 ? 定義 素短語 是滿足下面條件的短語： （ 1） 至少包含一個終結符號 。 （ 2） 該短語不再包含滿足第一個條件的 更小的短語 。 素短語的例子 ? 短語有 T+T*F+i， T+T*F，T*F，最左邊的 T， i。 其中， 素短語 為 T*F， i。 ? T+T*F+i， T+T*F不是 素短語 ，因為其中包含了 T*F。 ? T不是 素短語 ，因為其中不含終結符。 E E + T E Z T + F i T * F T 定理 ? 定理 ： 句型 [N1]T1? [Ni1]Ti1[Ni]Ti? [Nj]Tj[Nj+1]Tj+1? [Nk]Tk[Nk+1] 中滿足關系 Ti1≮ Ti ≈Ti+1≈? ≈Tj≯ Tj+1 的最左子符號串 [Ni]Ti ? [Nj]Tj[Nj+1] 就是句型的 最左素短語 。 句型識別過程 關 系 最左素短語 符號 句 型 1 ≮ i ≯ + i F i+(i+i)*i 2 ≮ +≮ (≮ I ≯ + i F F+(i+i)*i 3 ≮ +≮ (≮ +≮ i≯ ) i F F+(F+i)*i 4 ≮ +≮ (≮ +≯ ) F+F E F+(F+F)*i 5 ≮ +≮ (≈) ≯ * (E) F F+(E)*i 6 ≮ +≮ *≮ i ≯ i F F+F*i 7 ≮ +≮ *≯ F*F T F+F*F 8 ≮ +≯ F+T Z F+T 識別得到的語法樹 F Z + T * E F i F ) ( + F F i i i E E + T * E T T F ) ( + E F F i i F i F T T Z i 算符優(yōu)先技術的說明 ? 在算符優(yōu)先技術的應用中 ， 分析過程并不考慮非終結符 。 可以認為：編譯程序不考慮具體符號的名字 ， 只考慮它的意義 。 ? 需要有處理素短語的語義處理子程序 。 ? 在使用算符優(yōu)先技術的過程中 ， 我們可以使用同一個符號 N來表示歸約得到的非終結符 ， 分析過程照樣可以進行 。 識別算法流程圖 開始 i=1。 S[i]= R=Next Symbol S[i]?VT或 S[i]= j=i1 j=i S[j]R 否 i=i+1。 S[i]=R A N Y Y 識別算法流程圖 (續(xù) ) A Q=S[j]。 j=j1 S[j]?VT j=i1 S[j]Q 調(diào)用語義處理子程序 , 判斷是否素短語 ? 出錯處理 歸約 歸約已經(jīng) 完成 ? N N Y Y N 語義處理子程序 ? 語義處理子程序需要根據(jù)棧里面的符號 （ 和其它信息 ） 分析是否是一個素短語 。 ? 建議歸約的時候 ， 遵照以下法則： 對于素短語 w = [Ni1]Ti[Ni]Ti+1… Tj[Nj+1] 歸約到如下的非終結符 V： V ＝ u ＝ w 且在 u到 w的推導過程中 ， 只用到了形如U::=W的單規(guī)則 。 U， W為非終結符 。 + 實際應用的算符優(yōu)先分析技術 ? 可以使用優(yōu)先函數(shù)來替代優(yōu)先矩陣。優(yōu)先函數(shù)的求解方法等同于簡單優(yōu)先矩陣的算法。（前面的算法不考慮優(yōu)先關系的種類） ? 可以使用兩個棧：運算符棧，運算分量棧。運算分量（非終結符號）和運算符（終結符號）將分別存放在兩個棧中。 算符優(yōu)先文法的范圍 ? 可以被用來處理各種表達式。 ? 如果把各個關鍵字看作算符，這個技術也可以被使用來處理程序設計語言。 ? 對于實際使用的程序設計語言，只需要對文法稍微修改就可以應用算符優(yōu)先分析技術。 ? 對于有些情況，比如表達式，我們可以使用單優(yōu)先函數(shù)來解決。實際上即 f(S)=g(S) 兩種優(yōu)先技術的比較 使用范圍 簡單優(yōu)先文法 算符優(yōu)先文法 關系定義集 字匯表 終結符號集 項 目 簡單優(yōu)先技術 算符優(yōu)先技術 歸約方式 規(guī)范歸約 ‘規(guī)范’歸約 被歸約者 句柄 質(zhì)短語 語義子程序 要求少 要處理的多 功能 低 較高 存儲需求 比較大 比較小 歸約條件 控制方式 優(yōu)先矩陣或優(yōu)先函數(shù) 優(yōu)先矩陣或優(yōu)先函數(shù) 實現(xiàn)工具 棧 棧 優(yōu)先關系 簡單優(yōu)先關系 算符優(yōu)先關系
黨政相關相關推薦
鄂ICP備17016276號-1