编译原理课件(hdu)CHAPTER9(Run-TimeEnvironments)

Chapter9

Run-TimeEnvironments概述存储分配策略（Storage-allocationstrategies）访问非局部名字（Accesstononlocalnames）参数传递（Parameterpassing）11/23/20221Chapter9

Run-TimeEnvironme9.1概述在生成目标代码之前，必须了解目标代码执行时的环境1、空间环境目标代码的运行都是在操作系统分配的一块存储区内进行的这块存储区必须容纳目标代码和目标代码运行时的数据空间（目标代码中指令能访问的空间）11/23/202229.1概述在生成目标代码之前，必须了解目标代码执行时的环9.1概述编译程序分配目标程序运行时的数据空间的基本依据是设计程序语言时对程序运行中存储空间的使用和管理办法的规定代码生成器在生成目标代码时必须要体现该程序语言在设计时分配数据空间的规定11/23/202239.1概述编译程序分配目标程序运行时的数据空间的基本依据9.1概述2、寄存器环境寄存器是目标机器中的宝贵资源如何分配寄存器提高程序运行的效率是代码生成器主要要解决的问题，（详细内容见下一讲）**数据空间分配和寄存器分配最后都体现在生成的目标代码中11/23/202249.1概述2、寄存器环境寄存器是目标机器中的宝贵资源如何9.1概述几种典型程序设计语言的特点不同的语言有不同的分配数据空间的规定，有不同的组织运行时刻存储空间的方法11/23/202259.1概述几种典型程序设计语言的特点不同的语言有不同的分9.1概述几种典型程序设计语言的特点与差异：CPASCALALGOLFORTRAN过程递归调用过程嵌套定义动态数组动态内存申请指针检查√××√×√√×√√√√√×√×

×

×

