Microsoft Word - 第3章.doc

Transcription

1 第 3 章程序设计语言基础知识 程序设计语言是为了书写计算机程序而设计的符号语言, 用于对计算过程进行描述 组织和推导 程序设计语言的广泛使用始于 1957 年出现的 FORTRAN, 其发展和演化已经超越了运行程序的机器 3.1 程序设计语言概述 本节主要介绍程序设计语言的基本概念 基本成分和一些典型语言的特点及其适用范围 程序设计语言的基本概念 1. 低级语言和高级语言计算机硬件只能识别由 0 1 字符序列组成的机器指令, 因此机器指令是最基本的计算机语言 用机器语言编制程序效率低 可读性差, 也难以理解 修改和维护 因此, 人们设计了汇编语言, 用容易记忆的符号代替 0 1 序列, 来表示机器指令中的操作码和操作数 例如, 用 ADD 表示加法 SUB 表示减法等 虽然使用汇编语言编写程序的效率和程序的可读性有所提高, 但汇编语言是面向机器的语言, 其书写格式在很大程度上取决于特定计算机的机器指令 机器语言和汇编语言被称为低级语言 人们开发了功能更强 抽象级别更高的语言以支持程序设计, 因此就产生了面向各类应用的程序设计语言, 即高级语言, 常见的有 Java C C++ C# Python PHP 等 这类语言与人们使用的自然语言比较接近, 大大提高了程序设计的效率 2. 编译程序和解释程序目前, 尽管人们可以借助高级语言与计算机进行交互, 但是计算机仍然只能理解和执行由 0 1 序列构成的机器语言, 因此高级程序设计语言需要翻译, 担负这一任务的程序称为 语言处理程序 由于应用的不同, 程序语言的翻译也是多种多样的 它们大致可分为汇编程序 解释程序和编译程序 用某种高级语言或汇编语言编写的程序称为源程序, 源程序不能直接在计算机上执行 如果源程序是用汇编语言编写的, 则需要一个称为汇编程序的翻译程序将其翻译成目标程序后才

2 第 3 章程序设计语言基础知识 105 能执行 如果源程序是用某种高级语言编写的, 则需要对应的解释程序或编译程序对其进行翻译, 然后在机器上运行 解释程序也称为解释器, 它可以直接解释执行源程序, 或者将源程序翻译成某种中间表示形式后再加以执行 ; 而编译程序 ( 编译器 ) 则首先将源程序翻译成目标语言程序, 将目标程序与库函数链接后形成可执行程序, 然后在计算机上运行可执行程序 这两种语言处理程序的根本区别是 : 在编译方式下, 机器上运行的是与源程序等价的目标程序, 源程序和编译程序都不再参与目标程序的执行过程 ; 而在解释方式下, 解释程序和源程序 ( 或其某种等价表示 ) 要参与到程序的运行过程中, 运行程序的控制权在解释程序 解释器翻译源程序时不产生独立的目标程序, 而编译器则需将源程序翻译成独立的目标程序 3. 程序设计语言的定义一般地, 程序设计语言的定义都涉及语法 语义和语用 3 个方面 (1) 语法 语法是指由程序设计语言基本符号组成程序中的各个语法成分 ( 包括程序 ) 的一组规则, 其中由基本字符构成的符号 ( 单词 ) 书写规则称为词法规则, 由符号 ( 单词 ) 构成语法成分的规则称为语法规则 程序设计语言的语法可通过形式语言进行描述 (2) 语义 语义是程序设计语言中按语法规则构成的各个语法成分的含义, 可分为静态语义和动态语义 静态语义是指编译时可以确定的语法成分的含义, 而运行时刻才能确定的含义是动态语义 一个程序的执行效果说明了该程序的语义, 它取决于构成程序的各个组成部分的语义 (3) 语用 语用表示了构成语言的各个记号和使用者的关系, 涉及符号的来源 使用和影响 语言的实现还涉及语境问题 语境是指理解和实现程序设计语言的环境, 这种环境包括编译环境和运行环境 程序设计语言的分类和特点 1. 程序设计语言发展概述程序设计语言的发展是一个不断演化的过程, 其根本的推动力就是对抽象机制的更高要求, 以及对程序设计活动更好地支持 具体地说, 就是把机器能够理解的语言提升到也能够很好地模仿人类思考问题的形式 FORTRAN( FORmula TRANslator 的缩写 ) 是第一个高级程序设计语言, 在数值计算领域积累了大量高效而可靠的程序代码 FORTRAN 语言的最大特性是接近数学公式的自然描述, 具有很高的执行效率, 目前广泛地应用于并行计算和高性能计算领域

3 106 程序员教程 ( 第 5 版 ) ALGOL(ALGOrithmic Language) 诞生于晶体管计算机流行的年代,ALGOL60 是程序设计语言发展史上的一个里程碑, 主导了 20 世纪 60 年代程序语言的发展, 并为后来软件自动化及软件可靠性的发展奠定了基础 ALGOL60 有严格的公式化说明, 采用巴科斯范式 BNF 来描述语言的语法 ALGOL60 引进了许多新的概念, 如局部性概念 动态 递归等 PASCAL 语言是一种结构化程序设计语言, 由瑞士苏黎世联邦工业大学的沃斯 (N.Wirth) 教授设计, 于 1971 年正式发表 PASCAL 是从 ALGOL 60 衍生的, 但功能更强且容易使用, 该语言在高校计算机软件教学中曾经处于主导地位 C 语言是 20 世纪 70 年代发展起来的一种通用程序设计语言, 其主要特色是兼顾了高级语言和汇编语言的特点, 简洁 丰富 可移植 UNIX 操作系统及其上的许多软件都是用 C 编写的 C 提供了高效的执行语句并且允许程序员直接访问操作系统和底层硬件, 适用于系统级编程和实时处理应用 C++ 是在 C 语言的基础上于 20 世纪 80 年代发展起来的, 与 C 兼容 在 C++ 中, 最主要的是增加了类机制, 使其成为一种面向对象的程序设计语言 C++ 具有更强的表达能力, 提供了表达用户自定义数据结构的现代高级语言特性, 其开发平台还提供了实现基本数据结构和算法的标准库, 使得程序员能够改进程序的质量, 并易于代码的复用, 从而可以进行大规模的程序开发和系统组织 Java 产生于 20 世纪 90 年代, 其初始用途是开发网络浏览器的小应用程序, 但是作为一种通用的程序设计语言,Java 得到非常广泛的应用 Java 保留了 C++ 的基本语法 类和继承等概念, 删掉了 C++ 中一些不好的特征, 因此与 C++ 相比,Java 更简单, 其语法和语义更合理 各种程序设计语言都在不断地发展之中 目前, 程序设计语言及编程环境向着面向对象及可视化编程环境方向发展, 出现了许多新的语言及开发工具 C#(C Sharp) 是由 Microsoft 公司开发的一种面向对象的 运行于.NET Framework 的高级程序设计语言, 相对于 C++, 这个语言在许多方面进行了限制和增强 Objective-C 继承了 C 语言的特性, 是扩充 C 的面向对象编程语言, 其与流行的编程语言风格差异较大 由于 GCC(GNU Compiler Collection,GNU 编译器套装 ) 含 Objective-C 的编译器, 因此可以在运行 GCC 的系统中编译 该语言主要由 Apple 公司维护, 是 MAC 系统下的主要开发语言 与 C# 类似,Objective-C 仅支持单一父类继承, 不支持多重继承 Ruby 是松本行弘 (Yukihiro Matsumoto, 常称为 Matz) 大约在 1993 年设计的一种解释性 面向对象 动态类型的脚本语言 在 Ruby 语言中, 任何东西都是对象, 包括其他语言中的基本数据类型, 比如整数 ; 每个过程或函数都是方法 ; 变量没有类型 ; 任何东西都有值 ( 不管是数学或者逻辑表达式还是一个语句, 都会有值 ), 等等 Ruby 体现了表达的一致性和简单性, 它不仅是一门编程语言, 更是表达想法的一种简练方式

