编译原理理论教学大纲.doc

《编译原理理论教学大纲.doc》由会员分享，可在线阅读，更多相关《编译原理理论教学大纲.doc（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理理论教学大纲（2001年制订，2004年修订）课程编号： 英文名：Compiling Principle课程类别：专业主干课前置课：程序设计基础、数据结构、汇编语言、离散数学后置课：无学分：4学分课时：72课时（其中理论教学54课时，实验教学18课时）主讲教师：苏杭丽等选定教材：吕映之，张素琴，蒋维杜.编译原理.北京：清华大学出版社, 2001年.课程概述：本课程是计算机科学与技术专业的专业主干课程，介绍了程序设计语言编译程序构造的一般原理、基本设计方法、主要实现技术方法和一些自动构造工具，如：语言基础知识、词法分析、语法分析、有限自动机理论、形式语言的识别、语义检查、运行时的存储管理

2、、代码优化和代码生成以及整个编译程序的构造过程。教学目的：掌握编译程序构造的一般原理、基本设计方法、主要实现技术和一些自动构造工具，巩固程序设计语言、数据结构、汇编语言、离散数学等基础知识，能将编译程序中的概念和技术应用于一般的软件设计之中，能够独立完成小型编译程序。教学方法：理论讲课与上机实验结合。首先从剖析一个简单的编译程序（PL/0）入手，对编译程序设计的基本理论，如有穷自动机、上下文无关文法等给予必要的介绍；对于广泛使用的语法分析和语义分析技术，如递归子程序法、算符优先分析、LR分析及语法指导翻译等进行了详细讲解；对编译程序的结构及其各部分功能、实现方法以及整体的设计考虑等给予描述。此

3、外，还介绍了编译原理的构造工具。“编译原理”是一门对实践性要求较高的课程，教学中设置了实验课，强化对理论的理解。 各章教学要求及教学要点第一章 编译程序概论课时分配：2课时教学要求：了解什么是编译程序；了解编译过程。教学内容： 第一节什么是编译程序一、编译程序的基本知识第二节编译过程概述一、词法分析阶段二、语法分析三、语义分析阶段四、中间代码生成五、代码优化六、目标代码生成第三节编译程序的结构一、 编译程序的6个基本过程二、 编译程序的两个管理功能第四节编译阶段的组合一、 编译的前端二、 编译的后端第五节编译技术和软件工具一、 语言的结构化编辑器二、 语言的调试工具三、 语言的测试工具四、 高

4、级语言之间的转换工具五、 并行编译技术思考题：1.编译程序的工作过程包括哪几个基本阶段？2.介绍词法分析的概念。3.介绍语法分析的概念。4.介绍语义分析的概念。第二章 PL0编译程序的实现课时分配：4课时教学目的：了解PL0语言的描述；掌握PL0语言的语法描述图和EBNF表示；了解PL0编译程序的结构、词法分析、语法分析、目标代码结构以及语法错误处理；了解PL0编译程序的目标代码解释执行时的存储分配。教学内容：第一节PL0语言描述一、PL/0语言的语法描述图二、PL/0语言文法的EBNF表示第二节 PL0编译程序的结构一、 PL/0语言编译程序的过程二、 PL/0语言编译程序的函数结构第三节

5、PL0编译程序的词法分析一、 PL/0编译程序的词法分析过程二、 PL/0编译程序的取字符过程第四节 P0编译程序的语法分析一、语法分析程序的两大部分的功能：说明部分的处理和程序体部分的处理二、程序block过程第五节 PL0编译程序的目标代码结构一、PL/0编译程序的目标指令二、举例说明目标指令第六节 PL0编译程序的语法错误处理一、PL/0编译程序对语法错误、语义错误、运行错误的处理方法二、给出PL/0文法非终结符的开始符号与后继符号集合表三、介绍PL/0编译程序的test测试过程工作原理第七节PL0编译程序的目标代码解释执行时的存储分配一、PL/0编译程序的4个寄存器二、PL/0编译程序

6、的3个联系单元的作用思考题：1.给出对PL/0语言作如下功能扩充时的语法图和BNF的语法描述。(1)扩充一维整型数组。(2)扩充条件语句的功能使其为：ifthenelse(3)扩充repeat语句为：repeat;until2.对上题的(1)扩充给出：(1)符号表数据结构改动后的格式。(2)数组上下界的越界处理。(3)数组元素地址计算方法。(4)增加的目标指令形式及功能。3.给出1中的(2)、(3)扩充时：(1)所生成的目标代码结构示意图。(2)编译时此段目标代码生成的实现方法。第三章 文法和语言课时分配：6课时教学目的：了解文法的直观概念；了解符号和符号串；掌握文法和语言的形式定义；掌握文法

