《計算機編譯原理第04(4)章》由會員分享，可在線閱讀，更多相關《計算機編譯原理第04(4)章（23頁珍藏版）》請在裝配圖網上搜索。
1、Reading Fun,Sub topics go here,*,4.4.4,算符優先分析算法的設計,對于算符優先分析法，它雖然是一種自下而上的語法分析方法，但它并不是,一種規范歸約,的分析方法。,4.4.4,算符優先分析算法的設計,這是因為在算符優先文法中，僅在終結符號之間定義優先關系而未對非終結符定義優先關系，從而無法使用優先關系表去識別由單個非終結符組成的可歸約串，這也就是說，算符優先分析法不是用,句柄,來刻畫可歸約串，而是用,最左素短語,來刻畫可歸約串的。,4.4.4,算符優先分析算法的設計,1.,最左素短語,所謂句型的,素短語,是指這樣一種短語，它至少包含一個終結符，并且除自身之外，
2、不再包含其它的素短語。句型最左邊的素短語稱,最左素短語,。,4.4.4,算符優先分析算法的設計,例如，有文法,G E,E,E+T|T,T T,*,F|F,F (E)|id,求該文法句型,T+T*F+id,的素短語和最左素短語。,首先給出句型,T+T,*,F+id,的語法樹,見,下圖,:,4.4.4,算符優先分析算法的設計,其短語有：,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,算符優先分析算法
3、的設計,2,.,識別句型最左素短語的方法,由算符文法的定義可知，算符優先文法的任何句型都沒有相鄰的兩個非終結符。,其句型總可以表示成：,$N,1,a,1,N,2,a,2,N,n,a,n,N,n+1,$,其中每個,N,i,為非終結符或空,a,i,為終結符,（,1in,）,4.4.4,算符優先分析算法的設計,對算符優先文法,G,有如下定理：,一個算符優先文法,G,的任何句型的最左素短語是滿足下列條件的最左子串,:,N,i,a,i,N,i+1,a,i+1,a,j,N,j+1,a,i-1,a,i,.,6.3.3,算符優先分析算法的設計,需要指出的是出現在,a,i,左端的非終結符,N,i,和,a,j,右
4、端的非終結符,N,j+1,是屬于素短語的。,這是由于算符文法的任何句型中終結符和非終結符相鄰時含終結符的短語必含相鄰非終結符。,4.4.4,算符優先分析算法的設計,對上述句型,$T+T,*,F+id$,寫成算符優先分析形式為：,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,算符優先分析算法的設計,根據最左素短語的定理,，最左素短語中的終結符號具有相同的
5、優先關系，并且，由于最左素短語中的符號是當時最先要歸約的串，其優先關系先于最左素短語之外的符號，所以,我們使用一個用于存放文法符號的先進后出棧，并利用優先關系表，可以確定最左素短語是否已形成來決定分析器的動作,。,3.,算符優先分析程序的設計,4.4.4,算符優先分析算法的設計,基本思想,:,$,t,1,t,3,t,j+1,t,2,t,j,t,i+1,t,n,$,符號棧,優先關系,t,i,尾,頭,最左素短語,3.,算符優先分析程序的設計,.,=,.,.,.,.,a,j,a,j+1,a,i,a,i,a,j-1,a,j,=,.,=,.,返回圖,4.4.4,算符優先分析算法的設計,下面給出算符優先分
6、析算法,。,輸入：輸入符號串,W,和優先關系表。,輸出：若,W,是正確的句子，則接收，,否則輸出錯誤信息。,方法：執行下圖算法。,棧置初值,K,1,SK,$,當前輸入符號讀入,a,SK,是終結符？,j,K,Y,j,K1,N,S j,是終結符？,Q,S j ,j,j-1,Y,S j+1SK,是最左素短語,K,j+1,SK,N,Y.,K=2,且,a=$?,結束,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,$,移進,$,.,歸約,$,.,$,=,.,結束,$,id,+id$,移進,.,.,$N,+,id$,移進,.,歸約,4.4.6,算符優先分析法的局限性,由于算符優先分析法跳過了所有單非產生式之間的歸約，這樣算符優先分析比規范歸約要快得多，這既是優點也是缺點。,由于忽略非終結符在歸約過程中的作用，可能導致把本來不是句子的輸入串誤認為是文法句子。,4.4.6,算符優先分析法的局限性,設有算符優先文法,A A;D|D,D D(E)|F,F a|(A),E E+A|A,6.3.6,算符優先分析法的局限性,該文法對應的算符優先關系表如下表所示。,；,a,+,(
8、,),$,;,a,+,(,),$,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,=,.,=,.,4.4.6,算符優先分析法的局限性,對輸入串,(a,a),進行算符優先分析,其結果能正確地進行歸約。,但是，從該文法推導不出,(a,a),。,即輸入串,(a,a),不是文法句子。,當然，算符優先分析的這種局限性可以從技術上加以彌補。,Transitional Page,Backdrops:,-These are full sized backdrops,just scale them up!,-Can be Copy-Pasted out of Templates for use anywhere!,,
計算機編譯原理第04(4)章
