編譯原理 算符優(yōu)先分析法PPT課件

1、2021/3/914.3 自下而上分析法的一般原理 1 1 自下而上語法分析概述自下而上語法分析概述 基本思想：基本思想：用一個寄存文法符號的棧棧，將一個輸入串反向歸約歸約至文法的開始符號。 特點：特點：效率高、文法限制少。2021/3/921 1 自下而上語法分析概述自下而上語法分析概述 移進歸約過程實例。 例4.11 設(shè)有文法GA： (1)A aBcDe (2)B b (3)B Bb (4)D d對輸入串a(chǎn)bbcde$的移進歸約分析過程2021/3/93 對輸入串a(chǎn)bbcde$移進歸約分析過程： 步驟 符號棧 輸入串 動作012345678910$a$ab$aB$aBb$aB$aBc$aB

2、cd$aBcD$aBcDe$Aabbcde$bbcde$bcde$bcde$cde$cde$de$e$e$a進棧b進棧用B b歸約b進棧用B Bb歸約c進棧d進棧用D d歸約e進棧用A aBcDe歸約分析成功2021/3/942 2 移進歸約的基本思想 (1)用一個棧寄存文法符號，將一個終結(jié)符推進棧; (2)是將0個或多個符號從棧中彈出，用相應(yīng)產(chǎn)生式的左部一個非終結(jié)符壓入棧; 把棧頂被歸約的一串符號稱為 (3)重復(fù)這一過程直至整個輸入串分析完畢; (4)最終棧中，則所分析的輸入串是文法的正確句子;否則，出錯?？蓺w約串可歸約串2021/3/953 分類 算符優(yōu)先分析法算符優(yōu)先分析法 規(guī)范歸約分析

3、法 簡單優(yōu)先分析法 LR分析法分析法用 刻畫可歸約串用 刻畫可歸約串2021/3/964.4 4.4 算符優(yōu)先分析法算符優(yōu)先分析法 4.4.1 方法概述 1 特點 適合分析各類表達式; 宜于手工實現(xiàn); 規(guī)定運算符之間的優(yōu)先順序(優(yōu)先關(guān)系，結(jié)合性質(zhì))。 通過比較算符之間的優(yōu)先關(guān)系確定可歸約串。2021/3/974.4.1 方法概述 2 優(yōu)先關(guān)系 例 文法GE： E E+E|E*E|(E)|id 對輸入串id+id*id的規(guī)范歸約過程。(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

4、*id(5)E*E(6)E*優(yōu)先于：優(yōu)先于*：2021/3/984.4.1 方法概述 3 優(yōu)先關(guān)系種類 任何兩個a和b可能的優(yōu)先關(guān)系有3種： a b: a的優(yōu)先級低于b a b: a的優(yōu)先級等于b a b: a的優(yōu)先級高于b注：優(yōu)先關(guān)系與出現(xiàn)的有關(guān)，不同于數(shù)學(xué)符號。2021/3/994.4.1 方法概述 4 優(yōu)先關(guān)系矩陣(表) 矩陣的行和列都是文法的終結(jié)符; 矩陣元素是兩終結(jié)符間的優(yōu)先關(guān)系。 算符優(yōu)先分析法借助優(yōu)先關(guān)系表尋找句型的可歸約串。2021/3/910 算符優(yōu)先關(guān)系表實例 + * id ( ) $ + * id ( ) $棧頂?shù)谝粋€終結(jié)符當(dāng)前輸入串首字符2021/3/9114.4.2

5、算符優(yōu)先文法的定義 1 算符文法的定義 設(shè)有文法G，若G中沒有形如U VW的規(guī)則，其中V和W為非終結(jié)符，則G稱為算符文法，也稱OG文法。性質(zhì)： 1.在算符文法中任何句型都不包含兩個相鄰的非終結(jié)符。 2.如Ab或bA出現(xiàn)在算符文法的句型 中，則 中任何含b的短語必含有A。2021/3/9124.4.2 算符優(yōu)先文法的定義 2 算符優(yōu)先關(guān)系的定義 在OG中定義算符優(yōu)先關(guān)系： (1)a b :含有P ab，或 P aQb的 規(guī)則。 (2)a b :含有P aR的規(guī)則，且R b或 R Qb (3)a b:含有P Rb的規(guī)則，且R a或 R aQ。2021/3/9134.4.2 算符優(yōu)先文法的定義 2

6、算符優(yōu)先關(guān)系的定義 規(guī)定： 若S a或S Ca，則$ a 若S a或S aC，則a $2021/3/9144.4.2 算符優(yōu)先文法的定義 3 算符優(yōu)先文法的定義 設(shè)有一個不含 規(guī)則的OG文法G， 如果任意兩個終結(jié)符間至多有一種算符關(guān)系存在， 則稱G是算符優(yōu)先文法，也稱OPG文法。 結(jié)論：算符優(yōu)先文法是無二義的。2021/3/9154.4.3 算符優(yōu)先關(guān)系表的構(gòu)造 1 FIRSTVT集、 LASTVT集 FIRSTVT(A)=b|A b 或 A Bb ,b VT,B VN 即：非終結(jié)符往下推導(dǎo)所有可能出現(xiàn)的首個算符的集合LASTVT(A)=a|A a A aB, a VT,B VN 即：非終結(jié)符