7、的类型；掌握上下文无关文法及其语法树；掌握句型的分析。教学内容：第一节文法的直观概念一、文法的基本概念第二节符号和符号串一、 字母表的概念二、 符号串的概念三、 符号串连接的概念四、 符号串方幂的概念第三节文法和语言的形式定义一、 文法的定义二、 推导的概念三、 直接推导的概念四、 句型的概念五、 句子的概念第四节文法的类型一、文法的4种类型第五节上下文无关文法及其语法树一、 语法树二、 最左推导三、 最右推导四、 规范推导五、 规范句型六、 句型的二义性第六节句型的分析一、自上而下的分析方法、自下而上的分析方法、句型分析的有关问题二、短语、直接短语、句柄的概念第七节有关文法实用中的一些说明

8、一、有关文法的实用限制二、上下文无关文法中的规则 思考题：1.解释下列术语和概念：(1)字母表。(2)串、字和句子。(3)语言、语法和语义。2. 已知文法G：:=:=*/:= ()试给出下列表达式的推导及语法树。(1)i (2)(i) (3)i*i (4)i*i+i (5)i+(i+i) (6)i+i*i3.设有文法GT：T-T*F|F F-FP|P P-(T)|a ,写出该文法句型T*P(T*F)的直接短语。4.已知文法G(E)：ET|ETTF|T * FF(E)|i(1) 给出句型(T * Fi)的最右推导及画出语法树。(2) 给出句型(T * Fi)的短语、素短语。第四章 词法分析课时分

9、配：6课时教学目的：了解词法分析程序的设计；了解单词的描述工具；掌握有穷自动机及其化简；掌握正规式和有穷自动机间的转换；掌握正规文法和有穷自动机间的转换。教学内容：第一节词法分析程序的设计一、词法分析程序与语法分析程序的接口方式二、词法分析程序的输出三、将词法分析工作分离的考虑第二节正规文法一、正规文法、正规式的概念二、正规文法与正规式之间的相互转换方法第三节有穷自动机一、确定的有穷自动机（DFA）、不确定的有穷自动机（NFA）的定义及表示方法二、NFA-DFA的转换方法 三、确定有穷自动机的化简方法第四节正规式和有穷自动机的等价性一、NFA转化为正规式的方法二、正规式转化为NFA的方法第五节

10、正规文法和有穷自动机间的转换一、正规文法转化为NFA的方法二、NFA转化为正规文法的方法第六节词法分析程序的自动构造工具一、LEX语言思考题：1.构造一个DFA，它接收0,1上所有满足如下条件的字符串：每个1都有0直接跟在右边。然后再构造该语言的正则文法。2.请给出正则表达式（0|1）*000 所识别的语言，并构造其等价的正则文法。3. 将下图所示NFA转换成等价的DFA并最小化第五章 自顶向下语法分析方法课时分配：6课时教学目的： 了解确定的自顶向下分析思想；掌握LL（l）文法的判别；掌握某些非LL（1）文法到LL（1）文法的等价变换；了解不确定的自顶向下分析思想；掌握确定的自顶向下分析方法

11、。教学内容：第一节确定的自顶向下分析思想一、 FIRST、FOLLOW、SELECT的定义二、 上下文无关文法的概念第二节LL（l）文法的判别一、 FIRST集的计算方法二、 FOLLOW集的计算方法三、 SELECT集的计算方法第三节某些非LL（1）文法到LL（1）文法的等价变换一、 提取左公共因子二、 消除左递归的方法第四节不确定的自顶向下分析思想一、由于相同左部的产生式的右部FIRST集不为空而引起的回溯的情况二、由于相同左部非终结符的右部能够推导出且该非终结符FOLLOW集中含有其右部FIRST集的元素的情况三、由于文法含有左递归而引起回溯的情况第五节确定的自顶向下分析方法一、 递归子

