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

《河北工业大学编译原理期末复习》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、考试题型：填空24%+简答4*4=16%+解答4*15=6Chapter1重要概念1.什么编译程序？P3答：编译程序的主要功能是把用高级语言编写的源程序翻译为等价的目标程序。2.编译程序的工作过程？（6个阶段）P41、词法分析程序2、语法分析程序3、语义分析程序4、中间代码生成5、代码优化程序6、目标代码生成（不做优化是4个阶段，5、6不要）3.编译程序的逻辑结构？P4图1-2编译程序的逻辑结构4.执行高级语言编写的程序：（编译执行、解释执行）1）按编译方式在计算机上执行用高级语言编写的程序，一般须经过两个阶段。第一个阶段称为编译阶段，其任务是由编译程序将源程序编译为目标程序，若目标程

2、序不是机器代码，而是汇编语言程序，则尚需汇编程序再行汇编为机器代码程序；第二阶段称为运行阶段，其任务是在目标计算机上执行编译阶段所得到的目标程序。2）用高级语言编写的程序也可以通过解释程序来执行。解释程序也以源程序作为它的输入，它与编译程序的主要区别是在解释程序的执行过程中不产生目标程序，而是解释执行源程序本身。缺点：这种边翻译边执行的方式工作效率很低，但由于解释程序的结构比编译程序简单，且占用内存较少，在执行过程中也易于在源程序一级对程序进行修改，因此一些规模较小的语言，如BASIC，也常采用此种方式。5.P11第一段编译程序的各部分之间的关系，是指他们之间的逻辑关系，而不一定是执行

3、时间上的先后顺序，事实上，可按不同的执行流程来组织上述各部分的工作，这在很大程度上依赖与编译过程中对源程序扫描的遍数，以及如何划分各遍扫描所进行的工作。此处所说的“遍”，是指对源程序或其内部表示从头到尾扫视一次，并进行有关的加工处理工作。（执行过程：单遍扫描、多遍扫描（大多数））Chapter2前后文无关文法和语言1.文法和语言的形式定义产生语言就是制定出有限个规则（文法），借助于它们，就能产生出此语言的全部句子。2.文法规则四要素:文法:四要素（VN，VT，S，P）。1)产生语言的规则中的一系列需定义的语法范畴的名字称为非终结符号(大写字母),其集合记为VN2)规则中不需进一步定义的

4、基本符号称为终结符号,其集合记为VT3)非终结符中最终需定义的那个为推导句子开始的语法范畴,称其为开始符号或识别符号,记作S4)每一规则是用::=或->连接起来的有序对,也称为产生式,用P表示.3.句型的分析是指构造一种算法，用以判断所给符号串是否为某一文法的句型(或句子)。分两类方法：自顶向下分析：从开始符推导出句子或句型自底向上分析：从句子或句型归约出开始符4.短语和句柄语法树的应用——语法分析（自顶向下分析，自底向上分析）用语法树进行句型分析:用语法树自顶向下进行推导,---最右推导用语法树自底向上进行归约。--最左规约5.文法和语言的Chomsky分类1）0型文法或短语结构文法

5、(PSG)2）1型文法或前后文有关文法(CSG)3）2型文法或前后文无关文法(CFG).4）3型文法或正规文法。（左线性文法+右线性文法）编译过程的词法分析使用正规文法（3型文法）描述单词结构；语法分析采用前后文无关文法（2型文法）描述语句结构课堂练习1）Chomsky定义的四种形式语言文法分别为0型文法，1型文法，2型文法,3型文法,其中3型文法用于描述词法，2型文法用于描述语法。2）递归文法产生的语言语句集合是无限集合。3）规范推导是最右推导，规范归约是最左归约。定义每种语言的文法都是不（不

6、—）唯一的。文法的化简与改造主要包括无用符号和无用产生式的删除,ε－产生式的消除,单产生式

7、的消除几项内容。大题：1）画出句子的语法树，找出所有的短语，直接短语和句柄（运算符最低原则）Chapter3词法分析及词法分析程序1）了解6种定义，特点正规文法、状态转换图、有限自动机FA（NFA、DFA）、状态转换矩阵、正规表达式、正规集大题：正规式－－状态图（NFA）－－确定化－－－最小化顺序：或，连接，闭包（１）状态转换图的五要素1）有限非空状态集K2）有限输入字母表∑3）状态之间的映射关系f4）初态S0∈K5）终态集Z∈K（２）1.确定的有限自动机（DFA）若FA在每个状态，对输入符号的下一状态是唯一的，称此种FA为确定的有限自动机DFA2.非确定的有限自动机（NFA）若FA在

8、某个状态，对输入符号的下一状态不是唯一的，而是状态集的一个子集，称此种FA为非确定的有限自动机NFA。（3）正规式中用到符号：*闭包最优（优先顺序可用括号加以改变）·连接（不引起混乱可略去）次之

9、或最后正规式：将文法的终结符号用以上三种运算符连接起来组成的正规文法的表达式，是另一种用于描述正规文法的直观表示。正规集：正规式所描述的字符串的集合。（4）词法分析方法（正规文法、状态转换图、状态转换矩阵）（5）单词描述（正规文法、状态转换图、有限自动