4 第 3 章程序设计语言基础知识 107 PHP(Hypertext Preprocessor) 是一种在服务器端执行的 嵌入 HTML 文档的脚本语言, 其语言风格类似于 C 语言, 由网站编程人员广泛运用 PHP 可以快速地执行动态网页, 其语法混合了 C Java Perl 以及 PHP 自创的语法 由于在服务器端执行,PHP 能充分利用服务器的性能 另外,PHP 支持几乎所有流行的数据库以及操作系统 Python 是一种面向对象的解释型程序设计语言, 可以用于编写独立程序 快速脚本和复杂应用的原型 Python 也是一种脚本语言, 它支持对操作系统的底层访问, 也可以将 Python 源程序翻译成字节码在 Python 虚拟机上运行 虽然 Python 的内核很小, 但它提供了丰富的基本构建块, 还可以用 C C++ 和 Java 等进行扩展, 因此可以用它开发任何类型的程序 JavaScript 是一种脚本语言, 被广泛用于 Web 应用开发, 常用来为网页添加动态功能, 为用户提供更流畅美观的浏览效果 通常, 将 JavaScript 脚本嵌入在 HTML 中来实现自身的功能 Delphi 是一种可视化开发工具, 在 Windows 环境下使用, 其在 Linux 上的对应产品是 Kylix, 其主要特性为基于窗体和面向对象的方法 高速的编译器 强大的数据库支持 与 Windows 编程紧密结合以及成熟的组件技术 它采用面向对象的编程语言 Object Pascal 和基于构件的开发结构框架 Visual Basic.NET 是基于微软.NET Framework 的面向对象的编程语言 用.NET 语言 ( 包括 VB.NET) 开发的程序源代码不是直接编译成能够直接在操作系统上执行的二进制本地代码, 而是被编译成为中间代码 MSIL(Microsoft Intermediate Language), 然后通过.NET Framework 的通用语言运行时 (CLR) 来执行 程序执行时,.Net Framework 将中间代码翻译成为二进制机器码后, 使它得以运行 因此, 如果计算机上没有安装.Net Framework, 这些程序将不能够被执行 标记语言 (Markup Language) 用一系列约定好的标记来对电子文档进行标记, 以实现对电子文档的语义 结构及格式的定义 这些标记必须容易与内容区分, 并且易于识别 SGML XML HTML MathML WML SVG CML 和 XHTML 等都是标记语言 2. 程序设计范型程序设计语言的分类没有统一的标准, 从不同的角度可以进行不同的划分 从最初的机器语言 汇编语言 结构化程序设计语言发展到目前流行的面向对象语言, 程序设计语言的抽象程度越来越高 根据程序设计的方法将程序设计语言大致分为命令式程序设计语言 面向对象的程序设计语言 函数式程序设计语言和逻辑型程序设计语言等范型 1) 命令式程序设计语言命令式语言是基于动作的语言, 在这种语言中, 计算被看成动作的序列 程序就是用语言提供的操作命令书写的一个操作序列 用这类语言编写程序, 就是描述解题过程中每一步的过

5 108 程序员教程 ( 第 5 版 ) 程, 程序的运行过程就是问题的求解过程, 因此也称为过程式语言 FORTRAN ALGOL COBOL C 和 Pascal 等都是命令式程序设计语言 结构化程序设计语言本质上也属于命令式程序设计语言, 其编程的特点如下 (1) 用自顶向下逐步精化的方法编程 (2) 按模块组装的方法编程 (3) 程序只包含顺序 判定 ( 分支 ) 及循环结构, 而且每种结构只允许单入口和单出口 结构化程序的结构简单清晰 模块化强, 描述方式接近人们习惯的推理式思维方式, 因此可读性强, 在软件重用性 软件维护等方面都有所进步, 在大型软件开发中曾发挥过重要的作用 目前仍有许多应用程序的开发采用结构化程序设计技术和方法 C Pascal 等都是典型的结构化程序设计语言 2) 面向对象的程序设计语言面向对象的程序设计语言始于从模拟领域发展起来的 Simula, 在该语言中首次提出了对象和类的概念 C++ Java 和 Smalltalk 都是面向对象程序设计语言, 封装 继承和多态是面向对象编程的基本特征 3) 函数式程序设计语言函数式语言是一类以 λ- 演算为基础的语言, 其基本概念来自于 LISP, 这是一个在 1958 年为了人工智能应用而设计的语言 函数是一种对应规则 ( 映射 ), 它使定义域中每个元素和值域中唯一的元素相对应 例如 : 函数定义 1:Square[x]:=x*x 函数定义 2:Plustwo[x]:=Plusone[Plusone[x]] 函数定义 3:fact[n]:=if n=0 then 1 else n*fact[n-1] 在函数定义 2 中, 使用了函数复合, 即将一个函数调用嵌套在另一个函数定义中 在函数定义 3 中, 函数被递归定义 由此可见, 函数可以看成一种程序, 其输入就是定义中左边括号中的量, 它也可将输入组合起来产生一个规则, 组合过程中可以使用其他函数或该函数本身 这种用函数和表达式建立程序的方法就是函数式程序设计 函数型程序设计语言的优点之一就是对表达式中出现的任何函数都可以用其他函数来代替, 只要这些函数调用产生相同的值 函数式语言的代表 LISP 在许多方面与其他语言不同, 其中最为显著的是, 该语言中的程序和数据的形式是等价的, 这样数据结构就可以作为程序执行, 同样程序也可以作为数据修改 在 LISP 中, 大量地使用递归 4) 逻辑型程序设计语言逻辑型语言是一类以形式逻辑为基础的语言, 其代表是建立在关系理论和一阶谓词理论基础上的 PROLOG PROLOG 代表 Programming in Logic PROLOG 程序是一系列事实 数据对

