【教学课件】第十二章代码生成.ppt

第十二章代码生成,第一节 代码生成概述,第二节 一个简单的代码生成程序,第三节 几种常用的代码生成程序的开发方法,第四节 全局寄存器分配（图着色法）,第五节 代码生成程序的自动化构造,知识结构,12.1代码生成概述,代码生成是把经过语法分析或优化后的中间代码转换成特定目标机的机器语言或汇编语言，这样的转换程序称为代码生成程序衡量目标代码的质量主要从占用空间和执行效率两个方面综合考虑,第十二章代码生成,一.代码生成程序在编译系统中的位置代码生成程序在编译系统中的位置如图12.1所示：,目标代码一般有3种形式：（1）能够立即执行的机器语言代码，所有地址均已定位（2）待装配的机器语言模块，当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码（3）汇编语言代码，尚需经过汇编程序汇编，转换成可执行的机器语言代码,二.设计代码生成程序的基本问题1.代码生成程序的输入：代码生成程序的输入由前端所产生的中间表示和符号表中的信息组成代码生成程序可以利用符号表中的信息来决定中间代码中的名字所指示的数据对象的运行时地址,2.指令选择：所谓指令选择，是指寻找一个合适的目标机指令序列以实现给定的中间表示例如，对中间代码x:=y+z，其中x,y,z均为静态分配的变量，可以翻译成下述代码序列：LD R0,y/*将y放入寄存器R0*/ADD R0,z/*将z与R0相加*/ST R0,x/*将R0的值存入x*/,生成代码的质量取决于它的执行速度和代码序列的长度例如，如果目标机器有“加1”指令（INC），那么代码a:=a+1用INC a实现是最有效的，而不是用以下的指令序列实现：LD R0,a ADD R0,#1 ST R0,a,指令选择的基本原则：（1）减少产生代码的尺寸（2）减少目标代码的执行时间（3）降低目标代码的能耗这三者在某些情况下有可能会出现冲突，在具体选择的过程中应做折中考虑,3.寄存器分配：寄存器分配的工作是确定在程序的哪个点将哪些变量或中间量的值放在寄存器中比较有益将经常使用的操作数保存在寄存器中是比较有利的 一些目标机可能具有不同类型的寄存器，对寄存器使用的一致性方面也存在一定的约束,寄存器的使用可以分成：（1）分配阶段：为程序的某一点选择驻留在寄存器中的一组变量（2）指派阶段：挑出变量将要驻留的具体寄存器，即寄存器赋值,寄存器分配原则：（1）生成某变量的目标对象值时，尽量让变量的值或计算结果保留在寄存器中直到寄存器不够分配为止（2）当到基本块出口时，将变量的值存放在内存中（3）在同一基本块内后面不再被引用的变量所占用的寄存器应迟早释放，以提高寄存器的利用率,例如，考虑图12.2的两个三地址代码序列，它们仅有的区别是第2个语句的算符不同，其最短代码序列在图12.3中给出：,4.指令调度：指令调度是指确定程序指令的执行顺序例如，若在MIPS4KC上计算表示式(a+b)+c，可用表12.1中两个不同的指令序列，它们的主要不同在于指令顺序和寄存器的赋值：,12.2一个简单的代码生成程序,一.计算机模型假定一台M计算机具有n+1个通用寄存器为R0,R1,Rn，它们既可作为累加器又可作为变址器如果用op表示运算符，用M表示内存单元，用变量名表示该变量所在的单元，C表示常量，*表示间址方式存取,指令形式可包含以下四种类型，见表12.2：若op是一目运算符，则op Ri,M的意义为：op(M)Ri以上指令中的op包括一般计算机上常见的一些运算符,j,某些指令的意义说明如表12.3：,二.待用信息链表法若在一个基本块中，变量A在四元式i中被定值，在i后面的四元式j中要引用A值，且从i到j之间没有其他对A的定值点，这时称j是四元式i中对变量A的待用信息或称下次引用信息，同时也称A是活跃的，若A被多处引用则可构成待用信息链与活跃信息链为了得到在一个基本块内每个变量的待用信息和活跃信息，可以从基本块出口的四元式开始由后向前扫描，为每个变量名建立相应的待用信息链和活跃变量信息链,考虑到处理的方便，假定对基本块中的变量在出口处都是活跃的，而对基本块内的临时变量可分为两种情况处理：对于没有经过数据流分析，且中间代码生成的算法中不允许在基本块外引用的临时变量，则这些临时变量在基本块出口处都认为是不活跃的如果中间代码生成时的算法允许某些临时变量在基本块外引用时，则假定这些临时变量被认为是活跃的,在变量的符号表的记录项中设定了待用信息和活跃信息的栏目，其算法步骤如下：（1）对各基本块的符号表中的“待用信息”栏置“非待用”，对“活跃信息”栏，按在基本块出中处是否为活跃而置成“活跃”或“非活跃”，假定外部变量都是活跃的，临时变量都是非活跃的,（2）从后向前依次处理每个四元式i：A:=B op C，在符号表中依次执行下述步骤：A的待用信息和活跃信息附加到i上把A置成非待用F和非活跃FB和C的待用信息和活跃信息附加到i上把B和C待用信息置为i，活跃信息置成活跃L,例如，四元式如下：(A,B,C,D是变量，T,U,V是中间变量)(1)T:=A-B(2)U:=A-C(3)V:=T+U(4)D:=V+U,表12.4 待用信息链和活跃信息链,(4)DFL:=VFF+UFF(3)V(4)L:=TFF+U(4)L(2)U(3)L:=AFL-CFL(1)T(3)L:=A(2)L-BFL,(4)D:=V+U(3)V:=T+U(2)U:=A-C(1)T:=A-B,表12.4中“待用信息链”与“活跃信息链”的每列，从左至右为每当从后向前扫描一个四元式时相应变量的信息变化情况，空白处为没变化,三.代码生成算法寄存器和内存地址的描述：RVALUERi=A,C表示Ri的现行值是变量A，C的值AVALUEA=A表示A的值在内存中AVALUEA=Ri,A表示A的值在Ri中又在内存中AVALUEA=Ri表示变量A的值在寄存器Ri中,寄存器分配和代码生成的具体算法：设RETREG是一个函数过程，它的参数是一个形如i:A:=B op C的四元式，每次调用GETREG(i:A:=B op C)则返回一个寄存器R，用以存放A的结果值对如何给出寄存器R，要用到四元式i上的待用信息，以使寄存器分配合理，对每个四元式的代码生成都要调用函数GETREG,GETREG分配寄存器的算法为：（1）如果B的现行值在某寄存器Ri中，且该寄存器只包含B的值，或者B与A是同一标识符，或B在该四元式后不会再被引用，则可选择Ri为所需的寄存器R，并转（4）,（2）如果有尚未分配的寄存器，则从中选用一个Ri为所需的寄存器R，并转（4）,（3）从已分配的寄存器中选取一个Ri作为所需寄存器R，其选择原则为：占用该寄存器的变量值同时在主存中，或在基本块中引用的位置最远，这样对寄存器Ri所含的变量和变量在主存中的情况必须先做如下调整：即对RVALUERi中的每一变量M，如果M不是A且AVALUEM不包含M，则需完成以下处理：生成目标代码STRi，M；即把不是A的变量值由Ri中送入内存中如果M不是B，则令AVALUEM=M，否则，令AVALUEM=M,Ri删除RVALUERi中的M,（4）给出R，返回,这样，一旦得到一个为四元式运算的操作寄存器R，就可以进行代码生成，而当目标代码生成完成后，则又需修改寄存器的使用信息和地址信息用图12.4和图12.5给出算法的流程图：,12.3几种常用的代码生成程序的开发方法,一.解释性代码生成法解释性代码生成文法是建立一个代码生成专用语言，用这种语言以宏定义、子程序等形式描述代码生成过程通过这些宏定义和子程序把中间语言解释为目标代码这种方法使机器描述与代码生成算法结合在一起，与机器的联系直接反映在算法中机器描述是通过过程的形式提供的，如采用把源程序映像成两地址代码序列的方法进行代码生成过程中，对加法的代码生成算法如下：,macro ADD x,yif type of x=integer and type of y=integerthen IADD x,yelse if type of x=float and type of y=floatthen FADD x,yelse error,其中含有对IADD与FADD的宏调用，以生成目标机上的整数和浮点数加法指令，如对IBM360机，IADD可写为：macro ADD a,bfrom a in R1,b in R2emit(AR a,b)result in R1from a in R,b in Memit(A a,b)result in Rfrom a in M,b in Remit(A b,a)result in R,这种算法的局限性在于：（1）由于目标机的多样性、寻址方式、指令的差异等等，给中间代码的设计带来困难（2）代码生成语言与机器密切相关，可移植性受到限制（3）目标机的描述与代码生成算法混在一起，当描述改变时，势必引起算法的改变（4）需进行指令的选择、指令的排序等低层次的繁琐工作，产生的目标代码质量依赖于设计者的经验和能力（5）代码生成的视野有限，虽可进行一定范围的优化，但对协调上下文有关的优化较困难,二.模式匹配代码生成法模式匹配代码生成方法是把对机器的描述与代码生成的算法分开而对在解释性代码生成方法中，所需做的较繁重的具体情况分析的解释工作用模式匹配来代替,也就是建立一个代码生成用的机器描述语言，用以形式地描述目标机的资源、指令及其语义等有关信息代码生成程序根据这些信息，自动地把中间语言程序翻译成目标机的汇编语言或机器代码但在这种方法中，需通过形式描述的模式如实地反应机器的特性，这并不是一件容易的事，而且进行模式匹配时耗费时间很长，其目标代码的质量也不太理想,三.表驱动代码生成法表驱动代码生成方法，实质上是模式匹配代码生成方法的更进一步自动化，它是模仿从语法描述构造表和表驱动的 一种语法分析方法首先，把对目标机的形式化描述进行预加工转换成代码生成表然后，用表驱动的代码生成程序，来驱动代码生成表最后，把中间语言的内部表示翻译成目标机的汇编代码也就是说，它是用一个代码生成程序的生成器自动地构造一个代码生成程序,这种表驱动代码生成方法的好处是：容易使用和修改，并且能较容易地为不同的计算机构造适合于它们自己的代码生成程序这样将能增强编译程序的可移植性和灵活性，但是它所生成的目标代码的质量，将依赖于机器描述的完善程序最好的方法是用形式化的方法完善地描述一台计算机，但这并不是一件容易的事，因而这种方法有待进一步改进和完善,12.4全局寄存器分配（图着色法）,一.概述为减少存取操作的次数，可以将频繁使用的变量保留在固定的寄存器中，并使之贯穿不同的基本块边界，这就是全局寄存器分配问题1971年John Cokes提出，全局寄存器分配可以视为一种图着色问题图着色法最初在实验性编译程序IBM370PL/I中使用，且很快得到广泛的推广,图着色法的基本思想：将一个程序的所有对象和可供使用的实际寄存器视为一个无向图的不同结点若两个对象间满足下列条件之一，则在它们之间引入一条边，以表示它们相互干扰：同时为活跃变量的两个对象一个对象与之不能也不应该分配的寄存器,通过这种方式，构造出相应程序的干扰图然后利用最大可供使用寄存器数的颜色种数，对干扰图的所有结点进行着色在对干扰图进行着色过程中，用尽量少的颜色、且将相邻结点赋予不同的颜色,不同的颜色对应于不同的实际寄存器，若目标机具有R个寄存器，则可用R种颜色对该干扰图进行着色这个着色过程就是对该干扰图进行有效的寄存器赋值若不存在R种颜色，必须将其中一些变量或临时变量放在内存中而不是寄存器中，这个过程称为spilling,图着色的基本算法如下：（1）建立Web对象（2）用相邻矩阵表示干扰图（3）利用相邻矩阵合并寄存器，查找拷贝sisj，若si与sj不相互干扰，将sj的使用替换为si的使用，并将代码中的sj去掉。若完成寄存器合并,返回到第（1）步，否则继续下一步（4）构造干扰图的相邻列表表示（5）计算spill开销。对每个符号寄存器，计算将其spill到内存后又将其重新存入到寄存器中的开销,（6）干扰图的修剪。从干扰图的相邻列表中排除结点及其相应的边。所采用的方法为degreeR和消极试探法（7）寄存器赋值。利用相邻列表，尽量给每个结点着色，且使没有两个相邻的结点具有同样的颜色。若成功，将每个符号寄存器用与之具有相同颜色的实际寄存器替换，分配终止。若失败，进行下一步（8）寄存器的spill。将需要spill符号寄存器中的值放在内存中，然后插入spill函数(必要时再重新装入),返回到第（1）步,二.图着色寄存器分配法的相关技术1.web对象：web是用于分配寄存器的数据对象：一个web要么是一个定值-引用链，要么是几个相交的链的最大“并集”图12.6为一个抽象数据流图片断,给出了2个变量（X和Y）的定义和使用：,可以将其划分为4个web：其中一个web为在块B2定义，由块B4和B5使用，和另一个块B3中定义，由块B5使用的两个链的联合。其他的用链形成另外的一些web。4个web如下所示：web Componentsw1 def x in B2,def x in B3,use x in B4,use x in B5w2 def x in B5,use x in B6w3 def y in B2,use y in B4w4 def y in B1,use y in B3利用web代替变量名的主要好处在于，可以区分程序中具有相同命名但表示不同意义的变量，以方便寄存器的分配,2.干扰图的表示：在干扰图中，每个实际寄存器和每个web分别为干扰图的一个结点与某个结点相连的边数，称为该结点的度degree图12.6中4个web间的干扰图如图12.7所示：,若所有的寄存器是同构的，则没有必要将寄存器包括在干扰图中若目标机有两个以上的专用寄存器集合，则对这两类寄存器的分配可以分开处理，这样可以减少干扰图的复杂性，并使之具有较少的限制,对干扰图所占用空间和访问时间进行折中考虑，采用下述两种表示方法：（1）相邻矩阵表示法：相邻矩阵AdjMtx2.nwebs,1.nwebs-1是一个低三角矩阵,其中，矩阵的行与列分别表示干扰图中的结点若第i个寄存器与第j个寄存器是相邻的，则AdjMtxmax(i,j),min(i,j)的值为真，否则为假矩阵表示实现了干扰图的快速建立，同时，能快速确定某两个结点是否是相邻的,（2）相邻列表表示：相邻列表用具有6个成分的数组表示：color：为一整数，其值为该结点所选颜色的值,初始值disp：用于寄存器spilling，表示相应符号寄存器spill到某个栈的偏移地址，初始值spcost：spill开销，对符号寄存器,初值为0对实际寄存器，初值为nint：图中余下的与之相邻的结点数adjnds：图中余下的与之相邻的结点列表rmvadj：已从图中去掉的相邻结点列表,优点：能比较方便地确定有多少结点与给定的结点相邻，且有哪些结点与之相邻相邻矩阵主要用于寄存器合并，相邻列表主要用于实际的着色过程因此，一般情况下，首先建立相邻矩阵，并在寄存器合并过程中对其进行不断修改，然后根据相邻矩阵建立相应的相邻列表,3.寄存器合并：寄存器合并是一种复写传播变换，用于消除从一个寄存器到另一个寄存器的拷贝查找寄存器拷贝指令的中间代码，即sjsi，若sj与si不相互干扰，则查找向si写数据的指令，对其进行修改，并将其中相应数据写到寄存器sj中，移去拷贝指令；且在干扰图中将sj与si合并为一个结点。该结点的度为为结点sj和si度的并集,保证合并后为R可着色的情况下，才进行合并，为此需要两条安全策略：（1）若合并后所得结点(a,b)具有小于R个度大于或等于R的邻居，则结点a和结点b是可以合并的（2）对结点a的每个邻居t,要么t与结点b已是相互干扰的，要么t的度小于R，则这种合并是安全的,寄存器合并是一种功能强大的变换，其主要作用在于：（1）简化编译过程，如消除不必要的拷贝操作（2）在过程调用之前，保证参数值被移到合适的寄存器中（3）对源和目的操作数有特殊要求的机器指令，使其操作数和结果在适当的位置（4）对操作数或结果值需要使用寄存器对的指令，保证能够为其分配寄存器对，等等,4.spilling开销的计算：spilling的结果可能会将一个web分解为两个或多个web，从而减少干扰图中的干扰例如,通过将图12.6中引入相应的存取操作,如图12.8所示：,这样web w1被分成4个web:w5、w6、w7、w8：web Componentsw2 def x in B5,use x in B6w3 def y in B2,use y in B4w4 def y in B1,use y in B3w5 def x in B2,tmp x in B2w6 def x in B3,tmp x in B3w7 xtmp in B4,use x in B4w8 xtmp in B5,use x in B5,所得的干扰图如图12.9所示：,干扰图的相邻列表中每项有一个成分spcost。spcost用于计算spilling相应符号寄存器所需要的开销spill一个web的开销可表示为：,其中，def、use、copy是 web的单个定义、使用和拷贝：defwt、usewt和 copywt相对权值,在计算spill开销的过程中，应该考虑下述因素：（1）若重新计算一个web的值比重新装载更有效，可对其进行重新计算，因此，选择重新计算的开销（2）若spill了某条拷贝指令的源操作数或目的操作数，则可以不再考虑该指令（3）若在同一基本块中，某个被spill的值需要多次使用，且直到最后一次使用，重新装载的值一直是活跃的，则在该基本块中，只需做一次取操作,5.干扰图的修剪：（1）degreeR规则：结点的度degree表示与之相邻结点的个数基本思想：对给定包含一个度小于R的结点的干扰图是R可着色的，当且仅当不包含该结点的干扰图是可着色的当然，这种规则并不是对所有的干扰图都适用。如图12.10可以分别为2可着色的和3可着色的，但却不能利用这种规则进行修剪：,（2）消极试探法：消极试探法是通过排除图中degreeR的结点以对第一种方法进行推广基本原理：因为某个结点具有R或更多的相邻结点，这些相邻结点并不需要所有的均具有不同的颜色,进一步地说,它们并一定能用完R种颜色通过从图中反复查找度小于R的结点，开始对图进行着色选择一个degreeR的结点消极地放入栈中，选择原则：根据其spill cost值除以其目前的度，所得的值最小的结点优先级最高,三.示例如图12.11所示，代码片断中使用了符号寄存器：,假设可供分配使用的寄存器为r2、r3、r4，分别为其建立干扰图和相邻矩阵，如图12.12所示：,由于符号寄存器s1在退出块B1时，s0从其定义点之后都不再是活跃的，因此它们的spill开销值都为无穷大，如图12.13所示：,符号寄存器s1无相邻结点，首先将其先放入栈中。实际寄存器r2、r3、r4以及符号寄存器s4、s9的度都为2，依次将它们放入栈中，s9 s4 r4 r3 r2 s1。干扰图的修剪过程如图12.14所示：,修剪后的干扰图如图12.14(a)所示，可以看出，结点s8的度小于3，也将其压入栈中：s8 s9 s4 r4 r3 r2 s1这时，所得的干扰图如图12.14(b)所示：在余下的干扰图中，每个结点的度都大于或等于3，只好使用消极试探法，即把s7放入栈中，这样简化了干扰图使其变成如图12.14(c)所示：进而将s5压入栈中。这时所有的结点的度都小于3，将它们依次都放入栈中：s2 s3 s6 s5 s7 s8 s9 s4 r4 r3 r2 s1,依次将各个结点从栈中弹出的同时给它们赋予不同颜色值,并根据AdjLsts.rmvadj 域的值重构干扰图当弹出3个结点时，干扰图如图12.15所示：,当弹出第四个结点，即s5就没有可供使用的颜色。这时就需要进行寄存器的spilling。分别将块B4中的s7和s5 spilling到内存中，其基址寄存器为r10，偏移量disp分别为0和4。所得的代码的片断如图12.16所示：,重新为其建立干扰图，如图12.17所示：,利用degreeR规则对其进行修剪，并将实际寄存器赋给与之具有相同颜色的符号寄存器，所得的代码片断如图12.18所示：,12.5代码生成程序的自动化构造,在20世纪70年代和80年代，开始出现了编译后端的自动构造技术，开发了一系列代码生成程序的构造器，如：BEG、iburg、twig、MBURG等研究声明，这种利用声明性描述构造代码生成程序要比手工编写容易，而且需要的工作量少，但其产生代码的执行效率往往还不足手工开发的十分之一，从而很难为广大用户所接受,如图12.19所示，代码生成程序的构造器的输入是代码生成描述，输出是代码生成程序：,一.模式匹配与动态规划这种方法是由Aho、Ganapathi和Tjiang开发的基本思想：将目标机指令用树重写规则表示，机器指令集合表示为一个树模式集合，且将描述不同指令的树模式赋予相对权值以表示执行该指令的相对代价，然后利用动态规划技术选择最优的指令集合来计算相应的中间表示树。通过在中间表示树中重复查找与相应模板相匹配的子树并用相应的替换结点进行重写，即在将每个中间表示树规约为一个简单的结点过程中产生目标代码,树重写规则可表示为：label:patterncost=actionlabel是与文法规则左边的非终结符相对应的标识符pattern为树模式cost部分是由代码生成程序执行的C代码。当某个子树与一个特定模式相匹配时，它返回一个开销值供动态规划算法使用，同时确定是否该模式满足匹配子树的语义标准action部分也是C代码。若模式匹配成功且动态规划算法推断出该模式是整个树的最小覆盖的一部分，则可执行。action的可能包含动作有：用另一个树替换被匹配的子树、输出代码或别的动作若cost被删除，则返回一个缺省值并假定模式匹配成功若action被删除，则表示什么都不做,优化原则：若其所有的子问题已经得到比较优化的解，则通过一种特殊的方法将所有子问题的解结合起来，可以得到整个问题的最优解动态规划算法为IR树的每个结点赋一个开销值，其值为以覆盖该结点为根的子树的最好指令序列的各指令开销的总和,图12.20为简单的树重写系统：,重写规则用树的形式描述，断言IsShort()确定它的参数是否可以放进SPARC指令的13位常量域k中相应的twig规格说明如图12.21所示：,prologue实现函数IsShort()Label声明部分列出所有作为标号的标识符node声明列出除标号标识符之外所有出现在模式中的标识符$为指向被特定模式匹配的树的根结点的指针$i$为指向该根结点第i个孩子的指针ABORT通过返回一个无穷大的开销，终止模式匹配过程NODEPTR为结点的类型getreg()是寄存器分配器Emit_.()子程序的作用是输出指令,考虑下面一段中间代码：st(add(ld(r8,8),add(r2,ld(r8,4)相应的中间表示树如图12.22所示：,路径串可用整数标号替换结点标识符如图12.23所示：,图12.20的所有规则构造一个自动机，其路径串和规则如图12.24所示：,结果自动机如图12.25所示：,二.基于语法制导的代码生成程序自动构造技术也称为Graham-Glanville方法它利用类似于上下文无关文法的规则和相应的机器指令模板描述机器操作当一条代码生成描述规则与一条波兰式中缀表示字符串的子字符串相匹配，且满足有关的语义限制时，将被匹配的部分用相应规则左边的符号替代，同时输出实例化后相应的指令模板Graham-Glanville代码生成程序由中间语言变换、模式匹配器和指令生成3部分组成,图12.26中(a)给出了LIR指令的子集，其中每个参数的位置用一个数字表示，以用于中间表示字符串与代码生成规则和指令模板的匹配相应的规则和SPARC的指令模板如图12.26(b)和(c)所示其中，r.n表示寄存器，k.n表示常量，表示空字符串数字n的作用：协调模式匹配与代码输出的关系、在规则中描述语法限制,下面以图12.27的LIR代码序列的目标代码生成为例：在波兰式代码中，用表示load（取）操作，表示store（存）操作，mov表示从寄存器到寄存器的拷贝图12.28为该代码序列的树形表示假设当代码序列结束时，寄存器r3和r4不是活跃的因此，在树形图中不需要显式表示，但r1和r2需要保留该代码序列用波兰式可表示如下：r2 r8+r8 8+r2r1+r8 4+r8 4-r1 1,如图12.29所示，Graham-Glanville方法在语法分析的过程中进行模式匹配，同时输出SPARC指令，下划线以上部分显示被匹配的字符串，下划线以下部分为该字符串归约的结果：,这种代码生成程序实质上是一个SLR(1)的语法分析器只是它输出的是机器指令而不是语法分析树或中间代码这种语法分析器识别一种产生式为机器描述规则的语言,且在产生式规则中,将表示为非终结符N,并加入产生式SN*机器描述规则左边出现非终结符是允许的，与语法分析过程不一样，这里机器描述文法几乎总是具有二义性,解决二义性方法：在遇到既可以左移又可以归约的状态时，选择左移操作，且尽可能地匹配最长的字符串根据机器描述规则的优化级对其进行排序，即在代码生成过程，用第一个与之相匹配的规则进行归约,三.基于语义制导的代码生成程序自动构造技术基于语义制导的代码生成程序是由Ganapathi和Fischer开发的，也称为属性文法或词缀文法方法通过使用属性，将语义信息加入代码生成规则中用表示继承属性，表示综合属性，属性值写在箭头的后面在代码生成过程中，属性除了传递值之外，还用于控制代码的生成、产生新的属性值以及产生副作用控制部分通过断言（用大写斜体字表示）来实现一条规则是可应用的，当且仅当它与目标字符串语法上相匹配且满足所有的断言条件,action部分用大写字母表示，主要用于计算新的属性值和产生副作用。当然，最重要的副作用为输出目标代码因此，对地上一节讨论的Graham-Glanville方法中的寄存器内容与常量相加的规则是：r.3+r.1 k.2 add r.1,k.2,r.3r.3+k.2 r.1 add r.1,k.2,r.3转换为相应的属性文法规则为：rr2+rr1kk1 IsShort(k1)ALLOC(r2)EMIT3(“add”,r1,k1,r2)rr2+kk1rr1 IsShort(k1)ALLOC(r2)EMIT3(“add”,r1,k1,r2),除了从低级中间语言中产生目标代码之外，属性文法也用于存储绑定、将几种窥孔优化技术集成到代码生成中，以及对目标机描述规则集合进行分解以减少尺寸,【本章小结】由于代码生成的目标代码取决于具体的机器结构、指令格式、字长及寄存器的个数和种类，并与指令的语义和所用操作系统、存储管理等都密切相关，因此实现非常困难。通过本章学习，仅为学生初步了解一个高级程序设计语言编译程序目标代码生成需要考虑的问题和解决这些问题的基本原则和方法，为今后应用打下初步基础。,第12章习题第1题：一个编译程序的代码生成要着重考虑哪些问题?第2题：决定目标代码的因素有哪些？第3题：为什么在代码生成时要考虑充分利用寄存器？第4题：寄存器分配的原则是什么？,第12章作业题P301：1.,