02 第二章 高级语言及其语法描述.pptx

第1页：第二章高级语言及其语法描述

第二章高级语言及其语法描述

• 常用的高级语言
• FORTRAN数值计算
• COBOL事务处理
• PASCAL结构程序设计
• ADA大型程序、嵌入式实时系统
• PROLOG逻辑程序设计
• ALGOL算法语言
• C/C++系统程序设计
• JavaInternet程序设计

第2页：较接近于数学语言和工程语言

较接近于数学语言和工程语言

• 较接近于数学语言和工程语言，比较直观、自然和易于理解;
• 便于验证其正确性，易于改错;
• 编写效率高;
• 易于移植.

第3页：2.1程序语言的定义

2.1程序语言的定义

• 程序语言由两方面定义：
• 语法
• 语义
• 语用

第4页：一.语法

一.语法

语法

一组规则，用它可以形成和产生一个合式(well-formed)的程序。

第5页：词法规则

词法规则

词法规则

单词符号的形成规则。

描述工具

有限自动机

语法规则

语法单位的形成规则。

语法单位通常包括

表达式、语句、分程序、过程、函数、程序等;

描述工具

上下文无关文法

第6页：词法规则（续）

词法规则（续）

• 定义语法单位的意义属于语义问题。

第7页：二.语义

二.语义

语义

一组规则，用它可以定义一个程序的意义。

自然语言描述

隐藏错误、二义性和不完整性

• 描述方法：
• 形式描述：
• 操作语义(PL/1)
• 指称语义(ADA)
• 代数语义(PASCAL)

第8页：三．程序语言的基本功能和层次结构

三．程序语言的基本功能和层次结构

程序语言的基本功能

描述数据和对数据的运算。

第9页：三．程序语言的基本功能和层次结构（续）

三．程序语言的基本功能和层次结构（续）

• 过程、函数|语句|表达式|数据引用算符函数调用

第10页：三．程序语言的基本功能和层次结构

三．程序语言的基本功能和层次结构

• 抽象的逻辑的意义
• 数学意义
• 计算机实现的意义
• 具体实现

第11页：2.2高级语言的一般特性

2.2高级语言的一般特性

• 高级语言的分类
• 强制式语言(Imperative Languge)也称过程式语言：命令驱动，面向语句
• FORTRAN、C、Pascal，Ada
• 应用式语言（Applicative Language）：注重程序所表示的功能，而不是一个语句接一个语句地执行
• LISP、ML

第12页：2.2高级语言的一般特性（续）

2.2高级语言的一般特性（续）

• 2.2.1高级语言的分类
• 基于规则的语言（Rule-based Language）：检查一定的条件，当它满足值，则执行适当的动作
• Prolog
• 面向对象语言（Object-Oriented Language）：封装性、继承性和多态性
• Smalltalk，C++，Java

第13页：2.2高级语言的一般特性

2.2高级语言的一般特性

• 2.2.2程序结构
• FORTRAN
• 一个程序由一个主程序段和若干辅程序段组成。
• 辅程序段可以是子程序、函数段或数据块。
• 每个程序段有一系列的说明语句和执行语句组成。各段可以独立编译。
• 模块结构，没有嵌套和递归
• 各程序段中的名字相互独立，同一个标识符在不同的程序段中代表不同的名字。

第14页：2.2高级语言的一般特性（续）

2.2高级语言的一般特性（续）

• INE……end辅程序2FUNCTION……end

第15页：2.2高级语言的一般特性

2.2高级语言的一般特性

一个PASCAL过程

过程头；说明段（由一系列的说明语句组成）；begin执行体（由一系列的执行语句组成）；end

第16页：一个在子程序B1中说明

一个在子程序B1中说明

• 允许同一个标识符在不同的过程中代表不同的名字。
• 名字作用域规则--"最近嵌套原则"
• 如果B2是B1的一个内层子程序且B2中对标识符X没有新的说明，则原来的名字X在B2中仍然有效。如果B2对X重新作了说明，那么，B2对X的任何引用都是指重新说明过的这个X。

第17页：PASCAL嵌套过程作用域示例

PASCAL嵌套过程作用域示例

• real;…procedure P1var B:boolean;…begin…endprocedure P2var A:integer;…begin…endbegin…endA(real)B(real)B(bool)A(integer)

第18页：PASCAL嵌套过程作用域示例（续）

PASCAL嵌套过程作用域示例（续）

PASCAL提供了丰富的数据类型和运算方式，它允许用户动态地申请和退还存贮空间。

第19页：可见的规范说明部分

可见的规范说明部分

程序包(package)

把数据和操作代码封装在一起，支持数据抽象。