6 第 3 章程序设计语言基础知识 109 象或事实间的具体关系和规则的集合 通过查询操作把事实和规则输入数据库, 用户通过输入查询来执行程序 在 PROLOG 中, 关键操作是模式匹配, 通过匹配一组变量与一个预先定义的模式并将该组变量赋给该模式来完成操作 以值集合 S 和 T 上的二元关系 R 为例,R 实现后, 可以询问 : 已知 a 和 b, 确定 R(a,b) 是否成立 已知 a, 求所有使 R(a,y) 成立的 y 已知 b, 求所有使 R(x,b) 成立的 x 求所有使 R(x,y) 成立的 x 和 y 逻辑型程序设计具有与传统的命令式程序设计完全不同的风格 PROLOG 数据库中的事实和规则是一些 Hore 子句 Hore 子句的形式为 P:-P 1,P 2,,P n., 其中 n 0,P i (1 i n) 为形如 R i ( ) 的断言,R i 是关系名 该子句表示规则 : 若 P 1,P 2,,P n 均为真 ( 成立 ), 则 P 为真 当 n=0 时,Hore 子句变成 P., 这样的子句称为事实 一旦有了事实与规则后, 就可以提出询问 PROLOG 有很强的推理功能, 适用于编写自动定理证明 专家系统和自然语言理解等问题的程序 程序设计语言的基本成分程序设计语言的基本成分包括数据 运算 控制和传输等 1. 程序设计语言的数据成分程序中的数据对象总是对应着应用系统中某些有意义的东西, 数据表示则指示了程序中值的组织形式 数据类型用于描述数据对象, 还用于在基础机器中完成对值的布局, 同时还可用于检查表达式中对运算的应用是否正确 数据是程序操作的对象, 具有类型 名称 作用域 存储类别和生存期等属性, 在程序运行过程中要为它分配内存空间 数据名称由用户通过标识符命名, 标识符常由字母 数字和称为下划线的特殊符号 _ 组成 ; 类型说明数据占用内存空间的大小和存放形式 ; 作用域则说明可以使用数据的代码范围 ; 存储类别说明数据在内存中的位置 ; 生存期说明数据占用内存的时间范围 从不同角度可将数据进行不同的划分 (1) 常量和变量 按照程序运行时数据的值能否改变, 将数据分为常量和变量 程序中的数据对象可以具有左值和 ( 或 ) 右值 左值指存储单元 ( 或地址 容器 ), 右值是值 ( 或内容 ) 变量具有左值和右值, 在程序运行的过程中其右值可以改变 ; 常量只有右值, 在程序运行的过

7 110 程序员教程 ( 第 5 版 ) 程中其右值不能改变 (2) 全局量和局部量 按作用域可将变量分为全局变量和局部变量 一般情况下, 系统为全局变量分配的存储空间在程序运行的过程中一般是不改变的, 而为局部变量分配的存储单元是动态改变的 (3) 数据类型 按照数据组织形式的不同可将数据分为基本类型 用户定义类型 构造类型及其他类型 以 C/C++ 为例, 其数据类型如下 基本类型 : 整型 (int) 字符型(char) 实型(float double) 和布尔类型 (bool) 特殊类型 : 空类型 (void) 用户定义类型 : 枚举类型 (enum) 构造类型 : 数组 结构 联合 指针类型 :type * 抽象数据类型 : 类类型 其中, 布尔类型和类类型是 C++ 在 C 语言的基础上扩充的 2. 程序设计语言的运算成分程序设计语言的运算成分指明允许使用的运算符号及运算规则 大多数高级程序设计语言的基本运算可以分成算术运算 关系运算和逻辑运算等类型, 有些语言如 C(C++) 还提供位运算 运算符号的使用与数据类型密切相关 为了明确运算结果, 运算符号要规定优先级和结合性, 必要时还要使用圆括号 3. 程序设计语言的控制成分控制成分指明语言允许表述的控制结构, 程序员使用控制成分来构造程序中的控制逻辑 理论上已经证明, 可计算问题的程序都可以用顺序 选择和循环这 3 种控制结构来描述 (1) 顺序结构 顺序结构用来表示一个计算操作序列 计算过程从所描述的第一个操作开始, 按顺序依次执行后续的操作, 直到序列的最后一个操作, 如图 3-1 所示 顺序结构内也可以包含其他控制结构 (2) 选择结构 选择结构提供了在两种或多种分支中选择其中一种的逻辑 基本的选择结构是指定一个条件 P, 然后根据条件的成立与否决定控制流走 A 还是走 B, 只能从两个分支中选择一个来执行, 如图 3-2(a) 所示 选择结构中的 A 或 B 还可以包含顺序 选择和重复结构 程序设计语言中通常还提供简化了的选择结构, 如图 3-2(b) 所示, 以及描述多分支的选择结构

8 第 3 章程序设计语言基础知识 111 (a) (b) 图 3-1 顺序结构示意图 图 3-2 选择结构示意图 (3) 循环结构 循环结构描述了重复计算的过程, 通常由 3 个部分组成 : 初始化 需要重复计算的部分和重复的条件 其中, 初始化部分有时在控制的逻辑结构中不进行显式的表示 重复结构主要有两种形式 :while 型重复结构和 do while 型重复结构 while 型结构的逻辑含义是先判断条件 P, 若成立, 则进行需要重复的计算 A, 然后再去判断重复条件 ; 否则, 控制就退出重复结构, 如图 3-3(a) 所示 do while( 或 repeat until) 型结构的逻辑含义是先执行循环体 A, 然后再判断条件 P, 若成立则继续执行循环体 A 的过程并判断条件 ; 否则, 控制就退出重复结构, 如图 3-3(b) 所示 (a)while 循环结构 (b)do while 循环结构 图 3-3 循环结构示意图 C/C++ 提供的控制语句如下 (1) 复合语句 复合语句用于描述顺序控制结构 复合语句由一系列用 { 和 } 括起来的声明和语句组成, 其主要作用是将多条语句组成一个可执行单元 语法上允许出现语句的

9 112 程序员教程 ( 第 5 版 ) 地方都可以使用复合语句 复合语句是一个整体, 要么全部执行, 要么一条语句也不执行 (2)if 语句和 switch 语句 1 if 语句实现的是双分支的选择结构, 其一般形式为 : if ( 表达式 ) 语句 1; else 语句 2; 其中, 语句 1 和语句 2 可以是任何合法的 C/C++ 语句, 当语句 2 为空语句时, 可以简化为 : if ( 表达式 ) 语句 1; 使用 if 语句时, 需要注意 if 和 else 的匹配关系 C/C++ 语言规定,else 总是与离它最近的尚没有 else 的 if 相匹配 2 switch 语句描述了多分支的选择结构, 其一般形式为 : switch ( 表达式 ){ case 常量表达式 1: 语句 1; case 常量表达式 2: 语句 2;... case 常量表达式 n: 语句 n; default: 语句 n+1; } 执行 switch 语句时, 首先计算表达式的值, 然后用所得的值与列举的常量表达式的值依次比较, 若常量表达式 1 至常量表达式 n 都不能与表达式的值相匹配, 就执行在 default 部分的 语句序列 n+1, 然后结束 switch 语句 若所得的值与常量表达式 i(i=1,2,,n) 的值相同, 则执行 语句序列 i, 当 case i 的语句序列 i 中没有 break 语句时, 则执行随后的语句序列 i+1, 语句序列 i+2 直到语句序列 n+1 执行完成后, 才退出 switch 语句 ; 或者遇到了 break 而跳出 switch 语句 要使得程序在执行完 语句序列 i 后结束整个 switch 语句, 在语句序列 i 中应包含控制流能够到达的 break 语句 表达式可以是任何类型的, 常用的是字符型或整型表达式 多个常量表达式可以共用一个语句组 语句组可以包括任何可执行语句, 且无须用 { 和 } 括起来 (3) 循环语句 C/C++ 语言提供了 3 种形式的循环语句用于描述重复执行的控制结构 1 while 语句 while 语句描述了先判断条件再执行重复计算的控制结构,while 语句的一般形式是 : while ( 条件表达式 ) 循环体语句 ;

