《编译原理》教学大纲

编写人：李康满

审核人：(两人以上)

一、本大纲适用专业

本大纲适用于计算机科学与技术本科专业。

二、编写本教学大纲的说明

（一）课程类别与教学任务

《编译原理》是面向计算机专业的计算机专业基础课程，是该专业的核心课程之一，它既是一门技术性、实践性很强的课程，又是理论与实践紧密结合的课程。

本课程介绍编译程序构造的一般原理和基本实现方法，内容包括词法分析、语法分析、属性文法与语法制导翻译、语义分析与中间代码产生、符号表与运行时存储空间组织、优化与目标代码生成技术。

（二）本课程的基本要求

通过对该课程的学习，要求学生能够掌握编译原理的基础理论，基本方法，对形式语言作大概的了解，掌握自动机的理论，把不确定的自动机转换成确定的自动机，以及自动机的化简；掌握词法分析的理论，了解构造词法分析程序的基本思想；掌握自上而下的语法分析方法；掌握算符优先分析法；掌握LR（0），SLR（1），LR（1）分析法，会构造相应的分析表；了解属性文法的基本概念和简单赋值语句的翻译过程。

（三）本课程的重点与难点

重点：掌握正规方法与有限自动机、自上而下分析方法和自下而上分析方法思想，中间代码的表示、栈式存储管理以及中间代码的优化方法。

难点：正规表达式与有限自动机的等价性，有限自动的确定化和最小化。回溯、递归预测分析表的构造。算符优先分析表和优先函数的构造，LR（0）、SLR、LR（1）分析表的构造。DAG表示及其应用，循环优化。

（四）本课程与其他相关课程的联系和后续课程

先修课程：计算机导论、高级语言、数据结构、离散数学、操作系统。

（五）学时、学时分配安排

本课程课时为54课时,课外通过开放式机房提供相应的实践课时；具体学时安排见教学内容。

（六）本课程的教学方式及其它教学环节的安排

本课程采用通常的课堂教学方式，并注重理论与实践相结合的方法，即以教师的课堂教授为主，同时辅以学生课外实践，培养与提高学生对本学科的兴趣和研究能力。

三、教学基本内容和学时分配

第一章 引 论（2课时）

编译程序在计算机科学中的地位和作用，编译技术的发展历史，编译程序、解释程序的基本概念，编译过程，编译程序的逻辑结构和编译程序的组织形式。

1、什么叫编译程序

2、编译过程概述

3、编译程序的结构

4、编译程序与程序设计环境

5、编译程序的生成

第二章 高级语言及其语法描述（2课时）

理解文法、语言、规范推导、规范归约和短语、简单短语、句柄的基本概念；掌握语言的求解方法、文法的二义性与递归性的判断方法及句型的分析方法

1、程序语言的定义

2、高级语言的一般特性

3、程序语言的语法描述

第三章 词法分析（4课时）

编译程序的第一个阶段词法分析程序的设计原理和设计方法，要求掌握正则文法、状态转换图、DFA、NFA、正规式和正规集的基本概念和词法分析程序的设计与编写。

1、对于词法分析器的要求

2、词法分析器的设计

3、正规表达式与有限自动机

4、词法分析器的自动产生

第四章 语法分析--自上而下分析（6课时）

本章介绍编译程序的第二个阶段语法分析的设计方法和实现原理，包括自上而下分析的无回朔的递归下降分析、LL(1)分析法。

1、语法分析器的功能

2、自上而下分析面临的问题

3、LL(1)分析法

4、递归下降分析程序构造

5、预测分析程序

6、LL(1)分析中的错误处理

第五章 语法分析--自下而上分析（8课时）

要求理解算符优先文法、最左素短语、有效项目的基本概念；掌握算符优先分析方法、LR(0)文法的判断及LR(0)分析表的构造与分析方法、SLR(1)文法的判断与SLR(1)分析方法和LR(1)文法的判断与LR(1)分析方法。

1、自下而上分析基本问题

2、算符优先分析

3、LR分析法

4、语法分析器的自动产生工具YACC

第六章 属性文法和语法制导翻译（6课时）

本章介绍编译程序的第三个阶段语义分析及中间代码生成的设计原理和实现方法，要求理解语法制导翻译、语义动作的基本概念；掌握算数表达式和赋值语句到中间代码的翻译、布尔表达式和几种控制语句的目标代码结构分析和到四元式的语法制导翻译；说明语句的语法制导翻译。

1、属性文法

2、基于属性文法的处理方法

3、S-属性文法的自下而上计算

4、L-属性文法和自顶向下翻译

5、自下而上计算继承属性

