程序设计语言的刻划

《程序设计语言的刻划》由会员分享，可在线阅读，更多相关《程序设计语言的刻划（41页珍藏版）》请在金锄头文库上搜索。

1、,第2章 程序设计语言的刻划,程序设计语言需要有语言文本来精确地规定其功能、源程序的表示、语义和其限制，以及语用、语境等其他信息。 语言文本是实现者（厂商和开发人员）和使用者（编程人员）之间的界面。 不同程序设计语言文本的描写方法有相当大的差别。,2.1 程序设计语言的文本刻划,程序设计语言文本的共同点： （1）语言文本的标准化； 国际标准（ISO）、国家标准（GB）、军用标准（T）、部颁布标准、企业标准等。 程序设计语言的标准属于指导性标准，而不是强制性标准。 在当前的形势下不走标准的路是难以实现工业化发展的。,2.1 程序设计语言的文本刻划,（2）语言文本的格式和叙述相对刻板和严格，各个文

2、本本身有较为统一的书写风格。 （3）各个语法单位均有语法、语义等描述。 语法表示：BNF及其变形 语义部分：对语法的解释、语法元素的限制、语义的说明、语用和语境等，一般采用自然语言。,2.1 程序设计语言的文本刻划,2.1 程序设计语言的文本刻划,语言文本的兼容更新，需要保持风格的一致，包括语法语义部分的风格的一致。 有的语言一个文本仅允许为全集，有的允许以积木式组成若干合法的子集。 例如：Ada语言只允许为全集； COBOL语言允许有多级子集，且其组合情况最为复杂。 P27 表2.1,2.2.1 源程序 程序设计语言比自然语言简单但比形式语言复杂，形式语言是程序设计语言的理论基础。 在程序设

3、计语言中，句子即为正确的源程序。 正确：语法正确、语义合理、而语用、语境有适当解释。,2.2 程序设计语言和形式语言,语法正确的源程序：它可以由相应语法规则集产生的。如果语法是无歧义的，则语法正确的源程序有且仅有一棵语法树与之对应。 这里的语法是有序的，即所有的结点有先后次序，其树叶的有序排列（从左到右）即为源程序。 语法正确的源程序，其语义未必正确 如，某个名字未经说明，却在语句或表达式中出现。,2.2 程序设计语言和形式语言,2.2.2 程序设计语言的语法形式描述方法 一、BNF形式 BNF形式方法或其变种是使用最好最广的语法描述方法。是一种元语言。 元语言连接词： := (定义为) |（

4、或） , , +, *,2.2 程序设计语言和形式语言,元语言变量： 为语法单位 “汉字串2” “汉字串2”为语义限制词，用于限定或说明 。,2.2 程序设计语言和形式语言,元语言构成规则： 规则 = df元语言变量:=语法项 语法项 =df语法因子|语法因子 语法项 语法因子 =df元语言变量| |元语言变量语法因子 “元语言变量”的值是对象语言中的非终结符号。 在定义式的右端，“元语言变量”的值既可以是非终结符号也可以是终结符号。,2.2 程序设计语言和形式语言, A：表示A可以出现也可以不出现，但均符合语法，出现与否将可能影响其语义。 A：表示A出现一次。 A+：表示 A重复1次到无限多

5、次 * ：表示 A重复0次到无限多次 表示 A重复n次到m次,2.2 程序设计语言和形式语言,例如，Ada语言中的有关异常处理结构的定义如下； handled_sequence_of_statements := sequence_of_statements exception exception_handler exception_handler exception_handler := when choice_parameter_specification: exception_choice | exception_choice = sequence_of_statements choice

6、_parameter_specification := defining_identifier exception_choice := exception_name | others,2.2 程序设计语言和形式语言,exception when E1=处理程序1 when E2=处理程序2 when others=默认的处理程序,2.2 程序设计语言和形式语言,二、抽像语法 设有下列BNF表示的语法（设其中W为语句，B为条件，I为变量，E为表达式） W:= I:=E (用于定义 赋值语句) W:= if B then W else W (用于定义 条件语句) W:= while B do W

7、(用于定义 当语句) W:=W;W(用于定义顺序语句),2.2 程序设计语言和形式语言,上述语句可以用下列形式表示： Assignment(I,E) If (B,W1,W2) While(B,W) Block(W1,W2),2.2 程序设计语言和形式语言,三、属性文法 属性文AG是一个五元组。 AG=（D，V，S，A，P） 其中D是属性集合。（D1，D2f1,f2 ）是一个代数结构，具有属性域D1，D2 及部分函数f1,f2 。这些函数是在这些域的笛卡尔积上的操作。 V=Vn U Vt, 其中Vn是非终结符号， Vt 是终结符号,2.2 程序设计语言和形式语言,S是开始符号； A是属性文法符号

8、的集合，而每一个属性文法符号的形式为 其中xV,ai(i=1,n)Dj, ai前的表示或为（其后为继承属性），或为（其后为综合属性），P称为产生式集合。,2.2 程序设计语言和形式语言,语义可以从多角度分析： 从时间上可以分为静态语义和动态语义； 从机制上可以分成表达式语义、说明语义、过程语义、各种设施的语义； 从表达上可以分成形式语义和非形式语义. 静态语义：源程序本身进行分析时的语义 动态语义：源程序执行时的语义,2.3 程序设计语言的语义刻划,从本质上看，源程序program用于描述算法algorithm,两者是等价的。 设其输入值集为INPUT, 而其输出值集为OUTPUT，将prog