10 第 3 章程序设计语言基础知识 113 其中, 循环体语句是内嵌的语句, 当循环体语句多于一条时, 应使用 { 和 } 括起来 执行 while 语句时, 先计算条件表达式的值, 当值为非 0 时, 就执行循环体语句, 然后重新计算条件表达式的值后再进行判断, 否则就结束 while 语句的执行过程 2 do while 语句 do while 语句描述了先执行需要重复的计算再判断条件的控制结构, 其一般格式是 : do 循环体语句 ; while ( 条件表达式 ); 执行 do while 语句时, 先执行内嵌的循环体语句, 然后再计算条件表达式的值, 若值为非 0, 则再次执行循环体语句和计算条件表达式并判断, 直到条件表达式的值为 0 时, 才结束 do while 语句的执行过程 3 for 语句 for 语句的基本格式是 : for( 表达式 1; 表达式 2; 表达式 3) 循环体语句 ; 用 while 语句等价地表示为 : 表达式 1: while( 表达式 2){ 循环体语句 ; 表达式 3; } for 语句的使用很灵活, 其内部的 3 个表达式都可以省略, 但用于分隔三个表达式的分号 ; 不能遗漏 此外,C 语言中还提供了实现控制流跳转的 return break continue goto 语句 程序设计语言的传输成分指明语言允许的数据传输方式, 如赋值 数据的输入和输出等 4. 函数函数是程序模块的主要成分, 它是一段具有独立功能的程序 C 程序由一个或多个函数组成, 每个函数都有一个名字, 其中有且仅有一个名字为 main 的函数, 作为程序运行时的起点 函数的使用涉及 3 个概念 : 函数定义 函数声明和函数调用 1) 函数定义函数的定义描述了函数做什么和怎么做, 包括两部分 : 函数首部和函数体 函数定义的一

11 114 程序员教程 ( 第 5 版 ) 般格式是 : 返回值的类型函数名 ( 形式参数表 ) { 函数体 ; } // 函数首部 函数首部说明了函数返回值的数据类型 函数的名字和函数运行时所需的参数及类型 函数所实现的功能在函数体部分描述 如果函数没有返回值, 则函数返回值的类型声明为 void 函数名是一个标识符, 函数名应具有一定的意义 ( 反映函数的功能 ) 形式参数表列举了函数要求调用者提供的参数的个数 类型和顺序, 是函数实现功能时所必需的 若形式参数表为空, 可用 void 说明 C 程序中所有函数的定义都是独立的 在一个函数的定义中不允许定义另外一个函数, 也就是不允许函数的嵌套定义 有些语言 ( 如 PASCAL) 允许在函数内部定义函数 2) 函数声明函数应该先声明后引用 如果程序中对一个函数的调用在该函数的定义之前进行, 则应该在调用前对被调用函数进行声明 函数原型用于声明函数 函数声明的一般形式为 : 返回值类型函数名 ( 参数类型表 ); 使用函数原型的目的是告诉编译器传递给函数的参数个数 类型以及函数返回值的类型, 参数表中仅需要依次列出函数定义时参数的类型 函数原型可以使编译器更彻底地检查源程序中对函数的调用是否正确 3) 函数调用当在一个函数 ( 称为调用函数 ) 中需要使用另一个函数 ( 称为被调用函数 ) 实现的功能时, 便以名字进行调用, 称为函数调用 在使用一个函数时, 只要知道如何调用就可以了, 并不需要关心被调用函数的内部实现 因此, 程序员需要知道被调函数的名字 返回值和需要向被调函数传递的参数 ( 个数 类型 顺序 ) 等信息 函数调用的一般形式为 : 函数名 ( 实参表 ); 在 C 程序的执行过程中, 通过函数调用使得被调用的函数执行 函数体中若调用自己, 则称为递归调用 C 语言采用传值方式将实参传递给形参 调用函数和被调用函数之间交换信息的方法主要

12 第 3 章程序设计语言基础知识 115 有两种 : 一种是由被调用函数把返回值返回给主调函数, 另一种是通过参数带回信息 函数调用时实参与形参间交换信息的方法有传值调用和引用调用两种 (1) 传值调用 (Call by Value) 若实现函数调用时实参向形参传递相应类型的值, 则称为是传值调用 这种方式下形参不能向实参传递信息 函数 swap 的定义 : 定义一个交换两个整型变量值的函数 swap() void swap(int x,int y) { /* 要求调用该函数时传递两个整型的值 */ int temp; temp=x; x=y; y=temp; } 函数调用 :swap(a,b); 因为是传值调用,swap 函数运行后只能交换 x 和 y 的值, 而实参 a 和 b 的值并没有交换 在 C 语言中, 要实现被调用函数对实际参数的修改, 必须用指针作形参 即调用时需要先对实参进行取地址运算, 然后将实参的地址传递给指针形参 本质上仍属于传值调用 函数 swap 的定义 : 定义一个交换两个整型变量值的函数 swap() void swap(int *px, int *py) { /* 交换 *px 和 *py*/ int temp; temp=*px; *px=*py; *py=temp; } 函数调用 :swap(&a,&b); 由于形参 px py 分别得到了实参变量 a b 的地址, 所以 px 指向的对象 *px 即为 a,py 指向的对象 *py 就是 b, 因此在函数中交换 *px 和 *py 的值实际上就是交换实参 a 和 b 的值, 从而实现了调用函数中两个整型变量值的交换 这种方式是通过数据的间接访问来完成运算要求的 (2) 引用调用 引用是 C++ 中增加的数据类型, 当形参为引用类型时, 函数中对形参的访问和修改实际上就是针对相应实参所作的访问和改变 例如 : void swap(int &x, int &y) { /* 交换 x 和 y*/ int temp; temp=x; x=y; y=temp; } 函数调用 :swap(a,b); 引用调用方式下调用 swap(a,b) 时,x y 就是 a b 的别名, 因此, 函数调用完成后, 交换

