形式语义操作语义ppt课件.ppt
《形式语义操作语义ppt课件.ppt》由会员分享,可在线阅读,更多相关《形式语义操作语义ppt课件.ppt(76页珍藏版)》请在三一办公上搜索。
1、程序设计语言的形式语义,The Formal Semantics of Programming Languages,操作语义,操作语义(operational semantics)通过描述程序语法构造在机器上的运行效果而定义程序的语义。以抽象机器为语义解释对象操作语义关注程序的运行效果是怎样得到的HOW,操作语义,操作语义概述(1)1960s,对编译程序所产生的目标程序标准化、形式化的愿望;自动机理论研究的兴旺时期抽象机。抽象机是操作语义的核心,既是具体机器的抽象化,又是自动机的高级化向着直接反映高级语言语义的方向靠近。MaCarthy,比较明确的提出用抽象机表达操作语义,并用它描述了ALGO
2、L60的一个子集的语义。1964年Landin,SECD(Stack,Environment,Control, Dump);扩充为SM(共享机),描述了ALGOL60完整语义。1968年,Knuth提出属性文法。,操作语义,操作语义概述(2)传统的操作语义的顶峰是VDL(维也纳定义语言),IBM的维也纳实验室,形式化定义PL/1语言 与此同时,英国赫斯利实验室对PL/1语言 的形式化被ANSI接受为标准(形式化程度较低,规范的自然语言描述)操作语义的另一个变种是变换语义。用分而治之的思想降低复杂度(抽象复杂度+翻译复杂度)。德国CIP小组提出的广谱语言。M5,M4,M3,M2,M11981,P
3、lotkin提出结构化的操作语义。把公理化方法引入操作语义中,基本思想是:复合成分的操作语义可以归结为其各个组成部分的操作语义。,IMP一种简单的命令式语言,IMP语言的语法范畴: N,数集,包括正整数、负整数和零带符号位的正负十进制数的集合 T,真值集,T=true, false Loc,存储单元集字母开头的字母数字串 Aexp,算术表达式集 Bexp,逻辑表达式集 Com,命令集,IMP一种简单的命令式语言,语法成分的元变量(约定):n,m表示数集N中的元素x,y 表示存储单元集Loc中的元素a 表示算术表达式集Aexp中的元素b 表示逻辑表达式集Bexp中的元素c 表示命令集Com中的元
4、素可以加上标或下标,IMP一种简单的命令式语言,算术表达式的抽象语法,IMP一种简单的命令式语言,逻辑表达式的抽象语法,IMP一种简单的命令式语言,命令的抽象语法,四种语句空语句赋值语句分支语句循环语句 程序命令、程序语句、程序,IMP一种简单的命令式语言,定义2.1:IMP语言的算术表达式、逻辑表达式及命令的抽象语法,IMP一种简单的命令式语言,IMP语言语法扩展:,为了讲课方便扩充了一些运算,非本质的。,IMP一种简单的命令式语言,例2.1 交换程序及其语法树:,IMP一种简单的命令式语言,例2.2 阶乘程序:,变迁系统,操作语义通过描述程序在抽象机器上的运行过程来描述程序的语义。运行过程
5、用程序状态和当前要执行的命令的变换序列给出。,格局(configuration),程序的运行过程就是格局的变换序列,变迁系统,状态:直观模型:存储单元的内容决定了当前的状态状态集合, :LocN(x)是状态下存储单元x 的值或内容,程序中所出现的变量,变迁系统,格局:程序状态是一个特殊的格局变迁系统(Transition System)(转换系统)变迁系统是二元组(X, R),在状态下将要执行c,语句为空,省略尖括号,变迁系统的状态集,其元素称为状态或格局,RXX状态之间的变迁关系,变迁系统,可以将IMP程序理解为运行在一个变迁系统上运行过程是程序状态和下一步要执行的程序语句的变化变迁关系(c
6、1,1) (c2, 2):程序(命令)c1在状态1运行后得到状态2且下一步要执行的程序是c2 。(c1,1) 2:程序(命令)c1在状态1运行后得到状态2且没有后续语句要执行(程序结束) 。,变迁系统,小结:描述IMP语言的操作语义:格局 程序(命令)c在状态下运行 程序终止的状态变迁关系定义IMP语言的操作语义就是定义适当格局之间的变迁关系通过定义IMP语言的每个命令所引起的变迁来完成,表达式的语义,表达式是IMP语言的最基本的语法成分,包括算术表达式和逻辑表达式程序执行是对程序状态的变换;而表达式的计算并不改变程序状态,可以看作是对程序状态的某种观察。状态 :LocN定义一个新状态,程序变
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式 语义 操作 ppt 课件
链接地址:https://www.31ppt.com/p-2002032.html