




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、4.3 自下而上分析法的一般原理 1 1 自下而上語法分析概述自下而上語法分析概述 基本思想:基本思想:用一個寄存文法符號的棧棧,將一個輸入串反向歸約歸約至文法的開始符號。 特點:特點:效率高、文法限制少。1 1 自下而上語法分析概述自下而上語法分析概述 移進歸約過程實例。 例4.11 設有文法GA: (1)A aBcDe (2)B b (3)B Bb (4)D d對輸入串abbcde$的移進歸約分析過程 對輸入串abbcde$移進歸約分析過程: 步驟 符號棧 輸入串 動作012345678910$a$ab$aB$aBb$aB$aBc$aBcd$aBcD$aBcDe$Aabbcde$bbcde
2、$bcde$bcde$cde$cde$de$e$e$a進棧b進棧用B b歸約b進棧用B Bb歸約c進棧d進棧用D d歸約e進棧用A aBcDe歸約分析成功2 2 移進歸約的基本思想 (1)用一個棧寄存文法符號,將一個終結符推進棧; (2)是將0個或多個符號從棧中彈出,用相應產生式的左部一個非終結符壓入棧; 把棧頂被歸約的一串符號稱為 (3)重復這一過程直至整個輸入串分析完畢; (4)最終棧中,則所分析的輸入串是文法的正確句子;否則,出錯。可歸約串可歸約串3 分類 算符優先分析法算符優先分析法 規范歸約分析法 簡單優先分析法 LR分析法分析法用 刻畫可歸約串用 刻畫可歸約串4.4 4.4 算符優
3、先分析法算符優先分析法 4.4.1 方法概述 1 特點 適合分析各類表達式; 宜于手工實現; 規定運算符之間的優先順序(優先關系,結合性質)。 通過比較算符之間的優先關系確定可歸約串。4.4.1 方法概述 2 優先關系 例 文法GE: E E+E|E*E|(E)|id 對輸入串id+id*id的規范歸約過程。(1)id+id*id(2)E+id*id(3)E+E*id(4)E+E*E(5)E+E(6)E(1)id+id*id(2)E+id*id(3)E+E*id(4)E*id(5)E*E(6)E*優先于:優先于*:4.4.1 方法概述 3 優先關系種類 任何兩個a和b可能的優先關系有3種: a
4、 b: a的優先級低于b a b: a的優先級等于b a b: a的優先級高于b注:優先關系與出現的有關,不同于數學符號。4.4.1 方法概述 4 優先關系矩陣(表) 矩陣的行和列都是文法的終結符; 矩陣元素是兩終結符間的優先關系。 算符優先分析法借助優先關系表尋找句型的可歸約串。 算符優先關系表實例 + * id ( ) $ + * id ( ) $棧頂第一個終結符當前輸入串首字符4.4.2 算符優先文法的定義 1 算符文法的定義 設有文法G,若G中形如U VW的規則,其中V和W為,則G稱為算符文法,也稱OG文法。性質: 1.在算符文法中任何句型都不包含兩個相鄰的非終結符。 2.如Ab或bA
5、出現在算符文法的句型 中,則 中任何含b的短語必含有A。4.4.2 算符優先文法的定義 2 算符優先關系的定義 在OG中定義算符優先關系: (1)a b :含有P ab,或 P aQb的 規則。 (2)a b :含有P aR的規則,且R b或 R Qb (3)a b:含有P Rb的規則,且R a或 R aQ。4.4.2 算符優先文法的定義 2 算符優先關系的定義 規定: 若S a或S Ca,則$ a 若S a或S aC,則a $4.4.2 算符優先文法的定義 3 算符優先文法的定義 設有一個不含 規則的OG文法G, 如果任意兩個終結符間至多有一種算符關系存在, 則稱G是算符優先文法,也稱OPG
6、文法。 結論:算符優先文法是無二義的。4.4.3 算符優先關系表的構造 1 FIRSTVT集、 LASTVT集 FIRSTVT(A)=b|A b 或 A Bb ,b VT,B VN 即:非終結符往下推導所有可能出現的首個算符的集合LASTVT(A)=a|A a A aB, a VT,B VN 即:非終結符往下推導所有可能出現的最后一個算符的集合4.4.3 算符優先關系表的構造 2 算符優先關系表的構造方法 (1)為每個非終結符計算FIRSTVT(A),LASTVT(A) (2)計算算符之間的優先關系,并填表。計算方法: 關系:若Aab 或A aBb,則a b 關系:若A aB,則 b FIRS
7、TVT(B),a b 關系:若A Bb,則 a LASTVT(B),a b (3) 最后,在表中填入的優先關系:對FIRSTVT(S)中所有b,置$ b; 對 LASTVT(S)中所有a,置a $. 置 $ $。 例4.12 文法GE: E E+T|T T T*F|F F (E)|id構造該文法的算符優先關系表。 FIRSTVT LASTVT E T F +,*,(,id *,(,id (,id +,*,),id *,),id ),idHomework: (P105)- 4.5 (2)4.4.4 算符優先分析算法的設計 0 算符優先分析法與規范歸約的區別算符優先分析法:只考慮終結符之間的優先關
8、系來確定可歸約串,而與非終結符無關。規范歸約:自上而下最右推導的逆過程。例4.12文法GE: E E+T|T T T*F|F F (E)|id 句子id*id+id的自下向上的語法分析過程。規范歸約是最右推導的逆過程。算符優先分析法中,去掉了單個非終結符的歸約。EE+TTT*FFididFid4.4.4 算符優先分析算法的設計 1 最左素短語定義: 句型的素短語是 一個短語;至少包含一個終結符;除自身之外不再包含其他素短語處于句型最左邊的素短語為最左素短語求文法GE的句型T+T*F+id的素短語和最左素短語E E+T|T T T*F|F F (E)|idE+ETE+TTT*FFid短語:,T*
9、F,T+T*Fid,T+T*F+id素短語:最左素短語:T*F, idT*FHomework: (P105)-4.64.4.4 算符優先分析算法的設計 2 識別最左素短語方法算符優先文法的句型可以表示為:$N1a1N2a2NnanNn+1$ ,Ni為VN或空,ai為VT.句型的最左素短語是滿足下列條件的最左子串NiaiNi+1ai+1.NjajNj+1 : ai-1 ai ai ai+1 , . ,aj-1 aj aj aj+1注意:出現在ai左端的Ni和aj右端的Nj+1屬于素短語.求句型 $T+T*F+id$ 的最左素短語。 把該句型寫成算符優先分析形式: $N1a1N2a2N3a3a4$
10、 由優先表得: $ a1 a2 a3 a4 $ 故最左素短語為:N2a2N3 即:T*F4.4.4 算符優先分析算法的設計 3 算符優先算法過程(移進歸約) (1)使用棧存放文法符號,初始化為$。 (2)如果當前棧頂終結符和待輸入符號之間的關系是 或 ,則移進輸入符號。 (3)如果當前棧頂終結符和待輸入符號之間的優先關系是 ,表明已找到最左素短語的尾,查找棧內優先關系相同的符號串,進行歸約。 (非終結符對可歸約串的識別沒有影響,在歸約時可用任意的N代替。) (4)如果出現兩個終結符之間沒有任何優先關系,則出錯。 (5)當讀到句子結束符$,棧中只剩下$N時,成功。對4.12中的文法GE: E E+T|T T T*F|F F (E)|id寫出輸入串id+id$的算符優先分析過程。 S棧優先關系 當前符號 輸入流 動作$id$N$N+$N+id$N+N$N id + + id $ $ $+id$id$id$ 移進 歸約 移進 移進 歸約 歸約 接受 S棧優先關系 當前符號 輸入流 動作 4.4.6 算符優先分析法的局限性 1 一般語言的文法很難滿足算符優先文法的條件,僅在表
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025標準商業借款合同范本
- 2024年診斷用藥項目資金需求報告代可行性研究報告
- 2025年視覺識別設計合同范本
- 2025信托公司與銀行存款保管合同
- 2025解除勞動合同協議書樣本格式
- 2025商業店鋪租賃合同模板
- 2025年度合作合同貨車掛靠協議
- 2025華瑞科技產品銷售合同副本(修正版)
- 2025健身教練勞動合同范本
- 2025音樂演出取消、延遲保險合同
- 離職體檢免責協議書
- 光電工程師需掌握的常用計算試題及答案
- 煙草證借用合同范本
- 燒燙傷培訓課件
- 3D打印在康復輔具中的應用-全面剖析
- 煤礦重大事故隱患判定標準解讀與查找方法山西應急管理廳培訓課件
- 縣級安全生產大講堂課件
- 工業廢水處理工考核要素細目表與考核內容結構表(征求意見稿)
- 北京市門頭溝區2025屆高三一模考試生物試題(原卷版+解析版)
- 有限合伙制私募股權基金整體框架圖解及案例
- 2025年中小學教師資格考試題庫大全及答案
評論
0/150
提交評論