编译原理--教学大纲

计算机编译原理1《计算机编译原理》课程大纲一、适用对象本课程适用于计算机科学与技术以及相关专业的网络教育、成人教育学生。二、课程性质本课程是计算机科学与技术专业学生的专业基础课。编译原理课程是计算机专业的一门主干课程。课程介绍程序设计语言编译程序构造的一般原理、基本设计方法、主要实现技术和一些自动构造工具。首先从剖析一个简单的编译程序PL/0入手，对编译程序设计的基本理论，如有穷自动机、上下文无关文法等给予介绍；对于广泛使用的语法分析和语义分析技术，如递归子程序法、算符优先分析、LR分析及语法制导翻译等进行了详细的讲解；对编译程序的结构及其各部分功能、实现方法以及整体的设计考虑给予了描述；对编译程序的构造工具进行介绍；同时对面向对象语言的编译程序和构造进行介绍。前序课程：高级程序语言、离散数学、数据结构、计算机组成原理。三、教学目的通过本课程的学习，使学生掌握设计和实现程序设计语言的最基本的理论和技术，掌握编译程序工作原理和构造方法。同时，能够达到去鉴赏、评价和实现某种程序设计语言。主要有如下教学目的：（1）对编译过程从整体上有一个较清晰的了解，掌握高级语言程序的编译过程。（2）掌握文法、自动机、正规式等编译基本理论知识。（3）掌握确定的自顶向下的语法分析方法和自底向上的算符优先分析及LR分析方法。（4）掌握语法制导翻译的语义分析方法，掌握中间代码的优化和目标代码的生成。（5）理解符号表和目标程序运行时的存储组织。（6）了解面向对象语言编译程序的原理和构造。四、教材及学时安排教材：张素琴、吕映芝、蒋维杜、戴桂兰，编译原理（第2版），清华大学出版社，2005年2月，ISBN：9787302089797学时安排：序号课程内容学时1第1章引论22第2章PL/0编译程序的实现13第3章文法和语言64第4章词法分析105第5章自顶向下语法分析方法106第6章自底向上优先分析67第7章LR分析88第8章语法制导翻译和中间代码生成79第9章符号表210第10章目标程序运行时的存储组织2计算机编译原理2序号课程内容学时11第11章代码优化812第12章代码生成413第13章编译程序的构造214第14章面向对象语言的编译215第15章编译程序的面向对象构造2合计72五、教学要求第1章引论教学要求：编译程序是现代计算机系统的基本组成部分之一。通过本章的学习，理解编译程序的概念和任务，掌握高级程序设计语言编译过程的各阶段及编译程序的结构，了解编译技术、编译软件工具和程序设计语言范型。内容要点：（2学时）1.1：什么是编译程序编译程序的概念及其在计算机系统中的作用1.2：编译过程和编译程序的结构编译过程的阶段划分、每阶段的基本任务及阶段的组合1.3：解释程序和一些软件工具解释程序、处理源程序的软件工具1.4：程序设计语言范型程序设计语言的范型第2章PL/0编译程序的实现教学要求：为使学生在系统学习之前对编译程序的构造有一个感性的认识和初步的了解，本章分析说明著名的“PL/0语言的编译程序”。通过本章的学习，熟悉一个高级程序设计语言编译程序实现的基本技术和步骤，了解高级语言语法的描述、词法分析、语法分析以及代码生成的基本内容。内容要点：（1学时）2.1：PL/0语言描述用语法图和扩展的BNF描述PL/0语言2.2：PL/0编译程序的结构PL/0编译程序的基本结构计算机编译原理32.3：PL/0编译程序的词法分析PL/0编译程序的词法分析的过程2.4：PL/0编译程序的语法语义分析PL/0编译程序的语法、语义分析过程2.5：PL/0编译程序的目标代码结构和代码生成PL/0编译程序的目标代码结构和代码生成过程2.6：PL/0编译程序的语法错误处理PL/0编译程序的出错处理过程2.7：PL/0编译程序的目标代码解释执行时的存储分配PL/0编译程序目标代码解释执行时的存储分配机制第3章文法和语言教学要求：任何高级程序设计语言均有自己定义的语法规则。通过本章的学习，理解符号和符号串，掌握文法和语言的形式定义、文法的类型、语法树，理解句型的分析方法，了解文法在实用中的一些限制。内容要点：（6学时）3.1：文法的直观概念以自然语言为例说明语言文法的直观概念3.2：符号和符号串语言形式文法中使用的符号和符号串3.3：文法和语言的形式定义文法、产生式、推导、语言的形式定义3.4：文法的类型0型文法、1型文法、2型文法、3型文法3.5：上下文无关文法及其语法树语法树、最左（右）推导3.6：句型的分析自上而下、自下而上的句型分析方法及有关问题3.7：有关文法实用中的一些说明文法实用中多余规则、ε规则的限制第4章词法分析教学要求：编译程序首先是对源程序进行词法分析，识别出单词流。通过本章的学习，理解词法分析程序的输出及其与语法分析程序的关系，掌握单词的描述工具――正规文法，掌握有穷自动机DFA、NFA，掌握正规文法、正规式、DFA、NFA之间的等价性，了解词法分析程序的自动构造工具。内容要点：（10学时）4.1：词法分析程序的设计计算机编译原理4词法分析程序的输出及其与语法分析的关系4.2：单词的描述工具正规文法、正规式及其等价性4.3：有穷自动机有穷自动机DFA、NFA及其NFA到DFA的转换4.4：正规式和有穷自动机的等价性正规式和有穷自动机之间的相互转换4.5：正规文法和有穷自动机的等价性正规文法和有穷自动机间的转换4.6：词法分析程序的自动构造工具LEX工具第5章自顶向下语法分析方法教学要求：语法分析是编译程序的核心部分，其作用是识别由词法分析给出的单词序列是否构成符合给定文法的程序。常用的分析方法有自顶向下和自底向上两类，本章介绍自顶向下的语法分析方法。通过学习，理解确定和不确定的自顶向下的分析思想，掌握FIRST集、FOLLOW集、SELECT集的概念及其计算，掌握LL(1)文法的概念和判别，掌握某些非LL(1)文法到LL(1)文法的等价变换，掌握递归子程序法和预测分析方法两种确定的自顶向下分析方法。内容要点：（10学时）5.1：确定的自顶向下分析思想以实例引入FIRST集、FOLLOW集、SELECT集和LL(1)文法的概念5.2：LL(1)文法的判别LL(1)文法判别的步骤、FIRST集、FOLLOW集、SELECT集的计算5.3：某些非LL(1)文法到LL(1)文法的等价变换提取左公共因子、消除左递归5.4：不确定自顶向下分析思想回溯分析5.5：确定的自顶向下分析方法递归子程序、预测分析方法第6章自底向上优先分析方法教学要求：自底向上的语法分析通常又包括算符优先分析方法和LR分析法，本章介绍优先分析方法，通过本章的学习，理解自底向上优先分析的基本思想，理解优先关系的概念、简单优先文法的概念和简单优先分析方法，掌握算符优先文法的概念，掌握FIRSTVT集、LASTVT集的概念、计算及算符优先关系表的构造，掌握算符优先分析算法和优先函数，了解算符优先分析法的局限性。内容要点：（6学时）6.1：自底向上优先分析概述计算机编译原理5基本思想6.2：简单优先分析方法优先关系、简单优先文法的定义、分析步骤6.3：算符优先分析法包括算符优先文法的定义、算符优先关系表的构造、算符优先分析算法及优先函数和局限性第7章LR分析教学要求：自底向上分析的关键是在分析过程中如何确定句柄，LR分析正是给出一种能根据当前分析栈中符号和向右查看输入串来确定分析器中的动作。通过本章的学习，了解LR(k)分析方法及LR分析器，掌握可归前缀、活前缀和识别活前缀的有穷自动机，掌握LR(0)项目集规范族和LR(0)分析表的构造，掌握LR(1)项目集族和LR(1)分析表的构造，掌握LR(0)规范族中避免项目集移进-归约、归约-归约冲突的条件，掌握LR(1)项目集族合并同心集的方法，了解二义性文法在LR分析中的应用，了解语法分析程序的自动构造工具。内容要点：（8学时）7.1：LR分析法概述LR分析器的组成、分析过程7.2：LR(0)分析可归前缀、子前缀、活前缀，识别活前缀的有穷自动机，LR(0)项目、LR(0)项目集规范族及其构造，LR(0)分析表的构造7.3：SLR(1)分析SLR(1)文法的引入、SLR(1)分析表的构造7.4：LR(1)分析LR(1)项目集族和LR(1)分析表的构造7.5：LALR(1)分析同心集、LALR(1)分析表的构造7.6：二义性文法在LR分析中的应用二义文法增加优先性和结合性可构造LR分析器7.7：语法分析程序的自动构造工具YACCYACC工具介绍第8章语法制导翻译和中间代码生成教学要求：经过语法分析合乎给定文法的程序，应进行语义分析和中间代码的生成。通过本章的学习，了解属性文法，掌握语法制导的翻译方法和中间代码的基本形式，掌握简单赋值语句、布尔表达式、控制结构、说明语句、数组和结构的翻译。内容要点：（7学时）8.1：属性文法属性文法的概念计算机编译原理68.2：语法制导翻译概论计算语义规则、S-属性文法和L-属性文法的实现8.3：中间代码的形式逆波兰表示、三元式和树形表示、四元式8.4：简单赋值语句的翻译简单赋值语句翻译方案8.5：布尔表达式的翻译布尔表达式翻译方法、控制语句中布尔表达式的翻译8.6：控制结构的翻译条件转移、开关语句、for循环语句、出口语句的翻译8.7：说明语句的翻译简单说明语句、过程中的说明语句的翻译8.8：数组和结构的翻译数组说明和数组元素的引用、结构说明和引用的翻译第9章符号表教学要求：编译程序中符号表是用来存放语言程序中出现的有关标识符的属性信息，在编译过程的各阶段中，符号表不断地积累和更新信息并提供不同的属性信息。通过本章的学习，理解符号表的作用和地位，掌握符号表的主要属性和作用，掌握符号表的组织和管理。内容要点：（2学时）9.1：符号表的作用和地位符号表的功能9.2：符号的主要属性和作用符号名、类型、存储类别、作用域、可视性等属性9.3：符号表的组织总体组织、表项排列、关键字域的组织、下推链域的组织9.4：符号表的管理初始化、登录、查找管理第10章目标程序运行时的存储组织教学要求：编译程序必须组织与分配目标程序运行时的存储空间，存储分配是运行阶段进行的，但编译程序在编译阶段要为其设计好存储组织形式，并将这种组织形式通过生成的目标代码体现出来。通过本章的学习，掌握数据空间的静态存储分配、栈式动态存储分配、堆式动态存储分配，熟悉栈式存储分配的实现，掌握参数传递的方式，了解过程的调用、进入和返回。内容要点：（2学时）10.1：数据空间的三种不同使用和管理方法静态存储分配、动态存储分配方法计算机编译原理710.2：栈式存储分配的实现简单的栈式存储分配、嵌套过程语言的栈式分配实现、分程序结构的存储管理10.3：参数传递传值、传地址、过程参数10.4：过程调用、过程进入和过程返回过程的调用、进入和返回的基本概念第11章代码优化教学要求：由于语法制导翻译生成的是基于语法成分的中间代码，编译程序在中间代码或目标代码生成后要对生成的代码进行优化。通过本章的学习，掌握代码优化的概念及优化技术，掌握局部优化中的基本块的划分、变换、DAG表示及DAG应用，掌握程序流图、循环及循环的查找及循环优化技术，了解数据流分析与全局优化。内容要点：（8学时）11.1：优化技术简介优化的概念、常用优化技术11.2：局部优化基本块的划分、变换、DAG表示及应用11.3：控制流分析和循环优化程序流图的构造、循环的查找、循环优化技术11.4：数据流的分析与全局优化主要概念、数据流方程的一般形式、到达-定值、可用表达式、活跃变量数据流方程第12章代码生成教学要求：代码生成是把经过语法分析和优化后的中间代码转换成特定目标机器的机器语言或汇编语言。通过本章的学习，熟悉代码生成的讨论的计算机模型，掌握简单代码的生成方法，了解常用的代码生成程序的开发方法和自动化构造工具。内容要点：（4学时）12.1：代码生成概述代码生成程序的基本问题12.2：一个简单的代码生成程序代码生成的计算机模型、待用信息链及代码生成算法12.3：几种常用的代码生成程序的开发方法解释性代码生成、模式匹配