编译原理实践

编译原理实践--运行时的存储组织与分配在程序的执行过程中，程序中数据的存取是通过对应的存储单元进行的。在早期的计算机上，这个存储管理工作是由程序员自己来完成。在程序执行以前，首先要将用机器语言或汇编语言编写的程序输送到内存的某个指定区域中，并预先给变量和数据分配相应的内存地址。而有了高级语言之后，程序员不必直接和内存地址打交道，程序中使用的存储单元都由逻辑变量(标识符)来表示，它们对应的内存地址都是由编译程序在编译时分配或由其生成的目标程序运行时进行分配。所以，对编译程序来说，存储的组织及管理是一个复杂而又十分重要的问题。另外，有些程序设计语言允许有递归过程，有的允许有可变长度的串，有的允许有动态数组，而有些语言则不允许有这些，为什么呢？这都是因为采用了不同的存储分配方式。1、存储组织概述程序运行时，系统将为程序分配一块存储空间。这块空间用来存储程序的目标代码以及目标代码运行时需要或产生的各种数据：1）目标程序区：用来存放目标代码。2）静态数据区：用来存放编译时就能确定存储空间的数据。3）运行栈区：用来存放运行时才能确定存储空间的数据。4）运行堆区：用来存放运行时用户动态申请存储空间的数据。运行时存储空间的划分目标代码区静态数据区栈自由空间堆存储分配策略静态存储分配在运行前就能确定数据空间的大小，因而在编译时就能分配各种数据项的空间，如FORTRAN语言动态存储分配不能在编译时完全确定所有数据项的存储空间，只能在编译时产生各种必要的信息，而在运行时，再动态地分配数据项的存储空间。包括栈式动态存储分配和堆式动态存储分配1）栈式动态存储分配：运行时，每当进入一个分程序或过程，其中各项数据项所需的存储空间就动态地分配于栈顶，退出时，则释放所占用的空间特点：效率很高，但是分配的内存容量有限2）堆式动态存储分配：允许用户动态申请存储空间，每当需要时可从堆中分得一块，用完之后再退还给堆特点：动态内存的生存期由我们决定，使用非常灵活，但问题也最多注意：我们接下来只讨论栈式动态存储分配栈式动态存储分配在允许递归调用的语言中，每次递归调用都要重新分配局部变量。对于这种语言应该采用“栈式动态存储分配”，其分配策略是将整个程序的数据空间设计为一个栈，每当调用一个过程时就将其活动记录压入栈，在栈顶形成该过程工作时的数据区，而当过程结束时再将其活动记录弹出栈。在这种分配方式下，过程的调用关系是先进后出的栈模型，每个过程都可能有若干个不同的活动记录，每个活动记录代表了一次不同的调用。当前的AR首地址由栈指针SP指出。AR中通常应包含如下内容：i.被调用过程非局部变量存储区的首地址（静态链、Display表）ii.调用过程的AR首址（动态链，oldSP)iii.调用点的机器状态iv.形实参数通讯区v.返回值vi.被调用过程的局部量和临时变量存储区返回指针returnedpointer动态链dynamiclink静态链staticlink机器状态machinestates参数单元parameters局部变量localvariables临时变量temporaries高地址低地址mainpQcallQcallQcallpSPmain’sARp’sARQ’sAR(1)Q’sAR(2)栈增长方向过程的一次执行对应一个AR1）简单语言的栈式存储分配简单语言：无分程序结构，过程定义不嵌套，但允许过程的递归调用。如C语言。C语言不允许过程嵌套定义，即不允许在一个过程内定义另一个过程。C语言的全局变量只能出现在源程序的开头，可采用静态存储分配，编译时候就确定它们的地址计算局部变量或形参绝对地址的公式为：绝对地址=SP+相对地址比较简单，具体不再讨论2）嵌套过程语言的栈式存储分配嵌套过程语言：允许过程嵌套，如pascal,PL/0。AR中必须有一些内容，用于解决对非局部变量的引用问题“嵌套层次”，或称层数。主程序为0,过程S在层数为i的过程R定义，则S层数为i+1一个过程可以引用包围它的任一外层过程所定义的变量，解决方法很多，常见的方法：双指针方法和Display表方法双指针方法简单直接，但当嵌套层次较多时，对非局部量的访问效率较低！Display表方法效率较高，实现略复杂对于PL/0的编译程序，采用的是双指针方法PL/0数据动态存储采用的技术措施1.编译时为每一变量名、过程名和程序段确定一个反映静态嵌套深度的级别level2.调用一个过程时，把他的活动记录压入运行时的栈顶，返回时弹出相应的活动记录。活动记录包括：1.静态链接SL：指向定义该过程的直接外层过程的活动记录的基地址，以确保变量的正确存取2.动态链接DL：指向调用该过程前正在运行的那个过程的活动纪录的基地址，以确保能返回到调用过程段3.返回地址RA：保存该被调用过程返回后的地址，也就是调用过程指令的下一条指令的地址4.为过程局部变量预留的存储单元3.所有运算操作都从栈顶找到它的操作数，并以计算结果代之编译原理实践--目标计算机及其解释程序当前任务：将PL/0源程序翻译成为目标代码程序通常先将源程序翻译成一种中间代码程序，然后再对中间代码程序进行处理1.将中间代码程序翻译成某一种计算机的汇编指令程序，由该计算机的汇编程序对生成的汇编指令程序汇编，获得可以在该计算机上执行的目标程序2.编写一个独立的解释程序，解释执行生成的中间代码程序PL/0编译程序不仅完成通常的词法分析、语法分析，而且还产生中间代码和“目标”代码。最终我们要“运行”该目标码。为了不致陷入与本课程无关的实际机器的特有性质的考虑中去，我们假想有台适合PL/0程序运行的计算机，我们称之为PL/0处理机。PL/0处理机顺序解释生成的目标代码，我们称之为解释程序。注意：这里的假设与我们的编译概念并不矛盾，在本课程中我们写的只是一个示范性的编译程序，它的后端无法完整地实现，因而只能在一个解释性的环境下予以模拟。从另一个角度上讲，把解释程序就看成是PL/0机硬件，把解释执行看成是PL/0的硬件执行，那么我们所做的工作：由PL/0源语言程序到PL/0机器指令的变换，就是一个完整的编译程序。目标计算机的组织结构和指令格式数据存储器的动态存储器管理目标计算机指令系统及其解释解释程序interpret及其执行1.目标计算机的组织结构和指令格式目标计算机的组织结构程序存储器code数据存储器s程序地址寄存器p地址寄存器t指令寄存器i基本地址寄存器b目标计算机的指令结构LIT指令，把一个常数放入栈顶LOD指令，把一个变量放入栈顶STO指令，从栈顶把数放入一个变量单元里CAL指令，调用一个过程INT指令，预留数据存储位置JMP指令，无条件转移JPC指令，有条件转移OPR一组算术和关系运算指令PL/0计算机的指令格式FLAINT———常量LIT———常量LOD层次差数据地址STO层次差数据地址CAL层次差程序地址JMP———程序地址JPC———程序地址OPR———运算类别层次差为变量名或过程名引用和声明之间的静态层次差别，程序地址为目标数组code的下标，数据地址为变量在局部存贮中的相对地址PL/0的编译程序为每一条PL/0源程序的可执行语句生成后缀式目标代码。这种代码生成方式对于表达式、赋值语句、过程调用等的翻译较简单如赋值语句X:=YopZ（op为某个运算符），将被翻译成下面的目标代码序列：（设指令计数从第100号开始）100LODLevel_diff_Y,Addr_Y101LODLevel_diff_Z,Addr_Z102OPR0,op103STOLevel_diff_X,Addr_X2.数据存储器的动态存储器管理每一个PL/0过程可能含有局部变量。过程可以递归调用，每次递归调用，被调用过程又要求有自己的局部变量，因此不可能在编译时就为局部变量确定好固定的存储位置。只能在每次执行过程调用时才为过程的一组局部变量确定相应的存储位置。过程一结束，存储位置又被释放。后进先出—lastinfirstout按照栈的原理来管理数据存储器数据动态存储分析在调用一个过程时，先在栈顶为过程及其变量分配一些位置，叫做过程段每个过程在过程段里存放一些自己的数据，至少有被调用时的程序地址RA(返回地址)以及调用过程的段地址DL(动态链接)还需要有第二个链，能正确反映变量存取的路线，称为SL(静态链接)地址于是由编译程序表示为数据对l和a的形式。第一个数l表示调用者(调用程序段)与被调用变量之间的静态级差，它等于找到变量所在段须通过的SL链的个数。第二个数a是位移，即变量在所在段的相对地址程序静态级别和动态存储分配编译程序在编译过程中能为程序的每一个变量名、过程名以及程序段分配一个静态嵌套深度，或者说静态级别调用语句被翻译成call,a，其中a是被调用代码程序在程序存储器的开始地址，l是调用程序段的级与被调用过程的级之差函数base(l)数据动态存储采用的技术措施1.编译时为每一变量名、过程名和程序段确定一个反映静态嵌套深度的级别level2.采用数据栈的管理方式，先进后出。在解释执行前，数据栈是空栈，栈顶地址t=03.调用一个过程时，先在栈顶为过程分配确定的存储单元，包括：1.静态链接SL单元2.动态链接DL单元3.返回地址RA单元4.为过程局部变量预留的存储单元4.所有运算操作都从栈顶找到它的操作数，并以计算结果代之3.目标计算机指令系统及其解释表10-1P1374.解释程序interpret及其执行Program6.pas解释程序interpret