第四章程序语言的性质模型ppt课件

1、第四章 程序文语的性质言语的方式化模型BNF为描画程序设计言语的属性提供了一种很好的手段，但并不是充分的手段。BNF回答了程序看起来象什么，但没有回答程序是做什么的。方式化模型采用准确的数学模型来描写研讨对象，为研讨、分析和支配研讨对象提供严谨的数学工具和手段。本章将引见以下方式化模型：方式文法：乔姆斯基文法分级言语的语义：属性文法、指称语义程序的验证4.1 言语的方式化性质乔姆斯基分级文法言语的才干乔姆斯基分级文法文法由非终结符、终结符、开场非终结符、及产生式构成文法的类别3型文法：正那么文法，定义词法的模型2型文法：BNF文法，上下文无关文法1型文法：上下文有关文法0型文法：3型文法：正那

2、么文法为词法分析器提供模型。这类文法的大多数性质都是可断定的如，能产生什么样的串、给定串能否属于文法规定的言语、言语中的串能否有限等正那么文法可以产生形如an的串，其中a为有限字符序列正那么文法只能计数有限数常用于关键字或单词扫描2型文法上下文无关文法产生式的方式为：X , 其中可以是终结符和非终结符的恣意序列同样，这类文法的大多数性质都是可断定的如，能产生什么样的串、给定串能否属于文法规定的言语、言语能否为空等可用来计数和比较两个项，产生形如ancbn的串可以用堆栈来实现可用来自动产生程序的语法分析树2型和3型文法的相关问题都已根本上得到处理1型文法上下文有关文法产生式的方式为： , 其中恣

3、意非终结符串， 是终结符和非终结符的恣意序列，但中的符号个数应不多于的符号个数从开场符开场导出的串的长度是递增的在生成串时，需求运用固定数量的存储空间，例如识别上下文无关文法无法识别的串ancnbn上下文有关文法太复杂，很难用于程序设计言语人们对上下文有关文法的很多特征还不太清楚0型文法非限定型文法对产生式的方式 没有任何限制可用来识别恣意可计算的函数其大多数性质都是不可断定的前往不可断定性不同类型的文法越来越复杂，产生的言语也越来越复杂，但能否阐明计算机处理问题的才干可以越来越强，没有限制？例如：能否编写一个C言语程序来判别另一个C言语程序能否终了？但这根本上是不能够的，这不是编程人员的问题

4、，而是由于计算机所基于的数学模型本身的局限性而导致的。图灵机普通来说，用一种言语编写的程序也可以用其他另一种言语来实现。那么能否存在某个程序，只能用某种言语来实现，而用其他言语就无法实现？假设没有，那么有哪些程序是其它程序设计言语无法表示的，为什么还需求那么多种不同的言语？假设我们将可以表示一切计算的言语都称为通用言语，那么是不是一切言语都是通用言语？假设是，能否存在更简单的通用言语？图灵机的构造图灵机是一种用来定义可计算函数的笼统计算机图灵机只需一个单一的数据构造，即一个称为“带子的可变长线性数组带子被分为很多格，每格上只包含一个字符图灵机还有一个指针变量，称为“读出头，它总是指向带子上的某

5、个格。图灵机的操作图灵机只提供几个简单的操作：读出头所指定位置的字符可以被读出或被修正。程序可以根据读出的值进展转移。读出头可以左右挪动。假设读出头挪动到带子的最末端，那么自动在带子上加上一格，并赋予一个空字符作为初始值。图灵机的运转图灵机开场运转时，带子上存放输入数据，读出头指向输入数据的最左端的字符；图灵机根据预先编好的操作序列读写带子上的数据、或挪动读出头；假设最终可以停机，那么带子上的内容就是最后的输出结果。图灵机的才干恣意可计算函数都可以用图灵机计算出来Church论题图灵机等价于0型文法确定型图灵机等价于非确定型图灵机。停机问题能否存在某个通用的算法，它可以断定恣意给定的图灵机在恣

