• /  74
  • 下載費用: 24.9積分  

編譯原理課件 第六章.ppt

'編譯原理課件 第六章.ppt'
第六章 屬性文法和語法制導翻譯1屬性文法2基于屬性文法的處理3S-屬性文法的自下而上計算4L-屬性文法和自頂向下翻譯5自下而上計算繼承屬性6.1 屬性文法屬性文法(也稱屬性翻譯文法)Knuth在1968年提出在上下文無關文法的基礎上,為每個文法符號(終結符或非終結符)配備若干相關的“值”(稱為屬性)。屬性代表與文法符號相關信息,如類型、值、代碼序列、符號表內容等屬性可以進行計算和傳遞語義規則:對于文法的每個產生式都配備了一組屬性的計算規則屬性綜合屬性:“自下而上”傳遞信息繼承屬性:“自上而下”傳遞信息在一個屬性文法中,對應于每個產生式A→?都有一套與之相關聯的語義規則,每條規則的形式為:b:=f(c1,c2,…,ck) 這里,f是一個函數,而且或者1. b是A的一個綜合屬性并且c1,c2,…,ck是產生式右邊文法符號的屬性,或者2. b是產生式右邊某個文法符號的一個繼承屬性并且c1,c2,…,ck 是A或產生式右邊任何文法符號的屬性。 屬性b依賴于屬性c1,c2,…,ck。說明終結符只有綜合屬性,由詞法分析器提供非終結符既可有綜合屬性也可有繼承屬性,文法開始符號的所有繼承屬性作為屬性計算前的初始值對出現在產生式右邊的繼承屬性和出現在產生式左邊的綜合屬性都必須提供一個計算規則。屬性計算規則中只能使用相應產生式中的文法符號的屬性出現在產生式左邊的繼承屬性和出現在產生式右邊的綜合屬性不由所給的產生式的屬性計算規則進行計算,它們由其它產生式的屬性規則計算或者由屬性計算器的參數提供語義規則所描述的工作可以包括屬性計算、靜態語義檢查、符號表操作、代碼生成等等。例,考慮非終結符A,B和C,其中,A有一個繼承屬性a和一個綜合屬性b,B有綜合屬性c,C有繼承屬性d。產生式A→BC可能有規則 C.d:=B.c+1 A.b:=A.a+B.c而屬性A.a和B.c在其它地方計算 產 生 式 L→En E→E1+T E→T T→T1*F T→F F→ (E) F→digit語 義 規 則print(E.val) E.val := E1.val+T.val E.val :=T.val T.val :=T1.val* F.val T.val :=F.val F.val :=E.val F.val :=digit.lexval綜合屬性在語法樹中,一個結點的綜合屬性的值由其子結點的屬性值確定。使用自底向上的方法在每一個結點處使用語義規則計算綜合屬性的值僅僅使用綜合屬性的屬性文法稱S-屬性文法 產 生 式 L→En E→E1+T E→T T→T1*F T→F F→ (E) F→digit語 義 規 則print(E.val) E.val := E1.val+T.val E.val :=T.val T.val :=T1.val* F.val T.val :=F.val F.val :=E.val F.val :=digit.lexval3*5+4n的帶注釋的語法樹 digit.lexval=3F.val=3T.val=3*digit.lexval=5F.val=5T.val=15E.val=15+digit.lexval=4F.val=4T.val=4E.val=19nL 產 生 式 語 義 規 則 L→En print(E.val) E→E1+T E.val := E1.val+T.val E→T E.val :=T.val T→T1*F T.val :=T1.val* F.val T→F T.val :=F.val F→ (E) F.val :=E.val F→digit F.val :=digit.lexval繼承屬性在語法樹中,一個結點的繼承屬性由此結點的父結點和/或兄弟結點的某些屬性確定用繼承屬性來表示程序設計語言結構中的上下文依賴關系很方便 產 生 式 語 義 規 則 D→TL L.in := T.type T→int T.type := integer T→real T.type := real L→L1, id L1.in :=L.in   addtype(id.entry, L.in) L→id addtype(id.entry, L.in) 句子real id1,id2,id3的帶注釋的語法樹 id1L,id2L,id3LrealTDT.type=realL.in=realL.in=realL.in=real產 生 式 語 義 規 則 D→TL L.in := T.type T→int T.type := integer T→real T.type := real L→L1, id L1.in :=L.in addtype(id.entry, L.in) L→id addtype(id.entry, L.in) 6.2 基于屬性文法的的處理方法 由源程序的語法結構所驅動的處理辦法就是語法制導翻譯法語義規則的計算產生代碼在符號表中存放信息給出錯誤信息執行任何其它動作對輸入符號串的翻譯也就是根據語義規則進行計算的結果。 輸入串語法樹依賴圖語義規則計算次序6.2 基于屬性文法的的處理方法 依賴圖樹遍歷一遍掃描6.2.1 依賴圖 在一棵語法樹中的結點的繼承屬性和綜合屬性之間的相互依賴關系可以由稱作依賴圖的一個有向圖來描述為每一個包含過程調用的語義規則引入一個虛綜合屬性b,這樣把每一個語義規則都寫成b:=f(c1,c2,…,ck) 的形式依賴圖中為每一個屬性設置一個結點,如果屬性b依賴于屬性c,則從屬性c的結點有一條有向邊連到屬性b的結點。for 語法樹中每一結點n do for 結點n的文法符號的每一個屬性a do 為a在依賴圖中建立一個結點;for語法樹中每一個結點n do for 結點n所用產生式對應的每一個語義規則 b:=f(c1,c2,…,ck ) do for i:=1 to k do 從ci結點到b結點構造一條有向邊; E→E1+E2 E.val:=E1.val+E2.val E1+E2Evalvalval句子real id1,id2,id3的帶注釋的語法樹的依賴圖id1L,id2L,id3LrealTD4type5in6 - addtype(id.entry, L.in)7in8 addtype9in10 addtype1entry2entry3entry產 生 式 語 義 規 則 D→TL L.in := T.type T→。省略部分。de(‘-’,R.i,T.nptr)} R1 {R.s:=R.s} R → ? {R.s:=R.i} T → ( E ) {T.nptr:=E.nptr} T → id {T.nptr:=mkleaf(id,id.entry)} T → num {T.nptr:=mkleaf(num,num.val)}使用繼承屬性構造 a-4+c的抽象語法樹ETRidTo entry for aidT.nptr-Tnumnum4T.nptrR. i-R+TRidTo entry for cidT.nptrR. i+R. i?R. sR. sR. sE.nptrE → T {R.i:=T.nptr} R {E.nptr:=R.s}R → + T {R1.i:=mknode(‘+’,R.i,T.nptr)} R1 {R.s:=R1.s}R → - T {R1.i:=mknode(‘-’,R.i,T.nptr)} R1 {R.s:=R.s}R → ? {R.s:=R.i}T → ( E ) {T.nptr:=E.nptr}T → id {T.nptr:=mkleaf(id,id.entry)}T → num {T.nptr:=mkleaf(num,num.val)}6.4.3 遞歸下降翻譯器的設計 如何在遞歸下降分析中實現翻譯模式,構造遞歸下降翻譯器 設計遞歸下降翻譯器的方法 1. 對每個非終結符A構造一個函數過程,對A的每個繼承屬性設置一個形式參數函數的返回值為A的綜合屬性(作為記錄,或指向記錄的一個指針,記錄中有若干域,每個屬性對應一個域)。為了簡單,我們假設每個非終結只有一個綜合屬性A對應的函數過程中,為出現在A的產生式中的每一個文法符號的每一個屬性都設置一個局部變量。設計遞歸下降翻譯器的方法2. 非終結符A對應的函數過程中,根據當前的輸入符號決定使用哪個產生式候選。設計遞歸下降翻譯器的方法3. 每個產生式對應的程序代碼中,按照從左到右的次序,對于單詞符號(終結符)、非終結符和語義動作分別作以下工作:i) 對于帶有綜合屬性x的終結符X,把x的值存入為X.x設置的變量中。然后產生一個匹配X的調用,并繼續讀入一個輸入符號。ii) 對于每個非終結符B,產生一個右邊帶有函數調用的賦值語句c=B(b1,b2,…,bk),其中,b1,b2,…,bk是為B的繼承屬性設置的變量,c是為B的綜合屬性設置的變量。iii) 對于語義動作,把動作的代碼抄進分析器中,用代表屬性的變量來代替對屬性的每一次引用。構造抽象語法樹的屬性文法定義轉化成翻譯模式 E → T {R.i:=T.nptr} R {E.nptr:=R.s} R → + T {R1.i:=mknode(‘+’,R.i,T.nptr)} R1 {R.s:=R1.s} R → - T {R1.i:=mknode(‘-’,R.i,T.nptr)} R1 {R.s:=R.s} R → ? {R.s:=R.i} T → ( E ) {T.nptr:=E.nptr} T → id {T.nptr:=mkleaf(id,id.entry)} T → num {T.nptr:=mkleaf(num,num.val)}非終結符E、R、T的函數及其參數類型 function E:↑AST-node;function R(in:↑AST-node): ↑AST-node;function T: ↑AST-node; 用oddop代表+和- R → oddop T {R1.i:=mknode(addop.lexme, R.i,T.nptr)} R1 {R.s:=R1.s} R→ ? {R.s:=R.i} 產生式R→addop TR|?的分析過程 procedare R; begin if sym=addop then begin advance;T; R end else begin /*do nothing*/ end end;  function R (in:↑AST-node): ↑AST-node; var nptr, i1,s1,s: ↑AST-node; addoplexeme: char; begin if sym=addop then begin /*產生式 R→addop TR */ addoplexeme:=lexval; advance; nptr:=T; i1:=mknode (addoplexeme, in, nptr); s1:=R (i1) s:=s1 end else s:= in; return s end;R → oddop T {R1.i:=mknode(addop.lexme, R.i, T.nptr)} R1 {R.s:=R1.s} R→ ? {R.s:=R.i}6.5 自下而上計算繼承屬性 在自下而上的分析過程中實現L-屬性文法的方法可實現任何基于LL(1)文法的L-屬性文法,還可以實現許多(不是所有)基于LR(1)文法的L-屬性文法 6.5.1 從翻譯模式中去掉嵌入在產生式中間的動作 要求把所有的語義動作都放在產生式的末尾轉換方法,它可以使所有嵌入的動作都出現在產生式的末尾 加入新的產生式M→?把嵌入在產生式中的每個語義動作用不同的標記非終結符M代替,并把這個動作放在產生式M→?的末尾 翻譯模式 E → TRR → +T {print (‘+’)} R | -T {print (‘-’)} R | ?T → num {print (num.val)}轉換為 E → TRR → +TMR | -TNR | ?T → num {print (num.val)}M → ? {print (‘+’)}N → ? {print (‘-’)}作業P164 - 1,2,5,7P164 - 11,12(選作)
關 鍵 詞:
編譯 原理 第六
 天天文庫所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:編譯原理課件 第六章.ppt
鏈接地址: http://www.476824.live/p-51497020.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服點擊這里,給天天文庫發消息,QQ:1290478887 - 聯系我們

本站為“文檔C2C交易模式”,即用戶上傳的文檔直接賣給(下載)用戶,本站只是中間服務平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有【成交的100%(原創)】。本站是網絡服務平臺方,若您的權利被侵害,侵權客服QQ:1290478887 歡迎舉報。

[email protected] 2017-2027 http://www.476824.live 網站版權所有

粵ICP備19057495號 

收起
展開
球探网即时蓝球比分 广西快3万能码走势图 四川快乐12中奖奖金 浙江6 1什么时候开 吉林彩票11选五 山西高银股票配资公司 广东11选5和值计划 河南快三开奖结果 股价指数的计算方法主要有 哪个时时彩5分钟一期 广西快十开奖结果今天