×√11/23/202269.1概述几种典型程序设计语言的特点与差异：CPASCA9.1概述名字的联编（BindingsofNames）名字的左值(l-value)—内存地址，存储名字的瞬时值名字的右值(r-value)—名字的瞬时值名字的联编—将一个内存地址与一个名字联系起来在程序的一次运行中，一个名字右值（瞬时值）可能会经常改变，一个名字也可能被联编到多个地址（如递归调用中）11/23/202279.1概述名字的联编（BindingsofNames9.1概述运行时刻内存的典型划分操作系统收到运行目标程序的指令，分配一块连续的内存空间使目标程序在其上运行P397Fig7.7这只是一个典型的划分，具体语言不同，该划分也不同栈（Stack）：支持过程的递归调用堆（Heap）：支持动态内存申请11/23/202289.1概述运行时刻内存的典型划分操作系统收到运行目标程序9.1概述活动记录（ActivationRecords）是一段连续的存储区，用以存放过程的一次执行所需要的信息，如局部数据活动记录的结构P398Fig7.8参数域、状态域、数据域TOP指向栈顶，TOP-SP指向局部数据区的开始位置**这只是一个一般的结构，具体语言不同，活动记录的结构和内容也有差异11/23/202299.1概述活动记录（ActivationRecords9.1概述过程的活动（Activation）过程的一次完整执行（第一条语句到最后一条语句），称为过程的一次活动过程在执行中称它为活着的如果允许递归调用，程序的一次执行可能有同一个过程的多个实例是活着的**本章主要讨论不同语言的目标程序在运行时的存储分配策略及名字与其左值和右值的关系11/23/2022109.1概述过程的活动（Activation）过程的一次完9.2存储分配策略静态存储分配（Staticallocation）编译时确定所需的全部数据空间的大小编译时安排好每个名字的存储位置（相对地址）采用静态存储分配的典型语言是FORTRAN11/23/2022119.2存储分配策略静态存储分配（Staticalloc9.2存储分配策略FORTRAN语言程序是段结构的，主程序段+若干子程序（函数）段没有动态数据类型，每个名字所需空间是确定的没有递归调用，无需栈区没有动态数据结构（如链表），没有动态内存申请，无需堆区11/23/2022129.2存储分配策略FORTRAN语言程序是段结构的，主9.2存储分配策略因此，编译时可确定数据区大小，为每个名字分配好地址FORTRAN程序运行时内存划分为目标代码区和静态数据区，没有栈区和堆区程序例子：P402example7.4Fig.7.10Fig.7.11Fig.7.1211/23/2022139.2存储分配策略因此，编译时可确定数据区大小，为每个名9.2存储分配策略程序设计语言若允许递归调用、可变数组、可变数据结构：编译时无法确定运行时需要的存储空间大小动态存储分配包括：栈式分配（Stackallocation）和堆式分配（Heapallocation）只能在运行时动态地确定，采用动态存储分配11/23/2022149.2存储分配策略程序设计语言若允许递归调用、可变数组、9.2存储分配策略栈式存储分配的思想：在运行空间中划分一块存储空间作为栈区程序运行时每当调用一个过程，就将该过程的活动记录压入栈中，过程执行完毕将它的活动记录从栈中弹出例子：P405Fig.7.1311/23/2022159.2存储分配策略栈式存储分配的思想：在运行空间中划分一9.2存储分配策略栈式存储分配的实现反映在目标代码生成器的构造策略中，最终体现在生成的目标代码中调用序列(CallSequence)目标代码中的一个指令序列，完成调用一个过程的一系列操作，包括为被调用过程分配一个活动记录，并在相应的域中填入信息11/23/2022169.2存储分配策略栈式存储分配的实现反映在目标代码生成器9.2存储分配策略返回序列(ReturnSequence)目标代码中的一个指令序列，完成从一个被调用过程返回到它的调用过程的一系列操作，包括释放被调用过程的活动记录，并复制出返回值具体内容：P407Fig.7.1411/23/2022179.2存储分配策略返回序列(ReturnSequenc9.2存储分配策略有些程序设计语言允许用户自由申请内存空间，如C的malloc和free，PASCAL的new和dispose何时申请何时释放由用户决定有些程序设计语言在进行数据空间分配时不服从栈式的存储分配原则（即“先申请后释放、后申请先释放”）11/23/2022189.2存储分配策略有些程序设计语言允许用户自由申请内存空9.2存储分配策略这时采用堆式存储分配方案运行空间划分一块堆区用户（显式）或目标代码需要时从这堆中借用一块，不用时退还**这是一种完全动态的存储分配方案11/23/2022199.2存储分配策略这时采用堆式存储分配方案运行空间划分一9.3访问非局部名字非局部名字相对于引用点所在的过程或分程序来说的程序执行时引用的在当前过程（分程序）之外定义的变量称为非局部名字**本节主要讨论栈式存储分配中如何访问非局部名字11/23/2022209.3访问非局部名字非局部名字相对于引用点所在的过程或分9.3访问非局部名字最近嵌套的作用域规则（mostcloselynestedrule）P412这是大多数程序设计语言采用的作用域规则例子：P416Fig.7.22（过程）例子：P413Fig.7.18（块或分程序）11/23/2022219.3访问非局部名字最近嵌套的作用域规则P4129.3访问非局部名字分程序（块）结构——ALGOL和C分程序（块）含有局部数据说明的语句序列有定界符号，允许嵌套例子：P413Fig.7.1811/23/2022229.3访问非局部名字分程序（块）结构——ALGOL9.3访问非局部名字过程（活动记录）采用栈式存储分配，分程序中的局部数据在活动记录的局部数据区内也采用栈式分配并列的分程序中的名字可分配同一个地址，因为它们所属的分程序不会在同一时刻存活访问同一过程中的局部名字可以从栈顶到栈底进行定位（同一活动记录中）Fig.7.19**访问其它过程中的局部名字见下面的讨论11/23/2022239.3访问非局部名字过程（活动记录）采用栈式存储分配，分9.3访问非局部名字无过程嵌套定义——C程序中引用的名字或者在当前的过程中被定义，或者在所有过程之外被定义在所有过程之外被定义的变量，称之为全局变量，被存放在静态数据区，地址在编译时刻确定（放符号表中）11/23/2022249.3访问非局部名字无过程嵌套定义——C程序中引用的9.3访问非局部名字过程中的局部名字联编到过程的活动记录的局部数据区中访问非局部名字可根据符号表中该变量的地址直接到全局静态数据区中查找11/23/2022259.3访问非局部名字过程中的局部名字联编到过程的活动记录9.3访问非局部名字有过程嵌套定义——PASCALPASCAL语言的一个例子P416过程和函数的嵌套深度（nestingdepth）访问非局部名字的方法有两种，一种是通过存取链，一种是通过DISPLAY表主程序为111/23/2022269.3访问非局部名字有过程嵌套定义——PASCALP9.3访问非局部名字存取链（accesslinks）活动记录中的一个区，是一个指针若过程P直接嵌入在过程Q中，则P的活动记录中的存取链指向Q的最近的活动记录中的存取链11/23/2022279.3访问非局部名字存取链（accesslinks）活9.3访问非局部名字如何建立存取链？参见P417Fig.7.23（a）（b）（c）（d）区分两种情况：P4181、Np<Nx，Np是调用者深度，Nx是被调用者深度2、Np>=NxNp–Nx+1

11/23/2022289.3访问非局部名字如何建立存取链？参见P417F9.3访问非局部名字如何利用存取链访问非局部名字？根据当前过程的嵌套深度和非局部名字所在过程的嵌套深度，可以计算出需顺着存取链前进的步数，从而对非局部名字进行访问Np–Na11/23/2022299.3访问非局部名字如何利用存取链访问非局部名字？根据当9.3访问非局部名字DISPLAY表是一个指向活动记录的指针数组运行时刻要访问的嵌套深度为i的非局部名字就在d[i]所指的活动记录中这种方法只要一步就可到达要访问的非局部名字的活动记录，比存取链方法高效11/23/2022309.3访问非局部名字DISPLAY表是一个指向活动记录的9.3访问非局部名字如何建立与维护DISPLAY表？DISPLAY表的大小由程序中嵌套深度最大的过程决定参见P421Fig.7.26（a）（b）（c）（d）11/23/2022319.3访问非局部名字如何建立与维护DISPLAY表？9.3访问非局部名字当建立嵌套深度为i的过程的活动记录时，首先在新的活动记录中保存d[i]的值，然后置d[i]指向新的活动记录注意考虑调用和返回两种情况当从过程中返回时，从活动记录中恢复老的d[i]的值11/23/2022329.3访问非局部名字当建立嵌套深度为i的过程的活动记9.4参数传递传值调用（Call-by-Value）把实在参数的右值传递给形式参数调用序列计算实在参数的值，并将它复制到被调用过程活动记录的参数域中这种参数传递方法对调用过程的活动记录没有影响11/23/2022339.4参数传递传值调用（Call-by-Value）把实9.4参数传递引用调用（Call-by-Reference）把实在参数的左值（地址）传递给形式参数调用序列将实在参数的左值（地址）复制到被调用过程活动记录的参数域中被调用过程对形式参数的引用其实是对实在参数的地址（在被调用过程的活动记录中）进行引用11/23/2022349.4参数传递引用调用（Call-by-Referenc9.4参数传递复制恢复（Copy-Restore）传递参数同传值调用在从被调用过程返回前，把形式参数的现行右值复制回相应的实在参数的左值中这种方法与引用调用是有区别的：在被调用过程体中访问了非局部名字，而此非局部名字正是形式参数时P427Fig.7.3111/23/2022359.4参数传递复制恢复（Copy-Restore）传递参9.4参数传递传名调用（Call-by-Name）用实在参数对过程体进行宏扩展，必要时对被调用过程中的名字进行改名（防止与调用过程中的名字重复）**例子：P456练习7.6Fig.7.5311/23/2022369.4参数传递传名调用（Call-by-Name）用实在TheEnd!11/23/202237TheEnd!11/22/202237Chapter9

Run-TimeEnvironments概述存储分配策略（Storage-allocationstrategies）访问非局部名字（Accesstononlocalnames）参数传递（Parameterpassing）11/23/202238Chapter9

Run-TimeEnvironme9.1概述在生成目标代码之前，必须了解目标代码执行时的环境1、空间环境目标代码的运行都是在操作系统分配的一块存储区内进行的这块存储区必须容纳目标代码和目标代码运行时的数据空间（目标代码中指令能访问的空间）11/23/2022399.1概述在生成目标代码之前，必须了解目标代码执行时的环9.1概述编译程序分配目标程序运行时的数据空间的基本依据是设计程序语言时对程序运行中存储空间的使用和管理办法的规定代码生成器在生成目标代码时必须要体现该程序语言在设计时分配数据空间的规定11/23/2022409.1概述编译程序分配目标程序运行时的数据空间的基本依据9.1概述2、寄存器环境寄存器是目标机器中的宝贵资源如何分配寄存器提高程序运行的效率是代码生成器主要要解决的问题，（详细内容见下一讲）**数据空间分配和寄存器分配最后都体现在生成的目标代码中11/23/2022419.1概述2、寄存器环境寄存器是目标机器中的宝贵资源如何9.1概述几种典型程序设计语言的特点不同的语言有不同的分配数据空间的规定，有不同的组织运行时刻存储空间的方法11/23/2022429.1概述几种典型程序设计语言的特点不同的语言有不同的分9.1概述几种典型程序设计语言的特点与差异：CPASCALALGOLFORTRAN过程递归调用过程嵌套定义动态数组动态内存申请指针检查√××√×√√×√√√√√×√×

×

×

×√11/23/2022439.1概述几种典型程序设计语言的特点与差异：CPASCA9.1概述名字的联编（BindingsofNames）名字的左值(l-value)—内存地址，存储名字的瞬时值名字的右值(r-value)—名字的瞬时值名字的联编—将一个内存地址与一个名字联系起来在程序的一次运行中，一个名字右值（瞬时值）可能会经常改变，一个名字也可能被联编到多个地址（如递归调用中）11/23/2022449.1概述名字的联编（BindingsofNames9.1概述运行时刻内存的典型划分操作系统收到运行目标程序的指令，分配一块连续的内存空间使目标程序在其上运行P397Fig7.7这只是一个典型的划分，具体语言不同，该划分也不同栈（Stack）：支持过程的递归调用堆（Heap）：支持动态内存申请11/23/2022459.1概述运行时刻内存的典型划分操作系统收到运行目标程序9.1概述活动记录（ActivationRecords）是一段连续的存储区，用以存放过程的一次执行所需要的信息，如局部数据活动记录的结构P398Fig7.8参数域、状态域、数据域TOP指向栈顶，TOP-SP指向局部数据区的开始位置**这只是一个一般的结构，具体语言不同，活动记录的结构和内容也有差异11/23/2022469.1概述活动记录（ActivationRecords9.1概述过程的活动（Activation）过程的一次完整执行（第一条语句到最后一条语句），称为过程的一次活动过程在执行中称它为活着的如果允许递归调用，程序的一次执行可能有同一个过程的多个实例是活着的**本章主要讨论不同语言的目标程序在运行时的存储分配策略及名字与其左值和右值的关系11/23/2022479.1概述过程的活动（Activation）过程的一次完9.2存储分配策略静态存储分配（Staticallocation）编译时确定所需的全部数据空间的大小编译时安排好每个名字的存储位置（相对地址）采用静态存储分配的典型语言是FORTRAN11/23/2022489.2存储分配策略静态存储分配（Staticalloc9.2存储分配策略FORTRAN语言程序是段结构的，主程序段+若干子程序（函数）段没有动态数据类型，每个名字所需空间是确定的没有递归调用，无需栈区没有动态数据结构（如链表），没有动态内存申请，无需堆区11/23/2022499.2存储分配策略FORTRAN语言程序是段结构的，主9.2存储分配策略因此，编译时可确定数据区大小，为每个名字分配好地址FORTRAN程序运行时内存划分为目标代码区和静态数据区，没有栈区和堆区程序例子：P402example7.4Fig.7.10Fig.7.11Fig.7.1211/23/2022509.2存储分配策略因此，编译时可确定数据区大小，为每个名9.2存储分配策略程序设计语言若允许递归调用、可变数组、可变数据结构：编译时无法确定运行时需要的存储空间大小动态存储分配包括：栈式分配（Stackallocation）和堆式分配（Heapallocation）只能在运行时动态地确定，采用动态存储分配11/23/2022519.2存储分配策略程序设计语言若允许递归调用、可变数组、9.2存储分配策略栈式存储分配的思想：在运行空间中划分一块存储空间作为栈区程序运行时每当调用一个过程，就将该过程的活动记录压入栈中，过程执行完毕将它的活动记录从栈中弹出例子：P405Fig.7.1311/23/2022529.2存储分配策略栈式存储分配的思想：在运行空间中划分一9.2存储分配策略栈式存储分配的实现反映在目标代码生成器的构造策略中，最终体现在生成的目标代码中调用序列(CallSequence)目标代码中的一个指令序列，完成调用一个过程的一系列操作，包括为被调用过程分配一个活动记录，并在相应的域中填入信息11/23/2022539.2存储分配策略栈式存储分配的实现反映在目标代码生成器9.2存储分配策略返回序列(ReturnSequence)目标代码中的一个指令序列，完成从一个被调用过程返回到它的调用过程的一系列操作，包括释放被调用过程的活动记录，并复制出返回值具体内容：P407Fig.7.1411/23/2022549.2存储分配策略返回序列(ReturnSequenc9.2存储分配策略有些程序设计语言允许用户自由申请内存空间，如C的malloc和free，PASCAL的new和dispose何时申请何时释放由用户决定有些程序设计语言在进行数据空间分配时不服从栈式的存储分配原则（即“先申请后释放、后申请先释放”）11/23/2022559.2存储分配策略有些程序设计语言允许用户自由申请内存空9.2存储分配策略这时采用堆式存储分配方案运行空间划分一块堆区用户（显式）或目标代码需要时从这堆中借用一块，不用时退还**这是一种完全动态的存储分配方案11/23/2022569.2存储分配策略这时采用堆式存储分配方案运行空间划分一9.3访问非局部名字非局部名字相对于引用点所在的过程或分程序来说的程序执行时引用的在当前过程（分程序）之外定义的变量称为非局部名字**本节主要讨论栈式存储分配中如何访问非局部名字11/23/2022579.3访问非局部名字非局部名字相对于引用点所在的过程或分9.3访问非局部名字最近嵌套的作用域规则（mostcloselynestedrule）P412这是大多数程序设计语言采用的作用域规则例子：P416Fig.7.22（过程）例子：P413Fig.7.18（块或分程序）11/23/2022589.3访问非局部名字最近嵌套的作用域规则P4129.3访问非局部名字分程序（块）结构——ALGOL和C分程序（块）含有局部数据说明的语句序列有定界符号，允许嵌套例子：P413Fig.7.1811/23/2022599.3访问非局部名字分程序（块）结构——ALGOL9.3访问非局部名字过程（活动记录）采用栈式存储分配，分程序中的局部数据在活动记录的局部数据区内也采用栈式分配并列的分程序中的名字可分配同一个地址，因为它们所属的分程序不会在同一时刻存活访问同一过程中的局部名字可以从栈顶到栈底进行定位（同一活动记录中）Fig.7.19**访问其它过程中的局部名字见下面的讨论11/23/2022609.3访问非局部名字过程（活动记录）采用栈式存储分配，分9.3访问非局部名字无过程嵌套定义——C程序中引用的名字或者在当前的过程中被定义，或者在所有过程之外被定义在所有过程之外被定义的变量，称之为全局变量，被存放在静态数据区，地址在编译时刻确定（放符号表中）11/23/2022619.3访问非局部名字无过程嵌套定义——C程序中引用的9.3访问非局部名字过程中的局部名字联编到过程的活动记录的局部数据区中访问非局部名字可根据符号表中该变量的地址直接到全局静态数据区中查找11/23/2022629.3访问非局部名字过程中的局部名字联编到过程的活动记录9.3访问非局部名字有过程嵌套定义——PASCALPASCAL语言的一个例子P416过程和函数的嵌套深度（nestingdepth）访问非局部名字的方法有两种，一种是通过存取链，一种是通过DISPLAY表主程序为111/23/2022639.3访问非局部名字有过程嵌套定义——PASCALP9.3访问非局部名字存取链（accesslinks）活动记录中的一个区，是一个指针若过程P直接嵌入在过程Q中，则P的活动记录中的存取链指向Q的最近的活动记录中的存取链11/23/2022649.3访问非局部名字存取链（accesslinks）活9.3访问非局部名字如何建立存取链？参见P417Fig.7.23（a）（b）（c）（d）区分两种情况：P4181、Np<Nx，Np是调用者深度，Nx是被调用者深度2、Np>=NxNp–Nx+1

11/23/2022659.3访问非局部名字如何建立存取链？参见P417F9.3访问非局部名字如何利用存取链访问非局部名字？根据当前过程的嵌套深度和非局部名字所在过程的嵌套深度，可以计算出需顺着存取链前进的步数，从而对非局部名字进行访问Np–Na11/23/2022669.3访问非局部名字如何利