编译原理教学大纲.doc

编译原理课程教学大纲PRINCIPLES OF COMPILERS课程编号：6560101学 时 数：总学时64（其中：理论54 实验10） 学 分 数：3课程类别：学科基础选修课 开课学期：第6学期适用专业：计算机科学与技术专业 开课单位：计算机科学与技术系先修课程：汇编语言、数据结构、C语言程序设计、形式语言后续课程：自动机编写时间：2008年6月一、课程性质和目的 课程性质：编译原理是计算机科学与技术专业学科基础选修课，编译技术是计算机科学中发展最迅速，最成熟的一个分支，集中体现了计算机的成果与精华。编译程序构造的基本原理和技术广泛地应用于一般软件的设计和实现中，可以帮助人们研究和开发系统软件和软件工具，本课程主要介绍程序设计语言编译程序构造的一般原理、基本实现技术和一些自动构造工具等。目的：通过编译过程的介绍使学生能够掌握编译理论和方法方面的基本知识，全面了解编译系统的结构、工作流程及编译程序各组成部分的设计原理和实现技术，具有编写和维护编译程序等方面的初步能力。配合上机实验，培养学生编写编译程序的基本技巧，并为后续的专业课程的学习奠定基础。二、课程教学内容、学时分配和课程教学基本要求第1章 引论教学内容（小节及各节知识点）：本章共分3小节1. 什么是编译程序；2. 编译过程和编译程序的结构：编译过程概述，编译程序的结构，编译阶段的组合；3. 解释程序和一些软件工具：解释程序，处理源程序的软件工具；教学要求：1. 了解编译程序的概念；2. 了解编译的过程；3. 了解编译程序与解释程序的区别；教学重点：1. 编译程序的概念，编译程序与解释程序的区别；2. 编译的过程：词法分析、语法分析、语义分析和中间代码的生成、代码优化、目标代码的生成；教学难点：编译的过程；学时分配：本章课堂讲授4学时；实践环节：作业要求： 通过课后的习题，使学生理解编译程序，解释程序和遍的基本概念，掌握编译过程各阶段的任务和编译程序的逻辑结构及其各部分的基本功能。第二章 文法和语言教学内容（小节及各节知识点）：本章共分7小节1. 文法的直观概念；2. 符号和符号串：字母表，符号串，符号串的头尾，符号串的连接，符号串的方幂，符号串集合；3. 文法和语言的形式定义：文法、直接推导、句型和句子的定义；4. 文法的类型：0型文法，1型文法，2型文法和3型文法； 5. 上下文无关文法及其语法树：语法树、最左（最右）推导、规范推导和规范句型的定义，文法二义性的判断；6. 句型的分析文法：自上而下的分析法，自下而上的分析法，短语、直接短语和句柄的定义； 7. 有关文法中的一些说明 ：有关文法的实用限制，上下文无关文法中的e规则；教学要求：1. 了解文法、语言的基本概念；2. 了解字母表，符号串，符号串的头尾，符号串的连接和符号串的方幂等概念；3. 掌握语言的定义方法、符号串的推导；4. 了解文法的类型；5. 了解语法分析树的构造、文法的二义性判断方法；6. 了解句型的分析方法；教学重点：1. 文法和语言的形式定义：文法、直接推导、句型和句子的定义；2. 句型的分析文法：自上而下的分析法，自下而上的分析法，短语、直接短语和句柄的定义；教学难点：1. 文法和语言的定义；2. 短语、直接短语和句柄的分析；学时分配：本章课堂讲授8学时；实践环节：作业要求：通过课后的习题，使学生能够了解文法的概念，熟练掌握符号串的推导，语法分析树的 构造，文法的二义性判断和对句型的分析。第三章 词法分析教学内容（小节及各节知识点）：本章共分6小节1. 词法分析程序：词法分析器的功能和输出形式，词法分析器作为一个独立子程序；2. 单词的描述工具：正规文法，正规式；3. 有穷自动机：状态转换图，DFA，NFA，把NFA变为DFA， DFA的化简；4. 正规文法和有穷自动机间的等价； 5. 正规文法和有穷自动机间的转换；6. 词法分析程序自动构造工具；教学要求：1. 了解词法分析器的功能和输出形式；2. 掌握正规文法正规式，两者之间的转换；3. 掌握状态转换图，DFA ，NFA，把NFA变为DFA， DFA的化简；4. 掌握正规文法和有穷自动机间的转换；教学重点：1. 词法分析程序：词法分析器的功能和输出形式，词法分析器作为一个独立子程序； 2. 单词的描述工具：正规文法，正规式；3. 有穷自动机：状态转换图，DFA，NFA，把NFA变为DFA， DFA的化简；4. 正规文法和有穷自动机间的转换；教学难点：1. 单词的描述工具：正规文法，正规式；2. 有穷自动机：状态转换图，DFA，NFA，把NFA变为DFA， DFA的化简；3. 正规文法和有穷自动机间的转换；学时分配：本章课堂讲授12学时，上机实践4学时；实践环节：1. 实验要求：实验一：用c 语言设计一个词法分析器。通过该实验，要求掌握定义模拟的简单语言的词法构成，编制词法分析程序。 2. 作业要求： 通过课后的习题，使学生能够熟练地掌握正则文法、状态转换图、DFA、NFA、NFA的确定化和最小化，状态转换矩阵到状态转换图的转化,正规式和正规集的基本概念。第四章 自顶向下语法分析方法教学内容（小节及各节知识点）：本章共分5小节1. 确定的自顶向下分析思想：First集与Follow集的定义；2. LL（）文法的判别；3. 某些非LL（1）文法到LL（1）文法的等价变换；4. 不确定的自顶向下分析思想；5. 确定的自顶向下分析方法；教学要求：1. 了解确定的自顶向下分析思想，掌握First集与Follow集的构造算法；2. 掌握LL（1）文法的判别方法；3. 掌握某些非LL（1）文法到LL（1）文法的等价变换方法；4. 了解不确定的自顶向下分析思想；5. 了解确定的自顶向下分析方法；教学重点：1. First集与Follow集的构造算法；2. LL（1）文法的判别方法；3. 某些非LL（1）文法到LL（1）文法的等价变换方法教学难点：1. First集与Follow集的构造算法；2. 消除左递归，消除回溯；学时分配：本章课堂讲授6学时，上机实践2学时；实践环节：1. 实验要求：实验二：用Java或者 c语言设计一个语法分析器。通过该实验，要求掌握定义模拟的简单语言的语法构成，理解递归下降法和LL(1)分析法。2. 作业要求：通过课后的习题，使学生能够熟练地掌握LL(1)分析表的构造及左递归和回溯的消除。第五章 自底向上优先分析教学内容（小节及各节知识点）：本章共分3小节1. 自底向上优先分析概述；2. 简单优先分析法：优先关系，简单优先文法，简单优先文法的分析步骤；3. 算符优先分析法：直观算符优先分析法，算符优先文法的定义，算符优先关系表的构造，算符优先分析法，优先函数；教学要求：1. 了解自底向上优先分析法；2. 了解优先关系，简单优先文法，掌握简单优先分析法；3. 了解算符优先分析法：直观算符优先分析法，算符优先文法的定义，算符优先关系表的构造，掌握算符优先分析法，掌握优先函数的构造方法；教学重点：1. 优先关系，简单优先分析法；2. 算符优先文法的定义，算符优先关系表的构造，算符优先分析法，优先函数的构造方法；教学难点：1. 简单优先分析法；2. 算符优先分析法；学时分配：本章课堂讲授4学时，上机实践2学时；实践环节：作业要求：通过课后的习题，使学生能够熟练地掌握简单优先分析和算符优先分析方法。 第六章 LR分析教学内容（小节及各节知识点）：本章共分3小节1. LR(0)分析表的构造；2. SLR分析表的构造；3. LALR分析表的构造；教学要求：1. 理解并掌握LR(0)分析表的构造；2. 理解并掌握SLR（1）分析表；3. 理解并掌握LALR（1）分析表的构造；教学重点：LR分析思想；教学难点：1. LR(0)分析；2. SLR(1)分析；3. LALR(1)分析学时分配：本章课堂讲授6学时，上机实践2学时；实践环节：1. 实验要求：实验三：用Java或者 c语言设计一个语法分析器。通过该实验，定义模拟的简单语言的语法构成，将实验一输出的Token文件作为输入文件，编制语法分析程序，用LR分析表实现。要求将错误信息输出到语法错误信息文件中，输出语法树。2. 作业要求：通过对课后习题的讨论和讲解，使学生能够熟练地掌握LR(0)分析表、SLR分析表及LALR分析表的构造。第七章 语法制导翻译和中间代码生成教学内容（小节及各节知识点）：本章共分3小节1. 语义分析及中间代码生成的设计原理和实现方法；2. 语法制导翻译的具体实现；3. 中间代码的形式；4. 可执行语句和说明语句的语法制导翻译方法；教学要求：1. 理解属性的引入；2. 理解两种属性的计算原则；3. 理解S属性的计算方法；4. 掌握L属性翻译模式的计算（递归下降分析）和继承属性计算的四种方法；教学重点：1. 属性文法；2. 语法制导翻译概论；3. 中间代码生成；教学难点：1. 简单赋值语句的翻译；2. 布尔表达式的翻译；3. 控制结构的翻译；4. 说明语句的翻译；5. 数组和结构的翻译；学时分配：本章课堂讲授10学时，上机实践4学时；实践环节：1. 实验要求：实验四：用Java或者 c语言设计一个中间代码产生器。定义模拟的简单语言的语义成分，将语义分析程序编制成一个子程序，在实验2分析出各语法单位后，分析其含义，并将可执行语句或表达式翻译为四元式输出，并将错误信息输出。2. 作业要求：通过对课后习题的讨论和讲解，使学生能够熟练地掌握控制语句的翻译。第八章 符号表教学内容（小节及各节知识点）：本章共分3小节1. 符号表的管理；2. 符号表的作用、建立、符号表栏目的组织；3. 对符号表的基本操作；教学要求：1. 掌握符号表的作用、使用、管理的基本方法；2. 熟练使用和管理符号表；教学重点：1. 符号表的作用和地位；2. 符号的主要属性及作用；教学难点：1. 符号表的组织；2. 符号表的管理；学时分配：本章课堂讲授4学时；实践环节：作业要求：通过对课后习题的讨论和讲解，使学生了解建立程序的过程表和符号表的过程。三、各教学环节学时分配 章节主要内容各教学环节学时分配作业题量讲课实验讨论习题其他小计1引论4412文法和语言8833词法分析1221444自顶向下语法分析方法62835自底向上优先分析4426LR分析62837语法制导翻译和中间代码生成1041438符号表441合计54106420四、本课程与其它课程的联系和分工 该课程的先修课程为形式语言、汇编语言、数据结构、计算机组成原理、操作系统、C语言程序设计等。这四门课程中的形式语言、汇编语言及C语言的语法、数据结构的内容、操作系统的并行串行分析方法是本课程的基础。本课程的后续课程是：自动机等。本课程主要是介绍程序设计语言编译构造的基本原理和基本实现方法，对汇编语言、C语言的语法、数据结构的各种算法、操作系统的并行分析方面的要求较高，如词法分析程序的设计、自顶向下语法分析、语法制导翻译等，与后续相关课程联系紧密，自动机等。五、本课程的考核方式 本课程考核采取实践成绩结合期末考试成绩的方式进行，具体分值组成为：总成绩 = 实践成绩（30%）+ 期末考试成绩（70%）。六、建议教材与教学参考书 1. 张素琴，吕映芝等.编译原理（第2版）.北京：清华大学出版社，20072. 秦振松.编译原理及编译程序构造.南京：东南大学出版社，19973. 陈意云，马万里.编译原理与技术.合肥：中国科学技术大学出版社，1991 4. 何炎祥.编译原理.北京：高等教育出版社，2004 七、课程简介 本课程是计算机科学与技术专业学科基础课程选修课。本课程重点研究形式语言、有限自动机、自顶向下和自底向上的语法分析、LR分析方法、属性文法和语法制导翻译、符号表的组织与管理等。通过本课程的学习，使学生了解编译程序工作的基本过程及其各阶段的基本任务、编译程序的生成过程和构造工具，掌握词法分析器设计的原理、语法分析的分析方法和语法制导翻译的基本原理，能设计并实现一个简单的编译器。为后续课程的学习和今后从事专业技术打下坚实的基础。执笔人：徐艳群 审核人： 孙晓莹 教学主任（院长）：杜跃鹏 院学术委员会： 院长： 编译原理上机部分教学大纲一、课程的基本信息课程编号6560101课程名称编译原理课程类别学科基础选修课适用专业计算机科学与技术开课学期3总学时64（其中理论54学时，上机10学时）总学分3 上机项目数4先修课程C语言程序设计、形式语言、数据结构等并修课程编译原理教程课程简介计算机科学与技术专业学科基础课程选修课，本课程介绍了编译的过程及编译程序的开发技术。建议教材张素琴，吕映芝等.编译原理（第2版）.北京：清华大学出版社，2007 .参考书张素琴，吕映芝等.编译原理（第2版）.北京：清华大学出版社，2007 秦振松.编译原理及编译程序构造.南京：东南大学出版社，1997陈意云，马万里.编译原理与技术.合肥：中国科学技术大学出版社，1991何炎祥.编译原理.北京：高等教育出版社，2004 二、上机操作的目的与基本要求编译原理主要研究如何对高级语言程序进行编译的基本理论和方法。通过本课程的上机操作，使学生巩固所学基本理论，掌握最基本的编译技术，提高综合运用所学知识，提高计算机编程的能力。进一步加强学生独立分析问题、解决问题的能力、综合设计及创新能力的培养，同时注意培养学生实事求是、严肃认真的科学作风和良好的实验习惯，为今后的工作打下良好的基础在上机过程中，要求学生能严格按照教材中上机实践环节的内容进行操作。学生应做到课前预习实验内容，上机过程中能顺利完成程序的调试，独立完成上机习题，使学生养成良好的编程习惯。课后认真书写上机报告，内容分项清晰，字迹工整。三、上机操作项目内容、能力标准和学时分配序号项目名称上机类型主要内容应达到的基本要求或能力标准学时分配1 用Java或者 c 语言设计一个词法分析器综合训练定义模拟的简单语言的词法构成，编制词法分析程序。 独立操作，写出合格的实验报告22用Java或者 c语言设计一个语法（LL（1）分析器综合训练将实验一输出的Token文件作为输入文件，编制语法分析程序，可以用递归下降法实现，也可以用LL(1)分析表实现。独立操作，写出合格的实验报告23用Java或者 c语言设计一个语法（LR）分析器综合训练将实验一输出的Token文件作为输入文件，编制语法分析程序，可以用递归下降法实现，也可以用LR分析表实现。独立操作，写出合格的实验报告24用Java或者 c语言设计一个中间代码产生器综合训练在实验2分析出各语法单位后，分析其含义，并将可执行语句或表达式翻译为四元式输出。 独立操作，写出合格的实验报告4四、作业（报告）要求认真填写上机报告，书写整洁、条理清晰。内容包括：明确实验的目的及要求；说明上机过程中遇到的问题及调试步骤；记录程序的运行结果；写出实验结论；附带正确的程序代码。每个实验项目对应一次实验报告。五、考核方式上机考核主要由上机实践时教师检查的记录为主，再结合学生上机时的表现、独立解决问题的能力、上机报告的书写，给出学生的综合成绩。具体分值组成为：上机实践成绩 = 上机表现成绩（50%）+ 实验报告成绩（50%）。六、成绩评定上机表现成绩基于上机实验出勤情况及上机过程的表现，由任课教师酌情给予。实验报告成绩基于每个项目对应的实验报告完成情况，由任课教师酌情给予。七、必要的说明编译原理上机实验是此课程教学的重要组成部分，通过上机实验，可以将一些理论知识、概念、语法规则应用于实践中。通过程序的调试，加深对这些知识的理解和记忆，锻炼编写程序、调试程序的动手能力。在实验过程中，学生应能熟练使用开发环境，能阅读程序、分析程序、编写解决某个问题的正确程序。执笔人：徐艳群 审核人：孙晓莹编写时间：2008年6月编译原理课程考核大纲课程编号：6560101学 时：64学 分：3考核年级：三年级考核专业：计算机科学与技术一、考核目的通过考核了解学生是否掌握教学大纲所要求的内容，力求做到既能全面考核学生对本课程基础知识、基本技能的掌握情况，又能考察学生应用基础知识分析、解决实际问题的程序设计能力。二、考核方式、记分制和考核时间本课程考核采取考试方式进行，成绩评定采用百分制记分，考核于开课学期期末进行。三、考核基本要求及分值第1章 引论本章授课4学时，考核所占分值为48分，考核基本要求如下：1. 了解编译程序的概念；2. 了解编译的过程；3. 了解编译程序与解释程序的区别；第2章 文法和语言本章授课8学时，考核所占分值为814分，考核基本要求如下：1. 了解文法、语言的基本概念；2. 了解字母表，符号串，符号串的头尾，符号串的连接和符号串的方幂等概念；3. 掌握语言的定义方法、符号串的推导；4. 了解文法的类型；5. 了解语法分析树的构造、文法的二义性判断方法；6. 了解句型的分析方法；第3章 词法分析本章授课14学时，考核所占分值为2024分，考核基本要求如下：1. 了解词法分析器的功能和输出形式；2. 掌握正规文法正规式，两者之间的转换；3. 掌握状态转换图，DFA ，NFA，把NFA变为DFA， DFA的化简；4. 掌握正规文法和有穷自动机间的转换；第4章 自顶向下语法分析方法本章授课8学时，考核所占分值为814分，考核基本要求如下：1. 了解确定的自顶向下分析思想，掌握First集与Follow集的构造算法；2. 掌握LL（1）文法的判别方法；3. 掌握某些非LL（1）文法到LL（1）文法的等价变换方法；4. 了解不确定的自顶向下分析思想；5. 了解确定的自顶向下分析方法；第5章 自底向上优先分析本章授课4学时，考核所占分值为48分，考核基本要求如下：1. 了解自底向上优先分析法；2. 了解优先关系，简单优先文法，掌握简单优先分析法；3. 了解算符优先分析法：直观算符优先分析法，算符优先文法