编译原理课程复习重点与难点荟萃.docxVIP

编译原理课程复习重点与难点荟萃

编译原理作为计算机专业的核心课程之一，其理论性与实践性均较强，复习时需抓住主线，厘清脉络。本文旨在梳理课程中的重点与难点，为同学们的复习提供参考。

一、引论：编译程序概述

重点

*编译程序的基本概念与工作流程：理解编译程序的定义、主要功能以及从源程序到目标程序的完整转化过程，包括各个阶段的核心任务。明确编译与解释的根本区别。

*编译程序的逻辑结构：掌握编译程序的经典phases（阶段）划分，以及各阶段之间的联系与信息流。了解前端与后端的概念及其划分意义。

*编译程序的构造工具：了解诸如词法分析生成器（如Lex）、语法分析生成器（如Yacc/Bison）等工具的作用，它们如何简化编译程序的开发。

难点

*对编译全过程的整体把握：初学者易陷入具体算法细节，而忽略各阶段间的衔接与整体目标。需将各阶段置于“语言处理”这一大背景下理解其必要性。

*形式化方法的初步接触：编译原理大量采用形式化定义和描述，如正规式、文法等，初期理解可能存在障碍。

二、词法分析

重点

*词法分析的任务：主要包括识别单词符号（Token）、滤除空格与注释、行号记录、将识别出的Token及其属性传递给语法分析器。

*正规表达式与有限自动机：这是词法分析的理论基础。需掌握正规式与正规集的概念及运算；确定有限自动机（DFA）和非确定有限自动机（NFA）的定义、表示（状态图、状态表）及二者间的转换算法；DFA的最小化方法。

*词法分析器的构造：掌握基于DFA的词法分析器手工构造方法，以及如何使用Lex等工具自动生成词法分析器。理解Lex源程序的结构和工作原理。

难点

*NFA到DFA的转换：子集构造法的具体步骤，特别是ε-闭包的计算。

*DFA的最小化：Hopcroft算法或分割法的理解与应用，如何识别等价状态并进行合并。

*实际单词的识别：如标识符、常数（整数、实数、字符串）、关键字、运算符、界符的识别规则，以及如何处理单词间的冲突（如关键字与标识符的冲突）。

三、语法分析

重点

*语法分析的任务：根据文法规则，从词法分析器输出的Token序列中识别出语法结构（如表达式、语句、程序），并构建相应的语法树。

*上下文无关文法（CFG）：掌握CFG的定义（四元组）、文法的推导与归约、句型与句子、短语、直接短语、句柄等基本概念。理解文法的二义性及其判断，以及消除二义性的方法。

*LL(1)分析法：掌握LL(1)文法的定义、判别方法（FIRST集、FOLLOW集的计算，SELECT集的构造及无交集判定）；LL(1)预测分析表的构造；递归下降分析法的思想与实现；预测分析程序的工作过程。

*LR分析法：掌握LR(0)、SLR(1)、LR(1)、LALR(1)四种分析方法的基本思想、分析表的构造步骤（项目集规范族的构造、GO函数、冲突的解决）；LR分析器的工作过程（移进-归约）。理解这几种LR方法的区别与联系。

难点

*文法的等价变换：包括消除左递归（直接左递归、间接左递归）、提取左公因子，这些变换是文法满足LL(1)条件的前提。

*FIRST集与FOLLOW集的计算：尤其是当文法中存在ε产生式时，FOLLOW集的计算容易出错。

*LR分析表的构造：特别是LR(1)项目集规范族的构造，以及LALR(1)分析表构造中同心集的合并和可能引入的归约-归约冲突。理解各种冲突（移进-归约、归约-归约）产生的原因及解决策略。

*句柄的确定：在归约过程中，准确找到当前句型的句柄是关键。

四、语义分析与中间代码生成

重点

*语义分析的任务：主要包括类型检查（如运算数类型匹配、赋值相容性）、语义正确性检查（如数组下标是否为整数、函数调用实参与形参是否匹配）、变量的作用域分析、以及在语义正确的前提下生成中间代码。

*中间代码的形式：了解常见的中间代码形式，如三元式、四元式、间接三元式、逆波兰式（后缀表达式）、抽象语法树（AST）等，理解其特点和适用场景。

*属性文法与语法制导翻译：掌握属性文法的基本概念（属性、语义规则、综合属性、继承属性）；理解语法制导翻译的思想，即将语义规则与文法符号关联，在语法分析过程中执行这些规则以完成语义分析和中间代码生成。

*常见语法结构的翻译：如算术表达式、布尔表达式、赋值语句、控制流语句（if、while、for）、过程/函数调用等的语法制导翻译方法。

难点

*属性文法的设计与实现：如何为特定的语言结构设计合适的属性文法，并正确计算属性值。继承属性的计算流向及其依赖关系较难把握。

*控制流语句的翻译：特别是循环语句和条件语句中，如何正确处理跳转目标标号的生成与回填（Backpatch