第二章 高级语言及其语法描述 常用的高级语言 FORTRAN 数值计算 COBOL 事务处理 PASCAL 结构程序设计 第二章 高级语言及其语法描述 常用的高级语言 FORTRAN 数值计算 COBOL 事务处理 PASCAL 结构程序设计 ADA 大型程序、嵌入式实时系统 PROLOG 逻辑程序设计 ALGOL 算法语言 C/C++ 系统程序设计 Java Internet程序设计 程序设计语言(10) Alan J. Perlis (1966) -- ALGOL Edsger Wybe Dijkstra (1972) -- ALGOL John W. Backus (1977) -- FORTRAN Kenneth Eugene Iverson (1979) -- APL程序语言 Niklaus Wirth (1984) -- PASCAL John Cocke (1987) -- RISC & 编译优化 Ole-Johan Dahl，Kristen Nygaard (2001) -- Simula语言和面向对象概念 Alan Kay(2003) -- SmallTalk语言和面向对象程序设计 Peter Naur(2005) -- ALGOL60以及编译设计 形式语言, 程序语言语义 (4) Robert W. Floyd (1978) -- 编程语言语义，自动程序验证 C. Antony R. Hoare (1980) -- Hoare Logic, CSP Robin Milner (1991) -- LCF，ML，CCS，PI-calculus Amir Pnueli (1996) -- 时序逻辑和系统验证 国防科技大学计算机系602教研室

与机器语言或汇编语言比较，高级语言的优点： 较接近于数学语言和工程语言，比较直观、自然和易于理解; 便于验证其正确性，易于改错; 编写效率高; 易于移植. 国防科技大学计算机系602教研室

2.1 程序语言的定义 程序语言由两方面定义： 语法 语义 语用 国防科技大学计算机系602教研室

一. 语法 程序本质上是一定字符集上的字符串。 语法：一组规则，用它可以形成和产生一 个合式(well-formed)的程序。 一. 语法 程序本质上是一定字符集上的字符串。 语法：一组规则，用它可以形成和产生一 个合式(well-formed)的程序。 国防科技大学计算机系602教研室

语 法 词法规则：单词符号的形成规则。 语法规则：语法单位的形成规则。 语 法 词法规则：单词符号的形成规则。 单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。 描述工具：有限自动机 语法规则：语法单位的形成规则。 语法单位通常包括：表达式、语句、分程序、过程、函数、程序等; 描述工具：上下文无关文法 国防科技大学计算机系602教研室

语法规则和词法规则定义了程序的的形 式结构。定义语法单位的意义属于语义 问题。 E→i E→E+E E→E*E E→(E) 语法规则和词法规则定义了程序的的形 式结构。定义语法单位的意义属于语义 问题。 国防科技大学计算机系602教研室

二. 语义 语义：一组规则，用它可以定义一个程序的意义。 描述方法： 自然语言描述：隐藏错误、二义性和不完整性 形式描述： 操作语义(PL/1) 指称语义(ADA) 代数语义(PASCAL) 国防科技大学计算机系602教研室

三．程序语言的基本功能和层次结构 程序语言的基本功能：描述数据和对数据的运算。 所谓程序，本质上说是描述一定数据的处理过程。 国防科技大学计算机系602教研室

程序的层次结构 程序 | 子程序或分程序、过程、函数 语句 表达式 数据引用 算符 函数调用 国防科技大学计算机系602教研室

程序语言每个组成成分的逻辑和实现意义 抽象的逻辑的意义 数学意义 计算机实现的意义 具体实现 国防科技大学计算机系602教研室

2.2 高级语言的一般特性 高级语言的分类 强制式语言(Imperative Languge)也称过程式语言：命令驱动，面向语句 FORTRAN、C、Pascal，Ada 应用式语言（Applicative Language）：注重程序所表示的功能，而不是一个语句接一个语句地执行 LISP、ML 国防科技大学计算机系602教研室

2.2 高级语言的一般特性 2.2.1 高级语言的分类 基于规则的语言（Rule-based Language）：检查一定的条件，当它满足值，则执行适当的动作 Prolog 面向对象语言（Object-Oriented Language）：封装性、继承性和多态性 Smalltalk，C++，Java 国防科技大学计算机系602教研室

2.2 高级语言的一般特性 2.2.2 程序结构 FORTRAN 一个程序由一个主程序段和若干辅程序段组成。 辅程序段可以是子程序、函数段或数据块。 每个程序段有一系列的说明语句和执行语句组成。各段可以独立编译。 模块结构，没有嵌套和递归 各程序段中的名字相互独立，同一个标识符在不同的程序段中代表不同的名字。 国防科技大学计算机系602教研室

