资源描述
一、概述1、编译器各阶段2024/7/18词法分析器语法分析器语义分析器中间代码生成器代码优化器代码生成器错误处理器符号表管理器源程序目标程序2、编译器各阶段的分组前端:依赖于语言并很大程度上独立于目标机器。一般包括语法分析、词法分析、符号表的建立、语义分析、中间代码生成以及相关错误处理。后端:依赖于目标机器的阶段或某些阶段的某些部分。一般来说,后端完成的任务不依赖于源语言而只依赖于中间语言。主要包括代码优化、代码生成以及相关的错误处理和符号表操作。2024/7/18二、符号表符号表是编译器保存信息的中心库,编译器的各部分通过符号表进行交互,并访问符号表中的数据符号。符号表把各种名字映射到符号集合。常量、标识符和标号都是名字,不同名字有不同的属性。符号管理不仅要处理符号本身,还管理符号的作用域。2024/7/181、符号的表示 *;名称;作用域;在源程序中位置;连接符号表中上一个符号;可保存一个列表,表示使用情况;扩展存储类型符号标记;如变量、函数、常量、结构或联合等信息;被引用的粗略次数 联合u为标号、结构、联合、枚举、常量、全局和静态变量提供附加信息 u;x;由后端处理,如为变量分配寄存器为调试器产生数据信息2024/7/181、符号的表示域:1,;第k层中声明的局部变量其域等于。域:*;x,y;指名包含该符号定义文件名,y和x表示出现的行号及行中位置。域:符号扩展类型可以是、或等首字母大写的类型表示全小写类型的指针,如。2024/7/182、符号表的表示;同中域 ;符号表链表,指向1的表 ;*;*256;这是一个哈希链数组,方便插入、查找 ;指向当前及其外层所有符号列表的表头;2024/7/183、符号表举例、符号表举例 x,y;f(x,a)b;y=x+a*b;(y 5)a;y=x+a*b;2024/7/182024/7/183045600000a b x y4、符号表的相关操作查找和建立标识符(*,*,);(*,);标号:与标识符相似,但不涉及作用域常量:这些符号保存在表中产生变量:用于产生静态变量保存字符串等2024/7/18三、代码生成接口这一章内容定义了与目标机器无关的前端和与目标机器相关的后端之间的接口。接口包括一些共享数据结构、18个函数和包括36个操作符的语言。该语言用于将可执行代码从源程序生成(有向无环图)。共享数据结构可供前后端共享,但某些域为一端私有。就是一个共享数据结构。2024/7/181、类型度量 ,;:类型的大小;:对齐字节数;:控制相关类型的常量的放置。为1时,不出现在中,存于静态变量中。;2024/7/182、接口记录 x;为每一种目标机器形成一个独有的接口实例。x域是对的扩展,后段使用它存放与目标及其相关的接口数据和函数,对后端私有。2024/7/183、操作可执行代码用来描述。函数体是用组成的序列或森林。每个都可以同过函数传给后端。节点 ;3;2;x;2024/7/183、操作域存放操作符。操作符后缀表示操作数类型:,;如,有变体、等。=1;4、标识符识别 h:j:k:m:n:o:p:q:x:y:z:A:B:C:D:E:F:G:H:I:J:K:M:N:O:P:Q:R:S:T:U:V:W:X:Y:Z:(-=6 t=11 t=13)=t;t=();()p=(,p,(1(0);p2024/7/18条件表达式::?:2()p=3(4);(t?)l,r;2;(1 ()(a n,(p);p=(p);t=();0=;l=(:);1=;r=(2();p;2024/7/18另有二元表达式、一元表达式、后缀表达式和基本表达式。表达式分析多是用递归和大量语句实现。在编译领域用一个分析函数代替n个函数处理n级优先是非常流行的。关于表达式的分析还包括表达式语义的分析,如类型检查转换、函数调用分析等各种操作。2024/7/182、语句分析代码的表示:表达式首先被编译为分析树然后转化为。每个函数的在代码表中被串起来,代码表表示了函数的代码。结构:,;,;u;2024/7/18语句的识别:(,)=;(=2 15)(15 n);(t):(2),+1);:(3),+1);:(3),+1);(;);=;(;);2024/7/18语句的识别:0 L1 1L:2L1:(,)t=();();判断后的(();(),0,);包含函数生成并加入 2.0;森林,把入口加入代码表.同时根(,);据接过设置,(t )(+1);t=();();(,);(+1)-)(+1);();2024/7/18在循环、语句中都用到了标号和跳转,标号使通过函数定义的,而跳转通过函数生成。除语句识别外,还有声明的识别。声明的识别非常复杂,c语言中声明的形式很多,处理时大量的相互递归调用。经过前端的分析后,将源程序转化为,并添加进代码表。2024/7/183、小结六、中间代码生成编译器的后端通过接口函数调用和来遍历代码表。和函数操作处理森林。函数为节点分配内存并用它的参数只来初始化节点的域。还负责删除公共子表达式。2024/7/181、构建节点(,)p=,l,r;();()标识访问过的树;()=+();=+();()p;p;2024/7/182、控制流最简单的一元和二元操作加入结点表,但是并不会出现在根中。赋值等操作可以用这种情况解决。要改变控制流需要跳转。:l=(0,0,0);(,l,);();2024/7/18 (p)(p )()=;=p;=p;=p;2024/7/18是一个循环链表,不为空则指向链表最后一个节点,为空则将其初始化,域可以表示根结点。:代表大于转移,是接口标识符 l=(0,0,0);r=(1,0,0);()()+(),l,r,();()():=;:=;:=;:=;:=;:=;:(0);(+(),l,r,();(0)0-;2024/7/182024/7/18aiii0ii1作为一个。最后生成一个换行符。2024/7/183、寄存器的分配从上节我们可以看出,代码发送器可以生成汇编代码,但是汇编代码中的寄存器是如何分配的?寄存器分配包括两个内容:分配:决定哪些值占用寄存器指派:为每个值指派特定的寄存器2024/7/182024/7/18在后端选择指令并将子指令从树中分离出来,采用前序遍历分离的树,并按照最后执行的顺序链接指令。再将每条指令传递给函数,一般首先调用来释放不再被其子节点使用的寄存器,然后调用函数为自身分配一个寄存器。对于临时变量,在首次赋值的时候为它分配一个寄存器,在最后一次使用的时候释放该机存器。2024/7/18寄存器状态的跟踪 2;2;用掩码表示寄存器的状态对于寄存器r:n=;&n 为0表示寄存器忙2024/7/18寄存器分配:寄存器分配器对森林进行三遍扫描:第一遍对所有使用临时变量的节点建立一个表。该列表指名了临时变量节点的最后一次使用。第二遍对森林的扫描删去一些用于寄存器复制的指令,把计算源寄存器的表达式重定向,使用目的寄存器。最后一遍扫描为每个节点分配寄存器。2024/7/18寄存器的溢出:寄存器溢出是指寄存器分配器用完寄存器时需要生成代码来空出一个忙寄存器,将其值存储回存储器中,并将那些未被处理的使用该寄存器的节点替换成存储器结点。存储器分配用完时最有选择是把最远使用的寄存器存回存储器。这类似于操作系统中的内存调度,原理相同。2024/7/18八、总结是构造编译器的一种方法。在设计过程中对数以百计的技术策略进行了选择,这些策略很多都是可行的方法。中运用了许多编程技巧,使的很多方法得以巧妙的实现,减小了代码的体积。中的各个部分还可单独拿出做其他的应用,如语法分析可用于处理电子数据表,可处理各种树的模式匹配问题。2024/7/181、数据结构由于的共享数据结构不多,因此可以很好的处理前端与代码生成之间的数据结构共享。这样也有不足之处:比较其它简单的设计方法,这些结构更为复杂。有些人认为是c语言导致这种复杂性,用定义单独结构的方法可以减少这些复杂程度。例如用面向对象语言将结构分割。2024/7/182、接口剔除了许多冗余部分并做了简单性假定,一次是的代码很紧凑,但是这些假定限制了接口在其他语言和机器上的应用能力。接口假定符号和无符号整数以及长整数都具有相同的长度。假定所有指针表示相同。2024/7/183、语法和语义分析的语法和语义分析穿插进行。采用一遍扫描的策略,与相比她的开销更小,速度更快。2024/7/184、代码生成和优化代码生成需要综合平衡各种因素。功能强大的优化器可以产生更好的代码。但是他的速度太慢了。就每棵树来说,lcc的指令选择是最佳的。但相邻数的代码边界处就差一些。lcc可以在最后使用窥孔优化解决。lcc的寄存分配器比较原始,目前可以采用图的着色方法分配能力更为出色,但这样做会使代码多出很多。2024/7/18
展开阅读全文