自底向上優(yōu)先分析法(參考版)
2025-05-17 08:00本頁面
【正文】 ? 對于有些情況，比如表達(dá)式，我們可以使用單優(yōu)先函數(shù)來解決。 ? 如果把各個關(guān)鍵字看作算符，這個技術(shù)也可以被使用來處理程序設(shè)計(jì)語言。運(yùn)算分量（非終結(jié)符號）和運(yùn)算符（終結(jié)符號）將分別存放在兩個棧中。優(yōu)先函數(shù)的求解方法等同于簡單優(yōu)先矩陣的算法。 U， W為非終結(jié)符 。 j=j1 S[j]?VT j=i1 S[j]Q 調(diào)用語義處理子程序 , 判斷是否素短語 ? 出錯處理 歸約 歸約已經(jīng) 完成 ? N N Y Y N 語義處理子程序 ? 語義處理子程序需要根據(jù)棧里面的符號 （ 和其它信息 ） 分析是否是一個素短語 。 S[i]= R=Next Symbol S[i]?VT或 S[i]= j=i1 j=i S[j]R 否 i=i+1。 ? 在使用算符優(yōu)先技術(shù)的過程中 ， 我們可以使用同一個符號 N來表示歸約得到的非終結(jié)符 ， 分析過程照樣可以進(jìn)行 。 可以認(rèn)為：編譯程序不考慮具體符號的名字 ， 只考慮它的意義 。 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] 中滿足關(guān)系 Ti1≮ Ti ≈Ti+1≈? ≈Tj≯ Tj+1 的最左子符號串 [Ni]Ti ? [Nj]Tj[Nj+1] 就是句型的 最左素短語 。 ? T+T*F+i， T+T*F不是 素短語 ，因?yàn)槠渲邪?T*F。 素短語的例子 ? 短語有 T+T*F+i， T+T*F，T*F，最左邊的 T， i。 ? 定義 素短語 是滿足下面條件的短語： （ 1） 至少包含一個終結(jié)符號 。 算符優(yōu)先文法句型的識別 ? 由于算符優(yōu)先分析技術(shù)在分析的過程中 ，非終結(jié)符是 “ 不可見 ” 的 。 步驟 3：重復(fù)步驟 2，直到收斂。構(gòu)造算法為： 步驟 1：如果 U LASTTERM T， 那么 U LASTTERM+ T。 LASTTERM+的構(gòu)造算法 ? LASTTERM+ 不是 LASTTERM的傳遞閉包。構(gòu)造算法如下： 步驟 1：如果 U FIRSTTERM T， 那么 U FIRSTTERM+ T. 步驟 2：如果 U::=V? ，且 V FIRSTTERM+ T， 那么 U FIRSTTERM+ T。 U FIRSTTERM T 當(dāng)且僅當(dāng)存在規(guī)則 U::=T? 或者 U::=VT? U LASTTERM T 當(dāng)且僅當(dāng)存在規(guī)則 U::=? T 或者 U::=? TV FIRSTTERM+關(guān)系的構(gòu)造 ? FIRSTTERM+ 并不是 FIRSTTERM的傳遞閉包。 優(yōu)先關(guān)系例子 ? 文法： Z::=E E::=T|E+T T::=F|T*F F::=(E)|i ? 等同關(guān)系 ：（ ≈） 只有左、右括號 1對 ? 由推導(dǎo) Z→E→E+T→E+F→E+i Z→E→E+T→E+T*F→E+T*(E)→E+T*(E+T) Z→E→E+T→E+T+T→E+T+F→E+T+(E) 得到以下關(guān)系： +≮ i， +≮ *， *≮ (， (≮ +， +≯ )， +≯ +， +≮ ( 等 優(yōu)先關(guān)系的構(gòu)造 ? 優(yōu)先關(guān)系 ≈的構(gòu)造，只需要按照定義，枚舉各個規(guī)則的右部就可以得到。 + + + + 算符優(yōu)先關(guān)系的直觀意義 ? 算符優(yōu)先分析技術(shù)的基本思想是通過終結(jié)符之間的優(yōu)先關(guān)系，確定句型的 句柄 。 ? 定理 。 因此 xVy中存在兩個相鄰的非終結(jié)符 VU。 如果 w中有兩個相鄰的符號 TU， 且 T在 v中 ，而 U不在 v中 。 定理 和 的證明 ? 假設(shè) w=xvy是文法的句型 ， 而 v是相對于 V的短語 。 同樣 ， v的開始符也不是非終結(jié)符 。 根據(jù)算符文法的定義 ， u中也不包含相鄰的非終結(jié)符 。 ? 假設(shè) x=wUv， 而 y=wuv。 算符文法的性質(zhì) ? 定理 對于算符文法 ， 不存在包含有相鄰兩個非終結(jié)符的句型 。 算符文法 ? 定義 ：如果文法中沒有形狀如 U::= ? VW? 的規(guī)則，則該文法稱為算符文法。 只需要知道 *的優(yōu)先級高于 +， 就可以知道 T*F時句柄 。不需要考慮操作數(shù)就可以對表達(dá)式進(jìn)行分析 。 ? 算符優(yōu)先分析技術(shù)只在部分符號 （ 終結(jié)符 ）之間建立優(yōu)先關(guān)系 。 算符優(yōu)先分析法 ? 簡單優(yōu)先技術(shù)對字匯表中的所有符號之間建立優(yōu)先關(guān)系 。 –當(dāng)兩個關(guān)系既有 ?又有 ?時，成層法無
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1