网站鼠标特效代码,有哪些网站的搜索引擎,天津集团网站建设,泰州网站建设托管结构化操作语义 50年代是计算机语言兴起的年代#xff0c;这一阶段的早期#xff0c;计算机语言的设计往往要强调其方便的一面#xff0c;而比较忽略其严格的一面#xff0c;因而对语言的语义#xff0c;甚至语法#xff0c;未下严格的定义…结构化操作语义 50年代是计算机语言兴起的年代这一阶段的早期计算机语言的设计往往要强调其方便的一面而比较忽略其严格的一面因而对语言的语义甚至语法未下严格的定义从语言设计者和语言使用者对同一语言的语义缺乏共同的理解造成一定程度的混乱。后来在50年代和60年代间面向语法的编译自动化理论研究得到了很大发展使语法形式化研究的成果达到了实用化的地步。 语法形式化问题基本解决以后热门逐渐把注意力集中到语义形式化方面。60年代可以说是计算机语言形式语义学正式诞生的10年形式语义学的四大流派皆渊源于这一时期。其中1964年被认为是操作语义学和指称语义学的诞生年代Landin关于操作语义奠基性文章表达式的机械化处理和Strachey关于指称语义的奠基性文章关于形式语义学都问世与这一年。 操作语义的基本思想是用抽象的方法描述语言中每一成分的执行效果以免所描述的语义依赖于该语言实现时所用的具体计算机。通常地做法是设计一个抽象机定义一组抽象状态把语言的语法表示成抽象的形式。这种语义方法与语言实现道德关系比较紧密但是很难用数学方法处理而且对语义描述者个人使用的实现方法依赖很大。 抽象机是操作语义的核心它既是现实生活中具体计算机的抽象化又是理论研究中自动机的高级化——向着直接反映高级语言语义的方向靠近。人们希望抽象机结构简单合理便于验证语义。人们又希望抽象机功能足够强大便于描述高级语言的语义。由此产生了两个两个复杂度一个是抽象机本身的复杂度MC一个是从高级语言到抽象机语言的翻译复杂度TC。如何恰当地组合这一对矛盾的复杂度决定了抽象机设计的好坏。 1981年Plotkin提出了一种新的操作语义描述方法称为结构化的操作语义。Plotkin的基本思想是复合成分的操作语义应该可以归结为它的各个组成部分的操作语义。这样在证明语义正确定性时就可以使用结构化归纳法因此结构化操作语义的本质是把公理化方法引入操作引入操作语义之中。 一个语言的结构化操作语义由三部组成。第一部分是语法范畴也即在语义描述中所用到的基本语法成分例如一个简单语言的语法范畴可以包括一组变量一组常量一组函数标识符等等。第二部分是语法规则由于这里包括上下文有关的语法所以也叫静态语义。一般用 s 表示s是一个合法的语言成分用表示若s是一个合法的语言成分则t也是一个合法的语言成分。典型例子如 第三部分是动态语义由一组规则或称公理组成具体描述执行一个语言成分后状态起什么变化。规则的基本元素时组态常用表示意思是当前状态为待执行的程序是s。因此例如执行一个赋值语句的语义可以描述为 表示执行语句x:e后原来状态起了变化其中x原来的值被表达式e的值代替。 更多的规则取推理形式例如 表示若运行程序s的结果使s变为状态变为则运行程序s;t 的结果是使s;t 变为, 状态也是由变为。 结构化操作语义简称为SOSStructured Operational Semantics。为了给出一个程序设计语言的SOS描述应该同时列出三部分数据或公式包括语法范畴语言规则含静态语义及动态语义以后我们简称第二部分为静态语义。 语法范畴指的是该语言使用的所有语法符号。语法规则静态语义给出所有合法的语句结构其中基本规则以公理形式给出辅助规则以推理形式给出。动态语义以转换三元组的形式给出。 定义1以s表示任意语句表示状态此处状态可以理解为例如由全体变量值偶构成的集合则对偶称为一个组态表示当前状态为待执行语句为s此外也称为一个组态表示当前状态为但是无语句可以执行。 定义2以e表示任意表达式表示状态则表示在状态之下计算表达式所得的值。 定义3 是一个规则其中a为值 是一个规则表示从组态出发执行一定的语句后到达组态。当为空语句时上式右端为; 有限多个队则的并和交仍是规则 若和 是规则则 也是规则。表示若成立则亦成立 在一个具体的SOS中若某规则r恒成立且不为上式的形式则r称为公理。若有类如上式的规则成立则称为推理。 定义4三元组C,T,R称为一个转换三元组其中C是全体可能的组态的集合T是全体终结组态的集合R是全体公里和推理的结合简称公理集合。 终结组态是指形式为的组态或这样的组态对它们不存在使得 成立并且 。 BNF是描述编程语言的文法。自然语言存在不同程度的二义性。这种模糊不确定的方式无法精确定义一门程序设计语言。必须设计一种准确无误地描述程序设计语言的语法结构这种严谨、简洁、易读的形式规则描述的语言结构模型称为文法。最著名的文法描述形式是由Backus定义Algol60语言时提出的Backus-Naur范式Backus-Naur Form,BNF及其扩展EBNF。BNF能一种简洁灵活的方式描述语言的语法。BNF范式是一种用递归地思想来表述计算机语言符号集的定义规范具有如下的法则 ::表示定义 双引号里的内容表示字符 尖括号里的内容表示必选内容 | 竖线两边的是可选内容相当于or 现在以微型语言SL为例说明如何用SOS来描述。下面是SL语法的BNF形式一切细节均已略去。 语句:: 赋值|条件|循环|skip|语句;语句 赋值:: 变量:A表达式 条件:: ifB 表达式 then 语句 else 语句 fi 循环:: whileB 表达式 do 语句 od 下面给出它的各部分SOS描述。 语法范畴 变量集V元素为x,y,z; A表达式集 E,元素为 B表达式集元素为 ; 语句集S元素为s,t,u,v; 静态语义语法规则 动态语义转换规则 下面以一种稍微复杂的语言IMP一种简单的命令式语言进行说明 IMP语言的语法范畴 N,数集包括正整数、负整数和零带符号位的正负十进制数的集合 T,真值集T{true,false} Loc,存储单元集字母开头的字母数字串 Aexp,算术表达式集 Bexp,逻辑表达式集 Com,命令集 语法成分的元变量约定 n.m表示数集N中的元素 x,y表示存储单元集Loc中的元素 a表示算法表达式集Aexp中的元素 b表示逻辑表达式集Bexp中的元素 c表示命令集Com中的元素转载于:https://www.cnblogs.com/kexinxin/p/10147201.html
