【正文】 碼。當(dāng)某個(gè)子樹與一 個(gè)特定模式相匹配時(shí)，它返回一個(gè)開銷值供動(dòng)態(tài)規(guī)劃算法 使用，同時(shí)確定是否該模式滿足匹配子樹的語義標(biāo)準(zhǔn) ?action部分也是 C代碼。若模式匹配成功且動(dòng)態(tài)規(guī)劃算法推 斷出該模式是整個(gè)樹的最小覆蓋的一部分，則可執(zhí)行。 action的可能包含動(dòng)作有：用另一個(gè)樹替換被匹配的子樹 、輸出代碼或別的動(dòng)作 ?若 cost被刪除，則返回一個(gè)缺省值并假定模式匹配成功 ?若 action被刪除，則表示什么都不做 84 ?優(yōu)化原則：若其所有的子問題已經(jīng)得到比較優(yōu)化的解，則 通過一種特殊的方法將所有子問題的解結(jié)合起來，可以得 到整個(gè)問題的最優(yōu)解 ?動(dòng)態(tài)規(guī)劃算法為 IR樹的每個(gè)結(jié)點(diǎn)賦一個(gè)開銷值，其值為以 覆蓋該結(jié)點(diǎn)為根的子樹的最好指令序列的各指令開銷的總和 85 ?圖 ： 86 ?重寫規(guī)則用樹的形式描述，斷言 IsShort()確定它的參數(shù)是 否可以放進(jìn) SPARC指令的 13位常量域 k中 ?相應(yīng)的 twig規(guī)格說明如圖 ： 87 88 89 ?prologue實(shí)現(xiàn)函數(shù) IsShort() ?Label聲明部分列出所有作為標(biāo)號的標(biāo)識符 ?node聲明列出除標(biāo)號標(biāo)識符之外所有出現(xiàn)在模式中的標(biāo)識符 ?$$為指向被特定模式匹配的樹的根結(jié)點(diǎn)的指針 ?$i$為指向該根結(jié)點(diǎn)第 i個(gè)孩子的指針 ?ABORT通過返回一個(gè)無窮大的開銷，終止模式匹配過程 ?NODEPTR為結(jié)點(diǎn)的類型 ?getreg()是寄存器分配器 ?Emit_...()子程序的作用是輸出指令 90 ?考慮下面一段中間代碼： st(add(ld(r8,8),add(r2,ld(r8,4)))) ?相應(yīng)的中間表示樹如圖 ： 91 ?路徑串可用整數(shù)標(biāo)號替換結(jié)點(diǎn)標(biāo)識符如圖 ： 92 ?圖 ，其路徑串和規(guī)則如圖 ： 93 ?結(jié)果自動(dòng)機(jī)如圖 ： 94 二 .基于語法制導(dǎo)的代碼生成程序自動(dòng)構(gòu)造技術(shù) ?也稱為 GrahamGlanville方法 ?它利用類似于上下文無關(guān)文法的規(guī)則和相應(yīng)的機(jī)器指令模 板描述機(jī)器操作 ?當(dāng)一條代碼生成描述規(guī)則與一條波蘭式中綴表示字符串的 子字符串相匹配，且滿足有關(guān)的語義限制時(shí)，將被匹配的 部分用相應(yīng)規(guī)則左邊的符號替代，同時(shí)輸出實(shí)例化后相應(yīng) 的指令模板 ?GrahamGlanville代碼生成程序由中間語言變換、模式匹 配器和指令生成 3部分組成 95 ?圖 (a)給出了 LIR指令的子集，其中每個(gè)參數(shù)的位置 用一個(gè)數(shù)字表示，以用于中間表示字符串與代碼生成規(guī)則 和指令模板的匹配 ?相應(yīng)的規(guī)則和 SPARC的指令模板如圖 (b)和 (c)所示 ?其中， ， ， ε表示空字符串 ?數(shù)字 n的作用：協(xié)調(diào)模式匹配與代碼輸出的關(guān)系、在規(guī)則 中描述語法限制 96 97 ?下面以圖 LIR代碼序列的目標(biāo)代碼生成為例： ?在波蘭式代碼中，用 ↑表示 load（?。┎僮?， ↓表示 store （存）操作， mov表示從寄存器到寄存器的拷貝 ?圖 ?假設(shè)當(dāng)代碼序列結(jié)束時(shí)，寄存器 r3和 r4不是活躍的 ?因此，在樹形圖中不需要顯式表示，但 r1和 r2需要保留 ?該代碼序列用波蘭式可表示如下： ↑r2 r8←+r8 8+r2↑r1+r8 4←+r8 4r1 1 98 99 100 ?如圖 ， GrahamGlanville方法在語法分析的過程 中進(jìn)行模式匹配，同時(shí)輸出 SPARC指令，下劃線以上部分 顯示被匹配的字符串，下劃線以下部分為該字符串歸約的 結(jié)果： 101 102 ?這種代碼生成程序?qū)嵸|(zhì)上是一個(gè) SLR(1)的語法分析器 ?只是它輸出的是機(jī)器指令而不是語法分析樹或中間代碼 ?這種語法分析器識別一種產(chǎn)生式為機(jī)器描述規(guī)則的語言 ,且在 產(chǎn)生式規(guī)則中 ,將 ε表示為非終結(jié)符 N,并加入產(chǎn)生式 S N* ?機(jī)器描述規(guī)則左邊出現(xiàn)非終結(jié)符 ε是允許的，與語法分析過 程不一樣，這里機(jī)器描述文法幾乎總是具有二義性 103 ?解決二義性方法： ?在遇到既可以左移又可以歸約的狀態(tài)時(shí)，選擇左移操作，且 盡可能地匹配最長的字符串 ?根據(jù)機(jī)器描述規(guī)則的優(yōu)化級對其進(jìn)行排序，即在代碼生成過 程，用第一個(gè)與之相匹配的規(guī)則進(jìn)行歸約 104 三 .基于語義制導(dǎo)的代碼生成程序自動(dòng)構(gòu)造技術(shù) ?基于語義制導(dǎo)的代碼生成程序是由 Ganapathi和 Fischer開 發(fā)的，也稱為屬性文法或詞綴文法方法 ?通過使用屬性，將語義信息加入代碼生成規(guī)則中 ?用 ↓表示繼承屬性， ↑表示綜合屬性，屬性值寫在箭頭的 后面 ?在代碼生成過程中，屬性除了傳遞值之外，還用于控制代 碼的生成、產(chǎn)生新的屬性值以及產(chǎn)生副作用 ?控制部分通過斷言（用大寫斜體字表示）來實(shí)現(xiàn) ?一條規(guī)則是可應(yīng)用的，當(dāng)且僅當(dāng)它與目標(biāo)字符串語法上相 匹配且滿足所有的斷言條件 105 ?action部分用大寫字母表示，主要用于計(jì)算新的屬性值和產(chǎn) 生副作用。當(dāng)然，最重要的副作用為輸出目標(biāo)代碼 ?因此，對地上一節(jié)討論的 GrahamGlanville方法中的寄存器 內(nèi)容與常量相加的規(guī)則是： ? + add , , ? + add , , ?轉(zhuǎn)換為相應(yīng)的屬性文法規(guī)則為： ?r↑r2 +r↓r1k↓k1 IsShort(k1) ALLOC(r2) EMIT3(“add”,r1,k1,r2) ?r↑r2 +k↓k1r↓r1 IsShort(k1) ALLOC(r2) EMIT3(“add”,r1,k1,r2) 106 ?除了從低級中間語言中產(chǎn)生目標(biāo)代碼之外，屬性文法也用于 存儲綁定、將幾種窺孔優(yōu)化技術(shù)集成到代碼生成中，以及對 目標(biāo)機(jī)描述規(guī)則集合進(jìn)行分解以減少尺寸 107 【 本章小結(jié) 】 由于代碼生成的目標(biāo)代碼取決于具體的機(jī)器結(jié)構(gòu)、指令 格式、字長及寄存器的個(gè)數(shù)和種類，并與指令的語義和所用操 作系統(tǒng)、存儲管理等都密切相關(guān)，因此實(shí)現(xiàn)非常困難。通過本 章學(xué)習(xí)，僅為學(xué)生初步了解一個(gè)高級程序設(shè)計(jì)語言編譯程序目 標(biāo)代碼生成需要考慮的問題和解決這些問題的基本原則和方法 ，為今后應(yīng)用打下初步基礎(chǔ)。 108 第 12章 習(xí)題 第 1題：一個(gè)編譯程序的代碼生成要著重考慮哪些問題 ? 第 2題：決定目標(biāo)代碼的因素有哪些？ 第 3題：為什么在代碼生成時(shí)要考慮充分利用寄存器？ 第 4題：寄存器分配的原則是什么？ 109 第 12章 作業(yè)題 P301： 1.