9、ram视为一个函数： Program: INPUT OUTPUT 设 input INPUT, 那么当存在 output OUTPUT,使得 output = program(input),2.3 程序设计语言的语义刻划,如果将program的语义视为：如何从输入值input一步一步进行计算而获得 输出值output,这整个过程可定义为操作语义（operational semantics） 如果将program的语义视为：若有正确输入input，则进行program计算，得出对应的 输出值output,而且这个输出值是正确的，这为公理语义（axiomatic semantics） input是

10、正确的programoutput是正确的,2.3 程序设计语言的语义刻划,刻划“input是正确的”和“output是正确的”一般引进前置条件（precondition）和后置条件（postcondition）,2.3 程序设计语言的语义刻划,2.3.1操作语义描述法 将语言成分所对应的计算机系统的操作作为语言成分的语义，称为操作语义描述法。 “每一步”中包含串行和时序两个重要概念。 设有；x:=y; y:=x; (语句) 执行点A 执行点B 执行点C （串行执行点） t1 t2 t3 (时间点，时序) O(t1) O2(t1) t1+ t1 t2+ t2,2.3 程序设计语言的语义刻划,串行

11、执行必须有：t1t2t3 t3=t2+ t2 = t1+ t1 + t2 =O(t2)=O2(t1) “O”表示下一时刻比较统一和简单。 正确的串行算法必须是一步一步执行的；在有限时间内执行有限步结束。因此遇见循环（递归）时必须刻划和有效控制其循环次数（或递归深度）的有限性。,2.3 程序设计语言的语义刻划,2.3.2指称语义描述法 看待一个程序的含义和着眼点不同。 公理语义看重整个过程或解释中的阶段是否满足前提（precondition）和目标（postcondition）; 操作语义看重执行过程； 指称语义则看重执行语言成分的效果。,2.3 程序设计语言的语义刻划,指称语义方法认为语言成分

12、的含义是语言成分本身所固有的，是不依赖所在计算机系统的。不应将语言成分的执行过程计入语言成分的语义中。 语言成分的语义是执行语言成分所得到的最终结果。这种最终效果被看作是语言成分所指称的外在物体，称为语言成分的指称物（denotation）。 以语言成分的指称物作为其语义，称为指称语义学。,2.3 程序设计语言的语义刻划,指称语义学的描述方法在定义语言的语义时，先确定指称物，然后给出语言成分到指称物的语义映像。 要求满足：每个语言成分均应有指称物，复合成分的指称物只依赖于它的子成分的指称物。 将语言中一类语法成分的指称物组成的集合称为论域（domain）,2.3 程序设计语言的语义刻划,2.3

13、.3公理语义描述法 用归纳命题PSQ来刻划程序S（包括语句或语句段）有如下含义：如果程序变元的初始值满足程序变元的谓词P，则程序S执行终止后的程序变元结果值满足程序变元的谓词Q。刻划P、Q采用断言语言，分别用于描述前提和目标。P称为前置条件，Q称为后置条件。,2.3 程序设计语言的语义刻划,例：PS1R,RS2Q PS1;S2Q,2.3 程序设计语言的语义刻划,2.3.4代数语义描述法（略）,2.3 程序设计语言的语义刻划,2.4.1 程序设计语言中的语用描述 程序设计语言的语用是指程序设计语言和用户之间的人机交互。 程序设计语言成分和设施的设立和实现需要考虑软件开发人员的需求和心理因素。 界

14、面成分和输入输出数据是最终用户主要的机机交互内容，应当认真讨论。 对语用的讨论，有利于语言设施和设计方法学的发展，对提高可靠性会有帮助。,2.4 程序设计语言的语用和语境描述,2.4.2 程序设计语言中的语境描述 程序设计语言的语境是指理解和实现程序设计语言及其源程序的环境，包括实现环境（编译环境和运行环境）在内。 如：程序移植性的好坏依赖于平台（软硬件）的兼容性和无关性，数的最大和最小值等都可归结为“语境”。,2.4 程序设计语言的语用和语境描述,对源程序的理解依赖于语境，其语境的分类可以用下列树型结构表示： 1.源程序语境 1.1句子语境 1.1.1隐式语境 1.1.2显式语境 1.2句内

15、语境 1.2.1语段语境 1.2.2审视点语境,2.4 程序设计语言的语用和语境描述,句子语境：把源程序作为一个整体的语境； 句内语境：源程序内部的语段的语境； 隐式语境：源程序中隐含的因素构成了句子的隐式语境，如所规定的数据格式。 句子显式外语境：源程序中的外部量构成句子显式外语境，如外部变量，外部函数等。 句子显式内语境：程序设计语言所预定义的名和其他成分，以及由实现系统所定义的名和量，在源程序中不需定义可直接使用，这些因素构成句子显式内语境。,2.4 程序设计语言的语用和语境描述,2.5.4等价性理解 （1）源程序级的功能等价 源程序 （SL） 中间语言程序1 （SML1） 中间语言程序

16、2 （SML2） 目标程序 （SOL） 从功能上看，即从执行效果的语义角度看，SL、SML1、SML2、 SOL是等价的。,2.5 程序设计语言的实现,2.5 程序设计语言的实现,可以写成：meaning(SL) =meaning(SML1) =meaning(SML2) =meaning(SOL),2.5 程序设计语言的实现,（2）不同语言之间的功能等价 对于算法A，采用两个程序设计语言PL1和PL2，所编出源程序SPL1(A)和源程序SPL2(A)，如果对于任意的INPUT,OUTPUT. SPL1(A)(INPUT)= SPL2(A)(INPUT)=OUTPUT 则称算法PL1和PL2是功能等价的。 如果对任何算法均能满足上面的定义，则称PL1和PL2是语言功能等价的。,2.5 程序设计