• 它定义了程序包外面可以访问的对象。
• 一个程序包分为两部分：
• 程序包体，它实际定义程序包的实现细节。

第20页：ADA程序包STACKS示例

ADA程序包STACKS示例

rivatetypeSTACKislimitedprivate;procedurepush(S:inoutSTACK;E:inELEM);procedurepop(S:inoutSTACK;E:outELEM);…endSTACK;packagebodySTACKSisprocedurepush(S:inoutSTACK;E:inELEM);begin……实现细节endpush;procedurepop(S:inoutSTACK;E:outELEM);begin……实现细节endpop;end;

第21页：ADA程序包STACKS示例（续）

ADA程序包STACKS示例（续）

• Java是一种面向对象的高级语言
• 继承(Inheritance)
• 多态性(Polymorphism)和动态绑定(Dynamicbinding)

第22页：Java类与继承代码示例

Java类与继承代码示例

intdoor_number;intspeed;…push_break(){…}add_oil(){…}}classTrash_Carextendscar{doubleamount;fill_trash(){…}}

第23页：2.2.3数据类型与操作

2.2.3数据类型与操作

• 一个数据类型通常包括以下三种要素：
• 用于区别这种类型数据对象的属性
• 这种类型的数据对象可以具有的值
• 可以作用于这种类型的数据对象的操作

第24页：2.2.3数据类型与操作（续）

2.2.3数据类型与操作（续）

数值类型

整型、实型、复数、双精度，运算：+，-，*，/等

逻辑类型

布尔运算：∨，∧，┑

字符类型

符号处理

• 一．初等数据类型
• 指针类型

第25页：标识符与名字

标识符与名字

标识符

以字母开头的，由字母数字组成的字符串。

• 标识符与名字两者有本质区别：
• 标识符是语法概念
• 名字有确切的意义和属性

第26页：标识符与名字（续）

标识符与名字（续）

• ??

第27页：标识符与名字

标识符与名字

值

单元中的内容

属性

类型和作用域

隐含说明

FORTRAN以I,J,K,…N为首的名字代表整型，否则为实型。

动态确定

走到哪里，是什么，算什么

• 名字：
• 名字的性质的说明方式：
• 由说明语句来明确规定的

第28页：二数据结构1数组

二数据结构1数组

数组可变与不可变

编译时能否确定其存贮空间的大小。

访问

给出数组名和下标值

存放方式

按行存放,按列存放

第29页：数组元素地址计算

数组元素地址计算

• 数组A[10,20]的A[1，1]为a，各维下标为1，按行存放，那么A[i，j]地址为：a+(i-1)*20+(j-1)
• 数组元素地址计算公式

第30页：

第31页：内情向量

内情向量

• 把数组的有关信息记录在一个“内情向量”中，每个数组的内情向量必须包括：维数，各维的上、下限，首地址，以及数组（元素）的类型。

第32页：内情向量（续）

内情向量（续）

访问

复合名CARD[k].NAME

存储

连续存放

域的地址计算

相对于记录结构起点的相对数OFFSET。

第33页：3字符串

3字符串

字符串

符号处理、公式处理

表格

本质上是一种记录结构

线性表

一组顺序化的记录结构

栈

一种线性表，后进先出，POP, PUSH

第34页：三抽象数据类型

三抽象数据类型

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

第35页：2.2.4语句与控制结构

2.2.4语句与控制结构

形式

中缀、前缀、后缀X*Y-A P↑

• 一．表达式
• 表达式由运算量（也称操作数，即数据引用或函数调用）和算符（操作符）组成。
• 表达式形成规则

第36页：算符的优先次序

算符的优先次序

PASCAL

左结合A+B+C=(A+B)+C

FORTRAN

对于满足左、右结合的算符可任取一种，如A+B+C就可以处理成(A+B)+C，也可以处理成A+(B+C)。

• 一般的规定
• 注意两点：
• 代数性质能引用到什么程度视具体的语言不同而不同；
• 在数学上成立的代数性质在计算机上未必完全成立。

第37页：二．语句

二．语句

赋值语句

A := B

名字左值

该名字代表的那个单元（地址）称为该名字的左值。(所代表的存贮单元的地址)

右值

一个名字的值称为该名字的右值。(所代表的存贮单元的内容)

第38页：无条件转移语句goto L

无条件转移语句goto L

• 条件语句if B then Sif Bthen S1else S2
• 循环语句while B do Srepeat S until Bfor i:=E1step E2until E3do S
• 过程调用语句call P(X1, X2, ... ,Xn)
• 返回语句return (E)

第39页：无条件转移语句goto L（续）