6、意的输入下能否停机？停机问题是不可判别的，即不存在这样的通用算法。恣意一个不可判别的问题，都等价于停机问题。结论：任何一种程序设计言语都能够替代其它言语程序设计言语不存在质的区别，只需量的区别，如能否优美、易用、高效等任何一种程序设计言语都有它存在的理由前往4.2 言语的语义程序设计言语根本上都是以上下文无关文法(特别是 LR(k) 文法)的中心设计的。但语法分析曾经不再是人们感兴趣的研讨问题了。如今的问题是如何确定程序的含义即语义。言语的语义言语的手册必需定义言语中每个构造的含义，包括单独构造的含义以及和其他构造组合时的含义。言语提供了不同构造，用户为了写正确的程序，预测语句的执行效果和实现

7、者正确地实现言语需求这些构造的准确定义。大多数言语中，方式文法用于定义语法，一段文字或例子用于定义语义，但定义是不准确的，有二义性，不同作者能够有不同了解。语义定义问题还是实际研讨的目的，但至今没有令人称心的解答。已有各种方式方法用于语义定义。语义建模1文法模型对定义言语的BNF文法进展扩展，给出程序的语法分析树，从树中抽取出附加信息。属性文法便是抽取附加信息的一种方式。语义建模2命令或操作模型定义程序如何在某虚拟机上执行。通常描画为一自动机，但比语法用的简单自动机远为复杂。自动机有内部形状对应程序执行时的内部形状，包括一切变量的值、执行程序本身、以及各种系统定义的数据构造。语义建模2命令或操

8、作模型一组方式定义的操作用于刻划自动机内部形状如何改动。此外还需定义程序文本如何翻译成自动机的初始形状。言语的操作定义对言语如何实践执行给出了相当直接的笼统。也能够提出一个更笼统的模型，作为言语的软件解释的根底。70年代的VDLVienna Definition Language是一个操作方法。它扩展语法分析树已包含机器解释器。计算的形状是程序树加上描画机器中一切数据的树。每条语句的执行使树的形状发生变化。语义建模3作用型模型试图直接构造每个程序的函数的定义，采用层次式的构造方式。程序中每个根本的或程序员定义的操作代表一个数学函数。言语的程序控制构造用于将这些函数复合为更大的序列，代表表达式和

9、言语。语句序列和条件分叉表示为个体函数构造而成的函数。循环通常表示为递归函数。最终，为整个程序导出一个完好的函数模型，指称语义归于此类。语义建模4公理模型运用谓词演算，每个语法构造的语义被描画为公理或推导规那么，用于导出构造的执行效果。从一个初始假设开场，假设输入变量满足一定的约束，在程序语句执行后，运用公理和推导规那么来推导其他变量值需满足的限制，最终，程序的结果被证明满足希望的约束描画了它们的值和输入值的关系。如Hoare的公理语义。 语义建模5规约模型描画实现程序的各个函数的关系，只需我们可以证明一个实现符合了一切的函数间的关系，那么称实现相对于规约是正确的。代数数据类型是方式规约的一种

