河北工业大学编译原理期末复习.doc

考试题型：填空24%+简答4*4=16%+解答4*15=6Chapter 1 重要概念1. 什么编译程序？P3答：编译程序的主要功能是把用高级语言编写的源程序翻译为等价的目标程序。2. 编译程序的工作过程？（6个阶段）P41、 词法分析程序 2、语法分析程序 3、语义分析程序 4、中间代码生成5、 代码优化程序 6、目标代码生成（不做优化是4个阶段，5、6不要）3. 编译程序的逻辑结构？P4 图1-2 编译程序的逻辑结构4. 执行高级语言编写的程序：（编译执行、解释执行）1） 按编译方式在计算机上执行用高级语言编写的程序，一般须经过两个阶段。第一个阶段称为编译阶段，其任务是由编译程序将源程序编译为目标程序，若目标程序不是机器代码，而是汇编语言程序，则尚需汇编程序再行汇编为机器代码程序；第二阶段称为运行阶段，其任务是在目标计算机上执行编译阶段所得到的目标程序。2） 用高级语言编写的程序也可以通过解释程序来执行。解释程序也以源程序作为它的输入，它与编译程序的主要区别是在解释程序的执行过程中不产生目标程序，而是解释执行源程序本身。缺点：这种边翻译边执行的方式工作效率很低，但由于解释程序的结构比编译程序简单，且占用内存较少，在执行过程中也易于在源程序一级对程序进行修改，因此一些规模较小的语言，如BASIC，也常采用此种方式。5. P11 第一段编译程序的各部分之间的关系，是指他们之间的逻辑关系，而不一定是执行时间上的先后顺序，事实上，可按不同的执行流程来组织上述各部分的工作，这在很大程度上依赖与编译过程中对源程序扫描的遍数，以及如何划分各遍扫描所进行的工作。此处所说的“遍”，是指对源程序或其内部表示从头到尾扫视一次，并进行有关的加工处理工作。（执行过程：单遍扫描、多遍扫描（大多数）Chapter 2 前后文无关文法和语言1. 文法和语言的形式定义产生语言就是制定出有限个规则（文法），借助于它们，就能产生出此语言的全部句子。2. 文法规则四要素:文法 :四要素（VN，VT，S，P）。1)产生语言的规则中的一系列需定义的语法范畴的名字称为非终结符号(大写字母),其集合记为 VN2)规则中不需进一步定义的基本符号称为终结符号,其集合记为VT 3)非终结符中最终需定义的那个为推导句子开始的语法范畴,称其为开始符号或识别符号,记作S4)每一规则是用 := 或 - 连接起来的有序对,也称为产生式,用P表示.3.句型的分析是指构造一种算法，用以判断所给符号串是否为某一文法的句型(或句子) 。分两类方法：自顶向下分析：从开始符推导出句子或句型自底向上分析：从句子或句型归约出开始符4. 短语和句柄语法树的应用语法分析（自顶向下分析，自底向上分析）用语法树进行句型分析:用语法树自顶向下进行推导,-最右推导用语法树自底向上进行归约。-最左规约5. 文法和语言的Chomsky分类1）0型文法或短语结构文法(PSG)2）1型文法或前后文有关文法(CSG)3）2型文法或前后文无关文法(CFG).4）3型文法或正规文法。（左线性文法+右线性文法）编译过程的词法分析使用正规文法（3型文法）描述单词结构；语法分析采用前后文无关文法（2型文法）描述语句结构课堂练习1）Chomsky定义的四种形式语言文法分别为 0型文法，1型文法，2型文法 ,3型文法,其中3型文法用于描述词法，2型文法用于描述语法。2）递归文法产生的语言语句集合是无限集合。3）规范推导是最右推导，规范归约是最左归约。定义每种语言的文法都是不 （不|）唯一的。文法的化简与改造主要包括无用符号和无用产生式的删除 ,产生式的消除 ,单产生式的消除几项内容。大题：1）画出句子的语法树，找出所有的短语，直接短语和句柄（运算符最低原则）Chapter3 词法分析及词法分析程序1）了解6种定义，特点正规文法、状态转换图、有限自动机FA（NFA、DFA）、状态转换矩阵、正规表达式、正规集大题：正规式状态图（NFA）确定化最小化顺序：或，连接，闭包（） 状态转换图的五要素 1）有限非空状态集K 2）有限输入字母表 3）状态之间的映射关系f 4）初态S0K 5）终态集ZK （）1.确定的有限自动机（DFA）若FA在每个状态，对输入符号的下一状态是唯一的，称此种FA为确定的有限自动机DFA2.非确定的有限自动机（NFA）若FA在某个状态，对输入符号的下一状态不是唯一的，而是状态集的一个子集，称此种FA为非确定的有限自动机NFA。（3）正规式中用到符号： * 闭包 最优 （优先顺序可用括号加以改变） 连接（不引起混乱可略去） 次之 | 或 最后正规式：将文法的终结符号用以上三种运算符连接起来组成的正规文法的表达式，是另一种用于描述正规文法的直观表示。正规集：正规式所描述的字符串的集合。（4） 词法分析方法（正规文法、状态转换图、状态转换矩阵）（5） 单词描述（正规文法、状态转换图、有限自动机FA（NFA、DFA）、状态转换矩阵、正规表达式、正规集）课堂练习：1.单词的编译器内部表示为二元式（class , value）2.单词的描述形式有许多种，包括文法形式正规文法，图示方式状态转换图，便于计算机存储的状态转换矩阵，自动机又分为NFA,DFA两种，正规表达式和正规集最便于体现单词的结构3.Bell实验室M.Lesk等人用C语言研制的一个词法分析程序的自动生成工具叫LEX4.判断（对）所有带有的自动机都是非确定的自动机Chapter 4 语法分析和语法分析程序1.语法分析方法: 自顶向下分析法：如递归下降法，LL（1）等（最左推导）自底向上分析法：如算符优先法（分析表达式常用），LR等（最右规约）大题LR、SLR1（1）LL（1）-预测分析法（LL（1）分析法最左推导LL（1）分析表）1) 编写文法，消除二义性；2) 消除左递归、提取左因子；3) 求 FIRST 集和 FOLLOW 集FIRST():可以推出的开头的终结符号(或)FOLLOW(A):在所有句型中可能直接跟在A之后的终结符号4）检查是不是 LL(1) 文法（若不是 LL(1)，说明文法的复杂性超过自顶向下方法的分析能力 ）5） 按照 LL(1) 文法构造预测分析表6） 实现预测分析器（2）算符优先分析法(构造算符优先矩阵分析句子)广义运算符: 文法的终结符号 广义运算对象: 非终结符（3） LR（0）分析法A. 引入S-S拓广文法B. 构造识别所有规范句型全部的活前缀的DFAC. 构造LR（）分析表产生式编号D. 分析句子（4）SLR(1)分析表课堂练习1、LL（1）分析器由 缓冲区 ， 分析栈 ， 分析表 ， 控制程序 四部分组成。2、语法分析的方法主要分为 自顶向下 和 自底向上 两大类，前者又包括LL(1)分析法和递归下降法两种具体方法，后者又包括LR分析法和算符优先分析法两种具体方法3、判断（ 错）1、自顶向下语法分析采用规范推导。（最左）（ 对）2、所有左递归文法均无法直接用LL（1）分析方法进行语法分析。（ 错）3、所有的自底向上语法分析，每步分析都是找出当前句型的句柄进行归约。（算符优先矩阵最左素短语）（ 对）4、一个文法如果是LR（0）文法，则必定是LR（1）文法。（更多的文法适应（）Chapter 5 语法制导翻译及中间代码生成1) 语法制导翻译：在一遍扫描中，由语法分析引导,既完成语法分析任务，又完成语义分析和中间代码生成方面的工作。实现方法:对文法中的每一产生式，都附加一“语义动作”或“语义子程序”，且在语法分析过程中，每当用一产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作之外