教案-编译原理

《编译原理》教案课程名称：《编译原理》课程性质：专业课（必修）学时：48（理论教学）教材：（1）编译原理.李劲华等编，复旦大学出版社，2007年（2）编译原理（第2版）电子工业出版社，胡伦骏，骆婷编，2007年1.课程班级：软件工程11级1班,2班,3班教室：西教1—305授课时间：1-12周，星期二8,9节、星期四1,2节2.课程班级：计算机科学与技术11级1班,2班,3班,4班教室：西教1—304授课时间：1-12周，星期二3，4节、星期五3,4节授课教师：张永考核方式：闭卷总评成绩=平时成绩(20%)+期末考试成绩(80%)参考书1.Compilers:Principles,TechniquesandTools(2ndEdition).AlfredV.Aho,MonicaS.Lam,RaviSethi,JeffreyD.Ullman,AddisonWesley;20062.程序设计语言编译原理（第三版），陈火旺、刘春林等，2000年，国防工业出版社，2002年获国家级高等学校优秀教材一等奖。是国家“九五”重点建设教材。3.编译原理与技术，李文生，清华大学出版社，2008.7《编译原理》教案第1次课授课内容编译概述教学目的和要求让学生了解编译原理课程的内容、特点，编译过程。教学重点和难点重点：编译程序的地位、编译程序的工作的五个阶段。难点：编译程序，解释程序教学方法和手段教学方法：讲授+案例教学，师生互动教学手段：投影仪+板书教学进程本课程介绍程序设计语言编译程序构造的基本原理和基本实现技术.编译理论与方法计算机科学与技术中理论和实践相结合的最好典范什么是编译程序1.翻译程序把某一种语言程序(称为源语言程序)等价地转换成另一种语言程序(称为目标语言程序)的程序2.编译程序(compiler)把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序3.解释程序把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身编译程序vs.解释程序编译过程编译程序的工作一般分为五个阶段:词法分析语法分析中间代码产生优化目标代码产生编译程序结构编译程序与程序设计环境程序设计环境1.编辑程序2.编译程序3.连接程序4.调试工具集成化的程序设计环境一.编译程序生成二.关于学习编译原理意义:《编译原理》教案1.学习编译程序构造原理，技术2.更好地理解高级语言3.编译的原理和方法有助于构造一些实用的工具课程特点:1.理解性2.技术性作业：1.检索编译原理的发展简史。2.查找编译型程序设计语言和解释型程序设计语言？P72，3课后小结《编译原理》教案第2次课授课内容语言及其语法描述（1）教学目的和要求让学生理解高级语言的特点，了解高级语言涉及到的语法、语义概念级内容。教学重点和难点重点：高级语言的特点。难点：计算机低级语言和高级语言的关系，语法和语义概念及规则。教学方法和手段教学方法：讲授+案例教学，师生互动教学手段：投影仪+板书，教学进程介绍常用的高级语言FORTRAN数值计算COBOL事务处理PASCAL结构程序设计ADA大型程序、嵌入式实时系统PROLOG逻辑程序设计ALGOL算法语言C/C++系统程序设计JavaInternet程序设计与机器语言或汇编语言比较，高级语言的优点：较接近于数学语言和工程语言，比较直观、自然和易于理解;便于验证其正确性，易于改错;编写效率高;易于移植.1程序语言的定义程序语言由两方面定义：语法、语义、语用语法程序本质上是一定字符集上的字符串。语法：一组规则，用它可以形成和产生一个合式(well-formed)的程序。词法规则：单词符号的形成规则。单词符号是语言中具有独立意义的最基本结构。一般包括：常数、《编译原理》教案标识符、基本字、算符、界符等。描述工具：有限自动机语法规则：语法单位的形成规则。语法单位通常包括：表达式、语句、分程序、过程、函数、程序等;描述工具：上下文无关文法语法规则和词法规则定义了程序的的形式结构。定义语法单位的意义属于语义问题。语义语义：一组规则，用它可以定义一个程序的意义。描述方法：自然语言描述：隐藏错误、二义性和不完整性形式描述：操作语义(PL/1)、指称语义(ADA)代数语义(PASCAL)三．程序语言的基本功能和层次结构程序语言的基本功能：描述数据和对数据的运算。所谓程序，本质上说是描述一定数据的处理过程。程序语言每个组成成分的逻辑和实现意义抽象的逻辑的意义数学意义计算机实现的意义具体实现2高级语言的一般特性高级语言的分类强制式语言(ImperativeLanguge)也称过程式语言：命令驱动，面向语句FORTRAN、C、Pascal，Ada应用式语言（ApplicativeLanguage）：注重程序所表示的功能，而不是一个语句接一个语句地执行LISP、ML2.1高级语言的分类基于规则的语言（Rule-basedLanguage）：检查一定的条件，当它满足值，则执行适当的动作《编译原理》教案Prolog面向对象语言（Object-OrientedLanguage）：封装性、继承性和多态性Smalltalk，C++，Java2.2程序结构一个程序由一个主程序段和若干辅程序段组成。辅程序段可以是子程序、函数段或数据块。每个程序段有一系列的说明语句和执行语句组成。各段可以独立编译。模块结构，没有嵌套和递归各程序段中的名字相互独立，同一个标识符在不同的程序段中代表不同的名字。作用域：一个名字能被使用的区域范围称作这个名字的作用域。允许同一个标识符在不同的过程中代表不同的名字。名字作用域规则--最近嵌套原则2.3数据类型与操作一个数据类型通常包括以下三种要素：用于区别这种类型数据对象的属性这种类型的数据对象可以具有的值可以作用于这种类型的数据对象的操作一．初等数据类型数值类型：整型、实型、复数、双精度，运算：+，-，*，/等逻辑类型：布尔运算：∨，∧，┑字符类型：符号处理指针类型二数据结构1数组逻辑上，数组是由同一类型数据所组成的某种n维矩形结构，沿着每一维的距离，称为下标。2记录逻辑上说，记录结构由已知类型的数据组合在一起的一种结构。3字符串、表格、栈三抽象数据类型一个抽象数据类型包括：数据对象的一个集合；作用于这些数据对象的抽象运算的集合；这种类型对象的封装，即，除了使用类型中所定义的运算外，用户不能对这些对象进行操作。程序设计语言对抽象数据类型的支持2.4语句与控制结构一．表达式二．语句《编译原理》教案作业：分析所学过的高级语言所具有的特点。P301，2，3，4，5，6，7课后小结《编译原理》教案第3次课授课内容语言及其语法描述（2）教学目的和要求让学生掌握高级程序设计语言的语法内容，了解语法树及二义性问题，了解形式语言内容。教学重点和难点重点：语言的语法描述。难点：上下文无关文法，形式语言教学方法和手段教学方法：讲授+案例教学，师生互动，教学手段：投影仪+板书，教学进程3程序语言的语法描述几个概念:考虑一个有穷字母表∑字符集其中每一个元素称为一个字符∑上的字(也叫字符串)是指由∑中的字符所构成的一个有穷序列不包含任何字符的序列称为空字，记为ε用∑*表示∑上的所有字的全体,包含空字ε3.1上下文无关文法文法：描述语言的语法结构的形式规则Hegavemeabook.句子主语谓语间接宾语直接宾语主语代词谓语动词间接宾语代词直接宾语冠词名词代词代词名词冠词动词上下文无关文法的定义：一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且S：文法的开始符号，P：产生式集合(有限)，每个产生式形式为，，开始符S至少必须在某个产生式的左部出现一次。最左推导：任何一步都是对中的最左非终结符进行替换。《编译原理》教案最右推导：任何一步都是对中的最右非终结符进行替换。3.2语法树与二义性用一张图表示一个句型的推导,称为语法树。定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的3.3形式语言Chomsky于1956年建立形式语言体系，他把文法分成四种类型：0，1，2，3型。与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。作业：P308，9，10，11，12课后小结《编译原理》教案第4次课授课内容词法分析（1）教学目的和要求让学生掌握词法分析的过程，词法分析器的构成和设计，掌握状态转换图进行分析，掌握正则式和有限状态机。教学重点和难点重点：状态转换图，正则式，有限状态机难点：正则式的表达，有限状态机描述教学方法和手段教学方法：讲授+案例教学，师生互动，教学手段：投影仪+板书，教学进程词法分析词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。词法分析器(LexicalAnalyzer)又称扫描器(Scanner)：执行词法分析的程序3.1对于词法分析器的要求一、词法分析器的功能和输出形式功能:输入源程序、输出单词符号二、词法分析器作为一个独立子程序词法分析是作为一个独立的阶段，是否应当将其处理为一遍呢？作为独立阶段的优点：结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问题。不作为一遍：将其处理为一个子程序。3.2词法分析器的设计一、输入、预处理输入串放在输入缓冲区中。预处理子程序：剔除无用的空白、跳格、回车和换行等编辑性字符;区分标号区、捻接续行和给出句末符等扫描缓冲区二、单词符号的识别:超前搜索三、状态转换图1概念状态转换图是一张有限方向图。2例子助忆符：直接用编码表示不便于记忆，因此用助忆符来表示编码。3状态转换图的实现思想：每个状态结对应一小段程序。3.3正规表达式与有限自动机几个概念:考虑一个有穷字母表∑字符集《编译原理》教案其中每一个元素称为一个字符∑上的字(也叫字符串)是指由∑中的字符所构成的一个有穷序列不包含任何字符的序列称为空字，记为ε用∑*表示∑上的所有字的全体,包含空字ε3.3.1正规式和正规集正规集可以用正规表达式（简称正规式）表示。正规表达式是表示正规集一种方法。一个字集合是正规集当且仅当它能用正规式表示。3.3.2确定有限自动机(DFA)对状态图进行形式化，则可以下定义：自动机M是一个五元式M=(S,,f,S0,F),其中：1.S:有穷状态集，2.：输入字母表(有穷)，3.f:状态转换函数，为SS的单值部分映射，f(s，a)=s’表示：当现行状态为s，输入字符为a时，将状态转换到下一状态s’。我们把s’称为s的一个后继状态。4.S0S是唯一的一个初态；5FS：终态集(可空)。课后小结《编译原理》教案第5次课授课内容词法分析（2）教学目的和要求让学生掌握非有限自动机，掌握正规文法与有限自动机的等价性，了解词法分析器的自动产生—LEX。教学重点和难点重点：非确定有限自动机，正规文法与有限自动机的等价性。难点：等价性证明教学方法和手段教学方法：讲授+案例教学，师生互动，教学手段：投影仪+板书，教学进程3.3.3非确定有限自动机(NFA)定义：一个非确定有限自动机(NFA)M是一个五元式M=(S,,f,S0,F)，其中：1S:有穷状态集；2：输入字母表(有穷)；3f:状态转换函数，为S*2S的部分映射(非单值)；4S0S是非空的初态集；5FS：终态集(可空)。从状态图中看NFA和DFA的区别：1弧上的标记可以是*中的一个字，而不一定是单个字符；2同一个字可能出现在同状态射出的多条弧上。DFA是NFA的特例。定义：对于任何两个有限自动机M和M’，如果L(M)=L(M’)，则称M与M’等价。自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的。对于每个NFAM存在一个DFAM’，使得L(M)=L(M’)。亦即DFA与NFA描述能力相同。正规文法与有限自动机的等价性对于正规文法G和有限自动机M，如果L(G)＝L(M)，则称G和M是等价的。定理：1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA)M