10、方式。例如：实现栈的程序，S表示栈，那么有公理，pop(push(S,x)=S任何一个实现假设能坚持这种关系，那么称是栈的正确实现。语义模型小结上述各种方式语义模型各有优点，但均不能称为完全适用的和适用的，各有其适宜范围。操作语义为言语的实现提供了一种方式模型，但对用户来说太细节公理语义易于了解，但很难用来定义复杂的程序设计言语，且缺乏对言语实现的支持前往语义建模属性文法这是最早的开发语义模型的任务之一。其思想是对分析树中的每个结点关联一个函数，从而给出结点的语义内容。属性文法的创建过程是为文法中的每一条规那么都定义相关的语义函数。承继属性是一个函数，它将树中非终结符值和树中更高层的非终结符值

11、相关联。换言之，任何规那么右端的非终结符的函数值是左端非终结符的函数。综合属性是一个函数，它将左端非终结符和右端非终结符的值相关联，这些属性在树中向上传送信息，即从树中下层信息进展“综合。 属性文法例：思索算术表达式的简单文法。ET|E+TTP|TPPI|(E)其语义经过文法中非终结符间的关系集合定义。如：下面函数生成该文法生成的恣意表达式的值：产生式属性EE+TValue(E1)=V(E2)+V(T)ETV(E)=V(T)TTPV(T1)=V(T2)V(P)TPV(T)=V(P)PIV(P)=数I的值P(E)VP=VE 属性文法以下图是一个属性树，它给出了表达式2+4(1+2)值 属性文法属

12、性文法可用于在语法树中传送语义信息。例如，声明信息可以经过言语的声明产生式搜集。沿树向下传的符号表信息可用于生成表达式代码。下面属性可加到非终结符和来创建一个程序中声明的名字集合。产生式属性:= decl_set(declaration1)=declaname(decl) decl_set(declaration2):=decl_set(declaration)=decl-name(decl):=declare xdecl-name(decl)=x(decl):=declare ydecl-name(decl)=y(decl):=declare zdecl-name(decl)=z这是综合属性

13、，包含程序中声明的名字集合。该属性可以沿树向下传送，成为承继属性，用于正确地生成数据的代码。属性文法的运用首先创建语法分析树。属性文法假设他曾经知道表达式是如何推导出来的，它并不关怀是如何分析推导出来的。定义属性的函数可以是恣意给定的，因此定义属性的过程完全是手工完成的。假设只需综合属性，并且文法是 LR(k)，那么，属性文法可以用来在语法分析时自动产程中间代码。这就是 YACC 如何任务的，它利用属性文法来计算一切非终结符的值。在构造分析树时，非终结符的信息逐层向上传送给分析树上层的非终结符。语法分析终了，一切属性的值将计算出来。前往指称语义指称语义是一种用来描画程序设计言语的语义的作用型语

14、义模型指称语义基于-演算-演算-演算是一种和图灵机的计算才干相当的实际计算模型-演算可以作为程序设计言语的函数调用的模型Algol和Lisp都采用来-演算的函数调用语义指称语义是对-演算的扩展，它将-演算扩展为一种通用的数据类型实际-演算的表达式-表达式可以递归地定义如下：变量名为-表达式假设M为一个-表达式，那么x.M也是一个-表达式假设F和A都是-表达式，那么(F A)也是-表达式，其中F为操作符，A为操作数。方式语法：-expr := id | id.-expr | (-expr -expr)x相当于声明参数变量x，没有声明的变量为自在变量，否那么为约束变量。x.M相当于函数声明，其中x

15、相当于M的参数。例如：x x.x x.(xy) x.y (x.x y.y)-表达式的操作-表达式只需一种操作：约简(F A)约简相当于将A作为实践参数，交换F的方式参数的一切出现(x.M A) M，相当于用A交换M中x的一切自在出现。例如：(x.x y) y(x.(xy) x.x) x.x y y留意：约简并不一定能简化原来的表达式(x.(xx) x.(xx) (x.(xx) x.(xx) 指称语义指称语义的根本思想是定义一个语义函数指称函数，把程序的意义映射到某种意义明晰的数学对象就像用中文解释英文作为被指的数学对象可以根据需求选择对于简单的程序文语，一种很自然的选择是把程序的语义定义为指称

16、为从形状到形状的函数。定义语义就是定义好每个程序对应的函数。程序的形状由标识符到值的映射集合构成S = id | value, 指称语义表达式的语义e S val语句的语义s S S程序的语义m val val指称语义设为程序的当前形状表达式的语义常数：n = n变量：x = (x)算术表达式：e1 + e2 = e1 + e2语句的语义赋值语句：x = e = x | e复合语句：s1; s2 = s2(s1)条件语句：if b then s1 else s2 = if b then s1 else s2程序的语义m val val前往程序验证在编程时，人们越来越关怀程序的正确性和可靠性。人

17、们在设计程序设计言语时，也希望经过添加新的特征来加强程序的正确性和可靠性。我们可以用程序语义，按以下方式来讨论程序的正确性问题：给定程序P，其含义是什么？即，它的规范描画S是什么？给定规范描画S，开发实现了该规范描画的程序P规范描画S和程序P能否完成了一样的功能执行了一样的函数？相当于语义建模问题软件工程的中心问题程序验证的中心问题程序验证测试不能保证程序的正确性假设能找到不依赖于测试的保证程序正确性的方法，产生的程序就能更加可靠：程序计算了一个函数假设能给出该函数的规范描画，并且可以根据程序知道它究竟计算了一个什么样的函数，那么，假设可以证明程序所计算的函数与给定的函数等价或一样，就能证明程

18、序的正确性，而不需再测试。方式化的规范描画任一程序都可以表示成流程图基调：函数名：定义域 值域 fun1: S1 and P1 S3 fun2: S1 and not(P1) S3 fun3: S3 and not(P3) S4 fun4: S3 and P3 S4 S2 and P2 = S4 S2 and not(P2) = S3P1P2P3 Fcn1Fcn4Fcn3Fcn2S1S2S3S4方式化的规范描画续这样，程序可以看成是一个定义在其根本成分上的复杂函数：C(fun1, fun2, fun3, fun4, p1, p2, p3): S1 S4假设我们可以方式化地推导出上述关系，那么我

19、们就可以从数学上证明，给定S1, 程序将终止于形状 S4。但是：证明非常困难。另外，在证明时，我们总是想证明程序和某个给定的方式化规范等价，但问题是，假设没有给出规范描画，“程序能否正确？能够就没有了意义。公理化验证用谓词逻辑公式来描写程序的语义、用谓词演算来验证程序的正确性。 Tony Hoare 在1969年提出的。每个程序都遵照某种方式化的公理定义。实证Validation: 经过一系列测试数据的测试，展现程序满足了其规范描画。验证Verification: 根据程序构造，经过方式化的讨论，展现程序满足了其规范描画。Validation普通以为需求执行程序，而 verification不

20、需求。谓词逻辑公理P1SP2 表示假设 P1 为真，那么在 S 执行并终止后，P2 将为真。假设 A 为真，那么 B 也为真。逻辑公理：组合顺序1顺序2PS1Q,QS2R 组合语句PS1;S2RPSR, RQ 添加后置条件PSQPR, RSQ 添加前置条件 PSQ语句类型的公理条件语句1条件语句2While循环语句赋值语句PBSQ, Pnot(B)Q Pif B then SQPBS1Q,Pnot(B)S2Q Pif B then S1 else S2QPBSPPwhile B do SP not(B)，其中 P 为不变式P(e)x:=eP(x)，P(x) 为 x 的谓词。公理化的程序证明给定

21、程序：s1; s2; s3; s4; sn 及其规约：P 和 QP 为前置条件Q 为后置条件经过证明以下的谓词来证明 Ps1;snQ：Ps1p1p1s2p2 pn-1snQ反复运用组合公理，产生：Ps1; ; snQ例子B=01X:=B2Y:=03while X0 do4 begin5 Y:= Y+A6 X:= X-17 endY=AB即，给定非负的 B，证明当程序终止时， Y=A*B.证明过程概要普统统过回溯来进展。首先，找到循环的不变式：Y 为乘积的一部分，X 为剩下的乘数因此，Y 和 X*A 必需是所需的乘机，即不变式Y+X*A = A*B 就是建议的不变式可以试着用 (Y+X*A=A*

22、B and X=0)作为不变式 证明赋值语句公理(6): (Y+(X-1)A=A*B and X-1=0) X:=X-1 (Y+X*A=A*B and X=0)赋值语句公理(5): (Y+A)+(X-1)A=A*B and X-1=0) Y:=Y+A (Y+(X-1)*A=A*B and X-1=0) 组合公理 (5,6): (Y+A)+(X-1)*A=A*B and X-1=0) Y:=Y+A; X:=X-1 (Y+X*A=A*B and X=0)数学定理: Y+X*A=A*B and X0 (Y+A)+(X-1)*A=A*B and X-1=0)顺序语句公理: Y+X*A=A*B and

