南方医科大学本科专业教学大纲

编译原理

Compiler Implementation

适用专业：计算机科学与技术

 

 

 

 

 

 

 

 

 

执笔人：曹蕾、杨明经    

审定人：吕庆文

学院负责人：陈武凡

 

 

 

南方医科大学教务处

二○○六年十二月

课程编码：B030008

一、课程简介

本课程是计算机专业和信息工程专业的一门重要的专业课，既是一门理论性、实践性、技术性很强的课程，也是理论与实践紧密结合的课程。总学时54学时，2.5学分。

通过本课程的学习，使学生掌握和理解编译的基本过程、各个编译阶段的功能、常用的一些设计方法和技巧，最终具有设计、实现、分析和维护编译程序的初步能力。

本课程的先修课程主要有C语言程序设计、数据结构、离散数学等。学生应具有程序运行机制、树与二叉树、递归与回溯等知识结构，具有程序设计的基本能力。

Compiler Implementation is a very important professional course for students who major in Computer Science or Information Engineering. Students will see the theory behind different components of a compiler, the programming techniques used to put the theory into practice, and the interfaces used to modularize the compiler. The main object of this course is to demonstrate some important techniques that are now in common use: abstract syntax trees to avoid tangling syntax and semantics, separation of instruction selection from register allocation, copy propagation to give flexibility to earlier phases of the compiler, and containment of target-machine dependencies. The course includes 45 theory hours and 9 practice hours and weights 2.5 credit.

 

 

二、理论教学内容与要求

第一章   基础知识

内容：编译程序的基本概念，编译过程，编译程序的结构，编译程序和程序设计环境，编译程序的生成过程和构造工具。

要求：正确了解什么是编译程序，了解编译程序工作的基本过程几个阶段的基本任务，熟悉编译程序总框。

重点：编译过程和编译程序的结构。

 

第二章   高级语言与语法描述

内容：程序设计语言的定义，高级语言的一般特性，高级语言的语法描述，上下文无关文法，语法分析树和二义性，乔姆斯基文法体系。

要求：理解程序语言的词法、语法和语义等概念，进一步掌握高级程序设计语言的一般结构和主要共同特征，使学生具有必要的基础知识；理解文法和语言的一些基本概念，如文法的定义和构造、句型、句子、语言、推导、语法树等。

重点：语法，语义，文法的构造。

 

第三章   词法分析

内容：词法分析器的功能和输出形式，词法分析器的设计方法——状态转换图的实现，正规表达式与有限自动机，LEX的一般描述和实现。

要求：了解词法分析器的功能和输出形式，熟练掌握词法分析器设计的原理和方法，能够以转换图为工具使用某种语言的编写并调试一个扫描器。在正确理解正规表达式与有限自动机的有关概念、理论的基础上，了解词法分析的自动产生原理。

重点：词法分析器的功能和设计方法，正规表达式与有限自动机的等价性，有限自动机的确定化和最小化。

 

第四章    语法分析-自顶向下分析

内容：语法分析器的功能，自上而下分析面临的问题，LL（1）分析法，递归下降分析，预测分析程序。

要求：理解自上而下分析法的基本思想，掌握递归下降分析法的基本方法：如消除左递归、消除回溯、构造递归下降子程序。理解预测分析方法，掌握预测分析表的构造方法、LL（1）文法的定义。

重点：消除左递归，消除回溯、递归下降子程序的构造，预测分析表的构造。

 

第五章  语法分析-自底向上分析

内容：自下而上分析的基本问题，算符优先分析法，算符优先分析表和优先函数的构造，LR分析器的基本原理，LR文法，LR（0）、SLR、LR（1）分析表的构造，语法分析器的自动产生工具YACC。

要求：理解自下而上分析法的基本思想和有关归约、短语、句柄、规范归约等概念。掌握算符优先分析法，了解算符优先表和优先函数的构造技术。了解LR 分析器基本原理和工作方法，能够构造LR（0）、SLR、LR（1）分析表。了解YACC实现自动产生分析表的基本思想。

重点：算符优先分析表和优先函数的构造，LR（0）、SLR、LR（1）分析表的构造。

 

第六章     语义分析

内容：语法制导翻译的基本思想，属性文法的基本概念，基于属性文法的处理方法，在自上而下分析和自下而上分析中的属性计算。符号表的组织和作用，符号表的整理和查找方法，名字的作用范围，符号表的内容。