主程序 PROGRAM … … end 辅程序1 SUBROUTINE … 辅程序2 FUNCTION … 国防科技大学计算机系602教研室

PASCAL PASCAL程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和递归。 一个PASCAL过程： 过程头； 说明段（由一系列的说明语句组成）； begin 执行体（由一系列的执行语句组成）； end 国防科技大学计算机系602教研室

作用域：一个名字能被使用的区域范围称作这个名字的作用域。 允许同一个标识符在不同的过程中代表不同的名字。 名字作用域规则--"最近嵌套原则" 一个在子程序B1中说明的名字X只在B1中有效（局部于B1）； 如果B2是B1的一个内层子程序且B2中对 标识符X没有新的说明，则原来的名字X在 B2中仍然有效。如果B2对X重新作了说明， 那么，B2对X的任何引用都是指重新说明 过的这个X。 国防科技大学计算机系602教研室

A(real) A(integer) B(real) B(bool) program main var A, B : real; … procedure P1 var B:boolean; begin end procedure P2 var A:integer; 国防科技大学计算机系602教研室

PASCAL提供了丰富的数据类型和运算方式，它允许用户动态地申请和退还存贮空间。 国防科技大学计算机系602教研室

ADA 程序包(package)：把数据和操作代码封装在一起，支持数据抽象。 一个程序包分为两部分： 可见的规范说明部分，它定义了程序包外面可以访问的对象。 程序包体，它实际定义程序包的实现细节。 国防科技大学计算机系602教研室

type STACK is limited private; package STACKS is type ELEM is private; type STACK is limited private; procedure push (S: in out STACK; E: in ELEM); procedure pop (S: in out STACK; E: out ELEM); … end STACK; package body STACKS is procedure push(S: in out STACK; E: in ELEM); begin ……实现细节 end push; end pop; end; 国防科技大学计算机系602教研室

JAVA Java是一种面向对象的高级语言 类（Class） 继承(Inheritance) 多态性(Polymorphism)和动态绑定(Dynamic binding) 国防科技大学计算机系602教研室