23、X0 Y:=Y+A; X:=X-1 (Y+X*A=A*B and X=0)数学定理: (Y+X*A=A*B and X=0) and (X0) Y+X*A=A*B and X0顺序语句公理: (Y+X*A=A*B and X=0)and (X0) Y:=Y+A; X:=X-1 (Y+X*A=A*B and X=0) 用 * 来替代While循环语句公理: * Y+X*A=A*B and X=0while X0 do Y:=Y+A; X:=X-1 (Y+X*A=A*B and X=0) and not(X0)证明 (续)数学定理: (Y+X*A=A*B and X=0) and not(X0)

24、(Y+X*A=A*B and X=0) Y=AB顺序语句公理: Y+X*A=A*B and X=0while X0 do Y:=Y+A; X:=X-1 Y+A*B赋值语句公理: 0+X*A=A*B and X=0 Y:=0 Y+X*A=A*B and X=0赋值语句公理: 0+B*A=A*B and B=0 X:=B 0+X*A=A*B and X=0) 组合公理: 0+B*A=A*B and B=0 X:=B; Y:=0 Y+X*A=A*B and X=0)数学定理: (B=0) 0+B*A=A*B and B=0顺序语句公理: B=0 X:=B; Y:=0Y+X*A=A*B and X=0

25、)组合公理: B=0 program Y=A*B公理化验证小结需求为言语的一切特征建立公理，能否也为简单数组、过程调用、参数等建立公理？即使是要证明小程序也很困难，要证明大型程序就更困难了。还不能很好地处置非数学方面的问题，处置起来极端困难。很难自动化，而手工又会导致大量错误。但是准确，可以清楚地域别“程序是什么以及“程序是如何处理问题 它是大多数其他验证方法的根底，包括半方式化的规范表示法。对于关键运用，付出的代价还是值得的。程序验证只需程序正确性的验证过程可以自动化，程序验证才有实践意义但要证明那些没有构造化的程序、以及那些具有复杂构造的程序的正确性，非常困难，根本上是不能够的。程序验证任