13 116 程序员教程 ( 第 5 版 ) 了 a 和 b 的值 3.2 语言处理程序基础 语言处理程序是一类系统软件的总称, 其主要作用是将高级语言或汇编语言编写的程序翻译成某种机器语言程序, 使程序可在计算机上运行 语言处理程序主要有汇编程序 编译程序和解释程序 3 种基本类型 汇编程序基础 1. 汇编语言汇编语言是为特定计算机设计的面向机器的符号化程序设计语言 用汇编语言编写的程序称为汇编语言源程序 因为计算机不能直接识别和运行符号语言程序, 所以要用专门的汇编程序进行翻译 用汇编语言编写程序要遵循所用语言的规范和约定 汇编语言源程序由若干条语句组成, 一个程序中可以有三类语句 : 指令语句 伪指令语句和宏指令语句 (1) 指令语句 指令语句又称为机器指令语句, 将其汇编后能产生相应的机器代码, 这些代码能被 CPU 直接识别并执行相应的操作 基本的指令如 ADD SUB 和 AND 等, 书写指令语句时必须遵循相应的格式要求 指令语句可分为传送指令 算术运算指令 逻辑运算指令 移位指令 转移指令和处理机控制指令等类型 (2) 伪指令语句 伪指令语句指示汇编程序在汇编源程序时完成某些工作, 例如给变量分配存储单元地址, 给某个符号赋一个值等 伪指令语句与指令语句的区别是 : 伪指令语句经汇编后不产生机器代码, 而指令语句经汇编后要产生相应的机器代码 另外, 伪指令语句所指示的操作是在源程序被汇编时完成, 而指令语句的操作必须是在程序运行时完成 (3) 宏指令语句 在汇编语言中, 还允许用户将多次重复使用的程序段定义为宏 宏的定义必须按照相应的规定进行, 每个宏都有相应的宏名 在程序的任意位置, 若需要使用这段程序, 只要在相应的位置使用宏名, 就相当于使用了这段程序 因此, 宏指令语句就是宏的引用 2. 汇编程序汇编程序的功能是将汇编语言所编写的源程序翻译成机器指令程序 汇编程序的基本工作

14 第 3 章程序设计语言基础知识 117 包括 : 将每一条可执行汇编语句转换成对应的机器指令 ; 处理源程序中出现的伪指令和宏指令 由于汇编指令中形成操作数地址的部分可能在后面才能确定, 所以汇编程序一般需要扫描两次源程序才能完成翻译过程 第一次扫描的主要工作是定义符号的值并创建一个符号表 ST ST 记录了汇编时所遇到的符号的名和值 另外, 有一个固定的机器指令表 MOT1, 其中记录了每条机器指令的记忆码和指令的长度 在汇编程序翻译源程序的过程中, 为了计算各汇编语句中标号的地址, 需要设立一个位置计数器或单元地址计数器 LC(Location Counter), 其初值一般为 0 在扫描源程序时, 每处理完一条机器指令或与存储分配有关的伪指令 ( 如定义常数语句 定义存储语句 ),LC 的值就增加相应的长度 这样, 在汇编过程中,LC 的内容就是下一条被汇编的指令的偏移地址 若正在汇编的语句是有标号的, 则该标号的值就取 LC 的当前值 此外, 在第一次扫描中, 还需要对与定义符号值有关的伪指令进行处理 为了叙述方便, 不妨设立伪指令表 POT1 POT1 表的每一个元素只有两个域 : 伪指令助记符和相应的子程序入口 下面的步骤 (1)~(5) 描述了汇编程序第一次扫描源程序的过程 (1) 单元计数器 LC 置初值 0 (2) 打开源程序文件 (3) 从源程序中读入第一条语句 (4)while( 当前语句不是结束语句 ){ if( 当前语句有标号 ) 则将标号和单元计数器 LC 的当前值填入符号表 ST; if( 当前语句是可执行的汇编指令语句 ) 则查找 MOT1 表获得当前指令的长度 K, 并令 LC = LC+K; if( 当前指令是伪指令 ) 则查找 POT1 表并调用相应的子程序 ; if( 当前指令的操作码是非法记忆码 ) 则调用出错处理子程序 ; 从源程序中读入下一条语句 ; } (5) 关闭源程序文件 第二次扫描的任务是产生目标程序 除了使用前一次扫描所生成的符号表 ST 外, 还要使用机器指令表 MOT2, 该表中的元素有机器指令助记符 机器指令的二进制操作码 (Binary-code) 格式(Type) 和长度 (Length) 等 此外, 还要设立一个伪指令表 POT2, 供第二次扫描时使用,POT2 的每一个元素仍有两个域 : 伪指令记忆码和相应的子程序入口 在第二次扫描中, 伪指令有着完全不同的处理 在第二次扫描中, 可执行汇编语句应被翻译成对应的二进制代码机器指令 这一过程涉及两个方面的工作 : 一是把机器指令助记符转换成二进制机器指令操作码, 这可通过在 MOT2 中进行查找操作来实现 ; 二是求出操作数区各操作数的值 ( 用二进制表示 ) 在此基础上, 可以

15 118 程序员教程 ( 第 5 版 ) 装配出用二进制代码表示的机器指令 编译程序基础 1. 编译过程概述编译程序的功能是把某高级语言书写的源程序翻译成与之等价的目标程序 ( 汇编语言程序或机器语言程序 ) 编译程序的工作过程可以分为 6 个阶段, 如图 3-4 所示 实际的编译器中可能会将其中的某些阶段结合在一起进行处理 下面简要介绍各阶段实现的主要功能 图 3-4 编译器的工作阶段示意图 1) 词法分析词法分析阶段是编译过程的第一阶段, 这个阶段的任务是对源程序从前到后 ( 从左到右 ) 逐个字符地扫描, 从中识别出一个个 单词 符号 源程序可以被看成是一个多行的字符串 单词 符号是程序设计语言的基本语法单位, 如关键字 ( 或称保留字 ) 标识符 常数 运算符和分隔符 ( 标点符号 左右括号 ) 等 词法分析程序输出的 单词 常以二元组的方式输出, 即单词种类和单词自身的值 词法分析过程依据的是语言的词法规则, 即描述 单词 结构的规则 例如, 对于某 PASCAL 源程序中的一条声明语句和赋值语句 :

16 第 3 章程序设计语言基础知识 119 VAR X,Y,Z:real; X:=Y+Z*60; 词法分析阶段将构成这条语句的字符串分割成如下的单词序列 (1) 保留字 VAR (2) 标识符 X (3) 逗号, (4) 标识符 Y (5) 逗号, (6) 标识符 Z (7) 冒号 : (8) 标准标识符 real (9) 分号 ; (10) 标识符 X (11) 赋值号 := (12) 标识符 Y (13) 加号 + (14) 标识符 Z (15) 乘号 * (16) 常数 60 (17) 分号 ; 对于标识符 X Y Z, 其单词种类都是 id( 标识符 ), 字符串 "X""Y""Z" 都是单词的值 ; 而对于单词 60, 常数是该单词的种类,60 是该单词的值 这里, 用 id1 id2 和 id3 分别代表 X Y 和 Z, 强调标识符的内部标识由于组成该标识符的字符串不同而有所区别 经过词法分析后, 声明语句 VAR X,Y,Z:real; 表示为 VAR id1,id2,id3:real;, 赋值语句 X:=Y+Z*60; 表示为 id1:=id2+id3*60; 2) 语法分析语法分析的任务是在词法分析的基础上, 根据语言的语法规则将单词符号序列分解成各类语法单位, 如 表达式 语句 程序 等 语法规则就是各类语法单位的构成规则 通过语法分析确定整个输入串是否构成一个语法上正确的程序 如果源程序中没有语法错误, 语法分析后就能正确地构造出其语法树 ; 否则就指出语法错误, 并给出相应的诊断信息 词法分析和语法分析本质上都是对源程序的结构进行分析 对语句 id1:=id2+id3*60 进行语法分析后形成的语法树如图 3-5 所示 图 3-5 语法树示意图 3) 语义分析语义分析阶段主要分析程序中各种语法结构的语义信息, 包括检查源程序是否包含静态语义错误, 并收集类型信息供后面的代码生成阶段使用 只有语法和语义都正确的源程序才能被

