编译原理专业课程教学大纲(软件工程)

PAGEPAGE9编译原理教学大纲一、说明（一）课程性质《编译原理》课程是计算机科学与技术专业、软件工程专业学生必须掌握的重要专业必修课，也是一门理论性、实践性和技术性很强的课程。编译系统是现代计算机系统的基本组成之一，编译程序构造的基本原理和技术不仅应用于编译程序的设计，也广泛应用于一般软件的设计和实现。（二）教学目的本课程的学习目的在于使学生掌握编译程序的基本概念、基本原理、设计方法和实现技术，具有初步分析实际编译系统的能力，并能编制和调试简单编译程序，为今后从事编译及其他有关软件的研究和开发工作打下较为坚实的基础。（三）教学内容本课程系统讲述程序设计语言的编译程序的概念、构造、以及实现的主要算法和技术。通过对本课程的学习，使学生较为透彻地理解编译程序的概念、原理，了解语言翻译的全过程(词法分析、语法分析、语义分析与中间代码生成、代码优化和目标代码生成)，掌握编译程序中常用的主要算法和技巧；并通过上机实习初步掌握编译器构造的基本方法。（四）教学时数教学总学时数90，其中：理论课54实验课36（五）教学方式理论讲授与实验结合二、本文理论部分第1章绪论教学要点：1.高级语言程序的执行方式2.编译程序的基本结构及其各阶段的基本任务教学时数：3学时教学内容：1.1引言了解：高级程序设计语言与编译技术之间的联系1.2程序设计语言与程序（1学时）了解：程序设计语言的定义涉及到的四个方面掌握：BNF范式高级语言程序的两种执行方式1.2编译程序构造及有关概念（2学时）理解：编译程序的功能掌握：编译程序基本结构以及每一阶段的任务第2章文法与语言教学要点：1、符号串和符号串集合及其运算。2、文法和语言的形式定义。3、文法和语言的分类4、文法等价变换5、语法树，句型分析。教学时数：9学时教学内容：2.1符号串与符号串集合（1学时）了解：符号串与符号串集合的定义，以及相关运算2.2文法与语言的形式定义（2学时）理解：规则和文法的定义推导和归约熟练掌握：句子与句型，短语与简单短语，句柄语言的定义，由文法产生句型（句子），由句型（句子）确定文法难点：短语、简单短语、句柄的求法由文法产生句型（句子），由句型（句子）确定文法2.3语言的分类（1学时） 了解：形式语言与自动机掌握：Chomsky文法的定义文法和语言的分类2.4文法等价于等价变换（4学时） 掌握：文法等价的概念 熟练掌握： 压缩文法等价变换消去左递归的文法等价变换 难点：压缩文法等价变换消去左递归的文法等价变换2.5语法分析树与句型分析（1学时） 了解：句型分析存在的基本问题 理解：语法分析树规范推导和规范归约掌握：文法二义性的判断句型分析技术难点：文法二义性的判断第3章词法分析教学要点：1、状态转换图的构造和运行2、DFA和NFA以及他们之间的转换3、词法分析程序的实现教学时数：7学时教学内容：3.1引言了解：词法分析与词法分析程序词法分析程序的实现方式3.2正则表达式与有穷状态自动机（4）了解：正则式的性质掌握：正则式正则式和有穷自动机之间的相互转换正则文法构造正则式熟练掌握：构造状态转换图，运行状态转换图 确定的有穷自动机（DFA），不确定的有穷自动机（NFA）NFA→DFA的转换，DFA的化简难点：NFA→DFA的转换，DFA的化简正则式和有穷自动机之间的相互转换3.3词法分析程序的实现（1学时）了解：手工编写词法分析程序的基本思路理解：单词的描述工具3.4词法分析程序的自动生成（1学时）理解：词法分析程序自动生成的思想和实质第4章语法分析—自顶向下分析技术教学要点：自顶向下分析技术解决的问题递归下降分析技术及实现预测分析技术及实现教学时数：8学时教学内容：4.1引言理解：自顶向下分析技术的实质和要解决的问题4.2带回溯的自顶向下分析技术（2学时）理解：带回溯的自顶向下分析技术的基本思想，存在的问题及解决方法无回溯的自顶向下分析技术（6学时）理解：递归下降分析技术的实现思想递归下降程序的构造方法应用递归下降分析技术识别句子掌握：实施无回溯的自顶向下分析技术的先决条件预测分析技术的基本实现思想应用预测分析技术进行句型分析时语法分析树的构造熟练掌握：预测分析表的构造应用预测分析技术进行句型识别第5章语法分析—自底向上分析技术教学要点：1.算符优先分析技术2.LR（k）分析技术教学时数：12学时教学内容：引言（1学时）理解：自底向上分析技术的实质和要解决的基本问题掌握：移入-归约法算符优先分析技术（5学时）了解：优先函数的引入算符优先矩阵和优先函数的不足理解：算符优先分析技术算符文法和其性质熟练掌握：算法优先矩阵，算符优先关系的构造应用算符优先分析技术识别句型优先函数的构造LR（k）分析技术（6学时）了解：LR（k）的定义和性质LALR（1）分析表的构造理解：LR识别程序和识别算法四种LR分析技术之间的关系掌握：可归前缀和子前缀,识别活前缀的有限自动机活前缀及其可归前缀的一般计算方法；LR（0）分析技术的相关概念，LR（0）文法SLR（1）分析技术的相关概念，SLR（1）文法LR（1）项集规范族的构造，LR（1）分析表的构造熟练掌握：LR（0）项集规范族的构造，LR（0）分析表的构造SLR（1）分析表的构造第6章语义分析与目标代码生成教学要点：中间代码的形式几种常见语句和结构的翻译教学时数：9学时教学内容：6.1概况（1学时）了解：属性文法；语法制导翻译概论中间代码生成（2学时）了解：产生中间代码的必要性掌握：几类中间代码的格式控制语句的翻译（6学时）了解：数组元素引用的翻译过程语句的翻译说明语句的翻译熟练掌握：简单算术表达式和赋值语句的翻译布尔表达式的翻译控制语句的翻译第7章运行环境教学要点：几种存储分配策略教学时数：1学时教学内容：存储分配策略（1学时）了解：静态存储分配，栈式存储分配，堆式存储分配第8章代码优化教学要点：优化的定义、分类局部优化循环优化教学时数：4学时教学内容：引言理解：代码优化的概念和分类基本块的优化（2学时）了解：dag图掌握：几种基本块的优化技术循环优化（2学时）了解：循环优化的实现掌握：循环优化的几种技术窥孔优化了解：窥孔优化的概念和技术第9章程序错误的检查和校正教学要点：程序错误的必然性和类别词法错误的复原和校正语法错误的复原和校正教学时数：1学时教学内容：9.1概况了解：程序错误的必然性和类别词法错误的复原和校正了解：词法错误种类和校正方法语法错误的复原和校正了解：语法错误种类和校正方法实验部分（一）基本要求《编译原理》是计算机科学与技术专业的一门重要专业课，是一门理论性和实践性都比较强的课程。进行上机实验的目的是使学生通过完成上机实验题目加深对课堂教学内容的理解，同时培养学生实际动手能力。教学目的：通过实验要学会用BNF范式定义一个简单的程序设计语言。学会用高级程序设计语言设计一词法分析器、语法分析器、中间代码产生器，用这个简单的程序设计语言书写一段程序，并调试运行出来。3．进行科学研究的基本训练，培养学生严谨认真的科学态度，提高分析问题和解决问题的能力。基本要求：1．试验前做好预习，明确试验目的，基本原理及操作要点，2．在试验的整个过程中要注意观察试验结果，必要时重复试验；3．对试验结果进行分析，做好试验报告；（二）实验项目总表序号实验项目名称学时数项目类别项目类型1文法的表示与压缩6基础必做2从正则文法构造FA并运行6设计必做3预测分析表的生成，及应用预测分析技术识别句子8综合必做4SLR(1)分析表的生成及应用SLR(1)分析技术识别句子8综合必做5赋值语句的语义分析实现8综合必做（三）实验项目内容及要求实验一文法的表示与压缩实验目的及要求：掌握文法在计算机内的存储表示；了解Chomsky文法的四元组表示；掌握文法压缩的方法实验内容及学时分配：（6学时）1.输入任意上下文无关文法，输出四元组形式；2.输入任意的上下文无关文法，输出压缩后的文法实验二从正则文法构造FA并运行1、实验目的及要求：1.掌握有穷状态自动机的概念2.掌握FA的存储表示及其与正则文法的关系；3.运行有穷状态自动机；实验内容及学时分配：（6学时）输入任意的正则文法，五元组形式输出相应的有穷状态自动机。识别有穷状态自动机是确定的还是非确定的。输入该文法的句子，运行FA实验三预测分析表的生成，及应用预测分析技术识别句子1、实验目的及要求：1.掌握firse集合和follow集合的构造算法2.掌握应用预测分析表的构造3.利用预测分析技术进行句型分析；2、实验内容及学时分配：（8学时）1.输入任意的LL（1）文法及其待识别的符号串。2.输出first集合和follow集合以及预测分析表3.判断输入符号串是否问文法的句子实验四

SLR(1)分析表的生成及应用SLR(1)分析技术识别句子1、实验目的及要求：1.掌握LR（1）分析表生成的基本思想2.掌握应用LR（1）分析技术进行句型分析；2、实验内容及学时分配：（8学时，选做）1.输入任意压缩了的上下文无关文法，输出相应的SLR(1)分析表2.对待识别的符号串进行句型分析3.给出表列形式的语法分析树实验五赋值语句的语义分析实现1、实验目的及要求：掌握结合SLR(1)分析技术实现翻译方案2、实验内容及学时分配：（8学时）输入文法的任意赋值语句，输出相应的四元式序列。实验报告要求：要求实验报告包括如下内容：实验目的要求、算法描述、程序结构、主要变量说明、程序清单、结果分析、心得体会。成绩评定：根据程序设计的规范和技巧、程序运行的结果、实验报告的内容综合评定实验成绩。三、教材与参考书目教材张幸儿，《编译原理》，科学出版社，1999年4月，第三版参考书目1、吕映芝、张素琴、蒋维杜，《编译原理》，清华大学出版社，1998年1月