编译原理填空简答整理

填空一、素短语：含有终结符的短语，如果它不存在也具有这种性质的真子串，则该短语为素短语。二、二义性：文法G的一个句子如果能找到两种不同的规范推导或两棵不同的分析树，则称这个句子是二义性的，一个文法包含二义性的句子，则这个文法是二义性的，否则该文法是无二义性的。三、程序流图的构造：程序流图是程序结构的图形表示，我们把有唯一首节点n0的有向图G成为控制流程图，对一个程序流图来说，节点代表计算，有向边代表控制流，而首节点是程序起始位置所在的节点（基本块）。四、循环：循环是程序流图中有唯一入口结点的强连通的子图。循环要求强连通是很自然的，要求入口结点唯一是由于循环优化中需要将循环不变运算提到循环之外（代码外提）入口前的一个确定地点，这就要求入口结点是唯一的。五、必经结点集：从流图的首结点出发到达结点n的任一通路都必须经过结点d，则称d是n的必经结点，记为dDOMn。六、如果将DOM看成结点集N上的一种二元关系，那么它具有以下性质：（1）自反性（2）反对称性（3）传递性。七、可归约流图：一个流图删去了回边后的子图是个无环路的有向图，则称这个流图为可归约的流图。八、循环优化的例子：P161。九、在基本块范围内依次将三地址代码序列变换称目标代码，为使这种变换更有效，必须考虑到在基本块范围内如何充分利用寄存器的问题。选择标准是占用寄存器的变量不再被引用，或者引用点为最远的，这由待用信息来表示。十、并行编译系统就是能够处理并行程序设计语言，能够实现串行程序并行化，具有并行优化能力的编译系统。十一、并行编译技术中两个最重要的内容便是串行程序的向量化和并行化。十二、向量计算机：向量计算机是具有向量处理能力的计算机，它是在标量处理机的基础上增加了向量处理部分而构成的。向量处理部分通常含有若干向量寄存器、若干向量流水功能部件，以及一个控制向量操作长度的寄存器。十三、并行编译针对向量计算机的一个重要功能是串行程序向量化。显然，程序中的向量成分越多，向量机的运行效率越高。十四、共享存储器多处理机在更大的范围内提供了并行处理的能力，向量机只能并行处理向量操作，而多处理机可以并行执行多个循环迭代、语句块、子程序段。十五、分布存储器大规模并行计算机：分布存储器大规模并行计算机是由成百、上千乃至上万个结点构成的并行机，每个结点有自己的处理机和存储器，结点之间以互联网络相连。十六、并行编译系统的结构：并行编译系统通常包括程序分析、程序优化、和并行代码生成三个部分。简答一、编译程序总框图：P4。二、简述文法的定义：文法G是一个四元组，G=（VT，VN，S，P），其中：VT为终结符号集，这是个非空有限集。VN为非终结符号集，它也是个非空有限集。S为一文法的开始符，是一特殊的非终结符，S∈VN。P是产生式的非空有限集，其中每个产生式（或称规则）是一序偶（α，β），通常写成：α→β读作α是β或α定义为β。α为产生式左部，β为产生式右部。三、简述单词符号的种类：单词符号是程序语言最基本的语法符号，通常有五种。（1）基本字，有的称为关键字或保留字，如if，while，for，do，goto等。（2）标识符，用户用来命名程序中出现的变量、数组、函数、过程、标号等，通常是一个字母开头的字母数字串，如length、nextch等。（3）常数，包括各种类型的常数，如整型、实型、字符型等。（4）运算符，如+、-、*、/等。（5）界符，如；：、等。四、简述单词编码形成和特点：识别出来的单词符号应采用某种中间表示，以便为编译的后续阶段引用，其原则在于便以区别、便于识别，表示方法可多种多样，以有利于编译处理为准，通常单词符号可以用一个二元组表示：（单词类别，单词符号的属性值），第一元用以区分单词符号所属的类，以整数编码；第二元用以区分在该类中哪一个单词符号，即单词符号的值的编码，随类别不同而不同五、简述正规式与正规文法的关系：正规式与正规文法都是用来描述程序语言的词法结构，它们有着相同的表达能力。对任一正规文法，都可找到一个正规式，使正规式表示的正规集恰为正规文法产生的语言，反之亦然。正规式简洁，正规文法易识别，根据需要，可在两者之间进行转换。六、简述递归下降分析方法的特点：递归下降分析方法是一种自顶向下的分析方法，文法的每个非终结符，对应于一个递归过程。分析就是从方法开始符出发执行一组递归过程，向下推导，直到推导出句子。或者说从根结点出发，自上而下为输入串寻找一个最左匹配序列，建立一棵语法分析树。七、简述LR分析器特点：LR分析法是目前最广泛的无回溯的“移动-归约”方法，用上下文无关文法描述的程序语言，一般均可用LR分析方法，不只是因为LR分析方法对文法限制最少，而且效率同样很高，并且对发生的错误能准确定位。LR分析法也是一种表驱动分析方法，有一个分析栈、一个控制程序（或称为驱动程序）和一个分析表。八、简述堆分配的特点：作为堆的存储空间可以由固定长度的存储块组成，也可以由可变长度的存储块组成。在堆中可随机申请一个或几个存储块，活动结束时可随即释放。在这些存储块中有些正在使用由使用块记录指出各使用块的开始位置及块的大小等有用信息。有些则空闲，称为自由块。所有的自由块均被连接起来。由指针free指向其起始块每个自由块都有一个指针指向下一个自由块。当有一个使用块被释放时，该块连接到free块中，并从使用块中撤销该块的及录项。九、简述符号表的特点：在程序中，用户用标识符定义了不少名字来代表不同的数据对象，编译程序将这些名字保存在符号表中。符号表除了记录名字本身外，还记录了与名字关联的各种属性信息。总之，符号表的登记工作应在准确获得相关信息后即时完成。随之，在编译各阶段每当需要引用名字及其有关信息时，只要查询符号表便可获得。在符号表中为每一个名字设立一个表项，每一个表项是一个记录，通常由两个域构成，一个是名字域，一个是信息域。