編譯原理 - 自下而上的語法分析-預(yù)覽頁
【正文】 果一個算符文法 G中的任何終結(jié)符對 (a，b)至多只滿足下述三關(guān)系之一： a ≒ b， a ≮ b， a ≯ b 則稱 G是一個 算符優(yōu)先文法 。 算符優(yōu)先文法及優(yōu)先表構(gòu)造 ? 優(yōu)先關(guān)系表 （ 為終結(jié)符） + * ↑ i ( ) + * ? i ( ) ≯ ≯ ≯ ≯ ≮ ≯≮ ≮ ≯ ≯ ≯ ≮ ≯ ≮ ≮ ≮ ≮ ≯ ≮ ≯ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≯ ≯ ≯ ≯ ≒ ≯ ≯ ≯ ≯ ≯ ≯ ≒ ? 從算符優(yōu)先文法 G構(gòu)造優(yōu)先關(guān)系表的算法 ： ? 通過檢查 G的每個產(chǎn)生式的每個候選式，可找出所有滿足 a≒ b的終結(jié)符對。 FIRSTVT(P)的算法 ? 構(gòu)造集合 FIRSTVT(P)的算法 ： 按其定義，可用下面兩條規(guī)則來構(gòu)造集合FIRSTVT(P)： ?1. 若有產(chǎn)生式 P→a… 或 P→Qa… ，則a?FIRSTVT(P)； ?2. 若 a?FIRSTVT(Q)，且有產(chǎn)生式 P→Q… ，則 a?FIRSTVT(P)。 ? 運算： ? 如果棧 STACK不空，就將頂項逐出，記此項為 (Q， a)。 FIRSTVT(P)＝ {a | F[P， a]=TRUE} ? 同理，可構(gòu)造計算 LASTVT的算法。 3. G是算符優(yōu)先文法嗎 ? + * ? ( ) iE √ √ √ √ √T √ √ √ √F √ √ √P √ √}{ ( ,)(}(,* ,{)(}(,{)(}(,{ * ,)(iPF I R S T V TiEF I R S T V TiFF I R S T V TiTF I R S T V T????????+ * ? ( ) iE √ √ √ √ √T √ √ √ √F √ √ √P √ √}{ ) ,)(}),* ,{)(}),{)(}),{ * ,)(iPL A S T V TiEL A S T V TiFL A S T V TiTL A S T V T????????? G的算符優(yōu)先關(guān)系表： ? 結(jié)論 : G是算符優(yōu)先文法 + * ↑ i ( ) + * ? i ( ) ≯ ≯ ≯ ≯ ≮ ≯≮ ≮ ≯ ≯ ≯ ≮ ≯ ≮ ≮ ≮ ≮ ≯ ≮ ≯ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≯ ≯ ≯ ≯ ≒ ≯ ≯ ≯ ≯ ≯ ≯ ≒ 算符優(yōu)先分析算法 ? 為了解決在算符優(yōu)先分析過程中如何尋找到可歸約串的問題 ， 引進最左素短語的概念 。 ? 定理 ： 一個算符優(yōu)先文法 G的任何句型的最左素短語是滿足如下條件的最左子串 Njaj… NiaiNi+1， aj1 ≮ aj aj ≒ aj+1， … ， ai1≒ ai ai ≯ ai+1 算符優(yōu)先分析算法 ? 算符優(yōu)先分析法是一種廣為應(yīng)用、行之有效的方法。 ? 2 REPEAT ? 3 把下一個輸入符號讀進 a中； ? 4 IF S[k]?VT THEN j:=k ELSE j:=k1。 ? 13 S[k]:=N ? 14 END OF WHILE。 ? 算法的第 11行中的 N是指那樣一個產(chǎn)生式的左部符號，此產(chǎn)生式的右部和S[j+1]… S[k] 構(gòu)成如下一一對應(yīng)關(guān)系：自左至右，終結(jié)符對終結(jié)符，非終結(jié)符對非終結(jié)符，而且對應(yīng)的終結(jié)符相同。要進行一些特殊的判斷。賦給 fa的數(shù)作為 f(a)，賦給 ga的數(shù)作為 g(a)。 優(yōu)先函數(shù) 優(yōu)先函數(shù) f+ f* f? fi g+ g* g? gi + * ↑ if 2 4 4 7g 1 3 6 6+ * ↑ i + ≯ ≮ ≮ ≮ * ≯ ≯ ≮ ≮ ↑ ≯ ≯ ≮ ≮ i ≯ ≯ ≯ 練習(xí) ? 1 已知文法 G[S]為： S→a|∧ |(T) T→T,S|S ?(1) 計算 G[S]的 FIRSTVT和 LASTVT。 a ∧ ( ) , a ∧ ( ) , ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≯ ≯ ≒ ≯ ≯ ≯≯≮≯≯ ≯ ≯ ≯ ≒ ? (3) 輸入串（ a,(a,a)） 的算符優(yōu)先分析過程為： 棧 當前字符 剩余輸入串 動作 ( (a (N (N, (N,( (N,(a (N,(N (N,(N, (N,(N,a (N,(N,N (N,(N (N,(N) (N,N (N (N) N ( a , , ( a , , a ) ) ) ) ) ) a,(a,a)) ,(a,a)) (a,a)) (a,a)) a,a)) ,a)) a)) a)) )) ) ) ) Move in Move in Reduce: S→a Move in Move in Move in Reduce: S→a Move in Move in Reduce: S→a Reduce: T→T,S Move in Reduce: S→(T) Reduce: T→T,S Move in Reduce: S→(T)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1