17 120 程序员教程 ( 第 5 版 ) 翻译成正确的目标代码 语义分析的一个主要工作是进行类型分析和检查 程序设计语言中的一个数据类型一般包含两个方面的内容 : 类型的载体及其上的运算 例如, 整除取余运算符只能对整型数据进行运算, 若其运算对象中有浮点数就认为是类型不匹配的错误 在确认源程序的语法和语义之后, 就可对其进行翻译, 同时改变源程序的内部表示 对于声明语句, 需要记录所遇到的符号的信息, 因此应进行符号表的填查工作 在图 3-6(a) 所示的符号表中, 每行存放一个符号的信息 第一行存放标识符 X 的信息, 其类型为 real, 为它分配的逻辑地址是 0; 第二行存放 Y 的信息, 其类型为 real, 为它分配的逻辑地址是 4 对于可执行语句, 则检查结构合理的语句是否有意义 对语句 id1:=id2+id3*60 进行语义分析后的语法树如图 3-6(b) 所示, 其中增加了一个语义处理结点 inttoreal, 用于将一个整型数转换为浮点数 (a) 符号表 (b) 语法树 图 3-6 语义分析后的符号表和语法树示意图 4) 中间代码生成中间代码生成阶段的工作是根据语义分析的输出生成中间代码 中间代码 是一种简单且含义明确的记号系统, 可以有若干种形式, 它们的共同特征是与具体的机器无关 中间代码的设计原则主要有两点 : 一是容易生成, 二是容易被翻译成目标代码 最常用的一种中间代码是与汇编语言的指令非常相似的三地址码, 其实现方式常采用四元式 四元式的形式为 : 运算符, 运算对象 1, 运算对象 2, 运算结果例如, 对语句 X:=Y+Z*60, 可生成以下四元式序列 : 1 (inttoreal, 60,, t1) 2 (*, id3, t1, t2) 3 (+, id2, t2, t3) 4 (:=, t3, -,id1)

18 第 3 章程序设计语言基础知识 121 其中,t1 t2 t3 是编译过程中形成的临时变量, 用于存放中间运算结果 语义分析和中间代码生成所依据的是语言的语义规则 5) 代码优化由于编译器将源程序翻译成中间代码的工作是机械的 按固定模式进行的, 因此, 生成的中间代码往往在计算时间上和存储空间上有很大的浪费 当需要生成高效的目标代码时, 就必须进行优化 优化过程可以在中间代码生成阶段进行, 也可以在目标代码生成阶段进行 由于中间代码是不依赖于具体机器的, 此时所作的优化一般建立在对程序的控制流和数据流分析的基础之上, 与具体的机器无关 优化所依据的原则是程序的等价变换规则 例如, 在生成语句 X:=Y+Z*60 的四元式后,60 是编译时已知的常数, 把它转换为 60.0 的工作可以在编译时完成, 没有必要生成一个四元式, 同时 t3 仅仅用来将其值传递给 id1, 也可以化简掉, 因此上述的中间代码可优化成下面的等价代码 : 1 (*, id3, 60.0, t1) 2 (+, id2, t1, id1) 这只是优化工作中的一个简单示例, 真正的优化工作还要涉及公共子表达式的提取 循环优化等更多的内容和技术 6) 目标代码生成目标代码生成是编译器工作的最后一个阶段 这一阶段的任务是把中间代码变换成特定机器上的绝对指令代码 可重定位的指令代码或汇编指令代码, 这个阶段的工作与具体的机器密切相关 例如, 使用两个寄存器 R1 和 R2, 可对上述的四元式生成下面的目标代码 : 1 MOVF id3, R2 2 MULF #60.0, R2 3 MOVF id2, R1 4 ADDF R2, R1 5 MOV R1, id1 这里用 # 表明 60.0 为常数 7) 符号表管理符号表的作用是记录源程序中各个符号的必要信息, 以辅助语义的正确性检查和代码生成, 在编译过程中需要对符号表进行快速有效地查找 插入 修改和删除等操作 符号表的建立可以始于词法分析阶段, 也可以放到语法分析和语义分析阶段, 但符号表的使用有时会延续到目标代码的运行阶段 8) 出错处理用户编写的源程序不可避免地会有一些错误, 这些错误大致可分为静态错误和动态错误

19 122 程序员教程 ( 第 5 版 ) 动态错误也称动态语义错误, 它们发生在程序运行时, 例如变量取零时作除数 引用数组元素下标越界等错误 静态错误是指编译时所发现的程序错误, 可分为语法错误和静态语义错误, 如单词拼写错误 标点符号错误 表达式中缺少操作数 括号不匹配等有关语言结构上的错误称为语法错误 ; 而语义分析时发现的运算符与运算对象类型不合法等错误属于静态语义错误 在编译时发现程序中的错误后, 编译程序应采用适当的策略修复它们, 使得分析过程继续下去, 以便在一次编译过程中尽可能多地找出程序中的错误 对于编译过程的各个阶段, 在逻辑上可以把它们划分为前端和后端两部分 前端包括从词法分析到中间代码生成各阶段的工作, 后端包括中间代码优化和目标代码的生成及优化等阶段 以中间代码为分水岭, 把编译器分成了与机器有关的部分和与机器无关的部分 如此一来, 对于同一种程序设计语言的编译器, 开发出一个前端之后, 就可以针对不同的机器开发相应的后端, 前后端有机结合后就形成了该语言的一个编译器 当语言有改动时, 只会涉及前端部分的维护 对于不同的程序设计语言, 分别设计出相应的前端, 然后将各个语言的前端与同一个后端相结合, 就可得到各个语言在某种机器上的编译器 2. 词法分析 词法分析过程的本质是对构成源程序的字符串进行分析, 是一种对象为字符串的运算 语言中具有独立含义的最小语法单位是符号 ( 单词 ), 如标识符 无符号常数与界限符等 词法分析的任务是把构成源程序的字符串转换成单词符号序列 1) 字母表 字符串 字符串集合及运算 字母表 : 元素的非空有穷集合 例如, ={a, b} 字符 : 字母表 中的一个元素 例如, 上的 a 或 b 字符串 : 字母表 中字符组成的有穷序列 例如,a ab aaa 都是 上的字符串 字符串的长度 : 字符串中的字符个数 例如, aba =3 空串 ε: 由 0 个字符组成的序列 例如, ε =0 连接 : 字符串 S 和 T 的连接是指将串 T 接续在串 S 之后, 表示为 S T, 连接符号 可省略 显然, 对于字母表 上的任意字符串 S,S ε =ε S=S 空集 : 用符号 Φ 表示 * : 指包括空串 ε 在内的 上所有字符串的集合 例如, 设 ={a,b}, * ={ε, a, b, aa, bb, ab, ba, aaa, } 字符串的方幂 : 把字符串 α 自身连接 n 次得到的串, 称为字符串 α 的 n 次方幂, 记为 n α 0 n n, 1 n α = ε α = αα = α 1 α (n>0) 字符串集合的运算 : 设 A,B 代表字母表 上的两个字符串集合

