编译程序概述.ppt

编译原理 信息工程系王养廷 计算机学院 教学要求 1 上课时做笔记2 每班选一位课代表 负责收作业 联系 准备记分册 标上班长 学委电话 3 有问题及时向老师反馈4 课堂纪律 上课不允许说话 上机不允许玩游戏 手机打成震动 辅导答疑 辅导答疑 时间 每周周三11 12节 课前后地点 博观楼209可以另约时间答疑联系方式 Telmail wangyting QQ 1458920766 个人建议 培养正思维思维模式 行为模式 最终结果目标为了个人进步培养良好学习习惯多讨论怎样做好 不讨论为什么没做好树立目标目标 价值专业学习目标 主要内容 引入编译程序与解释程序编译程序的功能分解与组织结构编译程序的复杂性编译程序的设计与实现编译程序的测试与维护几个经典的编译程序 1引入 计算机科学与技术 编译原理 课程 编译原理 主要内容选用教材为什么要学习编译原理需要注意的问题 1 1计算机科学与技术 含义科学 构成计算基础的基本概念和模型 又称为 形式理论 技术 设计计算系统的工程和技术形式理论有限自动机 正则表达式 正则集合上下文无关文法下推机图灵机不可判定性与编译原理的关系形式理论是编译原理的理论基础在后面我们要讲到前三个部分 1 2 编译原理 课程 课程性质学科基础课先修课程程序设计语言 Pascal C等 程序设计 数据结构离散数学操作系统 1 3 编译原理 主要内容 按照编译程序的主要组成部分进行介绍词法分析语法分析语义分析代码生成和优化符号表和错误处理一个编译程序实例PL 0编译程序分析 1 4选用教材 教材金成植 编译程序设计原理 编译程序构造原理实现技术特点采用原理与实例相结合的方法进行介绍兼顾原理和实现技术 1 5为什么要学习编译原理 编译程序是一个大型综合 复杂的程序 通过该课程的学习了解一个大型软件的设计与实现有助于理解现有的编译程序的实现方法加深对程序设计语言的理解提高调试程序能力为进一步深造打下基础 1 6需要注意的问题 对课程的难度应该有足够的思想准备注意平时的听课和积累原理侧重理解具体的算法和程序需要实际动手分析 2编译程序与解释程序 语言与程序设计语言程序设计语言主要内容程序设计语言分类编译原理基本概念编译程序与解释程序的异同使用解释程序的情况 2 1语言与程序设计语言 语言人们用来交流的工具程序设计语言人与计算机交流的工具二者的区别对象二义性 2 2程序设计语言主要内容 数据定义字符集 常量 类型 变量 表达式语句顺序 分支和循环函数过程 函数 子程序复杂数据类型数组 记录 指针等等 2 3程序设计语言的分类 按照层次高级语言低级语言按照结构过程式语言 C Pascal 函数式语言 LISP ML 逻辑式语言 Prolog 对象式语言 SmallTalk Java C 2 4编译程序基本概念 源程序 用程序设计语言编制的程序目标程序 与源程序功能等价的目标代码编译程序 把源程序转换成目标程序的程序解释程序 执行源程序得到执行结果的程序汇编程序 把汇编源程序转换成目标程序的程序 2 5编译程序与解释程序区别 源程序 数据 源程序 解释程序 计算结果 编译程序 目标程序 2 6使用解释程序的情况 不追求执行速度有些程序允许执行式改变自身人机对话的交互语言由解释程序到编译程序的自动生成系统 3编译程序的功能分解与组织结构 功能结构图遍的概念源程序的处理过程 3 1功能结构图 3 1功能结构图 续 编译程序的输入 源程序编译程序的输出 目标程序编译程序的功能模块词法分析 把源程序变成单词串语法分析 检察源程序是否符合语法结构语义分析 标识符的含义是否正确代码生成 生成目标代码 3 2遍的概念 遍的概念对源程序或与其等价的中间代码扫描一次按遍划分一遍多遍一遍特点避免重复工作 速度快 代码质量不高多遍特点结构算法清晰 易于掌握 能够产生好的目标代码 3 3源程序的处理过程 预处理器 编译程序 汇编程序 装配连接 扩展程序 源程序 目标汇编程序 可重定位机器代码 可执行机器码 可重定位目标文件库 3 3源程序的处理过程 续 实例以DOS下的C语言处理过程为例C是多遍编译第一遍处理包含 宏等信息以后各遍进行编译过程第一遍编译得到标准C程序经过C编译器的到目标程序经过连接得到可执行程序装入DOS执行 4编译程序复杂性 元程序处理程序的程序编译程序复杂性元级程序高级语言与低级语言差别大编译程序要求高 5编译程序的设计与实现 设计编译程序条件精通源语言精通目标语言精通编译技术编译程序的性能可靠性 速度 目标代码速度 占用空间 可移植性 可维护性 可扩展性 5编译程序的设计与实现 续 开发编译程序的途径预处理法移植法直接移植交叉编译自展法工具法例如 LEX YACC理论法 6编译程序的测试和维护 编译程序测试机械证明测试测试用例设计编译程序维护长期有效地改正发现的错误 7几个经典的编译程序 Pascal编译程序设计者 Wirth使用技术 递归下降 一遍扫描 栈式抽象机特点 产生P代码C编译程序设计者 D M Ritchie使用技术 递归下降 二遍扫描 有可选的第三遍特点 可移植性好Fortran编译程序设计者 Lowry和Medlock使用技术 综合特点 优化好 小结 内容编译程序的基本概念和相关知识编译程序的组成和复杂性几个常见的编译程序要求掌握编译程序的组成和复杂性预习标准的Pascal语言预习TurboPascal开发环境 PASCAL语言基础知识 任课教师王养廷 复习 编译程序的主要组成部分 每个部分的功能编译程序为什么复杂预习标准的Pascal语言预习TurboPascal开发环境 主要内容 Pascal概述数据语句 1Pascal概述 Pascal历史WirthPascalPascal语言最初由瑞士苏黎士理工学院的尼古拉斯 沃斯 NiklausWirth 教授在1971年设计 作为Algol语言 1960年设计 简化本用于教学目的 TurboPascal1983年Borland公司推出了世界闻名的Pascal编译器 TurboPascal 由于既简洁功能又强 TurboPascal成为当时最畅销的编译器之一 而且在PC平台上非常流行 Delphi中的Pascal1995年Borland发布了Delphi 使Pascal成为一种可视化编程语言 1Pascal概述 续 一个Pascal程序实例programcircle input output constpi 3 1416 varr l s real beginread r l 2 pi r s pi r r write r l s end 2数据 字符集标识符和保留字常量变量运算符 2 1字符集 Pascal字符集字母数字其它符号字符集的引申多语言的处理 ASCII UniCode 2 2标识符和保留字 标识符定义 以字母开头 后面跟字母 数字组成的字符串 作用 用来表示各种程序元素的名称规定 大小写不敏感有效长度8 超过8个不起作用建议 采用一个或多个英文单词组成举例score charPosition 2 2表识符和保留字 续 保留字Pascal系统已经使用的单词主要保留字例如 program begin end const var read write if then else等等详细内容参考Pascal教程作用用来标识程序的语法成分 2 2表识符和保留字 续 注释注释的内容用 括起来例子 thisisacomment 这是一个例子 2 3常量 常量一般常量程序中的数值例如 23 1 2 a 符号常量定义 在const部分定义格式 常量名 表达式举例 constpi 3 14 st t 2 4变量 变量定义 在var部分定义格式 变量名表 类型 说明 类型名可以是任意Pascal类型变量名表是多个变量 中间用逗号间隔举例varx y integer flag boolean 2 4变量 续 类型主要有四个 整型integer描述一个整数类型实型real描述一个实数类型字符型char描述一个字符类型 值是一个字符布尔型boolean描述一个逻辑类型 只有两个 true和false 2 5运算符 算术运算符关系运算符逻辑运算符运算符优先级 2 5运算符 续 算术运算符 mod div说明用于算术运算 整数 实数运算符mod div整数运算符 实数运算符举例m nmod10 x y 100 2 5运算符 续 关系运算符用于关系表达式符号 举例X 10 yX 1 2 5运算符 续 逻辑运算符运算符not and or真值表 2 5运算符 续 运算符优先级两个运算符相邻 先参加高优先级运算同级运算符自左至右有扩号先计算括号内 3语句 程序结构语句声明语句简单语句分支语句循环语句 3 1程序结构 程序结构程序首部声明部分语句部分举例 3 1程序结构 续 programpl0 input output constnorw 11 no ofreservedwords typesymset setofsymbol varch char lastcharacterread procedureerror n integer beginwriteln cc 1 n 2 err err 1end error begin mainprogram forch chr 0 tochr 255 dossym ch nul getsym end 3 2语句 语句 数据类型是Pascal编程的一个基础 另一个则是语句分类声明语句可执行语句简单语句复合语句 3 3声明语句 常量声明格式 const常量名 表达式例如 constpi 3 1416类型声明格式 type类型名 类型定义例如 Tarray array 1 10 ofinteger 变量声明格式 var变量列表 类型例如 vari length integer 3 4简单语句 赋值语句格式 标识符 表达式例子 area pi r r READ语句格式 read 变量列表 例子 read ch1 x y readln语句WRITE语句格式 write 输出表 例如 write x x result x y writeln语句 3 4简单语句 续 例子 已知三角形的两边和夹角 求面积 programarea input output constpi 3 1416 vara b s alfa real beginwriteln pleaseinputa b alfa read a b alfa s 1 2 a b sin alfa writeln areais s end 3 5分支语句 作用根据条件进行不同的处理格式If条件表达式then语句1 else语句2 语句1和语句2可以是简单语句 也可以是复合语句 3 5分支语句 续 举例ifx 0theny 1elsey 0 3 5分支语句 续 举例 求三个数中最大数programmaxNumber input output varnum1 num2 num3 max integer beginread num1 num2 num3 if num1 num2 thenmax num1elsemax num2 if num3 max thenmax num3 writeln thelargestnumber max end 3 5分支语句 续 CASE语句作用用于多个分支的判断格式case表达式of值表1 语句1 值表2 语句2 else语句n end 3 6循环语句 for语句作用完成指定次数的循环格式for循环变量 循环初值to downto循环终值do循环体 例子fori 1to10dodata i 1 3 6循环语句 续 While语句作用完成条件循环格式while条件表达式do循环体举例i 0 sum 0 whileI 100dobeginsum sum i i i 1 end 3 6循环语句 续 Repeat语句作用完成条件循环格式repeat循环体 until条件表达式说明与while语句的不同之处在于先执行一次循环再判断条件 3 6循环语句 续 例子 求n的阶乘programfactorial input output varfac real n i integer beginread n fac 1 fori 2tondofac fac i write fac end 3 6循环语句 续 例子 计算正弦函数programsinx input output consteps 1e 7 varx term sun real n integer beginread x n 1 term x sum x repeatn n 2 term term x x n 1 n sum sum termuntilabs term eps writeln resultis sum end 小结 本次课程介绍了Pascal语言的基本数据语句作业输入20个数 统计正数 负数的个数自学Pascal语言相关内容答疑时间周二晚上单独约时间 PASCAL语言程序设计 任课教师王养廷 主要内容 过程和函数数组记录指针 1过程和函数 函数与过程过程的定义与调用函数的定义与调用过程与函数的区别形参与实参数值参数与变量参数变量的作用域 1 1函数与过程 例程例程又称为子程序 它式结构化程序设计的产物例程由一系列语句组成 例程名是唯一的 通过例程名你可以多次调用它 Pascal例程Pascal中的例程有两种形式 过程和函数 过程与函数区别过程相当一个语句函数相当一个值 1 2过程的定义与调用 过程定义位置 在变量声明之后 主程序之前 格式 procedure过程名 形式参数表 常量定义 类型定义 变量定义 过程或函数定义begin过程语句体 end 1 2过程的定义与调用 续 过程调用位置 同级过程 函数或同级主程序中格式 过程名 实际参数表 要求 实参的个数和类型要与形参匹配 1 2过程的定义与调用 续 实例过程定义procedureNumString n integer vars array 1 10 ofchar varv j integer beginv abs n j 2 repeats j chr vmod10 ord 0 v vdiv10 j j 1 untilv 0 ifn 0thens 1 elses 1 end 过程调用 NumString 10 str 1 3函数的定义与调用 函数的定义位置 在变量声明之后 主程序之前 格式 function函数名 形式参数表 类型 常量定义 类型定义 变量定义 过程或函数定义begin函数语句体 end 1 3函数的定义与调用 续 函数调用位置 同级过程 函数或同级主程序中格式 函数名 实际参数表 要求 实参的个数和类型要与形参匹配 1 3函数的定义与调用 续 实例函数定义functionmax a b integer real varm integer beginm a if b a thenm b max m end 函数调用 x max x y 1 4过程与函数的区别 区别在程序中的语法成分不同函数有类型说明函数要求有返回值为什么定义两种例程pascal严格区分语句和表达式 分别设计了两种例程 1 5形参与实参 形参过程或函数中 参数表中定义的参数实参过程或函数调用中 使用的参数形参与实参的对应要求过程或函数参数在个数和类型上要对应可以使用兼容类型 1 6数值参数和变量参数 数值的传入把实参的值传给形参实例x max x y 假设 x y的值分别为10 20在执行函数调用时 第一步是把两个数值传给形参a b这样在函数中参数a b的值分别为10 20 1 6数值参数和变量参数 续 数值返回函数或过程执行完成后需要返回结果一般使用函数来返回数值对于一些特殊情况需要使用参数返回结果数值多个数值复杂数据类型数值过程返回值 1 6数值参数和变量参数 续 数值参数不需要返回结果数值的参数参数定义格式变量表 类型 举例a b integer 1 6数值参数和变量参数 续 变量参数需要返回结果数值的参数参数定义格式var变量表 类型 举例vara b integer 说明函数或过程执行完成后 需要把变参的结果返回给相应的实参在调用中实参必须是一个变量 2数组 枚举类型子界类型数组数组应用 2 1枚举类型 类型定义定义一个星期中的各天的类型typeday sun mon tues wed thu fri sta 变量定义varpayday today firstday day 2 1枚举类型 续 举例programtodaytomorrow input output typeday sun mon tues wed thu fri sat vartoday tomorrow day number integer beginread number 2 1枚举类型 续 casenumberof0 today sun 1 today mon 2 today tues 3 today wed 4 today thu 5 today fir 6 today sat end iftoday satthentomorrow sunelsetomorrow succ day end 2 2子界类型 类型定义子界类型定义了某种类型的取值范围 这种类型必须是有序类型 如整型 字符型 定义举例 TypeTen 1 10 OverHundred 100 1000 Uppercase A Z 2 2子界类型 续 类型说明定义子界类型时 你不需要指定基类的名字 而只需提供该类型的两个常数 所用基类必须是有序类型 定义结果将是另一种有序类型 赋给子界类型变量的值必须是子界定义范围内的值 应用经常用于数组的定义 2 3数组 数组用来表示一组相同类型的数据定义TypeDayTemperatures array 1 24 ofInteger 说明方括号中填入一个子界类型的值 或者用两个有序类型的常量定义一个新的子界类型 2 3数组 续 数组类型变量的定义VarDayTemp1 DayTemperatures 数组的引用DayTemp1 1 54 DayTemp1 2 52 多维数组TypeMonthTemps array 1 24 1 31 ofInteger YearTemps array 1 24 1 31 Jan