《编译原理I》教学大纲

1、编译原理I Compilor Theory一、课程基本情况课程类别：专业任选课课程学分：3学分课程总学时：48学时，其中讲课：40学时，实验：0学时，上机：8学时，实习0学时，课外0学时课程性质：选修开课学期：第6学期先修课程：离散数学，C语言 适用专业：信息与计算科学教 材：不用教材。可参考推荐书目。开课单位：数学与统计学院信息与计算科学系二、课程性质、教学目标和任务编译原理是本科软件专业必修课程，讨论将高级语言程序翻译为计算机可执行代码的理论方法，包括词法分析、语法分析、语义分析、代码生成和代码优化等内容。这些也是理解和设计其它各种软件特别是大型软件的基础，是软件开发人员必备知识。本课程教

2、学目标是，理解和掌握编译原理的基本理论和核心方法，并自己动手编写一个小型语言的编译器。本课程对于编程不感兴趣的学生来说，难度较大。三、教学内容和要求1引论（2学时）（1）了解编译程序的功能、设计过程和构造工具。（2）理解编译过程的各阶段及其功能。（3）掌握编译过程的各阶段及其功能。重点：词法分析、语法分析和语义分析的功能和相互关系。难点：词法分析、语法分析和语义分析的功能和相互关系。2正规表达式（2学时）（1）了解形式语言若干基本概念，包括字符串有关概念和字符串的几种运算。了解正规表达式在设计扫描器（即词法分析器）中的作用，正规表达式中算符的优先规则，常用扩展符号。（2）理解正规表达式概念，包

3、括定义和含义。理解若干典型实例的正规表达式。（3）掌握语言的正规运算，正规表达式的设计技巧，若干典型实例的正规表达式。重点：语言的正规运算，正规表达式概念，典型实例的正规表达式。难点：理解正规表达式概念，正规表达式的设计。3有限自动机（2学时）（1）了解有限自动机的直观模型和计算方式，有限自动机的功能和特点。了解有限自动机是词法分析的算法模型。陷阱状态缺省约定。（2）理解确定型有限自动机的形式定义，状态的作用，转移函数的作用。DFA的转移图和转移矩阵。若干典型实例有限自动机及其所接受的语言。确定型有限自动机的特点（转移的确定性和完备性）。列方程组求DFA所接受的语言。（3）掌握DFA的计算方式

4、和接受条件，典型实例有限自动机及其所接受的语言，设计DFA的一般方法和技巧。重点：DFA的转移图和转移矩阵表示，典型语言的DFA，设计DFA的一般方法和技巧。难点：求DFA所接受的语言，设计DFA的一般方法和技巧。4. 非确定有限自动机（4学时）（1）了解NFA和DFA的区别和联系，NFA在扫描器设计中的作用。（2）理解NFA的形式定义、空转移的作用、计算路径和接受条件。典型实例语言的NFA状态转移图设计。消去空转移的方法，由正规表达式转化为NFA的Thompson方法，由NFA转化为DFA的子集构造法。（3）掌握消去空转移的方法，由正规表达式转化为NFA的Thompson方法，由NFA转化为

5、DFA的子集构造法。重点：消去空转移的方法，由NFA转化为DFA的子集构造法。难点：消去空转移的方法，由NFA转化为DFA的子集构造法。习题课一：讲解正规表达式和有限自动机方面的作业题，做补充习题，练习NFA设计、消去空转移方法和子集构造法。5. 扫描器设计（2学时）（1）了解扫描器的功能，与语法分析器和语义分析器的关系。了解Lex的功能和原理。（2）理解DFA的实现方法（板书或投影演示编程、调试和测试过程），理解实例扫描器的DFA模型。（3）掌握扫描器设计流程和实现方法。重点：掌握扫描器设计流程和实现方法。难点：扫描器DFA模型的构造方法。6上下文无关文法（2学时）（1）了解乔姆斯基谱系（文

6、法和语言，四类语言间的包含关系），CFG在语法分析中的作用，正规文法与有限自动机之间的等价转化关系。巴克斯范式与CFG的等价性，巴克斯范式常用符号。（2）理解CFG中变量、终极符号和产生式的含义：语法成分、基本成分、语法成分的定义。理解最左推导和语法分析树的构造方法，语法分析树的意义。短语、句型、句子等概念。（3）掌握CFG的形式定义和含义，根据CFG构造输入串的最左推导和语法分析树。重点：根据上下文无关文法，构造输入串的最左推导和语法分析树。难点：构造最左推导和语法分析树。7改造上下文无关文法（2学时）（1）了解最左推导是构造语法分析树的自上而下分析法。了解上下文无关文法的歧义性概念和实例，

7、了解文法确定性的含义：根据当前输入符号可以确定进行推导的唯一正确产生式。（2）理解三种简单不确定性（公共左因子、左递归和首空变量）的概念和负面作用：导致自上而下分析陷入无限循环，或者经常回溯以搜索正确的推导路径，从而大大降低效率。（3）掌握改造和消除三种简单不确定性的方法。重点：改造和消除三种简单不确定性的方法。难点：消除间接左递归和消除首空变量的方法（代入变量，再引入新变量）。8.上机实验课一：扫描器的设计（2学时）测试程序，提交报告，记入平时成绩。9LL(1)文法和预测表分析法（4学时）（1）了解LL(1)分析法基本思想及其适用的文法，即LL(1)文法。了解预测表分析法和递归下降分析法是L