无条件转移语句goto L（续）

说明语句：定义各种不同数据类型的变量或运算，定义名字的性质。

第40页：简单句和复合句

简单句和复合句

简单句

不包含其他语句成分的基本句

复合句

句中有句的语句

第41页：复习：程序语言的定义

复习：程序语言的定义

语法

一组规则，用它可以形成和产生一个合式(well-formed)的程序

词法规则

单词符号的形成规则。

语法规则

语法单位的形成规则。

语义

一组规则，用它可以定义一个程序的意义

• 程序语言由两方面定义：
• 常数、标识符、基本字、算符、界符等。
• 有限自动机
• 表达式、语句、分程序、过程、函数、程序等;
• 上下文无关文法

第42页：复习：程序语言的定义（续）

复习：程序语言的定义（续）

程序语言的基本功能

描述数据和对数据的运算。

第43页：复习：高级语言的一般特性

复习：高级语言的一般特性

• 高级语言的分类
• 程序结构
• 数据类型与操作
• 初等数据类型
• 数据结构
• 抽象数据类型
• 语句与控制结构

第44页：2.3程序语言的语法描述

2.3程序语言的语法描述

• 几个概念:
• 考虑一个有穷字母表∑字符集
• 其中每一个元素称为一个字符
• ∑上的字(也叫字符串)是指由∑中的字符所构成的一个有穷序列
• 不包含任何字符的序列称为空字，记为ε
• 用∑*表示∑上的所有字的全体,包含空字ε例如:设∑={a，b}，则∑*={ε,a,b,aa,ab,ba,bb,aaa,...}

第45页：2.3程序语言的语法描述（续）

2.3程序语言的语法描述（续）

那么

UV={ab,abb,aab,aabb}

• U＝{a, aa}V＝{b, bb}
• |
• U &
• V }

第46页：2.3程序语言的语法描述

2.3程序语言的语法描述

• |
• U &
• V }
• 规定V0={
• }，令V*=V0∪V1∪V2∪V3∪…称V*是V的闭包;
• 记V＋＝VV*，称V+是V的正规闭包。

第47页：2.3程序语言的语法描述（续）

2.3程序语言的语法描述（续）

• U*={
• ,a,aa,aaa,aaaa,…}U＋={a,aa,aaa,aaaa,…}

第48页：2.3.1上下文无关文法

2.3.1上下文无关文法

文法

描述语言的语法结构的形式规则

• He gave me a book.<句子>
• <主语><谓语><间接宾语><直接宾语><主语>
• <代词><谓语>
• <动词><间接宾语>
• <代词><直接宾语>
• <冠词> <名词><代词>
• He<代词>
• me<名词>
• book<冠词>
• a<动词>
• gave

第49页：2.3.1上下文无关文法（续）

2.3.1上下文无关文法（续）

• 句子>
• <主语><谓语><间接宾语><直接宾语><主语>
• <代词><谓语>
• <动词><间接宾语>
• <代词><直接宾语>
• <冠词> <名词><代词>
• He<代词>
• me<名词>
• book<冠词>
• a<动词>
• gave<句子>
• <主语><谓语><间接宾语><直接宾语>
• <代词><谓语><间接宾语><直接宾语>
• He<谓语><间接宾语><直接宾语>
• He<动词><间接宾语><直接宾语>
• Hegave<间接宾语><直接宾语>
• Hegave<代词><直接宾语>
• Hegaveme<直接宾语>
• Hegaveme<冠词><名词>
• Hegavemea<名词>
• Hegavemeabook

第50页：2.3.1上下文无关文法

2.3.1上下文无关文法

VT

终结符集合(非空)

VN

非终结符集合(非空)，且VT

S

文法的开始符号，S

P

产生式集合(有限)，每个产生式形式为P

• VN=
• VN
• ，P
• VN，
• (VT
• VN)*
• 开始符S至少必须在某个产生式的左部出现一次。

第51页：2.3.1上下文无关文法（续）

2.3.1上下文无关文法（续）

• iE
• E+EE
• E*EE
• (E)

第52页：定义只含+

定义只含+

”也可以用“

:="表示，这种表示称为巴科斯范式(BNF)

• 定义只含+，*的算术表达式的文法G=<{i，+，*，(，)}，{E}，E，P>，其中，P由下列产生式组成：E
• “
• P
• 1P
• 2可缩写为P
• 1|
• 2|
• |
• n
• P
• n其中，“|”读成“或”，称为P的一个候选式。
• 表示一个文法时，通常只给出开始符号和产生式，如上例，可表示为：G(E)：E
• i | E+E | E*E | (E)
• iE
• E+EE
• E*EE
• (E)