第七章 语义分析和中间代码产生（10课时）

语法制导翻译方法、完成语义规则、属性文法概念，四种中间代码形式。

1、中间语言

2、说明语句

3、赋值语句的翻译

4、 布尔表达式的翻译

5、控制语句的翻译

6、过程调用的处理

7、类型检查

第八章 符号表（2课时）

本章介绍编译程序的组成部分之一符号表的管理，要求掌握符号表的管理方法。

1、符号表的组织与作用

2、整理与查找

3、名字的作用范围

4、符号表的内容

第九章 运行时存储空间组织（4课时）

本章介绍目标程序运行时的存储组织方式，包括静态存储分配和动态存储分配。要求掌握各种存储组织形式的基本方法。

1、目标程序运行时的活动

2、运行时存储器的划分

3、静态存储分配

4、简单的栈式存储分配

5、嵌套过程语言的栈式实现

6、堆式动态存储分配

第十章 优化（6课时）

优化的相关知识，要求掌握局部优化，基本块的DAG表示及其应用，控制流分析和循环查找算法，到达定值与引用定值链，循环优化。

1、概 述

2、局部优化

3、循环优化

4、数据流分析

第十一章 目标代码生成（4课时）

本章介绍编译程序的第五阶段目标代码的生成的设计原理和实现方法，要求掌握四元式到汇编语言的目标代码生成方法。

1、基本问题

2、目标机器模型

3、一个简单的代码生成器

4、寄存器分配

5、DAG的目标代码

6、窥孔优化

% U6 {: l% N& u( N/ Z% y# B四、参考书目

1、陈火旺主编《程序设计语言编译原理》国防工业出版社

2、张素琴等编著《编译原理》清华大学出版社

3、陈意云等编著《编译原理》高等教育出版社

《编译原理》考试大纲

编写人：李康满

审核人：(两人以上)

一、考试对象

修完该课程所规定内容的计算机科学与技术专业本科学生。

二、考试目的

《编译原理》是计算机科学与技术及相关学科的重要基础课程，考试目的是测试考生是否掌握编译程序构造的一般原理和基本实现方法，内容包括词法分析、语法分析、属性文法与语法制导翻译、语义分析与中间代码产生、符号表与运行时存储空间组织、优化与目标代码生成技术。

三、考试的内容

第一章 引 论

1、编译过程和编译程序的结构

2、程序设计环境

3、编译程序的生成

第二章 高级语言及其语法描述

1、文法和语言的形式定义

2、分析树和二义性

3、形式语言概观

第三章 词法分析

1、词法分析程序的功能

2、输入缓冲

3、正规表达式与正规集

4、正规表达式与正规文法

5、状态图与基本符号的识别

6、有限自动机

第四章 语法分析--自上而下分析

1、语法分析器的功能

2、自上而下分析面临的问题

3、书写文法

第五章 语法分析--自下而上分析

1、自下而上分析

2、算符优先分析

3、LR分析法

第六章 属性文法和语法制导翻译

1、属性文法

2、基于属性文法的处理方法

3、S-属性文法的自下而上计算

4、L-属性文法和自顶向下翻译

5、自下而上计算继承属性

第七章 语义分析和中间代码产生

1、中间语言

2、说明语句

3、赋值语句的翻译

4、 布尔表达式的翻译

5、控制语句的翻译

6、过程调用的处理

7、类型检查

第八章 符号表

1、符号表的组织与作用

2、整理与查找

3、名字的作用范围

4、符号表的内容

第九章 运行时存储空间组织

1、目标程序运行时的活动

2、运行时存储器的划分

3、静态存储分配

4、简单的栈式存储分配

5、嵌套过程语言的栈式实现

6、堆式动态存储分配

第十章 优化

1、优化的概念

2、局部优化

3、循环优化

4、基本块的DAG表示及其应用

第十一章 目标代码生成

1、目标机器

2、运行存储管理

3、一个简单的代码生成器

4、寄存器分配

5、DAG的目标代码

6、窥孔优化

四、考试方法和考试时间

1．考试方法：笔试为主，平时实践考核为辅。

2．考试时间：120分钟。

五、评价标准

学生修完本课程并参加期末考试后，其成绩的评定为：期末考试成绩（60%）+ 平时成绩（40%），其中期末考试成绩按统一的评分标准阅卷评定，平时成绩包括考勤、作业、课堂提问、平时实践等。

六、试卷设计的结构

1．难度比例

试题的难度等级分为简单、中等难度、较难题三个等级，大致比例为40:45:15。

2．题型比例

客观性试题分为选择题、判断题，主观性试题分为简答题、综合应用题，其中主观性试题约占60%-70%左右。