編譯原理：第五章 語法分析5

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

2、 移進(jìn),NEXT a e # e# a 移進(jìn),NEXT e # a# a A 移進(jìn),NEXT # e# a A e 歸約 A - e # aAe a 歸約 B - aA # aAe a A - Sb S - b 歸約 e a e # b# a 移進(jìn),NEXT b b e a e # a# 歸約 a e # e # a S 移進(jìn),NEXT e a e # b# a 移進(jìn),NEXT b e a e # b# A A a a b e e句柄(接上頁) 利用分析棧記錄行分析過程：【注】何時(shí)棧頂出現(xiàn)句柄？怎樣求當(dāng)前句柄產(chǎn)生式 ？設(shè) 待分析的符號(hào)串: abbeae# S b# aAe # B句柄 S -

3、aAeB 歸約# # S OK同時(shí)歸約者為相等關(guān)系，記作 ；3. 文法符號(hào)之間的優(yōu)先關(guān)系歸約過程中如何確認(rèn)句柄？ 是否是句柄，還要看其所在符號(hào)串中的位置。語法樹從語法樹上，找出優(yōu)先關(guān)系（指相臨符號(hào)之間）如下： S b，a A，A e，e B 如：左后歸約者為小于關(guān)系，記作； 如：ab,ae, e； 如：bb,be 當(dāng)把優(yōu)先關(guān)系納入待分析的符號(hào)串時(shí)，有如下關(guān)系： # a b e a # # a e a # # a A e a # # a A e # # # 結(jié)論：一個(gè)句型的句柄，位于第一次（自左至右）出現(xiàn)在之間的符號(hào)串！ 從文法中獲取優(yōu)先關(guān)系! 設(shè)si ，sj是兩個(gè)文法符號(hào); 如：a A，A e

4、，e B，S b； si sj ，當(dāng)且僅當(dāng)有Usi sj ； 優(yōu)先關(guān)系的定義 G(S): SaAeB|b ASb|e BaA si +如：ae，aS，aa，ab，esj ，當(dāng)且僅當(dāng)有 UVsj ，且 V si； = +如：bb，Bb，Ab，eb。 (3)頭符號(hào)集合和尾符號(hào)集合 設(shè) AVN， si ，sj是兩個(gè)文法符號(hào);則: 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 頭符號(hào)集合尾符號(hào)集合優(yōu)先矩陣表項(xiàng)=空表示兩個(gè)符號(hào)不可能相臨。 +簡單優(yōu)先分析器的基本組成：優(yōu)先分析法要求文法應(yīng)是簡單優(yōu)先文法。優(yōu)先矩陣分析表 優(yōu)先分析控制器 分析中只查看當(dāng)前符號(hào)就可確認(rèn)句柄；5.5.2 簡單優(yōu)先分析器設(shè)計(jì)1.簡單優(yōu)先文法及其判定 文法產(chǎn)生式?jīng)]有相同的右部； 如A ，B ， 滿足下述特點(diǎn)的文法稱為簡單優(yōu)先文法。例5.12 文法，就是簡單優(yōu)先文法，請(qǐng)看：文法符號(hào)之間至多有一種優(yōu)先關(guān)系！ 【算法】 si sj ， 當(dāng)且僅當(dāng)有Usi sj ； si sj ， 當(dāng)且僅當(dāng)有UVsj，且siLASTVT(V)。 2. 簡單優(yōu)先分析矩陣分析表構(gòu)造

6、設(shè) W,VVN,si，sj是兩個(gè)文法符號(hào); 簡單優(yōu)先分析表是優(yōu)先分析法的知識(shí)表,是文法的一種機(jī)內(nèi)表示形式：終結(jié)符 +非終結(jié)符+# a Z #優(yōu)先關(guān)系符號(hào)終結(jié)符+非終結(jié)符+#3. 簡單優(yōu)先控制程序設(shè)計(jì)開始PUSH(#)NEXT(w)查優(yōu)先分析表R(Xk,w)=? 空?nerr(#S#) 結(jié)束PUSH WPOP(sj)，POP(sj-1)，POP(si)；PUSH(A)。從sj（棧頂符）開始，往棧內(nèi)查找，找到第一個(gè)使si-1?yn只考慮算符（終結(jié)符）之間的優(yōu)先關(guān)系 （1）算符文法 設(shè)有一文法G，如果G中沒有形如AQR的產(chǎn)生式，其中Q和R為非終結(jié)符，則稱該文法為算符文法（OG文法）。 5.5.3 算

7、符優(yōu)先分析(2)頭符號(hào)集合和尾符號(hào)集合 設(shè) aVT，P,RVN， 則: FIRSTVT(P)=a| P a 或 P Ra, = +LASTVT(P) =a| P a 或 P aR。 = + = + = +設(shè)a,bVT，P,Q,RVN， a b ， 當(dāng)且僅當(dāng)有 Pab 或 PaQb ； (3) 算符優(yōu)先關(guān)系定義 a + ab ， 當(dāng)且僅當(dāng)有 PRb ，且R a 或 R aQ； = +(4)算符優(yōu)先文法 如果算符文法G中的任何一對(duì)終結(jié)符a和b之間，僅滿足上述一種關(guān)系，則G就是一個(gè)算符優(yōu)先文法（OPG）。 = + = +習(xí)題：【習(xí)題5.13】已知下述文法：G(E): E - T | E + T | E - T