[理學]第6章自底向上優(yōu)先分析-閱讀頁
2024-10-31 21:23本頁面
【正文】 為非終結符 , b為終結符 , 則句型 ?中任何含 b的短語必含有 A. 20 算符優(yōu)先文法的定義 定義 2 設 G是一個不含 ?產(chǎn)生式的算符文法 , a和 b是任意兩個終結符 , A、 B、 C是非終結符，算符優(yōu)先關系定義如下： 1) a=b 當且僅當文法中有形如 A→或 A→ 的規(guī)則。aB或 B? Cb 3) ab iff 文法中有形如 A→ 的規(guī)則 , 其中 B? aC 。 例：文法 E?E+E|E*E|(E)|i不是算符優(yōu)先文法。 分析程序 優(yōu)先關系矩陣 符號棧 輸入串 當棧內(nèi)終結符的優(yōu)先級＜＝棧外的終結符的優(yōu)先級時，移進；棧內(nèi)終結符的優(yōu)先級＞棧外的終結符的優(yōu)先級時，移進。 32 文法 G[E] E::=E+T|T T::=T*F|F F::=(E)|i 分析句型 T+T*F+i 步驟 句型 關系 最左子串 規(guī)約符號 1 2 3 4 T+T*F+i T+T+i E+i E+F +*+i ++i +i + T*F T+T i E+F T E E F . . . . . . . . . . . . . . 可以看出 : 1. 每次 規(guī)約 最左子串 ,確實是當前句型的 最左素短語 (語法樹） 2. 規(guī)約的不都是真句柄（僅 i規(guī)約為 F是句柄，但它是最左短語 ) 3. 沒有完全按規(guī)則進行規(guī)約 ,因為 素短語不一定是簡單短語 33 文法 G[E] E::=E+T|T T::=T*F|F F::=(E)|i 對輸入串 i+i進行歸約 步驟 棧 優(yōu)先關系 當前符號 剩余輸入串 移進或歸約 1 i +i 移進 2 i + i 歸約 3 F + i 移進 4 F+ i 移進 5 F+i 歸約 6 F+F 歸約 7 F = 接受 34 優(yōu)先函數(shù) 用優(yōu)先關系矩陣存儲算符之間的優(yōu)先關系，需要耗費大量的內(nèi)存空間 (n+1)2。 定義兩個優(yōu)先函數(shù) f、 g， 滿足如下條件： – 當 a=b， 則令 f(a)=g(b) – 當 ab， 則令 f(a)g(b) – 當 ab， 則令 f(a)g(b) 35 優(yōu)先函數(shù)的構造方法 （ 1）由定義直接構造優(yōu)先函數(shù) f、 g ① 對所有終結符 a（ 包括 ）令 f(a)=g(a)=1。 一般地，如果重復過程中有一個值大于 2n， 則表明該算符優(yōu)先文法不存在算符優(yōu)先函數(shù)。 a b a = b = = 39 2. 用關系圖構造優(yōu)先函數(shù) 構造步驟 （ 1）對所有終結符 a(包括 )用帶下標的 fa, ga標注結點，共 2n個 （ 2）若 aiaj， 或 ai=aj， 則從 fai到 gaj畫一條箭弧 若 aiaj， 或 ai=aj， 則從 gaj到 fai畫一條箭弧 （ 3）給每個結點賦一個數(shù)，它等于從該結點出發(fā)所能到達的所有結點（包括其自身）的個數(shù)。 40 構造的優(yōu)先關系圖如右圖： 其優(yōu)先函數(shù)構造如下： 注：并非所有的優(yōu)先關系矩陣都可利用優(yōu)先關系圖，求得其優(yōu)先函數(shù)。 42 G[B]: B?BoT|T T?TaF|F F?nF|(B)|t|f ? 解答 1. 計算 FIRSTVT集和 LASTVT集 FIRSTVT(B)={o, a, n, (, t, f} LASTVT(B)= {o, a, n, ), t, f} FIRSTVT(T)={a, n, (, t, f} LASTVT(T)= {a, n, ), t, f} FIRSTVT(F)={n, (, t, f} LASTVT(f)= {n, ), t, f} 43 o a n ( ) t f o a n ( = ) t f = FIRSTVT(B)={o, a, n, (, t, f} LASTVT(B)= {o, a, n, ), t, f} FIRSTVT(T)={a, n, (, t, f} LASTVT(T)= {a, n, ), t, f} FIRSTVT(F)={n, (, t, f} LASTVT(f)= {n, ), t, f} 文法的算符優(yōu)先關系矩陣構造如下 各算符之間的優(yōu)先關系是唯一的， G[B]是算符優(yōu)先文法！ 44 2. 對輸入串 ntofat的分析過程如下： 步驟 符號棧 當前符號 剩余輸入串 移進或歸約 （ 1） n tofat 移進 （ 2） n t ofat 移進 （ 3） nt o fat 歸約 （ 4） nN o fat 歸約 （ 5） N o fat 移進 （ 6） No f at 移進 （ 7） Nof a t 歸約 45 步驟 符號棧 當前符號 剩余輸入串 移進或歸約 （ 8） NoN a t 移進 （ 9） NoNa t 移進 （ 10） NoNat 歸約 （ 11） NoNaN 歸約 （ 12） NoN 歸約 （ 13） N 分析成功 2. 對輸入串 ntofat的分析過程如下：
教學課件相關推薦
鄂ICP備17016276號-1