《計(jì)算機(jī)編譯原理第04(4)章》由會員分享，可在線閱讀，更多相關(guān)《計(jì)算機(jī)編譯原理第04(4)章（23頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、Reading Fun,Sub topics go here,*,4.4.4,算符優(yōu)先分析算法的設(shè)計(jì),對于算符優(yōu)先分析法，它雖然是一種自下而上的語法分析方法，但它并不是,一種規(guī)范歸約,的分析方法。,4.4.4,算符優(yōu)先分析算法的設(shè)計(jì),這是因?yàn)樵谒惴麅?yōu)先文法中，僅在終結(jié)符號之間定義優(yōu)先關(guān)系而未對非終結(jié)符定義優(yōu)先關(guān)系，從而無法使用優(yōu)先關(guān)系表去識別由單個(gè)非終結(jié)符組成的可歸約串，這也就是說，算符優(yōu)先分析法不是用,句柄,來刻畫可歸約串，而是用,最左素短語,來刻畫可歸約串的。,4.4.4,算符優(yōu)先分析算法的設(shè)計(jì),1.,最左素短語,所謂句型的,素短語,是指這樣一種短語，它至少包含一個(gè)終結(jié)符，并且除自身之外，

2、不再包含其它的素短語。句型最左邊的素短語稱,最左素短語,。,4.4.4,算符優(yōu)先分析算法的設(shè)計(jì),例如，有文法,G E,E,E+T|T,T T,*,F|F,F (E)|id,求該文法句型,T+T*F+id,的素短語和最左素短語。,首先給出句型,T+T,*,F+id,的語法樹,見,下圖,:,4.4.4,算符優(yōu)先分析算法的設(shè)計(jì),其短語有：,T+T,*,F+id,T+T,*,F,T,T,*,F,id,由素短語定義可知,T,*,F,和,id,是素短語。,T,*,F,為最左素短語。,注意,：,T,是該句型的句柄，而不是素短語。,E,E,+,T,E +T F,T T *F id,4.4.4,算符優(yōu)先分析算法

3、的設(shè)計(jì),2,.,識別句型最左素短語的方法,由算符文法的定義可知，算符優(yōu)先文法的任何句型都沒有相鄰的兩個(gè)非終結(jié)符。,其句型總可以表示成：,$N,1,a,1,N,2,a,2,N,n,a,n,N,n+1,$,其中每個(gè),N,i,為非終結(jié)符或空,a,i,為終結(jié)符,（,1in,）,4.4.4,算符優(yōu)先分析算法的設(shè)計(jì),對算符優(yōu)先文法,G,有如下定理：,一個(gè)算符優(yōu)先文法,G,的任何句型的最左素短語是滿足下列條件的最左子串,:,N,i,a,i,N,i+1,a,i+1,a,j,N,j+1,a,i-1,a,i,.,6.3.3,算符優(yōu)先分析算法的設(shè)計(jì),需要指出的是出現(xiàn)在,a,i,左端的非終結(jié)符,N,i,和,a,j,右

4、端的非終結(jié)符,N,j+1,是屬于素短語的。,這是由于算符文法的任何句型中終結(jié)符和非終結(jié)符相鄰時(shí)含終結(jié)符的短語必含相鄰非終結(jié)符。,4.4.4,算符優(yōu)先分析算法的設(shè)計(jì),對上述句型,$T+T,*,F+id$,寫成算符優(yōu)先分析形式為：,a,i,a,i+1,a,j-1,a,j,=,.,=,.,a,j,a,j+1,.,a,i-1,a,i,.,$N,1,a,1,N,2,a,2,N,3,a,3,a,4,$,因有,$+,*,+$,.,.,.,故由最左素短語定理有,N,2,a,2,N,3,即,T,*,F,是,最左素短語。,4.4.4,算符優(yōu)先分析算法的設(shè)計(jì),根據(jù)最左素短語的定理,，最左素短語中的終結(jié)符號具有相同的

5、優(yōu)先關(guān)系，并且，由于最左素短語中的符號是當(dāng)時(shí)最先要?dú)w約的串，其優(yōu)先關(guān)系先于最左素短語之外的符號，所以,我們使用一個(gè)用于存放文法符號的先進(jìn)后出棧，并利用優(yōu)先關(guān)系表，可以確定最左素短語是否已形成來決定分析器的動作,。,3.,算符優(yōu)先分析程序的設(shè)計(jì),4.4.4,算符優(yōu)先分析算法的設(shè)計(jì),基本思想,:,$,t,1,t,3,t,j+1,t,2,t,j,t,i+1,t,n,$,符號棧,優(yōu)先關(guān)系,t,i,尾,頭,最左素短語,3.,算符優(yōu)先分析程序的設(shè)計(jì),.,=,.,.,.,.,a,j,a,j+1,a,i,a,i,a,j-1,a,j,=,.,=,.,返回圖,4.4.4,算符優(yōu)先分析算法的設(shè)計(jì),下面給出算符優(yōu)先分

6、析算法,。,輸入：輸入符號串,W,和優(yōu)先關(guān)系表。,輸出：若,W,是正確的句子，則接收，,否則輸出錯(cuò)誤信息。,方法：執(zhí)行下圖算法。,棧置初值,K,1,SK,$,當(dāng)前輸入符號讀入,a,SK,是終結(jié)符？,j,K,Y,j,K1,N,S j,是終結(jié)符？,Q,S j ,j,j-1,Y,S j+1SK,是最左素短語,K,j+1,SK,N,Y.,K=2,且,a=$?,結(jié)束,Y,N,SK,a,K,K+1,Y,error,N,j,j-1,N,S j a?,.,S j,a?,或,S j,a?,N,.,=,.,Y,S j Q?,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.

7、,.,=,.,.,.,.,.,歸約,id,$,移進(jìn),$,.,歸約,$,.,$,=,.,結(jié)束,$,id,+id$,移進(jìn),.,.,$N,+,id$,移進(jìn),.,歸約,4.4.6,算符優(yōu)先分析法的局限性,由于算符優(yōu)先分析法跳過了所有單非產(chǎn)生式之間的歸約，這樣算符優(yōu)先分析比規(guī)范歸約要快得多，這既是優(yōu)點(diǎn)也是缺點(diǎn)。,由于忽略非終結(jié)符在歸約過程中的作用，可能導(dǎo)致把本來不是句子的輸入串誤認(rèn)為是文法句子。,4.4.6,算符優(yōu)先分析法的局限性,設(shè)有算符優(yōu)先文法,A A;D|D,D D(E)|F,F a|(A),E E+A|A,6.3.6,算符優(yōu)先分析法的局限性,該文法對應(yīng)的算符優(yōu)先關(guān)系表如下表所示。,；,a,+,(

8、,),$,;,a,+,(,),$,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,=,.,=,.,4.4.6,算符優(yōu)先分析法的局限性,對輸入串,(a,a),進(jìn)行算符優(yōu)先分析,其結(jié)果能正確地進(jìn)行歸約。,但是，從該文法推導(dǎo)不出,(a,a),。,即輸入串,(a,a),不是文法句子。,當(dāng)然，算符優(yōu)先分析的這種局限性可以從技術(shù)上加以彌補(bǔ)。,Transitional Page,Backdrops:,-These are full sized backdrops,just scale them up!,-Can be Copy-Pasted out of Templates for use anywhere!,,