26、务的研讨成果通常用来指点程序设计言语的设计例如，在C+中加断言等。ML 概述ML (元言语) 是一种函数式言语，其程序的方式与 C 或 Pascal 类似。 ML 由 Robin Milner 于1970年代中期开发，是一种机器辅助方式化证明的机制。ML 也可以作为一种通用符号支配言语。1983，该言语中参与了模块等概念，并经过重新设计，构成了如今的规范ML。 ML 是一种具有静态类型、强类型、和函数式执行的言语，但类型不用由程序员来指定。ML 程序由假设干个函数定义构成。每个函数的类型是静态的，函数可以前往恣意类型的值。由于是函数型的言语，变量的存储与C或Fortran言语的很不一样。ML

27、可以经过其类型系统支持多态，还支持数据笼统。ML 程序例子 1 fun digit(c:string):int = ord(c)-ord(0); 2 (* Store values as a list of characters *) 3 fun SumNext(V) = if V= then (print(n Sum=); 0) 4 else (print(hd(V); 5 SumNext(tl(V)+digit(hd(V); 6 fun SumValues(x:string):int= SumNext(explode(x); 7 fun ProcessData() = 8 (let val infile = open_in(data.sml); 9 val count = digit(input(infile,1) 10 in 11 print(SumValues(input(infile,count) 12 end; 13 print(n);把一个列表颠倒过来的函数datatype list a, b, c, d, ehd(x)：列表的头，或第一个元素tl(x)：列表的尾，或除第一个元素外的元素x:y 表示头为 x，尾为 y 的列表xy 表示衔接列表 x 和 yfun reverse(L) = if L = nil then nilelse reverse(tl(L) h