編譯原理:第五章 語法分析5_第1頁
編譯原理:第五章 語法分析5_第2頁
編譯原理:第五章 語法分析5_第3頁
編譯原理:第五章 語法分析5_第4頁
編譯原理:第五章 語法分析5_第5頁
已閱讀5頁,還剩9頁未讀, 繼續免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、 簡單優先分析法是一種從左到右掃描、最左歸約分析法;它屬于自底向上分析方法。 該方法利用文法符號之間的優先關系來確定待歸約的句柄 ,即可確定當前句型的句柄。5.5 簡單優先分析法 利用一個分析表,登記選擇句柄產生式的知識; 利用一個分析棧,記錄分析過程;【分析算法】依次讀取單詞,并進行如下操作: 當棧頂出現句柄時,規約之,否則移進。 5.5.1. 簡單優先分析法基本概念 簡單優先分析法的基本要點有三:1. 什么是簡單優先分析法? 2. 簡單優先分析過程示例 符號串: = abbeae #SaAeBSbbaG(S): SaAeB|b ASb|e BaAAe 句柄產生式 操 作 剩余串 w 分析棧

2、 移進,NEXT a e # e# a 移進,NEXT e # a# a A 移進,NEXT # e# a A e 歸約 A - e # aAe a 歸約 B - aA # aAe a A - Sb S - b 歸約 e a e # b# a 移進,NEXT b b e a e # a# 歸約 a e # e # a S 移進,NEXT e a e # b# a 移進,NEXT b e a e # b# A A a a b e e句柄(接上頁) 利用分析棧記錄行分析過程:【注】何時棧頂出現句柄?怎樣求當前句柄產生式 ?設 待分析的符號串: abbeae# S b# aAe # B句柄 S -

3、aAeB 歸約# # S OK同時歸約者為相等關系,記作 ;3. 文法符號之間的優先關系歸約過程中如何確認句柄? 是否是句柄,還要看其所在符號串中的位置。語法樹從語法樹上,找出優先關系(指相臨符號之間)如下: S b,a A,A e,e B 如:左后歸約者為小于關系,記作; 如:ab,ae, e; 如:bb,be 當把優先關系納入待分析的符號串時,有如下關系: # a b e a # # a e a # # a A e a # # a A e # # # 結論:一個句型的句柄,位于第一次(自左至右)出現在之間的符號串! 從文法中獲取優先關系! 設si ,sj是兩個文法符號; 如:a A,A e

4、,e B,S b; si sj ,當且僅當有Usi sj ; 優先關系的定義 G(S): SaAeB|b ASb|e BaA si +如:ae,aS,aa,ab,esj ,當且僅當有 UVsj ,且 V si; = +如:bb,Bb,Ab,eb。 (3)頭符號集合和尾符號集合 設 AVN, si ,sj是兩個文法符號;則: FIRSTVT(A)=si| A si, = +LASTVT(A) = sj|A sj。 = +【例5.12】G(S): SaAeB|b,ASb|e,BaA S A B a b e S A B a e S A BFIRSTVT a , b S,e,a,b aLASTVT B

5、,b,A,e b , e A , b , e 頭符號集合尾符號集合優先矩陣表項=空表示兩個符號不可能相臨。 +簡單優先分析器的基本組成:優先分析法要求文法應是簡單優先文法。優先矩陣分析表 優先分析控制器 分析中只查看當前符號就可確認句柄;5.5.2 簡單優先分析器設計1.簡單優先文法及其判定 文法產生式沒有相同的右部; 如A ,B , 滿足下述特點的文法稱為簡單優先文法。例5.12 文法,就是簡單優先文法,請看:文法符號之間至多有一種優先關系! 【算法】 si sj , 當且僅當有Usi sj ; si sj , 當且僅當有UVsj,且siLASTVT(V)。 2. 簡單優先分析矩陣分析表構造

6、設 W,VVN,si,sj是兩個文法符號; 簡單優先分析表是優先分析法的知識表,是文法的一種機內表示形式:終結符 +非終結符+# a Z #優先關系符號終結符+非終結符+#3. 簡單優先控制程序設計開始PUSH(#)NEXT(w)查優先分析表R(Xk,w)=? 空?nerr(#S#) 結束PUSH WPOP(sj),POP(sj-1),POP(si);PUSH(A)。從sj(棧頂符)開始,往棧內查找,找到第一個使si-1?yn只考慮算符(終結符)之間的優先關系 (1)算符文法 設有一文法G,如果G中沒有形如AQR的產生式,其中Q和R為非終結符,則稱該文法為算符文法(OG文法)。 5.5.3 算

7、符優先分析(2)頭符號集合和尾符號集合 設 aVT,P,RVN, 則: FIRSTVT(P)=a| P a 或 P Ra, = +LASTVT(P) =a| P a 或 P aR。 = + = + = +設a,bVT,P,Q,RVN, a b , 當且僅當有 Pab 或 PaQb ; (3) 算符優先關系定義 a + ab , 當且僅當有 PRb ,且R a 或 R aQ; = +(4)算符優先文法 如果算符文法G中的任何一對終結符a和b之間,僅滿足上述一種關系,則G就是一個算符優先文法(OPG)。 = + = +習題:【習題5.13】已知下述文法:G(E): E - T | E + T | E - T

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論