搜索
《编译原理》课程教学大纲（课程编号711302学分-学时-上机4.0-64-16）东南大学计算机科学与工程学院一、课程的性质与目的本课程是软件工程专业必修的专业核心课。本课程的教学目的，是使学生在学习程序设计基础及语言和数据结构的基础上，进一步理解程序及程序设计语言的本质，掌握程序词法分析和句法分析的基本原理和方法。学会构造一个编译程序，用以将一种语言所编写的程序（如，用C语言编写的程序）等价变换为另一种语言所编写的程序（如，用汇编语言编写的程序），并能对变换过程中所生成的中间代码程序及变换所得的程序进行优化，以培养良好的程序设计优化思维，提高学生的编程能力，为学习有关专业课程和进行大型软件实践打下必要的基础。二、课程内容的教学要求1.编译原理及编译程序构造引论（1）开设编译原理课程的主要作用：让学生理解开设编译原理课程的意义和作用，编译原理课程在计算机专业课程体系中的地位，学习编译原理课程应采用的方法，编译原理课程知识体系结构，让学生初步认识学习编译原理课程的重要性和潜在的使用价值。（2）编译程序及其构造过程概述：介绍编译程序的基本含义、作用和结构，简述编译程序构造的基本过程，以让学生形成编译程序构造的总体印象。2.（程序设计）语言和语法描述（1）语言描述体系结构：了解语言的语法、语义和语用的基本含义及相互作用，掌握描述语言语法的基本方法和过程，使学生清楚语言语法描述应包括由字符构造单词的词法描述，及由单词构造句子的句法描述。（2）语言和文法的基本概念：掌握语言与文法的相关基本概念，如，串、句子、句型、文法、产生式、推导与归约等，语言文法对语言语法描述的作用，文法的形式化描述方法和过程，Chomsky形式语言文法体系及其在语言语法描述中的应用、特别是正规文法及上下文无关文法在语言语法描述中的应用。（3）从语言构造文法：了解常见语言句子构造模式，掌握从典型语言句子模式构造对应无产生式文法的方法，使学生能够理解由语言构造文法的重要性。（4）语法树、分析树与二义文法：掌握语法树、分析树及二义文法的基本概念，如，语法树、分析树、短语、句柄、二义文法，语法树在语言语法分析过程中的作用，语法树构造方法和过程，二义文法对语言文法的简化描述的作用。3.词法分析（1）词法分析程序的作用和基本构造过程：让学生掌握词法分析程序的作用和基本构造过程，了解词法分析程序构造的关键问题，如，词法描述方法、由词法描述构造相应词法分析程序的思想方法。（2）正规表达式、正规语言与正规文法：掌握正规表达式对单词模式表达的作用，由基本字符构造正规表达式的方法和过程，识别一个正规表达式的方法，以及正规语言的基本概念，理解正规表达式、正规语言、正规文法三者之间的等价关系和转换方法。（3）有限自动机：让学生了解有限自动机对正规表达式识别(也就是单词识别)的作用，掌握有限自动机的基本概念，熟悉由正规表达式构造非确定有限自动机的方法与过程，掌握将非确定有限自动机确定化的理由、方法与过程，熟悉确定有限自动机最小化的理由、方法和过程，了解正规文法(正规表达式、正规语言)与有限自动机之间的相互转换方法、以及由确定有限自动机构造相应词法分析程序的方法和过程。（4）词法分析程序生成工具Lex：了解Lex的基本思想和使用方法。4.语法(句法)分析（1）语法分析基本过程和方法概述：进一步理解上下文无关文法与语言语法描述的关联，了解利用下推自动机进行语法分析的基本过程，熟悉典型语法分析方法的基本思想，深刻理解“推导—匹配”、“移进—归约”的语法分析的思想。（2）自顶向下语法分析：理解自顶向下语法分析方法的基本思想和基本过程，了解基于递归下降分析法构造语法分析程序的基本思想和基本过程，掌握预测分析法LL(1)的基本思想和基本技巧、特别是左递归消除、首符集First和随符集Follow构造的技巧，能够由上下文无关文法构造LL(1)分析表，了解基于LL(1)分析表进行具体句子的分析过程。（3）自底向上语法分析：理解自底向上语法分析方法的基本思想和基本过程，重点掌握LR分析法的基本思想和基本过程，能够由上下文无关文法构造简单的LR分析表(SLR(1)分析表)和规范的LR分析表(LR(1)分析表)，了解由LR(1)构造LALR(1)分析表的基本思想和基本过程。（4）二义文法的语法分析：掌握语法分析过程解决文法二义性的基本思想，能够通过二义文法的附加条件构造相应的SLR(1)或LR(1)分析表。（5）语法分析程序生成工具YACC：了解YACC的基本思想和应用过程。5.语义分析（1）属性文法：了解引入符号属性对语言语义描述的作用，理解将上下文无关文法转换为属性文法的意义、过程和关键，掌握属性文法中语义规则的使用方法，理解边进行语法分析、边进行语义分析的语义属性值计算的基本思想。（2）属性文法中的综合属性值计算方法：能够由只具有综合属性的属性文法构造一个句子的加以属性标注的分析树。（3）类型检查：了解类型作为一种特殊的属性时的属性计算过程和方法，即，类型检查的基本思想和方法。6.中间代码生成（1）常见中间代码形式：了解常见中间代码形式，掌握三地址码和四元式的基本思想。（2）典型语句生成三地址码的方法：掌握表达式、基本赋值语句、含有数组元素的语句、If语句、While语句翻译成三地址码的方法，能够将一段含有上述语句的程序翻译成三地址码语句序列。（3）典型语句生成四元式的方法：掌握表达式、基本赋值语句、含有数组元素的语句、If语句、While语句翻译成四元式的方法，能够将一段含有上述语句的程序翻译成四元式序列，熟悉翻译过程中拉链回填的基本技巧。7.运行时环境（1）程序执行过程与激活树：了解程序在计算机系统中执行过程，掌握激活树概念。（2）程序运行时数据存储空间分配策略：了解程序运行时数据存储空间分配策略，重点理解栈式存储分配策略。（3）栈式存储分配策略：掌握活动记录的基本概念，理解C语言程序运行过程中基于活动记录的数据存储分配策略，能够构造一个C语言程序对应的数据存储栈图。8.程序优化（1）程序分块与程序流图：了解程序优化的一般方法和过程，掌握程序基本块的概念，能够将一段程序划分为基本块、并构造以基本块为结点的程序流图。（2）块内优化：能够构造表示一个基本块所涉及数据量及其关联的有向无环图，掌握基于有向无环图的块内优化方法，能够对一个基本块进行块内优化并写出优化后的代码序列。（3）循环优化：掌握必经结点集和回边的基本概念，能够找出程序流图中的循环，了解循环优化的基本方法。（4）基于数据流分析的优化：了解数据流分析的作用，理解变量引用定值链、定值到达数据流方程、活跃变量数据流方程的含义和作用。三、上机实习要求了解程序设计语言的词法和语法(句法)的表示形式，理解词法和语法分析程序的构造方法和过程，了解简单的块内优化方法。四、能力培养的要求1.分析能力的培养：主要是对程序结构、编译程序构造方法和过程、程序优化方法进行分析的能力的培养，同时也要注意培养针对具体程序设计语言构造编译程序的能力的培养。2.算法分析和实现能力的培养：要求学生通过本课程的学习，具备对各种相关算法进行实现的能力。3.外文文献阅读能力的培养：该课程采用英文教材、英文课件和英文试卷，要求学生通过本课程的学习，能够具备直接阅读专业外文文献的能力。4.自学能力的培养：通过本课程的教学，要培养和提高学生对所学知识进行整理、概括、消化吸收的能力，以及围绕课堂教学内容，阅读参考书籍和资料，自我扩充知识领域的能力。5.表达能力的培养：主要是通过作业，清晰、整洁地表达自己解决问题的思路和步骤的能力。6.创新能力的培养：培养学生独立思考、深入钻研问题的习惯，和对问题提出多种解决方案、选择不同方法，以及对方法进行简化和举一反三的能力。五、建议学时分配课程内容讲课习题课或课堂讨论实验上机编译原理及编译程序构造引论3开设编译原理课程的主要作用1编译程序及其构造过程概述2程序设计语言和语法描述92语言描述体系结构2语言和文法的基本概念2从语言构造文法32语法树、分析树与二义文法2词法分析1024词法分析程序的作用和基本构造过程1正规表达式、正规语言与正规文法2有限自动机724词法分析程序生成工具Lex1语法分析15412语法分析基本过程和方法概述1自顶向下语法分析424自底向上语法分析728二义文法的语法分析2语法分析程序生成工具YACC1语义分析52属性文法2属性文法中的综合属性值计算方法22类型检查1中间代码生成62常见中间代码形式1典型语句生成三地址码的方法1典型语句生成四元式的方法42运行时环境52程序执行过程与激活树1程序运行时数据存储空间分配策略1栈式存储分配策略32程序优化92程序分块与程序流图2块内优化32循环优化2基于数据流分析的优化2复习2六、考核方式总评成绩＝平时成绩（包括作业和考勤）＋上机实验＋期末考试成绩平时成绩占10％上机试验占20%期末考试成绩占70％七、教材及参考书1、A.VAho,RaviSethi,J.DUllman.Compilers:Principles,Techniques,andTools(SecondEdition).人民邮电出版社，2008(影印版)2、秦振松.编译原理及编译程序构造.东南大学出版社,19973、陈火旺.程序设计语言编译原理.国防工业出版社,2000