7、往下推導(dǎo)所有可能出現(xiàn)的最后一個算符的集合2021/3/9164.4.3 算符優(yōu)先關(guān)系表的構(gòu)造 2 算符優(yōu)先關(guān)系表的構(gòu)造方法 (1)為每個非終結(jié)符計算FIRSTVT(A),LASTVT(A) (2)計算算符之間的優(yōu)先關(guān)系，并填表。計算方法： 關(guān)系:若Aab 或A aBb,則a b 關(guān)系:若A aB,則 b FIRSTVT(B),a b 關(guān)系:若A Bb,則 a LASTVT(B),a b (3) 最后，在表中填入的優(yōu)先關(guān)系：對FIRSTVT(S)中所有b,置$ b; 對 LASTVT(S)中所有a,置a $. 置 $ $。 2021/3/917例4.12 文法GE: E E+T|T T T*F|

8、F F (E)|id構(gòu)造該文法的算符優(yōu)先關(guān)系表。 FIRSTVT LASTVT E T F +,*,(,id *,(,id (,id +,*,),id *,),id ),idHomework: (P105)- 4.5 (2)2021/3/9184.4.4 算符優(yōu)先分析算法的設(shè)計 0 算符優(yōu)先分析法與規(guī)范歸約的區(qū)別算符優(yōu)先分析法:只考慮終結(jié)符之間的優(yōu)先關(guān)系來確定可歸約串，而與非終結(jié)符無關(guān)。規(guī)范歸約:自上而下最右推導(dǎo)的逆過程。2021/3/919例4.12文法GE: E E+T|T T T*F|F F (E)|id 句子id*id+id的自下向上的語法分析過程。規(guī)范歸約是最右推導(dǎo)的逆過程。算符優(yōu)先

9、分析法中，去掉了單個非終結(jié)符的歸約。EE+TTT*FFididFid2021/3/9204.4.4 算符優(yōu)先分析算法的設(shè)計 1 最左素短語定義： 句型的素短語是 一個短語；至少包含一個終結(jié)符；除自身之外不再包含其他素短語處于句型最左邊的素短語為最左素短語2021/3/921求文法GE的句型T+T*F+id的素短語和最左素短語E E+T|T T T*F|F F (E)|idE+ETE+TTT*FFid短語：,T*F,T+T*Fid,T+T*F+id素短語：最左素短語：T*F, idT*FHomework: (P105)-4.62021/3/9224.4.4 算符優(yōu)先分析算法的設(shè)計 2 識別最左素

10、短語方法算符優(yōu)先文法的句型可以表示為：$N1a1N2a2NnanNn+1$ ,Ni為VN或空,ai為VT.句型的最左素短語是滿足下列條件的最左子串NiaiNi+1ai+1.NjajNj+1 : ai-1 ai ai ai+1 , . ,aj-1 aj aj aj+1注意:出現(xiàn)在ai左端的Ni和aj右端的Nj+1屬于素短語.2021/3/923求句型 $T+T*F+id$ 的最左素短語。 把該句型寫成算符優(yōu)先分析形式: $N1a1N2a2N3a3a4$ 由優(yōu)先表得: $ a1 a2 a3 a4 $ 故最左素短語為:N2a2N3 即:T*F2021/3/9244.4.4 算符優(yōu)先分析算法的設(shè)計 3

11、 算符優(yōu)先算法過程(移進歸約) (1)使用棧存放文法符號,初始化為$。 (2)如果當(dāng)前棧頂終結(jié)符和待輸入符號之間的關(guān)系是 或 ,則移進輸入符號。 (3)如果當(dāng)前棧頂終結(jié)符和待輸入符號之間的優(yōu)先關(guān)系是 ,表明已找到最左素短語的尾,查找棧內(nèi)優(yōu)先關(guān)系相同的符號串,進行歸約。 (非終結(jié)符對可歸約串的識別沒有影響,在歸約時可用任意的N代替。) (4)如果出現(xiàn)兩個終結(jié)符之間沒有任何優(yōu)先關(guān)系,則出錯。 (5)當(dāng)讀到句子結(jié)束符$,棧中只剩下$N時,成功。2021/3/925對4.12中的文法GE： E E+T|T T T*F|F F (E)|id寫出輸入串id+id$的算符優(yōu)先分析過程。 S棧優(yōu)先關(guān)系 當(dāng)前符號 輸入流 動作$id$N$N+$N+id$N+N$N id + + id $ $ $+id$id$id$ 移進 歸約 移進 移進 歸約 歸約 接受 S棧優(yōu)先關(guān)系 當(dāng)前符號 輸入流 動作 2021/3/9264.4.6 算符優(yōu)先分析法的局限性 1 一般語言的文法很難滿足算符優(yōu)先文法的條件，僅在表達式局部中應(yīng)用; 2 由于忽略非終結(jié)符在歸約過程中的作用，可能導(dǎo)致對錯誤的句子得到正確的