[理學(xué)]第四章2自下而上語法分析(編輯修改稿)
2025-11-12 22:57 本頁面
【文章內(nèi)容簡介】 F→id E+F *id 3 9) 歸約 T→F E+T *id 3 10) 移進(jìn) E+T* id3 11) 移進(jìn) E+T*id3 12) 歸約 F→id E+T*F 13) 歸約 T→T*F E+T 14) 歸約 E→E+T E 15) 接受 所得的結(jié)果是：用產(chǎn)生式序列表示語法分析樹 (1) EE+T|T (2) TT*F|F (3) F(E)|id id1 + id2 * id3 F T E F T F T E 移進(jìn)歸約分析中的問題 ? 1) 移進(jìn) 歸約沖突 – 在分析到某一步時，既可以移進(jìn)，又可以歸約 – 上例第 10)步可以移進(jìn) *，也可以按產(chǎn)生式E→E+T 進(jìn)行歸約。 ? 2) 歸約 歸約沖突 – 存在兩個可選的句柄，可對棧頂符號進(jìn)行歸約 – 例如上述第 13)步，可以用 T→F 進(jìn)行歸約，又可以按 T→T*F 進(jìn)行歸約。 ? 各種分析方法中處理沖突的技術(shù)不同 算符優(yōu)先分析 ? 算符優(yōu)先分析法的思想源于表達(dá)式的分析，即利用相鄰終結(jié)符號之間的關(guān)系來尋找可歸約串。 ? 將句型中的終結(jié)符號當(dāng)作 “ 算符 ” ，借助于算符之間的優(yōu)先關(guān)系確定句柄。 ? 顯然，在一個符號串中，任意兩個相鄰終結(jié)符號 a和 b之間，只可能存在以下四種優(yōu)先關(guān)系： (1) a, b優(yōu)先性相同，記作 a b。 (2) a優(yōu)先性高于 b， 記作 a b。 (3) a優(yōu)先性低于 b ，記作 a b。 (4) a與 b不可能相鄰，即此符號串不是句型 (出錯 )。 如果以上四種關(guān)系中的任意兩種都不會同時成立，則可以根據(jù)終結(jié)符號之間的歸約關(guān)系進(jìn)行語法分析。 ? :一個上下無關(guān)文法 G,如果沒有 P?,且沒有 P...QR...(P,Q,R屬于非終結(jié)符 ),則 G是一個 算符文法。 ? 的定義 (自底向上 ,可通過樹形結(jié)構(gòu)觀察 ) ① a b,G中有 P...ab...或 P...aQb... (在同一產(chǎn)生式中 ) ② a b,G中有 P...aR...的產(chǎn)生式 ,且 R=b...或R=Qb... (注意 ab相鄰 ) ③ a b,G中有 P...Rb...的產(chǎn)生式 ,且 R=...a或R=...aQ (注意 ab相鄰 ) 算符優(yōu)先文法的定義 + + + + 例： E→E+E | E*E | (E) | i 證明不是算符優(yōu)先文法 。 因為： E→E+E ， E?E*E 則有 + * 又因為： E→E*E, E?E+E 則有 + * 所以不是算符優(yōu)先文法 。 ? – 算符文法 G的任何終結(jié)符 a,b之間要么沒有優(yōu)先關(guān)系，若有優(yōu)先關(guān)系 ,至多有 = , , 中的一種成立 ,則 G為一 算符優(yōu)先文法 。 算符優(yōu)先關(guān)系表 的構(gòu)造 ? 用表格形式來表示各終結(jié)符號的優(yōu)先關(guān)系，這種表稱為優(yōu)先表。 ? 構(gòu)造優(yōu)先關(guān)系表的方法： – ①按照定義手工計算 – ②使用算法 ? 由 F(E) 得 ( = ) T = i, 得 + i T = T*F, 得 + * T = (E), 得 + ( 由 EE+T E = i, 得 i + E = E+T, 得 + + E = T*F, 得 * + E = (E), 得 ) + + * i ( ) + * i ( ) 例 : P: EE+T|T TT*F|F F(E)|i 求算符優(yōu)先表。 終結(jié)符 +?‘ 終結(jié)符 +?‘ 對于結(jié)束符 和其它終結(jié)符 a有關(guān)系 : a 。a * * * * * * * ? 在優(yōu)先表中，空白部分是一種錯誤關(guān)系 ? 相同的終結(jié)符之間的優(yōu)先關(guān)系不一定是 ? 如果有 a b,不一定有 b a(不具傳遞性 )， 因為只定義相鄰運(yùn)算符之間的優(yōu)先關(guān)系， a,b相鄰時，不一定 b,a相鄰。 ? a,b之間未必有優(yōu)先關(guān)系 ( , , ) 算符優(yōu)先關(guān)系表的構(gòu)造算法 ? – 定義： 對每個非終結(jié)符 P, FIRSTVT(P)={a|P=a...或 P=Qa...,a為終結(jié)符 ,P， Q為非終結(jié)符 } + + 由優(yōu)先性低于的定義和 FIRSTVT集合的定義可以得出： 若存在某個產(chǎn)生式： …aP… ，對所有： b∈ firstVT(P) 都有： a b。 構(gòu)造 FIRSTVT集 算法 : ? 按照下面兩條 規(guī)則 來構(gòu)造 FIRSTVT集： – ① 若有產(chǎn)生式
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1