《编译原理知识点总结》由会员分享，可在线阅读，更多相关《编译原理知识点总结（6页珍藏版）》请在金锄头文库上搜索。
1、学习好资料欢迎下载考试题型：填空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、译阶段，其任务是由编译程序将源程序编译为目标程序，若目标程序不是机器代码， 而是汇编语言程序，则尚需汇编程序再行汇编为机器代码程序；第二阶段称为运行阶段， 其任务是在目标计算机上执行编译阶段所得到的目标程序。2）用高级语言编写的程序也可以通过解释程序来执行。解释程序也以源程序作为它的输 入，它与编译程序的主要区别是在解释程序的执行过程中不产生目标程序，而是解释执行 源程序本身。缺点：这种边翻译边执行的方式工作效率很低，但由于解释程序的结构比编译程序简单， 且占用内存较少，在执行过程中也易于在源程序一级对程序进行修改，因此一些规模较小 的语言，如BASIC,也常米用此种方式。5. P 11第一段
3、编译程序的各部分之间的关系，是指他们之间的逻辑关系，而不一定是执行时间上的先后 顺序，事实上，可按不同的执行流程来组织上述各部分的工作，这在很大程度上依赖与编 译过程中对源程序扫描的遍数，以及如何划分各遍扫描所进行的工作。此处所说的“遍”，是指对源程序或其内部表示从头到尾扫视一次，并进行有关的加工处理工作。（执行过程：单遍扫描、多遍扫描（大多数）Chapter 2前后文无关文法和语言1. 文法和语言的形式定义产生语言就是制定出有限个规则（文法），借助于它们，就能产生出此语言的全部句子。2. 文法规则四要素：文法：四要素（VN, VT，S，P）。1）产生语言的规则中的一系列需定义的语法范畴的名字
4、称为非终结符 号（大写字母）,其集合记为VN2）规则中不需进一步定义的基本符号称为终结符号,其集合记为VT3）非终结符中最终需定义的那个为推导句子开始的语法范畴，称其为开始符号或识别符号，记作S4）每一规则是用：:= 或- 连接起来的有序对，也称为产生式，用P表示3. 句型的分析 是指构造一种算法，用以判断所给符号串是否为某一文法的句型（或句子）。分两类方法：自顶向下 分析：从开始符 推导出句子或句型自底向上 分析：从句子或句型 归约出开始符4. 短语和句柄语法树的应用语法分析（自顶向下分析，自底向上分析）用语法树进行句型分析：用语法树自顶向下进行推导 ，-最右推导用语法树自底向上进行归约。-
5、最左规约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）规范推导是最 右推导，规范归约是最 左归约。 定义每种语言的文法都是 不（不| ）唯
6、一的。文法的化简与改造主要包括无用符号和无用产生式的删除，产生式的消除，单产生式的消除几项内容。大题：1）画出句子的语法树，找出所有的短语，直接短语和句柄（运算符最低原则）Chapter3词法分析及词法分析程序1）了解6种定义，特点正规文法、状态转换图、有限自动机FA（NFA DFA）、状态转换矩阵、正规表达式、正规集大题：正规式状态图（ NFA 确定化最小化顺序：或，连接，闭包（1）状态转换图的五要素1 ）有限非空状态集 K2 ）有限输入字母表刀3 ）状态之间的映射关系 f4 ）初态S0 K5 ）终态集Z K（2）1.确定的有限自动机（DFA若FA在每个状态，对输入符号的下一状态是唯一的，称
7、此种FA为确定的有限自动机 DFA2. 非确定的有限自动机（NFA若FA在某个状态，对输入符号的下一状态不是唯一的，而是状态集的一个子集，称此种FA为非确定的有限自动机 NFA（3）正规式中用到符号：闭包连接（不引起混乱可略去）最优（优先顺序可用括号加以改变） 次之最后正规式：将文法的终结符号用以上三种运算符连接起来组成的正规文法的表达式，是另一种用于描述正规文法的直观表示。正规集：正规式所描述的字符串的集合。（4）词法分析方法（正规文法、状态转换图、状态转换矩阵）（5） 单词描述（正规文法、状态转换图、有限自动机FA（NFA DFA、状态转换矩阵、正 规表达式、正规集）课堂练习：1. 单词的
8、编译器内部表示为二元式（class , value ）2. 单词的描述形式有许多种，包括文法形式正规文法，图示方式状态转换图，便于计算机存储的 状态转换矩阵，自动机又分为NFAQFA两种，正规表达式和 正规集最便于体现单词的结构3. Bell实验室M.Lesk等人用C语言研制的一个词法分析程序的自动生成工具叫LEX4. 判断（对）所有带有的自动机都是非确定的自动机Chapter 4语法分析和语法分析程序1.语法分析方法：自顶向下分析法：如递归下降法，LL （1 ）等（最左推导）自底向上分析法：如算符优先法（分析表达式常用），LR等（最右规约）大题 LR、SLR1（1）LL （1）-预测分析法（
9、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. 构造识别所有规范句型全部的活前
10、缀的DFAC. 构造LR （0 ）分析表 r产生式编号D. 分析句子（4）SLR（1）分析表将文法拓广（2）构造识别文法全部规范句型活前缀的DFA求非终结符号Follow（）集合（4）对每个项目集按以下四条规则填表： 若项目集L中有S,-S 置if#=Me 若项目集Ii中有a的项目，A” 口为第j个产生式，则Follow（A）元素所在列置归约动作为町 若项目集I冲形如A a 的项目若二口/为终结符，置i以】为Sj”x为非终结符,置【i“为j - 分析表中无定义的元素均表示出错课堂练习1、LL （1）分析器由_缓冲区 _ ,分析栈_，分析表 _,控制程序四部分组成。2、 语法分析的方法主要分为自
11、顶向下_和 自底向上_两大类，前者又包括 LL（1）分析法 和递归下降法 两种具体方法，后者又包括 LR分析法和算符优先分析法 两种具体方法3、判断（错）1、自顶向下语法分析采用规范推导。（最左）（对）2、所有左递归文法均无法直接用LL（ 1）分析方法进行语法分析。（错）3、所有的自底向上语法分析，每步分析都是找出当前句型的句柄进行归约。（算符优先矩阵t最左素短语 ）（对）4、一个文法如果是 LR （ 0）文法，则必定是 LR （1）文法。（更多的文法适应SL R（l）Chapter 5语法制导翻译及中间代码生成1）语法制导翻译： 在一遍扫描中，由语法分析引导 ，既完成语法分析任务，又完成语义分析 和中间代码生成方面的工作。实现方法：对文法中的每一产生式，都附加一“语义动作”或“语义子程序”，且在语法分析过程中，每当用一产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作 之外，同时调用相应的语义子程序。2）属性文法：一种附带有语义属性的前后文无关文法。3）中间代码：介于源程序与目标程序之间的代码形式，形式简单、含义明确、结构清晰、易于优化4）四元式：（操作符，第一操作数，第二操作数，结果）大题：1.算术表达式2. 布尔表达式改进记值3. 程序流程控制语句的翻译（序列、条件分支、while循环）