第53页：直接推出

直接推出

• 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)

第54页：假定G是一个文法

假定G是一个文法

• 假定G是一个文法，S是它的开始符号。如果，则
• 1出发，经过一步或若干步，可以推出
• n。用表示：从
• 1出发，经过0步或若干步，可以推出
• n。所以：即或
• 称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。

第55页：假定G是一个文法（续）

假定G是一个文法（续）

• 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)是句型。

第56页：假定G是一个文法

假定G是一个文法

• c|AbG1(A)的语言?L(G1)={c，cb，cbb，
• }以c开头，后继若干个b

第57页：假定G是一个文法（续）

假定G是一个文法（续）

• ABA
• aA|aB
• bB|bG2(S)的语言?L(G2)={ambn|m，n>0}

第58页：1}的文法

1}的文法

• 1}的文法。G3(S)：S
• aSbS
• ab

第59页：2n}的文法

2n}的文法

• n
• m
• 2n}的文法。G4(S)：S
• aSb | aaSbS
• ab | aab

第60页：最左推导

最左推导

• 任何一步
• i+E
• i+i E+E
• E+i
• i+i
• 都是对
• 中的最左非终结符进行替换。最右推导：任何一步
• 都是对
• 中的最右非终结符进行替换。

第61页：2.3.2语法树与二义性

2.3.2语法树与二义性

• 用一张图表示一个句型的推导,称为语法树。
• (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)•一棵语法树是不同推导过程的共性抽象。G(E)：E
• i | E+E | E*E | (E)(i*i+i)

第62页：2.3.2语法树与二义性（续）

2.3.2语法树与二义性（续）

如果使用最左(右)推导，则一个最左(右)推导与语法树一一对应。 一个句型是否只对应唯一一棵语法树？

第63页：语言的二义性

语言的二义性

• 一个语言是二义性的，如果对它不存在无二义性的文法。
• i|E+E|E*E|(E)是二义文法。
• 可能存在G和G’，一个为二义的，一个为无二义的。但L(G)=L(G’)
• 二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的。
• 可以找到一组无二义文法的充分条件。

第64页：二义文法

二义文法

(表达式) | i无二义文法

G(E)：E

• G(E)：E
• i|E+E|E*E|(E)表达式
• 项|表达式+项项
• 因子|项*因子因子
• T | E+TT
• F | T*FF
• (E) | i

第65页：二义文法（续）

二义文法（续）

• 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)考虑句子(i*i+i)

第66页：二义文法

二义文法

• P形式的产生式2每个非终结符P必须有用处即：

第67页：2.3.3形式语言鸟瞰

2.3.3形式语言鸟瞰

• Chomsky于1956年建立形式语言体系，他把文法分成四种类型：0，1，2，3型。
• 与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。

第68页：2.3.3形式语言鸟瞰（续）

2.3.3形式语言鸟瞰（续）

• 其中：
• (VT
• VN)*且至少含有一个非终结符；
• (VT
• VN)*
• 1型(上下文有关文法，线性界限自动机)：产生式形如：
• 其中：|
• |
• |
• |，仅S
• 例外。

第69页：2.3.3形式语言鸟瞰

2.3.3形式语言鸟瞰

• 其中：A
• VN；
• (VT
• VN)*。
• 3型(正规文法，有限自动机)：产生式形如：A
• B或A
• 其中：
• VT*；A，B
• VN产生式形如：A
• B
• 或A
• 其中：
• VT*；A，B
• VN右线性文法左线性文法

第70页：2.3.3形式语言鸟瞰（续）

2.3.3形式语言鸟瞰（续）

四种类型描述能力比较0型1型2型3型

第71页：2.3.3形式语言鸟瞰

2.3.3形式语言鸟瞰

• 1}不能由正规文法产生，但可由上下文无关文法产生：G5(S)：S
• aSb| ab
• 1}不能由上下文无关文法产生，但可由上下文有关文法产生：G6(S)：S
• aSBC| aBCCB
• BCaB
• abbB
• bbbC
• bccC
• cc

第72页：2.3.3形式语言鸟瞰（续）

2.3.3形式语言鸟瞰（续）

• c
• |
• (a|b)*}不能由上下文无关文法产生，甚至连上下文有关文法也不能产生，只能由0型文法产生。
• 标识符引用
• 过程调用过程中，"形-实参数地对应性"(如个数，顺序和类型一致性)
• 现今程序设计语言的语言结构，用上下文无关文法描述就足够了。

第73页：2.3.3形式语言鸟瞰

2.3.3形式语言鸟瞰

• P36-6，7，8，9，10，11