class Trash_Car extends car { double amount; fill_trash ( ) { class Car{ int color_number; int door_number; int speed; … push_break ( ) { } add_oil ( ) {   class Trash_Car extends car { double amount; fill_trash ( ) { 国防科技大学计算机系602教研室

2.2.3 数据类型与操作 一个数据类型通常包括以下三种要素： 用于区别这种类型数据对象的属性 这种类型的数据对象可以具有的值 2.2.3 数据类型与操作 一个数据类型通常包括以下三种要素： 用于区别这种类型数据对象的属性 这种类型的数据对象可以具有的值 可以作用于这种类型的数据对象的操作 国防科技大学计算机系602教研室

2.2.3 数据类型与操作 一．初等数据类型 数值类型：整型、实型、复数、双精度， 运算：+，-，*，/等 逻辑类型：布尔运算：∨，∧，┑ 2.2.3 数据类型与操作 一．初等数据类型 数值类型：整型、实型、复数、双精度， 运算：+，-，*，/等 逻辑类型：布尔运算：∨，∧，┑ 字符类型：符号处理 指针类型 国防科技大学计算机系602教研室

标识符与名字 标识符：以字母开头的，由字母数字组成的字符串。 标识符与名字两者有本质区别： 标识符是语法概念 名字有确切的意义和属性 国防科技大学计算机系602教研室

Jordan ? 标识符！ ? ? 国防科技大学计算机系602教研室

标识符与名字 名字： 名字的性质的说明方式： 值：单元中的内容 属性：类型和作用域 由说明语句来明确规定的 隐含说明：FORTRAN 以I,J,K,…N为首的名字代表整型，否则为实型。 动态确定：走到哪里，是什么，算什么 国防科技大学计算机系602教研室

二 数据结构 1 数组 逻辑上，数组是由同一类型数据所组成的某种n维矩形结构，沿着每一维的距离，称为下标。 二 数据结构 1 数组 逻辑上，数组是由同一类型数据所组成的某种n维矩形结构，沿着每一维的距离，称为下标。 数组可变与不可变：编译时能否确定其存贮 空间的大小。 访问：给出数组名和下标值 存放方式: 按行存放,按列存放 存放方式: 按行存放(C, PASCAl),按列存放(FORTRAN) 国防科技大学计算机系602教研室

数组元素地址计算 数组A[10,20]的A[1，1]为a，各维下标为1，按行存放，那么A[i，j]地址为： a+(i-1)*20+(j-1) 数组元素地址计算公式 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室

内情向量 把数组的有关信息记录在一个“内情向量”中，每个数组的内情向量必须包括：维数，各维的上、下限，首地址，以及数组（元素）的类型。 国防科技大学计算机系602教研室

2 记录 逻辑上说，记录结构由已知类型的数据组合在一起的一种结构。 访问：复合名 CARD[k].NAME 存储：连续存放 record { char NAME[20]; integer AGE; bool MARRIED; } CARD[1000] 访问：复合名 CARD[k].NAME 存储：连续存放 域的地址计算：相对于记录结构起点的相对数OFFSET。 国防科技大学计算机系602教研室

3 字符串、表格、栈 字符串：符号处理、公式处理 表格：本质上是一种记录结构 线性表：一组顺序化的记录结构 栈：一种线性表，后进先出，POP, PUSH 国防科技大学计算机系602教研室

三 抽象数据类型 一个抽象数据类型包括： 程序设计语言对抽象数据类型的支持 数据对象的一个集合； 作用于这些数据对象的抽象运算的集合； 三 抽象数据类型 一个抽象数据类型包括： 数据对象的一个集合； 作用于这些数据对象的抽象运算的集合； 这种类型对象的封装，即，除了使用类型中所定义的运算外，用户不能对这些对象进行操作。 程序设计语言对抽象数据类型的支持 Ada语言通过程序包（package）提供了数据封装的支持 Smalltalk、C++和Java语言则通过类（Class）对抽象数据类型提供支持。 国防科技大学计算机系602教研室

2.2.4 语句与控制结构 一．表达式 表达式由运算量（也称操作数，即数据引用或函数调用）和算符（操作符）组成。 形式：中缀、前缀、后缀 2.2.4 语句与控制结构 一．表达式 表达式由运算量（也称操作数，即数据引用或函数调用）和算符（操作符）组成。 形式：中缀、前缀、后缀 X*Y -A P↑ 表达式形成规则 国防科技大学计算机系602教研室

算符的优先次序 一般的规定 注意两点： PASCAL：左结合A+B+C=(A+B)+C FORTRAN：对于满足左、右结合的算符可任取一种，如A+B+C就可以处理成(A+B)+C，也可以处理成A+(B+C)。 注意两点： 代数性质能引用到什么程度视具体的语言不同而不同； 在数学上成立的代数性质在计算机上未必完全成立。 国防科技大学计算机系602教研室

二．语句 赋值语句： A := B 名字左值：该名字代表的那个单元（地址）称为该名字的左值。(所代表的存贮单元的地址) 右值：一个名字的值称为该名字的右值。(所代表的存贮单元的内容) 国防科技大学计算机系602教研室

控制语句： 无条件转移语句 goto L 条件语句 if B then S if B then S1 else S2 循环语句 while B do S repeat S until B for i:=E1 step E2 until E3 do S 过程调用语句 call P(X1, X2, ... ,Xn) 返回语句 return (E) 国防科技大学计算机系602教研室

说明语句：定义各种不同数据类型的变量或运算，定义名字的性质。 国防科技大学计算机系602教研室

简单句和复合句 简单句：不包含其他语句成分的基本句 复合句：句中有句的语句 国防科技大学计算机系602教研室

复习：程序语言的定义 程序语言由两方面定义： 语法：一组规则，用它可以形成和产生一个合式(well-formed)的程序 词法规则：单词符号的形成规则。 常数、标识符、基本字、算符、界符等。 有限自动机 语法规则：语法单位的形成规则。 表达式、语句、分程序、过程、函数、程序等; 上下文无关文法 语义:一组规则，用它可以定义一个程序的意义 国防科技大学计算机系602教研室

复习：程序语言的基本功能和层次结构 程序语言的基本功能：描述数据和对数据的运算。 所谓程序，本质上说是描述一定数据的处理过程。 程序 | 子程序或分程序、过程、函数 语句 表达式 数据引用 算符 函数调用 国防科技大学计算机系602教研室

复习：高级语言的一般特性 高级语言的分类 程序结构 数据类型与操作 语句与控制结构 初等数据类型 数据结构 抽象数据类型 国防科技大学计算机系602教研室

2.3 程序语言的语法描述 几个概念: 考虑一个有穷 字母表∑ 字符集 其中每一个元素称为一个字符 2.3 程序语言的语法描述 几个概念: 考虑一个有穷 字母表∑ 字符集 其中每一个元素称为一个字符 ∑上的字(也叫字符串) 是指由∑中的字符所构成的一个有穷序列 不包含任何字符的序列称为空字，记为ε 用∑*表示∑上的所有字的全体,包含空字ε 例如: 设 ∑={a， b}，则 ∑*={ε,a,b,aa,ab,ba,bb,aaa,...} 国防科技大学计算机系602教研室

∑*的子集U和V的连接（积）定义为 UV＝{  | U & V } 设： U＝{ a, aa } V＝ { b, bb } 那么： UV= { ab, abb, aab, aabb} 国防科技大学计算机系602教研室

UV＝{  | U & V } Vn=VV…V V*=V0∪V1∪V2∪V3∪… 称V*是V的闭包; 记 V＋＝VV* ，称V+是V的正规闭包。 国防科技大学计算机系602教研室

设： U＝{ a, aa } 那么： U* = {  , a, aa, aaa, aaaa, …} 国防科技大学计算机系602教研室

2.3.1 上下文无关文法 文法： 描述语言的语法结构的形式规则 He gave me a book. 2.3.1 上下文无关文法 文法： 描述语言的语法结构的形式规则 He gave me a book. <句子>  <主语><谓语><间接宾语><直接宾语> <主语>  <代词> <谓语>  <动词> <间接宾语>  <代词> <直接宾语>  <冠词> <名词> <代词>  He <代词>  me <名词>  book <冠词>  a <动词>  gave 国防科技大学计算机系602教研室

<句子>  <主语><谓语><间接宾语><直接宾语> <主语>  <代词> <谓语>  <动词> <间接宾语>  <代词> <直接宾语>  <冠词> <名词> <代词>  He <代词>  me <名词>  book <冠词>  a <动词>  gave <句子> <主语><谓语><间接宾语><直接宾语> <代词><谓语><间接宾语><直接宾语> He <谓语><间接宾语><直接宾语> He <动词><间接宾语><直接宾语> He gave <间接宾语><直接宾语> He gave <代词><直接宾语> He gave me <直接宾语> He gave me <冠词><名词> He gave me a <名词> He gave me a book 国防科技大学计算机系602教研室

上下文无关文法的定义： 一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中 VT：终结符集合(非空) VN：非终结符集合(非空)，且VT  VN= S：文法的开始符号，SVN P：产生式集合(有限)，每个产生式形式为 P， PVN，   (VT  VN)* 开始符S至少必须在某个产生式的左部出现一次。 国防科技大学计算机系602教研室

G=<{i，+，*，(，)}，{E}，E， P>， 其中，P由下列产生式组成： 例，定义只含+，*的算术表达式的文法 G=<{i，+，*，(，)}，{E}，E， P>， 其中，P由下列产生式组成： E  i E  E+E E  E*E E  (E) 国防科技大学计算机系602教研室

G(E)： E  i | E+E | E*E | (E) 几点规定： “  ”也可以用“::="表示， 这种表示称为巴科斯范式(BNF) P  1 P  2 可缩写为 P  1|2||n  P  n 其中，“|”读成“或”，称为P的一个候选式。 表示一个文法时，通常只给出开始符号和产生式，如上例，可表示为： G(E)： E  i | E+E | E*E | (E) 例，定义只含+，*的算术表达式的文法 G=<{i，+，*，(，)}，{E}，E， P>， 其中，P由下列产生式组成： E  i E  E+E E  E*E E  (E) 国防科技大学计算机系602教研室

如果1  2   n，则我们称这个序 列是从1到n的一个推导。若存在一个从 1到n的推导，则称1可以推导出n 。 定义：称A直接推出，即 A 仅当A  是一个产生式， 且，  (VT  VN)* 。 如果1  2   n，则我们称这个序 列是从1到n的一个推导。若存在一个从 1到n的推导，则称1可以推导出n 。 对文法G(E)： E  i | E+E | E*E | (E) E  (E)  (E+E) (i+E) (i+i) 国防科技大学计算机系602教研室

通常，用 表示：从1出发，经过 一步或若干步，可以推出n。 所以 ： 即 或 定义：假定G是一个文法，S 是它的开始符号。 如果 ，则称是一个句型。仅含终结符 号的句型是一个句子。文法G所产生的句子的全 体是一个语言，将它记为 L(G)。 国防科技大学计算机系602教研室

G(E)： E  i | E+E | E*E | (E) 的一个句子。 证明： 例： (i*i+i)是文法 G(E)： E  i | E+E | E*E | (E) 的一个句子。 证明： E  (E)  (E+E) (E*E+E) (i*E+E) (i*i+E)  (i*i+i) E，(E)，(E*E+E)，…，(i*i+i)是句型。 国防科技大学计算机系602教研室

例：文法G1(A)： A  c|Ab G1(A)的语言? L(G1)={c，cb，cbb，} 以c开头，后继若干个b 国防科技大学计算机系602教研室

例：文法G2(S)： S  AB A  aA|a B  bB|b G2(S)的语言? L(G2)={ambn|m，n>0} 国防科技大学计算机系602教研室

例：给出产生语言为{anbn|n1}的文法。 G3(S)： S  aSb S  ab 国防科技大学计算机系602教研室

例：给出产生语言为{ambn|1nm2n}的 文法。 G4(S)： S  aSb | aaSb S  ab | aab 国防科技大学计算机系602教研室

E+Ei+Ei+i E+EE+ii+i 从一个句型到另一个句型的推导往往不唯一。 E+Ei+Ei+i E+EE+ii+i 最左推导：任何一步  都是对中的最 左非终结符进行替换。 最右推导：任何一步  都是对中的最 右非终结符进行替换。 国防科技大学计算机系602教研室

2.3.2 语法树与二义性 用一张图表示一个句型的推导,称为语法树。 (i*i+i)的语法树 E (E) (E+E) (E*E+E) G(E)： E  i | E+E | E*E | (E) (i*i+i) E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i) E (E) (E+E) (E+i) (E*E+i) (E*i+i) (i*i+i) 一棵语法树是不同推导过程的共性抽象。 国防科技大学计算机系602教研室

如果使用最左(右)推导，则一个最左(右)推导与语法树一一对应。 一个句型是否只对应唯一一棵语法树？ 国防科技大学计算机系602教研室

G(E)： E  i|E+E|E*E|(E) 是二义文法。 定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。 G(E)： E  i|E+E|E*E|(E) 是二义文法。 语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。 可能存在G和G’，一个为二义的，一个为无二义的。但L(G)=L(G’) 二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的。 可以找到一组无二义文法的充分条件。 国防科技大学计算机系602教研室

G(E)： E  i|E+E|E*E|(E) 二义文法： G(E)： E  i|E+E|E*E|(E) 无二义文法： G(E)：E  T | E+T T  F | T*F F  (E) | i 表达式 项|表达式+项 项  因子 | 项*因子 因子  (表达式) | i 国防科技大学计算机系602教研室

) E F T i + * ( 考虑句子(i*i+i) E T F (E) (E+T) (T+T) (T*F+T) (F*F+T) (i*F+T) (i*i+T) (i*i+F) (i*i+i) 国防科技大学计算机系602教研室

描述程序设计语言时，对于上下文无关文法的限制 ： 1 不含PP形式的产生式 2 每个非终结符P必须有用处 即： 国防科技大学计算机系602教研室

2.3.3 形式语言鸟瞰 Chomsky于1956年建立形式语言体系，他把文法分成四种类型：0，1，2，3型。 2.3.3 形式语言鸟瞰 Chomsky于1956年建立形式语言体系，他把文法分成四种类型：0，1，2，3型。 与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。 国防科技大学计算机系602教研室

0型(短语文法，图灵机)： 1型(上下文有关文法，线性界限自动机)： 产生式形如：    产生式形如：    其中： (VT  VN)*且至少含有一个非终结符； (VT  VN)* 1型(上下文有关文法，线性界限自动机)： 其中：||  ||，仅 S 例外。 国防科技大学计算机系602教研室

2型(上下文无关文法，非确定下推自动机)： 产生式形如： A   其中：A VN； (VT  VN)*。 3型(正规文法，有限自动机)： 产生式形如： A  B 或 A   其中：  VT*；A，BVN 产生式形如： A  B 或 A   右线性文法 左线性文法 国防科技大学计算机系602教研室

四种类型描述能力比较 0型 1型 2型 3型 国防科技大学计算机系602教研室

L5={anbn|n1} 不能由正规文法产生，但可由上下文无关文法产生： G5(S)： S  aSb| ab L6={anbncn|n1}不能由上下文无关文法产 生，但可由上下文有关文法产生： G6(S)： S  aSBC| aBC CB  BC aB  ab bB  bb bC  bc cC  cc 国防科技大学计算机系602教研室

程序设计语言不是上下文无关语言，甚至不是上下文有关语言。 L7={c| (a|b)*}不能由上下文无关文法产生，甚至连上下文有关文法也不能产生，只能由0型文法产生。 标识符引用 过程调用过程中，"形-实参数地对应性"(如个数，顺序和类型一致性) 现今程序设计语言的语言结构，用上下文无关文法描述就足够了。 国防科技大学计算机系602教研室

作业 P36-6，7，8，9，10，11 国防科技大学计算机系602教研室