要求：要求学生理解语法制导翻译和属性文法的基本思想和方法，掌握属性的计算方法。了解符号表的作用、组织方法和包含的一般内容，掌握名字作用域分析。

重点：属性的计算。符号表的作用、组织方法和内容，名字的作用范围。

 

第七章   中间代码生成

内容：中间语言的形式——后缀式、图表示法、三地址代码，说明语句的语义分析，赋值语句的翻译，布尔表达式的翻译，控制语句的翻译，过程调用的处理，类型检查。

要求：熟悉几种中间语言的描述，掌握各种语句的翻译方法，会给出各种语句的语义规则和语义子程序。

重点：表达式和控制语句的翻译。

 

第八章   运行时环境

内容：运行时目标程序的活动，参数传递机制，运行存储器的划分，静态存储分配——FORTRAN存储分配，简单栈式存储分配，嵌套过程语言的栈式实现，堆式动态存储分配，面向对象语言的存储分配。

要求：了解目标程序运行时存贮空间的使用和组织管理方法，熟悉参数传递机制，理解静态分配和动态分配的基本思想，掌握栈式分配中活动记录的作用、组织、内容及使用，掌握目标程序运行时动态运行栈的内容的组织和变化过程。

重点：栈式存储分配的实现。

 

第九章   代码生成与优化

内容：目标代码生成的基本问题，简单代码生成器，寄存器分配，优化的概念，局部优化，基本块的DAG表示及其应用，DAG的目标代码。

要求：了解代码生成过程中的基本问题，理解待用信息、寄存器描述和地址描述等概念，掌握简单代码生成器的生成算法、寄存器分配策略，了解DAG的目标代码生成。

重点：单代码生成器的生成算法。

 

 

三、实验（见习）内容与要求

实验一

以PL语言（PASCAL语言的子集）为背景，实习编译程序的构造方法。首先通过调试PL编译程序，了解一个小的编译程序的总体框架，掌握递归下降分析程序的构造，理解和掌握错误处理方法及符号表的组织方式，理解和掌握语法制导翻译。然后扩充PL语言成分，并对相应的编译程序进行扩充。扩充内容：

（1）扩充语句，如增加for 语句、repeat 语句、case语句等

（2）增加函数的说明和使用

（3）扩充数据类型，如实型、记录类型等

（4）扩充其它语言成分

 

实验二

了解便于程序构造工具的使用：

（1）词法分析器的自动产生器——LEX

（2）语法分析器的自动产生器——YACC

 

 

四、基本技能要求

本课程内容多且难度大，学生通过系统的学习编译系统的结构、工作流程及编译程序各部分的设计原理和实现技术，掌握编译理论和方法的基本知识，并通过必要的上机实习，初步具有设计、实现、维护编译程序的基本能力。

 

 

五、教材与教学资源

教材：《程序设计语言编译原理》 陈火旺等 著   国防工业出版社

参考书：

《现代编译原理》-C语言描述（英文版） Andrew W. Appel 著 人民邮电出版社

《编译原理 习题与解析》伍春香 编著  清华大学出版社

 

 

六、考核

考核种类：停课、闭卷理论考试

考试时间：120分钟

计分方法：百分制

课程成绩组成：平时成绩（作业）占总成绩10%，上机实习占总成绩10%，期终考试占总成绩80%

附：考核命题计划双向细目表

 

 

七、教学时数分配

（一）理论课学时分配

章节	理论课内容（中英文对照）	学时
第一章	基本知识	3
第二章	该机语言与语法描述	3
第三章	词法分析	6
第四章	语法分析—自顶向下分析	6
第五章	语法分析—自底向上分析	6
第六章	语义分析	6
第七章	中间代码生成	6
第八章	运行时环境	3
第九章	代码生成与优化	3
	考试	3
理论课总学时数		45

 

（二）实验课学时分配

序号	实验课内容（中英文对照）	实验类型	学时
1	实验一	综合性实验	6
2	实验二	验证性实验	3
实验课总学时数			9

 

 

  八、课程实施要求及相关说明

1、课堂教学与上机实习相结合。在课堂教学中系统地讲述基本概念、基本原理和基本方法，通过上机实习深化对基本知识点的认识和理解。

2、充分利用其它的教学辅助手段和方式。结合课后作业开展答疑辅导；补充完善配合本课程的网上教学资源（包括课件、辅导材料、教学软件等）。