下载文档原格式
北京语言大学网络教育学院《编译原理》模拟试卷一注意：1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。
请监考老师负责监督。
2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。
3.本试卷满分100分，答题时间为90分钟。
4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。
一、【单项选择题】(本大题共10小题，每小题2分，共20分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。
1、一个编译程序中，包含词法分析、（）、中间代码生成、代码优化、目标代码生成等五个部分。
[A] 语法分析[B] 文法分析[C] 语言分析[D] 解释分析2、词法分析器用于识别（）。
[A] 字符串[B] 语句[C] 单词[D] 标识符3、语法分析器则可以发现源程序中的（）。
[A] 语义错误[B] 语法和语义错误[C] 错误并校正[D] 语法错误4、下面关于解释程序的描述正确的是（）。
(1) 解释程序的特点是处理程序时不产生目标代码。
(2) 解释程序适用于COBOL 和FORTRAN 语言。
(3) 解释程序是为打开编译程序技术的僵局而开发的。
[A] (1)(2)[B] (1)[C] (1)(2)(3)[D] (2)(3)5、解释程序处理语言时, 大多数采用的是（）方法。
[A] 源程序命令被逐个直接解释执行[B] 先将源程序转化为中间代码, 再解释执行[C] 先将源程序解释转化为目标程序, 再执行[D] 以上方法都可以6、编译过程中, 语法分析器的任务就是（）。
(1) 分析单词是怎样构成的(2) 分析单词串是如何构成语句和说明的(3) 分析语句和说明是如何构成程序的(4) 分析程序的结构[A] (2)(3)[B] (2)(3)(4)[C] (1)(2)(3)[D] (1)(2)(3)(4)7、编译程序是一种（）。
[A] 汇编程序[B] 翻译程序[C] 解释程序[D] 目标程序8、文法G 所描述的语言是（）的集合。
编译原理目标程序运行时的存储组织引言在编译原理中，目标程序是指通过编译器将高级源代码转换为机器可执行的程序。
在目标程序运行时，需要一定的存储空间来存储程序的指令和数据。
本文将介绍编译原理中目标程序运行时的存储组织的基本概念和原理。
程序的内存模型目标程序在运行时的存储组织是通过内存模型来描述的。
内存模型定义了目标程序在内存中的存储方式和访问机制。
常见的内存模型有栈式模型、堆式模型和段式模型等。
栈式模型栈式模型将程序的内存划分为栈和堆两部分。
栈用于存储程序的局部变量、函数调用和返回地址等信息，而堆用于动态存储分配，如动态创建的对象以及通过malloc等函数分配的内存。
栈式模型的存储空间是连续分配的，栈的大小是固定的，而堆的大小可以根据需要进行动态调整。
堆式模型堆式模型将程序的内存划分为堆和栈两部分。
堆是动态分配的内存空间，用于存储程序运行时动态创建的对象和变量。
栈则用于存储函数调用的临时变量、函数参数和返回地址等信息。
堆式模型的存储空间可以动态调整，但需要手动管理内存的分配和释放，以避免内存泄漏和内存碎片的产生。
段式模型段式模型将程序的内存划分为若干个段，每个段用于存储特定类型的数据。
常见的段包括代码段、数据段、堆段和栈段等。
代码段用于存储程序的指令，数据段用于存储常量、全局变量和静态变量等数据，堆段和栈段与堆式模型和栈式模型类似。
段式模型可以更灵活地管理不同类型的数据，提高了内存的利用率。
存储器分配在目标程序运行时，编译器负责将程序的指令和数据分配到合适的存储器中。
存储器分配的主要目标是提高程序的执行效率和优化存储空间的利用率。
静态存储器分配静态存储器分配是在编译时确定存储器的分配方式。
静态存储器分配将程序的指令和数据分配到固定的内存地址上，程序运行时不会改变存储器分配。
静态存储器分配适用于程序结构稳定、数据量较小的场景，但难以适应动态创建和销毁对象的情况。
栈式存储器分配栈式存储器分配将程序的局部变量、函数调用和返回地址等信息存储在栈中。
编译原理目标程序运行时的组织简介在编译原理中，目标程序是由程序设计语言的源代码通过编译器转换而成的可执行文件。
目标程序的运行是通过操作系统的支持以及相关的硬件来完成的。
在目标程序运行时，需要对内存的组织进行有效的管理，以保证程序能够正确地执行。
程序的存储结构目标程序在运行时的组织首先涉及到程序的存储结构。
一般来说，目标程序在存储器中被组织为多个段或者区块。
这些段或者区块包括代码段、数据段、堆栈段等。
每个段都有不同的权限，比如代码段通常是只读的，数据段和堆栈段都是读写的。
代码段代码段是存储目标程序的机器指令的区域。
代码段在目标程序运行时是只读的，因为在运行时不能更改源代码。
代码段通常是按照顺序组织的，每条指令都有一个地址。
当程序执行时，计算机会从代码段中读取指令并逐条执行。
数据段数据段是存储目标程序的静态数据、全局变量以及常量的区域。
数据段在目标程序运行时是读写的，因为数据段中的数据可能会发生变化。
数据段通常是按照数据的类型和大小进行组织的，每个数据都有一个地址。
堆栈段堆栈段是存储目标程序的局部变量、函数的参数和返回值等临时数据的区域。
堆栈段在目标程序运行时是读写的，因为堆栈中的数据会被不断压入和弹出。
堆栈段通过栈的数据结构进行组织，数据的压入和弹出都是通过栈指针来实现的。
内存管理目标程序在运行时需要使用内存进行存储和计算。
内存管理是指程序如何分配、使用和释放内存资源的过程。
在目标程序运行时，操作系统负责管理内存的分配和释放，并对内存进行保护，以防止程序的错误操作导致系统崩溃或安全风险。
内存管理的主要任务包括内存分配、内存回收和内存保护。
内存分配是指为程序分配所需的内存空间。
常见的内存分配方式有静态分配和动态分配。
静态分配是在程序加载到内存时预先分配一定的内存空间，而动态分配是根据程序的需要，在运行时临时分配内存空间。
内存回收是指当某个内存空间不再被程序使用时，将其释放回系统。
常见的内存回收方式有手动回收和自动回收。
编译原理程序运行时的存储组织一、程序的应该存储区域1.代码区：也称为文本区或者只读区，用于存放程序的目标代码。
代码区是只读的，不允许修改。
在程序运行过程中，代码区的内容不会发生变化。
2.全局数据区：用于存放全局变量和静态数据。
全局数据区在程序开始运行时就被分配好空间，在程序的整个运行过程中都存在，直到程序结束。
3.堆区：用于存放动态分配的内存空间，也称为动态内存分配区。
堆区的内存空间是在程序运行时动态分配和释放的，可以根据程序的需要进行扩大或者缩小。
4.栈区：用于存放函数的局部变量和函数调用信息。
栈区的空间是在程序运行时自动分配和释放的，由编译器负责管理。
在函数调用时，会为函数分配一块栈区空间，函数返回后，该空间被自动释放。
二、内存管理方式1.静态内存管理：静态内存管理是指在程序编译阶段，由编译器根据程序的静态内存需求，在编译过程中为程序分配好固定大小的内存空间，静态内存管理的特点是内存空间的分配和释放都是在编译时确定的，程序运行时不需要进行内存管理。
2.动态内存管理：动态内存管理是指在程序运行时根据需要动态地分配和释放内存空间，动态内存管理的特点是内存空间的分配和释放是在程序运行过程中动态确定的。
动态内存管理可以通过堆区进行。
三、内存分配和释放编译原理程序在运行时的存储组织中，对于静态内存区域的分配和释放是由编译器在编译时确定的，程序在运行时无法进行修改。
对于动态内存区域的分配和释放，可以通过堆区进行，可以使用以下几个函数进行动态内存的分配和释放：1. 分配内存：程序可以使用malloc函数、calloc函数或者realloc函数来分配内存空间。
malloc函数用于分配指定字节数的内存空间，calloc函数用于分配指定数量和大小的内存空间，realloc函数用于调整已经分配的内存空间的大小。
2. 释放内存：程序在使用完动态分配的内存空间后，需要使用free函数来释放内存空间。
free函数会将之前分配的内存空间标记为可用状态，可以供其他程序使用。
第十章代码优化某些编译程序在中间代码或目标代码生成之后要对生成的代码进行优化。
所谓优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。
优化可在编译的不同阶段进行，对同一阶段，涉及的程序范围也不同，在同一范围内，可进行多种优化。
一般，优化工作阶段可在中间代码生成之后和（或）目标代码生成之后进行。
中间代码的优化是对中间代码进行等价变换。
目标代码的优化是在目标代码生成之后进行的，因为生成的目标代码对应于具体的计算机，因此，这一类优化在很大程度上依赖于具体的机器，我们不做详细讨论。
另外依据优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化三个不同的级别。
局部优化指的是在只有一个入口、一个出口的基本程序块上进行的优化。
循环优化对循环中的代码进行的优化。
全局优化是在整个程序范围内进行的优化。
本章重点：局部优化基本块的DAG表示第一节优化技术简介为了说明问题，我们来看下面这个例子，源程序是：P :=0For I :=1 to 20 doP :=P+A[I]*B[I];经过编译得到的中间代码如图10-1-1所示，这个程序段由B1和B2两个部分组成，B2是一个循环，假定机器按字节编址。
那么，对于这个中间代码段，可进行如下这些优化。
1、删除多余运算（删除公共子表达式）优化的目的在于使目标代码执行速度较快。
图10-1-1中间代码（3）和（6）中都有4＊I的运算，而从（3）到（6）没有对I赋值，显然，两次计算机的值是相等的。
所以，（6）的运算是多余的。
我们可以把（6）变换成：T4 :=T1。
这种优化称为删除多余运算或称为删除公共子表达式。
2、代码外提减少循环中代码总数的一个重要办法是代码外提。
这种变换把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面。
使之只在循环外计算一次，上例中，我们可以把（4）和（7）提到循环外。
经过删除多余运算和代码外提后，代码变成图10-1-2。
第一章：编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执行目标程序。
解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。
编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。
解释程序和编译程序的根本区别：是否生成目标代码第三章：Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类：0型文法（PSG）◊ 0型语言或短语结构语言文法Ｇ的每个产生式α→β中：若α∈Ｖ*ＶNＶ*, β∈(ＶN∪ＶT)* ，则Ｇ是0型文法，即短语结构文法。
1型文法（CSG）◊ 1型语言或上下文有关语言在0型文法的基础上：若产生式集合中所有|α|≤|β|，除Ｓ→ε(空串)外，则Ｇ是１型文法,即：上下文有关文法另一种定义：文法G的每一个产生式具有下列形式：αAδ→αβδ，其中α、δ∈V*，A∈VN，β∈V+；2型文法（CFG）◊ 2型语言或上下文无关语言文法Ｇ的每个产生式A→α，若A∈ＶN ,α∈(ＶN∪ＶT)*，则Ｇ是２型法，即：上下文无关文法。
3型文法（RG）◊ 3型语言或正则(正规)语言若Ａ、Ｂ∈ＶN，ａ∈ＶT或ε，右线性文法：若产生式为Ａ→ａＢ或Ａ→ａ左线性文法：若产生式为Ａ→Ｂａ或Ａ→ａ都是３型文法（即：正规文法）最左（最右）推导在推导的任何一步α⇒β，其中α、β是句型，都是对α中的最左（右）非终结符进行替换规范推导：即最右推导。
规范句型：由规范推导所得的句型。
句子的二义性（这里的二义性是指语法结构上的。
）文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。
文法的二义性一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。
第十章目标程序运行时的存储组织课前索引【课前思考】◇回顾一般的编译过程,能否找到本章所讲内容在哪个过程？◇为什么编译程序要考虑目标程序运行时存储区的管理和组织？◇请归纳C语言和PASCAL语言的程序结构和数据类型的不同点【学习目标】全面了解目标程序运行时存储区的整体布局；每种存储区的组织方式和管理方法；并通过实例着重掌握，对允许过程嵌套定义的情况，栈式动态存储分配的组织方式和运行时进栈退栈的活动实现方法。
【学习指南】在代码生成前，编译程序必须进行目标程序运行环境的配置和数据空间的分配。
一般来讲，假如编译程序从操作系统中得到一块存储区以使目标程序在其上运行，该存储区需容纳生成的目标代码和目标代码运行时的数据空间。
我们这里所说的运行时的存储区组织，是指目标程序运行时的数据空间的管理和组织。
【难重点】◇目标程序运行时，存储区域的整体布局，以及各区域的作用。
◇各种不同类型的数据表示。
◇允许过程嵌套定义的情况，栈式动态分配的组织管理。
◇对过程的调用，进入和退出时，栈式动态分配的工作原理。
◇过程活动纪录的各项内容和它们的作用，以及活动纪录的组织方式。
◇过程参数传递的不同方式。
【知识结构】从逻辑上看，在代码生成前，编译程序必须进行目标程序运行环境的配置和数据空间的分配。
一般来讲，假如编译程序从操作系统中得到一块存储区以使目标程序在其上运行，该存储区需容纳生成的目标代码和目标代码运行时的数据空间。
数据空间应包括：用户定义的各种类型的数据对象（变量和常数）所需的存储空间，作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元，以及组织输入/输出所需的缓冲区。
目标代码所占用空间的大小在编译时能确定。
有些数据对象所占用的空间也能在编译时确定，其地址可以编译进目标代码中。
而有些数据对象具有可变体积和待分配性质，无法在编译时确定存储空间的位置。
因此运行时的存储区常常划分成：目标区、静态数据区、栈区和堆区，如图10.1就是一种典型划分，代码(code)区用以存放目标代码，这是固定长度的，即编译时能确定的；静态数据区(static data)用以存放编译时能确定所占用空间的数据；堆栈区(stack and heap)用于可变数据以及管理过程活动的控制信息。
