编译原理总复习

《编译原理》总复习题型及分值教材各章知识点概览习题讲解.题型及分值一、判断题（1′×5=5′）二、填空题（1′×15=15′）三、选择题（2′×5=10′）四、名词解释题（3′×5=15′）五、计算题(5小题)（5′+10′+15′+15′+10′=55′）.教材各章知识点概览第一章引论第二章高级语言及其语法描述第三章词法分析第四章语法分析—自上而下分析第五章语法分析—自下而上分析第六章属性文法和语法制导翻译第七章语义分析和中间代码产生第八章符号表第十章优化.第一章引论基本概念

翻译程序，编译程序，编译前端、编译后端编译过程的五个阶段，各阶段的任务及其依循的规则、描述工具分别是什么？编译错误的种类语法错误、语义错误.第一章引论程序翻译的两种方式，它们的区别

编译方式、解释方式编译程序的生成方法用机器语言/汇编语言作工具用高级语言作工具自编译方式建立专门的编制编译程序的有效工具.第二章高级语言及其语法描述基本概念

文法、上下文无关文法、推导、句型、句子、语言、语义、词法规则、语法规则、语义规则名字和标识符及其区别数组，内情向量、表达式最左推导、最右推导、语法分析树及其与推导之间的关系文法的二义性及其消除.第二章高级语言及其语法描述语句的分类功能上：说明性语句、执行性语句形式上：简单句、复合句、分程序形式语言分类(chomsky,1956)

0型普通（短语）文法

1型上下文有关文法

2型上下文无关文法

3型线性（正规、正则）文法.第三章词法分析基本概念

DFA、NFA、状态等价词法分析器的功能及其输出形式单词符号的种类关键字、标识符、常数、运算符、界符正规式→NFA→DFA→最少化DFA（注意：状态函数定义不完整之情形）词法分析器的自动产生工具：

LEX状态转换图的构造(标识符、整数).第四章语法分析—自上而下分析语法分析的方法自上而下、自下而上自上而下分析的基本思想自上而下分析面临的主要问题左递归、回溯自上而下分析的基本方法

LL（1）分析法、递归下降分析器LL（1）的含义，LL（1）文法的判别.第四章语法分析—自上而下分析LL(1)分析器的组成部分输入缓冲区、分析栈、分析表、总控程序LL(1)分析的四种动作成功、匹配、推导、报错预测分析表的构造左递归的消除（直接、间接）

FIRST、FOLLOW集的计算

LL(1)文法的判定及其分析表的构造.第五章语法分析—自下而上分析基本概念短语、直接短语、句柄、素短语、最左素短语、规范归约与规范推导自下而上分析的基本思想及其核心自下而上分析的基本方法算符优先分析法（非规范归约）LR分析法（规范归约）给定一个文法的句型，找出其短语、直接短语、句柄、素短语和最左素短语.第五章语法分析—自下而上分析LR分析法的基本思想及其组成部分思想：记住历史、展望未来、定夺现在组成：输入缓冲区、分析栈（状态、符号）、分析表（动作、转换）、总控程序可归约串的刻画方式算符优先：最左素短语LR分析法：句柄LR(0)、LR(1)、LR(k)、SLR的含义.第五章语法分析—自下而上分析LR分析器的四种动作移进、归约、接受、报错LR分析法可能遇到的问题及其解决办法移进——归约冲突归约——归约冲突语法分析器的自动产生工具

YACC.第五章语法分析—自下而上分析算符优先关系表的构造

算符文法及其算符优先文法的判定

FIRSTVT、LASTVT集的构造算符优先表的构造优先表与优先函数之间的关系LR（0）、SLR、LALR（1）、LR（1）分析表的构造

拓广文法、构造LR(0)或LR(1)项目集规范簇、构造相应LR分析表.第六章属性文法和语法制导翻译基本概念

S—属性文法L—属性文法属性的分类综合属性继承属性抽象语法树的表示.第七章语义分析和中间代码产生

常见的中间代码的几种形式后缀式（逆波兰式）、三地址代码（三元式、四元式、间接三元式）、DAG图表示、抽象语法树后缀式（逆波兰式）的表示各类语句的翻译（四元式）表达式（算术及布尔）、赋值语句、数组、IF语句、WHILE语句.第八章符号表

符号表的基本组成、基本操作组成：名字栏和信息栏操作：查表、填表、访表、更新、删除符号表的组织方式直接方式、间接方式符号表的构造和处理方法线性表、二叉树、杂凑（哈希）.第八章符号表

内情向量的基本表项维数、首地址、各维界差、各维上界、各维下届、数组元素类型、地址不变量.第十章优化基本概念优化、基本块、局部优化优化遵循的原则等价原则、有效原则、合算原则常见的优化的几种方法删除公共子表达式、复写传播、删除无用代码、合并已知量、代码外提、强度削弱、删除归纳变量。（后三种涉及循环优化）.第十章优化基本块的划分及其程序流图的构造

.习题讲解计算题注意复习书上的例题及其平时作业题。在复习时，一定要亲手独立做一遍！.习题讲解计算题构造与下列正规式等价的最少化DFA

1(0|1)*101(0|1)*(00|11)(0|1)*.习题讲解计算题令文法G为：

E→E-T|TT→T/F|FF→（E）|i（1）消除文法的左递归并构造其LL(1)分析表（2）构造该文法的算符优先分析表.习题讲解计算题（3）分析该文法是否为LR(0)、LR(1)、SLR、LALR文法，若是构造相应分析表（4）使用最左（右）推导的方法证明（T/F-i）/i是该文法的一个句型（5)求出句型（T/F-i）/i的所有短语、直接短语、句柄、素短语、最左素短语。.习题讲解计算题将下列程序段翻译成四元式序列。

while