编译原理填空简答整理.docx

《编译原理填空简答整理.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、填空一、素短语：含有终结符的短语，如果它不存在也具有这种性质的真子串，则该短语为素短语。二、二义性：文法G的一个句子如果能找到两种不同的规范推导或两棵不同的分析树，则称这个句子是二义性的，一个文法包含二义性的句子，则这个文法是二义性的，否则该文法是无二义性的。三、程序流图的构造：程序流图是程序结构的图形表示，我们把有唯一首节点n0的有向图G成为控制流程图，对一个程序流图来说，节点代表计算，有向边代表控制流，而首节点是程序起始位置所在的节点（基本块）。四、循环：循环是程序流图中有唯一入口结点的强连通的子图。循环要求强连通是很自然的，要求入口

2、结点唯一是由于循环优化中需要将循环不变运算提到循环之外（代码外提）入口前的一个确定地点，这就要求入口结点是唯一的。五、必经结点集：从流图的首结点出发到达结点n的任一通路都必须经过结点d，则称d是n的必经结点，记为dDOMn。六、如果将DOM看成结点集N上的一种二元关系，那么它具有以下性质：（1）自反性（2）反对称性（3）传递性。七、可归约流图：一个流图删去了回边后的子图是个无环路的有向图，则称这个流图为可归约的流图。八、循环优化的例子：P161。九、在基本块范围内依次将三地址代码序列变换称目标代码，为使这种变换更有效，必须考虑到在基本块范

3、围内如何充分利用寄存器的问题。选择标准是占用寄存器的变量不再被引用，或者引用点为最远的，这由待用信息来表示。十、并行编译系统就是能够处理并行程序设计语言，能够实现串行程序并行化，具有并行优化能力的编译系统。十一、并行编译技术中两个最重要的内容便是串行程序的向量化和并行化。十二、向量计算机：向量计算机是具有向量处理能力的计算机，它是在标量处理机的基础上增加了向量处理部分而构成的。向量处理部分通常含有若干向量寄存器、若干向量流水功能部件，以及一个控制向量操作长度的寄存器。一、并行编译针对向量计算机的一个重要功能是串行程序向量化。显然，程序中的

4、向量成分越多，向量机的运行效率越高。二、共享存储器多处理机在更大的范围内提供了并行处理的能力，向量机只能并行处理向量操作，而多处理机可以并行执行多个循环迭代、语句块、子程序段。三、分布存储器大规模并行计算机：分布存储器大规模并行计算机是由成百、上千乃至上万个结点构成的并行机，每个结点有自己的处理机和存储器，结点之间以互联网络相连。四、并行编译系统的结构：并行编译系统通常包括程序分析、程序优化、和并行代码生成三个部分。简答一、编译程序总框图：P4。二、简述文法的定义：文法G是一个四元组，G=（VT，VN，S，P），其中：VT为终结符号集，这

5、是个非空有限集。VN为非终结符号集，它也是个非空有限集。S为一文法的开始符，是一特殊的非终结符，S∈VN。P是产生式的非空有限集，其中每个产生式（或称规则）是一序偶（α，β），通常写成：α→β读作α是β或α定义为β。α为产生式左部，β为产生式右部。三、简述单词符号的种类：单词符号是程序语言最基本的语法符号，通常有五种。（1）基本字，有的称为关键字或保留字，如if，while，for，do，goto等。（2）标识符，用户用来命名程序中出现的变量、数组、函数、过程、标号等，通常是一个字母开头的字母数字串，如length、nextch等。（3）

6、常数，包括各种类型的常数，如整型、实型、字符型等。（4）运算符，如+、-、*、/等。（5）界符，如；：、等。四、简述单词编码形成和特点：识别出来的单词符号应采用某种中间表示，以便为编译的后续阶段引用，其原则在于便以区别、便于识别，表示方法可多种多样，以有利于编译处理为准，通常单词符号可以用一个二元组表示：（单词类别，单词符号的属性值），第一元用以区分单词符号所属的类，以整数编码；第二元用以区分在该类中哪一个单词符号，即单词符号的值的编码，随类别不同而不同五、简述正规式与正规文法的关系：正规式与正规文法都是用来描述程序语言的词法结构，它们有

7、着相同的表达能力。对任一正规文法，都可找到一个正规式，使正规式表示的正规集恰为正规文法产生的语言，反之亦然。正规式简洁，正规文法易识别，根据需要，可在两者之间进行转换。一、简述递归下降分析方法的特点：递归下降分析方法是一种自顶向下的分析方法，文法的每个非终结符，对应于一个递归过程。分析就是从方法开始符出发执行一组递归过程，向下推导，直到推导出句子。或者说从根结点出发，自上而下为输入串寻找一个最左匹配序列，建立一棵语法分析树。二、简述LR分析器特点：LR分析法是目前最广泛的无回溯的“移动-归约”方法，用上下文无关文法描述的程序语言，一般均可

8、用LR分析方法，不只是因为LR分析方法对文法限制最少，而且效率同样很高，并且对发生的错误能准确定位。LR分析法也是一种表驱动分析方法，有一个分析栈、一个控制程序（或称为驱动程序）和一个分析表。