20 或 ( 合并 ): A B = { α α A或 α B} 积 ( 连接 ): AB = { αβ α A且 β B} n n 1 n 1 0 幂 : A A A = = A A( n > 0) A = { ε}, 并规定 正则闭包 +: A = A A A 闭包 *: A * = A 0 A + * 显然, Σ = Σ Σ Σ 2) 正规表达式和正规集 第 3 章程序设计语言基础知识 123 词法规则可用 3 型文法 ( 正规文法 ) 或正规表达式描述, 它产生的集合是语言基本字符集 ( 字母表 ) 上的字符串的一个子集, 称为正规集 对于字母表, 其上的正规式及其表示的正规集可以递归定义如下 (1)ε 是一个正规式, 它表示集合 L(ε )={ε} (2) 若 a 是 上的字符, 则 a 是一个正规式, 它所表示的正规集为 L(a)={a} (3) 若正规式 r 和 s 分别表示正规集 L(r) 和 L(s), 则 : 1 r s 是正规式, 表示集合 L(r) L(s) 2 r s 是正规式, 表示集合 L(r)L(s) 3 r * 是正规式, 表示集合 (L(r)) * 4 (r) 是正规式, 表示集合 L(r) 仅由有限次地使用上述 3 个步骤定义的表达式才是 上的正规式 运算符 * 分别称为 或 连接 和 闭包 在正规式的书写中, 连接运算符 可省略 运算符的优先级从高到低顺序排列为 * 设 ={a, b}, 在下表中列出了 上的一些正规式和相应的正规集 正规式 ab a b a * (a b) * a(a b) * (a b) * abb 正规集字符串 ab 构成的集合字符串 a 字符串 b 构成的集合由 0 个或多个 a 构成的字符串集合所有由所有字符 a 和 b 构成的串的集合以 a 为首字符的 a b 字符串的集合以 abb 结尾的 a b 字符串的集合 若两个正规式表示的正规集相同, 则认为二者等价 两个等价的正规式 U 和 V 记为 U=V 例如,b(ab) * =(ba) * b,(a b) * =(a * b * ) * 3) 有限自动机有限自动机是一种识别装置的抽象概念, 它能准确地识别正规集 有限自动机分为两类 : 确定的有限自动机和不确定的有限自动机

21 124 程序员教程 ( 第 5 版 ) (1) 确定的有限自动机 (Deterministic Finite Automata,DFA) 一个确定的有限自动机是个五元组 :(S,Σ,f,s 0,Z), 其中 : 1 S 是一个有限集合, 它的每个元素称为一个状态 2 Σ 是一个有穷字母表, 它的每个元素称为一个输入字符 3 f 是 S Σ S 上的单值部分映像 f (A, a)=q 表示当前状态为 A 输入为 a 时, 将转换到下一状态 Q 称 Q 为 A 的一个后继状态 4 s 0 S, 是唯一的开始状态 5 Z 是非空的终止状态集合, Z S 一个 DFA 可以用两种直观的方式表示 : 状态转换图和状态转换矩阵 状态转换图是一个有向图, 简称转换图 DFA 中的每个状态对应转换图中的一个结点 ;DFA 中的每个转换函数对应图中的一条有向弧, 若转换函数为 f (A, a)=q, 则该有向弧从结点 A 出发, 进入结点 Q, 字符 a 是弧上的标记 例 3-1 DFA M1=({s 0, s 1, s 2, s 3 },{a, b},f,s 0,{s 3 }), 其中 f 为 : f (s 0, a)=s 1,f (s 0, b)=s 2,f (s 1, a)=s 3,f (s 1, b)=s 2,f (s 2, a)=s 1,f (s 2, b)=s 3,f (s 3, a)= s 3 与 DFA M1 对应的状态转换图如图 3-7(a) 所示, 其中, 状态 s 3 表示的结点是终态结点 状态转换矩阵可以用一个二维数组 M 表示, 矩阵元素 M [A, a] 的行下标表示状态, 列下标表示输入字符,M [A, a] 的值是当前状态为 A 输入字符为 a 时, 应转换到的下一状态 与 DFA M1 对应的状态转换矩阵如图 3-7(b) 所示 在转换矩阵中, 一般以第一行的行下标对应的状态作为初态, 而终态则需要特别指出 (a) 状态转换图 (b) 状态转换矩阵 图 3-7 确定的有限自动机示意图 对于 中的任何字符串 ω, 若存在一条从初态结点到某一终止状态结点的路径, 且这条路径上所有弧的标记符连接成的字符串等于 ω, 则称 ω 可由 DFA M 识别 ( 接受或读出 ) 若一个 DFA M 的初态结点同时又是终态结点, 则空字 ε 可由该 DFA 识别 ( 或接受 ) DFA M 所能识别的语言 L(M)={ω ω 是从 M 的初态到终态的路径上的弧上标记所形成的串 }

22 第 3 章程序设计语言基础知识 125 例如, 对于字符串 "ababaa", 在图 3-7(a) 所示的状态转换图中, 识别 "ababaa" 的路径是 s 0 s 1 s 2 s 1 s 2 s 1 s 3 由于从初态结点 s 0 出发, 存在到达终态结点 s 3 的路径, 因此该 DFA 可识别串 "ababaa" 而"abab" 和 "baab" 不能被该 DFA 接受 对于字符串 "abab", 从初态结点 s 0 出发, 经过路径 s 0 s 1 s 2 s 1 s 2, 当串结束时还没有到达终态结点 s 3 ; 而对于串 "baab", 经过路径 s 0 s 2 s 1 s 3, 虽然能到达终态结点 s 3, 但串尚未结束又不存在与下一字符 "b" 相匹配的弧 (2) 不确定的有限自动机 (Nondeterministic Finite Automata,NFA) 一个不确定的有限自动机也是一个五元组, 它与确定有限自动机的区别如下 1 f 是 S Σ 2 S 上的映像 对于 S 中的一个给定状态及输入符号, 返回一个状态的集合 即当前状态的后继状态不一定是唯一确定的 2 有向弧上的标记可以是 ε 例 3-2 已知有 NFA N=({s 0, s 1, s 2, s 3 },{a, b},f,s 0,{s 3 }), 其中 f 为 : f (s 0, a)= s 0, f (s 0, a)= s 1, f (s 0, b)= s 0, f (s 1, b)= s 2, f (s 2, b)= s 3 与 NFA M2 对应的状态转换图和状态转换矩阵如图 3-8 所示 (a) 状态转换图 (b) 状态转换矩阵 图 3-8 NFA 的状态转换图和转换矩阵 显然,DFA 是 NFA 的特例 实际上, 对于每个 NFA M, 都存在一个 DFA N, 且 L(M)=L(N) 词法分析器的任务是把构成源程序的字符流翻译成单词符号序列 手工构造词法分析器的方法是先用正规式描述语言规定的单词符号, 然后构造相应有限自动机的状态转换图, 最后依据状态转换图编写词法分析器 ( 程序 ) 3. 语法分析程序设计语言的语法常采用上下文无关文法描述 文法不仅规定了单词如何组成句子, 而且刻画了句子的组成结构 形式文法是一个规则 ( 或称产生式 ) 系统, 它规定了单词在句子中的位置和顺序, 也描述了句子的层次结构 下面以一个简单算术表达式的文法为例进行说明, 其中,E 代表算术表达式

