計(jì)算機(jī)編譯原理第04(4)章

Reading Fun,Sub topics go here,*,4.4.4,算符優(yōu)先分析算法的設(shè)計(jì),對(duì)于算符優(yōu)先分析法，它雖然是一種自下而上的語(yǔ)法分析方法，但它并不是,一種規(guī)范歸約,的分析方法4.4.4,算符優(yōu)先分析算法的設(shè)計(jì),這是因?yàn)樵谒惴麅?yōu)先文法中，僅在終結(jié)符號(hào)之間定義優(yōu)先關(guān)系而未對(duì)非終結(jié)符定義優(yōu)先關(guān)系，從而無(wú)法使用優(yōu)先關(guān)系表去識(shí)別由單個(gè)非終結(jié)符組成的可歸約串，這也就是說(shuō)，算符優(yōu)先分析法不是用,句柄,來(lái)刻畫(huà)可歸約串，而是用,最左素短語(yǔ),來(lái)刻畫(huà)可歸約串的4.4.4,算符優(yōu)先分析算法的設(shè)計(jì),1.,最左素短語(yǔ),所謂句型的,素短語(yǔ),是指這樣一種短語(yǔ)，它至少包含一個(gè)終結(jié)符，并且除自身之外，不再包含其它的素短語(yǔ)句型最左邊的素短語(yǔ)稱,最左素短語(yǔ),4.4.4,算符優(yōu)先分析算法的設(shè)計(jì),例如，有文法,G E,E,E+T|T,T T,*,F|F,F (E)|id,求該文法句型,T+T*F+id,的素短語(yǔ)和最左素短語(yǔ)首先給出句型,T+T,*,F+id,的語(yǔ)法樹(shù),見(jiàn),下圖,:,4.4.4,算符優(yōu)先分析算法的設(shè)計(jì),其短語(yǔ)有：,T+T,*,F+id,T+T,*,F,T,T,*,F,id,由素短語(yǔ)定義可知,T,*,F,和,id,是素短語(yǔ)。

T,*,F,為最左素短語(yǔ)注意,：,T,是該句型的句柄，而不是素短語(yǔ)E,E,+,T,E +T F,T T *F id,4.4.4,算符優(yōu)先分析算法的設(shè)計(jì),2,.,識(shí)別句型最左素短語(yǔ)的方法,由算符文法的定義可知，算符優(yōu)先文法的任何句型都沒(méi)有相鄰的兩個(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ì),對(duì)算符優(yōu)先文法,G,有如下定理：,一個(gè)算符優(yōu)先文法,G,的任何句型的最左素短語(yǔ)是滿足下列條件的最左子串,:,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,右端的非終結(jié)符,N,j+1,是屬于素短語(yǔ)的這是由于算符文法的任何句型中終結(jié)符和非終結(jié)符相鄰時(shí)含終結(jié)符的短語(yǔ)必含相鄰非終結(jié)符4.4.4,算符優(yōu)先分析算法的設(shè)計(jì),對(duì)上述句型,$T+T,*,F+id$,寫(xiě)成算符優(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,$,因有,$+,*,+$,.,.,.,故由最左素短語(yǔ)定理有,N,2,a,2,N,3,即,T,*,F,是,最左素短語(yǔ)。

4.4.4,算符優(yōu)先分析算法的設(shè)計(jì),根據(jù)最左素短語(yǔ)的定理,，最左素短語(yǔ)中的終結(jié)符號(hào)具有相同的優(yōu)先關(guān)系，并且，由于最左素短語(yǔ)中的符號(hào)是當(dāng)時(shí)最先要?dú)w約的串，其優(yōu)先關(guān)系先于最左素短語(yǔ)之外的符號(hào)，所以,我們使用一個(gè)用于存放文法符號(hào)的先進(jìn)后出棧，并利用優(yōu)先關(guān)系表，可以確定最左素短語(yǔ)是否已形成來(lái)決定分析器的動(dòng)作,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,$,符號(hào)棧,優(yōu)先關(guān)系,t,i,尾,頭,最左素短語(yǔ),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)先分析算法,輸入：輸入符號(hào)串,W,和優(yōu)先關(guān)系表輸出：若,W,是正確的句子，則接收，,否則輸出錯(cuò)誤信息方法：執(zhí)行下圖算法棧置初值,K,1,SK,$,當(dāng)前輸入符號(hào)讀入,a,SK,是終結(jié)符？,j,K,Y,j,K1,N,S j,是終結(jié)符？,Q,S j ,j,j-1,Y,S j+1SK,是最左素短語(yǔ),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?,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,=,.,.,.,.,.,歸約,id,$,移進(jìn),$,.,歸約,$,.,$,=,.,結(jié)束,$,id,+id$,移進(jìn),.,.,$N,+,id$,移進(jìn),.,歸約,4.4.6,算符優(yōu)先分析法的局限性,由于算符優(yōu)先分析法跳過(guò)了所有單非產(chǎn)生式之間的歸約，這樣算符優(yōu)先分析比規(guī)范歸約要快得多，這既是優(yōu)點(diǎn)也是缺點(diǎn)。

由于忽略非終結(jié)符在歸約過(guò)程中的作用，可能導(dǎo)致把本來(lái)不是句子的輸入串誤認(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)先分析法的局限性,該文法對(duì)應(yīng)的算符優(yōu)先關(guān)系表如下表所示a,+,(,),$,;,a,+,(,),$,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,=,.,=,.,4.4.6,算符優(yōu)先分析法的局限性,對(duì)輸入串,(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!,,。