12、程序法二、 预测分析方法思考题：1.对文法GS:Sa|(T)TT,S|S(1)给出(a,(a,a)和(a,a), ,(a),a)的最左推导。(2)对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。(3)经改写后的文法是否是LL(1)的？给出它的预测分析表。(4)给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。2.对下面的文法G：E TE E+E|eT FTTT|eFPFF*F|e P(E)|a|b| (1)计算这个文法的每个非终结符的FIRST集和FOLLOW集。(2)证明这个文法是LL(1)的。3.设有文法GS:S-aBc|bABA-aAb|bBb|e构造其LL(1

13、)分析表，并分析符号串baabbb是否是该文法的句子。第六章 自底向上优先分析法课时分配：6课时教学目的：了解自底向上优先分析法；了解简单优先分析法；掌握算符优先分析法。教学内容： 第一节自底向上优先分析法概述一、自底向上分析方法的分析过程第二节简单优先分析法一、 优先关系二、 简单优先关系的定义三、 简单优先分析方法第三节算符优先分析法一、 算符优先文法的定义二、 算符优先关系表的构造方法三、 算符优先分析算法四、 算符优先分析法的局限性思考题：1.对文法GS:Sa|(T)TT,S|S(1)计算GS的FIRSTVT和LASTVT。(2)构造GS的算符优先关系表并说明GS是否为算符优先文法。(

14、3)计算GS的优先函数。(4)给出输入串(a,(a,a)#和(a,a)#的算符优先分析过程。2.对题的GS：(1)给出(a,(a,a)和(a,a)的最右推导和规范规约过程。(2)将(1)和题中的(4)进行比较给出算符优先规约和规范规约的区别。3.给出文法：ET|ETTF|T * FF(E)|i的终结符优先关系矩阵，判断符号串i*(i+i)#是否本文法的句子，并对算符（不包括i和#）给出优先函数。第七章 LR分析法课时分配：6课时教学目的：了解LR分析方法；掌握LR（0）分析；掌握SLR（l）分析；掌握LR（1）分析；掌握LALR（1）分析。教学内容：第一节 LR分析概述一、LR分析器的3个组成

15、部分及作用第二节 LR（0）分析一、可归前缀和子前缀的定义二、识别活前缀的有限自动机三、活前缀及其可归前缀的一般计算方法四、LR（0）项目集规范族的构造方法第三节 SLR（l）分析一、SLR（0）分析的方法二、SLR（0）与LR（0）分析方法的区别第四节LR（1）分析 一、LR（l）项目集族的构造 二、LR（1）分析表的构造第五节LALR（1）分析一、 LALR（1）分析的方法二、 LALR（1）与LR（1）分析方法的区别第六节二义性文法在 LR分析中的应用一、二义性文法在LR分析中的应用思考题：1.已知文法为:Sa|(T)TT,S|S(1)构造它的LR(0),LALR(1),LR(1)分析表

16、。(2)给出对输入符号串(a#和(a,a#的分析表。(3)说明(1)中三种分析表发现错误的时刻和输入串的出错位置有何区别。2.对算术表达式文法GE:EE+T|TTT*F|FF(E)|a(1)构造算符优先关系表和LR分析表，并对GE进行适当的改写后构造预测分析表。(2)分别使用三种表对句子i+i*i#进行分析。(3)对于错误的输入串(i+(*i)#和 *+i)+(i*#，分别查看错误的发现时刻和输入串的出错位置。3.已知文法GZ：Z-ABACA-AdB-bB-cC-cC-dD-e构造该文法的LR(0)句法分析控制表，并用LR(0)句法分析控制表分析aebaed是否该文法的句子。第八章 语法制导翻

17、译和中间代码生成课时分配：6课时教学目的： 了解属性文法；了解语法制导翻译；了解中间代码的形式；了解简单赋值语句的翻译；了解布尔表达式的翻译；了解控制结构的翻译；了解说明语句的翻译；了解数组和结构的翻译。教学内容： 第一节属性文法一、属性文法的定义第二节语法制导翻译概论一、语法指导翻译第三节中间代码的形式一、逆波兰记号、三元式、树型和四元式的表示方法第四节简单赋值语句的翻译一、简单赋值语句的翻译第五节布尔表达式的翻译一、布尔表达式的翻译第六节控制结构的翻译一、控制结构的翻译第七节说明语句的翻译一、说明语句的翻译第八节数组和结构的翻译一、数组和结构的翻译思考题：1.将表达式-(a+b)*(c+d

18、)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。2.下列文法生成一种表达式文法，其意义为：将算术运算符“+”施用于整数或实常数，只有当两个整数相加时，结果类型才是整数，否则为实数。EE+T|TTn,n|n(1)给出语法制导翻译的语义规则，其决定每个子表达式的类型。(2)给出语法制导翻译的语义规则，其不仅决定每个子表达式的类型，并且给出中缀表达式的逆波兰表示。3.写出表达式(ab*c)/(ab)d的逆波兰表示及三元式序列。第九章 符号表课时分配：4课时教学目的： 掌握符号表的作用和地位、符号的主要属性及作用、符号表的组织及符号表的管理。教学内容：第一节符号表的作用和地位一、符号表的作

19、用第二节符号的主要属性及作用一、符号的主要属性及作用第三节符号表的组织一、 符号表的总体组织二、 符号表项的排列三、 关键字域的组织四、 其他域的组织五、 下推链域的组织第四节符号表的管理一、 符号表的初始化二、 符号的登录三、 符号的查找四、 符号表中分程序结构层次的管理思考题：1.根据你所了解的某个FORTRAN语言的实现版本，回答以下问题：(1)该语言的名字作用域有哪几种？(2)请给该语言设计一种符号表结构。2.C语言中规定变量标识符的定义可分为extern、extern static、auto、local static和register五种存储类：(1)对五种存储类所定义的每种变量分别

20、说明其作用域。(2)试给出适合上述存储类变量的内存分配方式。(3)符号表中登录的存储类属性，在编译过程中支持什么样的语义检查？3.对分程序结构的语言，为其符号表建立重名动态下推链的目的是什么？概述编译过程中重名动态下推链的工作原理。第十章 目标程序运行时的存储组织课时分配：2课时教学目的：掌握数据空间的三种不同使用方法和管理方法、栈式存储分配的实现、参数传递、过程调用、过程进入和过程返回。教学内容：第一节数据空间的三种不同使用方法和管理方法一、 静态存储分配二、 动态存储分配三、 栈式动态存储分配四、 堆式动态存储分配第二节栈式存储分配的实现一、 简单的栈式存储分配的实现二、 嵌套过程语言的栈

21、式实现三、 分程序结构的存储管理第三节参数传递一、 传值二、 传地址三、 过程参数第四节 过程调用、过程进入和过程返回一、 过程调用二、 过程进入三、 过程返回思考题：1.名字和标识符有什么不同？2.名字的作用域是指什么？3.什么是过程？什么是局部变量？4.分程序是指什么？分程序结构中关于名字作用域的规定是什么？5.过程参数的传递方式有几种？简述“传地址”和“传值”的实现原理。第十一章 代码优化课时分配：2课时教学目的：掌握了解优化技术、局部优化、控制流分析和循环优化、数据流的分析与全局优化。教学内容：第一节优化技术简介一、 删除多余运算二、 代码外提三、 强度削弱四、 变换循环控制条件五、

22、合并已知量与复写传播六、 删除无用赋值的方法第二节局部优化一、基本块的划分二、基本块的变换三、基本块DAG表示的方法四、DAG的应用第三节控制流分析和循环优化一、 程序流图与循环的查找二、 可归约流图三、 循环优化第四节数据流的分析与全局优化一、 一些主要的概念二、 数据流方程的一般形式三、 到达一定值数据流方程可用表达式及其数据流方程活跃变量数据流方程四、 复写传播思考题：1.何谓代码优化？进行代码优化所需要的基础是什么？2.编译过程中可进行的优化如何分类？3.最常用的代码优化技术有哪些？第十二章 代码生成课时分配：2课时教学目的：了解代码生成；了解一个计算机模型以及一个简单的代码生成器；了

23、解代码生成研究现状。教学内容；第一节 代码生成简介一、代码生成过程第二节一个计算机模型一、模拟计算机的运行过程第三节一个简单的代码生成器一、 寄存器分配的原则二、 待用信息链表法三、 代码生成算法第四节代码生成研究现状一、中间语言的选择二、代码生成的自动化研究思考题：1.一个编译程序的代码生成需考虑哪些问题？2.试以PASCAL语言的赋值语句为例，叙述目标代码结构的设计及有关信息的保存与截取。3.若以PL/0抽象机器的代码为目标代码，则对于条件语句：IF x0 THEN y:=x+1 ELSE z:=x-1;其相应的目标代码是什么？第十三章 编译程序实现的途径课时分配：2课时教学目的：了解编译

24、程序的书写语言与T型图、编译程序的自展技术、编译程序的构造工具。教学内容：第一节 编译程序的书写语言与T型图一、源语言、目标语言和编译程序之间的关系及T形图表示第二节 编译程序的自展技术一、编译程序的自展技术第三节 编译程序的构造工具一、 基于LALR（1）的语法分析程序的生成器YACC二、 基于LL（2）文法的编译器的构造工具三、 词法分析程序的生成器LEX思考题：1.构造一个编译程序有哪些途径？2.若需在HP机上实现Ada语言，而已知在WAX机上有用Ada语言编写的Ada语言的自编译程序，产生的目标程序为WAX的汇编语言，试给出在HP机上实现Ada语言编译程序的方案。3.给出题2用T型图描

25、述实现步骤。附录:参考书目 1伍春香.编译原理考点精要与解题指导M.北京:人民邮电出版社,2002.2金成植.编译原理与实现M.北京：高等教育出版社,1992.3陈火旺.程序设计语言编译原理M.北京：国防工业出版社,2000.4陈意云.编译原理和技术M.北京：中国科学技术大学出版社,2000.5. 康慕宁.编译原理常见题型解析及模拟题M.西安:西北工业大学出版社,2002.6刘春林.编译原理典型题解析与实战模拟M.长沙：国防科技大学出版社,2001.7前沿考试研究室.计算机专业研究生入学考试全真题解M.北京：人民邮电出版社,2001.8伍春香.编译原理M.北京：清华大学出版社,2001.9陈英

26、.编译原理M.北京：北京理工大学出版社,2001.10.胡元义,柯丽芳.编译原理辅导M.西安：西安电子科技大学出版社,2001.11.刘坚.编译原理基础M.西安：西安电子科技大学出版社,2001. 执笔人：苏杭丽 2004年5月审定人：曹聪 2004年5月院（系、部）负责人：韩忠愿 2004年5月编译原理实验教学大纲（2001年制订，2004年修订）课程编号： 英文名：Compiling Principle课程类别：专业主干课前置课：程序设计基础、数据结构、汇编语言、离散数学后置课：无学分：4学分课时：72课时（其中理论教学54课时，实验教学18课时）实验指导教师：苏杭丽等选定教材：吕映之，张

27、素琴，蒋维杜.编译原理.北京：清华大学出版社, 2001年.课程概述：本课程是计算机科学与技术专业的专业主干课程，介绍了程序设计语言编译程序构造的一般原理、基本设计方法、主要实现技术方法和一些自动构造工具，如：语言基础知识、词法分析、语法分析、有限自动机理论、形式语言的识别、语义检查、运行时的存储管理、代码优化和代码生成以及整个编译程序的构造过程。实验目的： 通过实验，使学生能够加深对编译原理的理解，能够实现小型编译程序，使学生对编译过程有进一步的了解，能实现一定的应用。实验方法： 利用实验室中的计算机软/硬件设备，完成老师布置的作业，最后将实验结果以纸质或以电子文档的形式交给指导老师。各实验

28、名称、所需课时、实验内容及实验要求：实验一编译程序的分析与验证课时分配：4课时实验内容：验证一个程序输出结果的正确性。自行设计一程序进行正确性验证，并给出二元式序列的注释及状态栈STACK加工分析对应的符号栈内容。实验要求：了解编译程序中LR分析表的作用以及语义加工程序的功能。实验二算术表达式的扩充课时分配：5学时实验内容：参照算术表达式LR分析表的设计方法，设计扩充后的算术表达式LR分析表，并对原语义加工程序进行修改，加入新添加的内容。算术表达式文法扩充如下：EE+E|E-E|E*E|E/E|(E)|I根据该文法添加单词“-”、“/”的内部定义以及重新设计LR分析表，并修改语义加工程序，最后

29、验证修改的结果。实验要求：掌握LR分析表的设计方法和语义加工程序的扩充。实验三添加新的程序语句（一）课时分配：5学时实验内容：对添加的语句设计LR分析表及相应处理程序，并将其添加到程序语义处理程序中。将计数循环for语句的功能添加到编译程序中。实验要求：通过添加新的程序语句，全面了解一个语句的编译程序设计过程。实验四添加新的程序语句（二）课时分配：4学时实验内容：通过深入了解语句的内在功能，利用等价变换的方法实现语句的编译过程。试在编译程序中用等效的while 语句实现repeat语句的功能。实验要求掌握另一种添加语句功能的方法。附录:参考书目 1伍春香.编译原理考点精要与解题指导M.北京:人

30、民邮电出版社,2002.2金成植.编译原理与实现M.北京：高等教育出版社,1992.3陈火旺.程序设计语言编译原理M.北京：国防工业出版社,2000.4陈意云.编译原理和技术M.北京：中国科学技术大学出版社,2000.5. 康慕宁.编译原理常见题型解析及模拟题M.西安:西北工业大学出版社,2002.6刘春林.编译原理典型题解析与实战模拟M.长沙：国防科技大学出版社,2001.7前沿考试研究室.计算机专业研究生入学考试全真题解M.北京：人民邮电出版社,2001.8伍春香.编译原理M.北京：清华大学出版社,2001.9陈英.编译原理M.北京：北京理工大学出版社,2001.10.胡元义,柯丽芳.编译原理辅导M.西安：西安电子科技大学出版社,2001.11.刘坚.编译原理基础M.西安：西安电子科技大学出版社,2001. 执笔人：苏杭丽 2004年5月审定人：曹聪 2004年5月院（系、部）负责人：韩忠愿 2004年5月