8、L(1)分析法的两种具体实现方法。了解递归下降分析法。（2）理解首字符集、后字符集和选择集的计算方法，预测表的构造方法。预测表分析法的步骤描述和实现方法。 （3）掌握首字符集、后字符集和选择集的计算方法，预测表的构造方法。预测表分析法的实现方法。 重点：掌握首字符集、后字符集和选择集的计算方法，预测表的构造方法。难点：首字符集、后字符集和选择集的计算公式。10优先分析法（2学时）（1）了解自下而上语法分析的基本思想，规范归约和句柄等概念。（2）理解简单优先关系的计算方法和确定句柄方法。理解算符优先关系的计算方法和确定素短语的方法。理解移进-归约法。（3）掌握简单优先关系矩阵和算符优先关系矩阵的

9、构造方法，掌握移进归约法。重点：简单优先关系矩阵和算符优先关系矩阵的构造方法，移进归约法。难点：简单优先关系和算符优先关系的计算公式。11LR(0)分析法（4学时）（1）了解LR(0)分析法的基本思想、适用范围和理论意义。（2）理解句型的可归约前缀、活前缀等概念。理解识别可归前缀的LR(0)自动机的功能以及各接受状态与文法产生式的对应关系。理解根据LR(0)自动机进行移进-归约的方法。理解LR(0)项目定义、分类和意义。理解以LR(0)项目为状态的NFA构造方法和作用。理解LR(0)项目规范集定义和含义。理解LR(0)项目规范集的定义和含义，理解以LR(0)项目规范集为状态的DFA的构造方法和

10、作用。理解LR(0)分析表的含义和根据分析表进行移进-归约的方法。理解根据LR(0)自动机构造LR(0)分析表的方法。（3）掌握LR(0)项目定义、分类和意义，LR(0)项目规范集的定义和含义，以LR(0)项目规范集为状态的DFA的构造方法，根据LR(0)自动机构造LR(0)分析表的方法。重点：根据LR(0)自动机构造LR(0)分析表的方法，根据LR(0)分析表进行移进-归约的方法。难点：根据LR(0)自动机进行移进-归约的方法，以LR(0)项目规范集为状态的DFA的构造方法。12.上机实验课二：预测表分析器的设计（2学时）测试程序，提交报告，记入平时成绩。13LR(1)分析法选学（4学时）（

11、1）了解简单LR(1)分析法（SLR(1)分析法）、规范LR(1)分析法和向前看LR(1)分析法（LALR(1)分析法）的基本思想和适用范围和优缺点。（2）理解SLR(1)、LR(1)和LALR(1)分析法中处理冲突项目的方法，分析表的构造方法。（3）掌握SLR(1)和LALR(1)分析表的构造方法。重点： SLR(1)和LALR(1)分析法处理冲突项目的方法，SLR(1)和LALR(1)分析表的构造方法。难点：SLR(1)和LALR(1)分析法处理冲突项目的方法。注：这一讲属于选修内容，课时不足时只讲解SLR(1)分析法。14属性文法和语法制导翻译（2学时）（1）了解语义分析的功能，几种中间

12、代码（抽象语法树、三地址码），属性文法的功能，继承属性与综合属性的概念，语法制导翻译基本思想。（2）理解声明语句的属性文法，算术表达式和赋值语句的属性文法，根据属性文法生成三地址码。理解算术表达式的自下而上和自上而下的翻译方法。（3）掌握根据属性文法计算语义属性的方法。重点：算术表达式和赋值语句的属性文法，根据该属性文法生成三地址码。难点：根据算术表达式和赋值语句的属性文法，对表达式赋值语句进行语法-语义分析，并生成三地址码。算术表达式的自下而上和自上而下的翻译方法。15条件控制语句的翻译（2学时）（1）了解条件控制语句翻译的难点在于确定布尔表达式的出口。（2） 理解布尔表达式的控制流翻译和回

13、填式翻译；理解for循环语句的回填式翻译；break、continue以及goto语句的翻译。（3）掌握布尔表达式的翻译方法。重点：布尔表达式的翻译方法。难点：布尔表达式的翻译方法。16.上机实验课三：语义分析器设计（2学时）测试程序，提交报告，记入平时成绩。17运行时的存储空间管理（2学时）（1）了解嵌套过程语言程序运行时整个运行栈的内容的组织。（2）理解静态分配和动态存储分配基本思想、目标程序运行进存储空间的使用和组织管理方式。（3）掌握栈式动态分配中活动记录的作用、组织、内容及使用。重点：栈式动态分配中活动记录的作用、组织、内容及使用。难点：目标程序运行进存储空间的使用和组织管理方式。18目标代码生成（4学时）（1）了解目标代码生成过程及其中的基本问题。（2）理解目标代码生成器的原理。 （3）掌握简单代码生成算法、寄存器分配策略。重点：简单代码生成算法、寄存器分配策略。难点：目标代码生成器的原理；简单代码生成算法、寄存器分配策略。习题课二：讲解典型题型及其解法，做补充练习。19.上机实验课四：代码生成器设计（2学时）测试程序，提交报告，记入平