编译原理 （第二版）

编译原理 第二版 郑洪编著 第2章程序语言 2 1高级语言 2 1 1高级语言的分类1 过程式语言过程式语言以语句为核心 命令驱动 过程式语言设计的程序以语句为最小执行单位 程序由一系列的语句组成 这种语言设计的程序通常具有如下形式 语句1 语句2 语句n 2 面向对象语言面向对象语言 Object OrientedLanguage 是如今使用最广 最为重要的语言 它的主要特征是支持封装性 继承性和多态性 把复杂的特性和用于这些数据的操作装在一起 构成对象 对简单对象进行扩充 继承简单对象的特性 从而设计出复杂的对象 3 应用式语言将已知的函数作为新开发函数的参数 利用函数的嵌套与递归使得程序的功能由简单变为复杂 最终满足程序设计的要求 这种语言的结构形式是 函数n 函数2 函数1 数据 4 基于规则的语言基于规则的语言以判断 选择语句为基本执行单位 其程序的执行过程是 检查一定的条件 当它满足时选择适当的操作 最有代表性的基于规则语言是PROLOG 其程序结构形式为 条件1 动作1条件2 动作2 条件n 动作n 2 1 2数据类型及其操作 1 数值数据 数值数据包括整数 实数 复数以及这些类型的双长 或多倍长 精度数 对数值类型的数据可描述为算术运算集合 2 逻辑数据 很多语言有专门用于布尔代数的数据类型 即逻辑型数据类型 有的语言甚至还有位串型数据 对逻辑数据可实施逻辑运算 and or not等 3 字符数据 有些语言可以处理字符或字符串 字符数据类型用来承载字符或字符串 对字符数据的操作有很多 包括判断 转换以及对字符串的各种加工 4 指针类型 指针类型的数据不是用来描述客观事物的 它的作用是为运算提供数据的地址 常见的结构型数据类型有以下几种 1 数组一个数组是由同一类型数据组成的有序的集合 数组下标与数组元素的存储地址密切相关 二者呈线性关系 因此数组元素也称为下标变量 N维数组的每个元素有N个下标 由N个下标决定数组元素的存储位置 2 记录记录是由不同类型数据所组成的集合 记录结构中每个元素所占有的存储空间可能互不相同 记录的元素称为分量 例如 C语言采用下面的形式定义记录 structstudent charname 8 intstudclass floatmath 结构分量是通过名字而不是像数组元素那样通过下标访问的 结构分量的名字是所谓复合名字 例如 结构名 分量名 结构分量的使用与基本数据结构定义的变量相同 如下述3个赋值语句 student name LIMING student studclass 3student math 95 4每个分量的存储地址由记录结构的首地址与相应分量的偏移地址相加而成 记录结构的每个分量 域 所占用的存储字节数称为该域的长度 通过累加分量的长度可计算出各分量的偏移量 student name占8个字节 student studclass占2个字节 student math占4个字节 可计算三者对应的偏移量为0 8 10 若student记录结构在运行时被分配一个基址a 则其各分量的地址为 student name astudent studclass a 8student math a 10 3 字符串 表格和队列不同的语言根据不同的需要会拓展出一些实用数据类型 有越来越多的语言把字符串作为一种基本的数据类型 串的长度不加限制 这种数据类型给各种处理文字语言的程序带来很多便利 2 1 3语句与表达式1 语句每当用户创建了一个名称 就要用说明语句来说明这个名称所指对象的意义 是一种变量 一种操作 还是一个子程序 而执行性语句就是描述计算机操作的 其还可分为赋值语句 控制语句 输入 输出语句 1 说明语句说明语句的作用在于定义名字的属性 即赋予名字意义 如 intx C语言定义整型变量 2 赋值语句 赋值语句在不同的程序设计语言中可能有不同的语句形式 但实现功能基本相同 例如 X Y PASCAL赋值语句 3 控制语句 计算机程序之所以能够实现各种强大的功能 原因是有了控制语句 控制语句的核心操作就是 判断 选择 这是一切智能行为的基础 条件语句ifEthenSifEthenSelseS1循环语句while E BdoSrepeatSuntilBforI E1stepE2untilE3doS 过程调用语句callp x1 x2 xn 返回语句return E 无条件转移语句gotoL 2 表达式表达式由运算对象和算符组成 对于多数程序语言来说 表达式的形式规则如下 1 变量 包括下标变量 是表达式 2 若E1 E2为表达式 是一个二元算符 则E1 E2是表达式 表达式一般采用中缀形式 3 若E是表达式 为一元算符 则 E或E 是表达式 4 若E是表达式 则 E 是表达式 一般程序设计语言中算术算符和逻辑算符的优先顺序 乘幂 或 一元负 乘 除 加减 关系符 非 not或NOT 与 and或AND 或 or或OR 等值 或equi 2 1 4程序的结构1 FORTRAN一个FORTRAN程序由一个主程序和若干个 可以是0个 辅程序段组成 PROGRAMMAIN ENDSUBROUTINESUB1 END SUBROUTINESUBn END辅程序段可以是函数 过程或数据块 每个程序段由一系列说明语句和执行语句组成 各段可以独立编译 这对于模块设计特别合适 2 C语言一般由一个主函数和若干个 可以是0个 函数组成 C语言的程序结构如下 main typefunction1 参数表 typefunctionn 参数表 3 PASCALPASCAL语言的特点是允许子程序嵌套定义 一个PASCAL程序可以看作是由操作系统调用的一个子程序 而子程序中又可以定义别的子程序 1 一个子程序B1中说明的名字X只在B1中有效 2 如果B2是B1的一个内层子程序 且B2中对X没有新的说明 则原来的名字在B2中仍然有效 如果B2对X重新作了说明 那么B2中对X的任何引用都是指重新说明过的那个X 4 JavaJava很重要的概念是类 Class 及继承 Heritanced Java同时支持多态性 Polymorphism 和动态绑定 DynamicBinding 等特性 classCar intcalor number intdoor number intspeed push break Addoil classTrash CarextendsCar doubleamount fill trash 2 2中间语言 2 2 1逆波兰表示法逆波兰表示表达式高级语言表示表达式ab a bab c a b cabcd a b c d ab cd a b c d高级语言表达式E的逆波兰表示法可这样定义 1 若E是高级语言中的一个变量或常数 则E的逆波兰表示式仍是E 2 若高级语言中的表达式为E1opE2 其中 op是一个二元算符 E1 E2也是表达式 则逆波兰式表示为E1 E2 op 其中 E1 是E1的逆波兰式 E2 是E2的逆波兰式 3 若高级语言中的表达式为 E 则逆波兰表示式为去掉括号的E E 为E的逆波兰表示式 若把逆波兰表达式视为一个字符串 则计算逆波兰式的算法为 1 读入字串左端的一个字 2 如果读入空字 计算结束 3 如果读入一个操作数 将操作数推进栈 转 1 4 如果读入一个一元操作符 取栈顶一个操作数与一元操作符进行运算 并将运算结果推进栈 转 1 5 如果读入一个二元操作符 取栈顶两个操作数与二元操作符进行运算 并将运算结果推进栈 转 1 例2 1 有以下用高级语言所编写的表达式 3 5 4转换为逆波兰表达式为 354 计算逆波兰表达式354 的过程 2 2 2三地址代码三地址代码是由下面一般形式的语句构成的序列 x yopz其中x y z是变量名或编译时产生的临时变量名 y z还可以是常数 op代表某种操作符 这种中间语言的特点有两个 1 非常接近汇编语言形式 包括汇编语言中最基本的操作 2 每个语句中赋值号的右边只有一个操作符 使得句子意义最小且不可分 三地址代码的具体实现常以记录的形式表示 通常有3种表示方法 四元式 三元式 间接三元式 四元式的一般形式为 三地址码四元式x A A x x opA op A x x AopB op A B x 对于转移类语句 上述四元式记录的内涵要做适当的修改 例如 下面的三地址码转移类语句用四元式表示为 三地址码四元式gotoL JP L ifarelopbgotoL Jrelop a b L ifago