23 126 程序员教程 ( 第 5 版 ) E E + T T (1) T T * F F (2) F (E) N (3) D (4) N DN D (5) 读作 定义为, 上述产生式规定简单算术表达式的运算符号为 加 (+) 乘 (*), 运算符号写在运算对象的中间, 运算对象是非负整数, 乘 运算的优先级高于 加 运算, 表达式或运算对象可加括号 有了以上文法, 对于算术表达式 2+3*4, 其结构可从上面的文法推导得出, 如图 3-9(a) 所示 ( 分析树 ), 简化的语法树如图 3-9(b) 所示 (a) 分析树 (b) 语法树 图 3-9 分析树和语法树示意图 解释程序基础解释程序是另一种语言处理程序, 在词法 语法和语义分析方面与编译程序的工作原理基本相同, 但是在运行用户程序时, 它直接执行源程序或源程序的内部形式 因此, 解释程序不产生源程序的目标程序, 这是它和编译程序的主要区别 图 3-10 显示了以解释方式实现高级语言的 3 种方式 源程序被直接解释执行的处理方式如图 3-10 中的标记 A 所示 这种解释程序对源程序进行逐个字符的检查, 然后执行程序语句规定的动作 例如, 如果扫描到字符串序列 :

24 第 3 章程序设计语言基础知识 127 GOTO L 解释程序就开始搜索源程序中标号 L 后面紧跟冒号 : 的出现位置 这类解释程序通过反复扫描源程序来实现程序的运行, 效率很低 解释程序也可以先将源程序翻译成某种中间代码形式, 然后对中间代码进行解释来实现用户程序的运行, 这种翻译方式如图 3-10 中的标记 B 和 C 所示 通常, 在中间代码和高级语言的语句间存在一一对应的关系 解释方式 B 图 3-10 解释器类型示意图和 C 的不同之处在于中间代码的级别, 在方式 C 下, 解释程序采用的中间代码更接近于机器语言 在这种实现方案中, 高级语言和低级中间代码间存在着 1 n 的对应关系 PASCAL-P 解释系统是这类解释程序的一个实例, 它在词法分析 语法分析和语义分析的基础上, 先将源程序翻译成 P- 代码, 再由一个非常简单的解释程序来解释执行这种 P- 代码 这类系统具有比较好的可移植性 下面简要描述解释程序的基本结构 这类系统通常可以分成两部分 : 第一部分是分析部分, 包括与编译过程相同的词法分析 语法分析和语义分析程序, 经语义分析后把源程序翻译成中间代码, 中间代码常采用逆波兰表示形式 第二部分是解释部分, 用来对第一部分产生的中间代码进行解释执行 下面简要介绍第二部分的工作原理 设用数组 MEM 模拟计算机的内存, 源程序的中间代码和解释部分的各个子程序都存放在数组 MEM 中 全局变量 PC 是一个程序计数器, 它记录了当前正在执行的中间代码的位置 这种解释部分的常见结构可以由下面两部分组成 (1)PC:=PC+1; (2) 执行位于 opcode-table[mem[pc]] 的子程序 ( 解释子程序执行后返回到前面 ) 用一个简单例子来说明其工作原理 设两个实型变量 A 和 B 进行相加的中间代码是 : start: Ipush A Ipush B Iaddreal 其中, 中间代码 Ipush 和 Iaddreal 实际上都是 opcode-table 表的索引值 ( 即位移 ), 而该表的单元中存放着对应的解释子程序的起始地址,A 和 B 都是 MEM 中的索引值 解释部分开始执行时,PC 的值为 start-1 opcode-table[ipush]=push

25 128 程序员教程 ( 第 5 版 ) opcode-table[iaddreal]=addreal 解释部分可表示如下 : interpreter-loop: PC:=PC+1; goto opcode-table[mem[pc]]; push: PC:=PC+1; stackreal(mem[mem[pc]]); goto interpreter-loop; addreal: stackreal(popreal()+popreal()); goto interpreter-loop; ( 其余各解释子程序 ) 其中,stackreal() 表示把相应值压入栈中, 而 popreal() 表示取得栈顶元素值并弹出栈顶元素 上面的解释部分基于栈实现了将两个数值相加并将结果存入栈中的处理 对于高级语言的编译和解释翻译方式, 可从以下几个方面进行比较 (1) 效率 编译比解释方式可能取得更高的效率 一般情况下, 在解释方式下运行程序时, 解释程序可能需要反复扫描源程序 例如, 每一次引用变量都要进行类型检查, 甚至需要重新进行存储分配, 从而降低了程序的运行速度 在空间上, 以解释方式运行程序需要更多的内存, 因为系统不但需要为用户程序分配运行空间, 而且要为解释程序及其支撑系统分配空间 在编译方式下, 编译程序要生成源程序的目标代码并进行优化, 该过程比解释方式需要更多的时间 虽然与仔细写出的机器程序相比, 一般由编译程序创建的目标程序运行的时间更长, 需要占用的存储空间更多, 但源程序只需要被编译程序翻译一次, 就可以多次运行 因此总体来讲, 编译方式比解释方式可能取得更高的效率 (2) 灵活性 由于解释程序需要反复检查源程序, 这也使得解释方式能够比编译方式更灵活 当解释器直接运行源程序时, 在运行中 修改程序就成为可能, 如增加语句或者修改错误等 另外, 当解释器直接在源程序上工作时, 它可以对错误进行更精确地定位 (3) 可移植性 源程序是由解释器控制来运行的, 可以提前将解释器安装在不同的机器上, 从而使得在新环境下无须修改源程序使之运行 而编译方式下则需要针对新机器重新生成源程序的目标代码才能运行 由于编译方式和解释方式各有特点, 因此现有的一些编译系统既提供编译的方式, 也提供解释的方式, 甚至将两种方式结合在一起 例如, 在 Java 虚拟机上发展的一种 compiling-just-intime 技术, 就是当一段代码第一次运行时进行编译, 其后运行时就不再进行编译了