（计算机软件与理论专业论文）一个过程式语言操作语义的设计与可视化实现.pdf

摘要 形式语义学是计算机软件与理论专业的研究生学位课，在研究生计算机教育中 占有重要的地位。它是程序设计理论的组成部分，以数学为工具，利用符号和公式精确 地定义和解释计算机程序设计语言的语义，使语义形式化的学科。为了让学生能够领会 相关概念和方法，加深理论认识的同时提高实践能力，在这种理论性极强的课程中增加 实践环节并提供可视化工具十分有必要。 本论文就是为了更好地帮助学生深入理解程序设计语言的形式语义而设计，采用递 增的方式，按照不同难度级别定义一系列过程式语言，包括：表达式、语句、输入输 出语句、变量声明、嵌套语句、过程函数等级别。采用抽象机方法定义该语言的操作 语义，给出它们的抽象语法及形式定义，设计相应语言的抽象机，并可视化抽象机的执 行过程，实现过程式语言操作语义的可视化演示。 本系统可以应用于课堂教学及网络教学当中，作为辅助教学工具，辅助教师进行课 堂教学，为学生自主学习提供良好的支撑环境。从而用形象的图形界面为学生搭起通向 掌握抽象思维方法的桥梁。 关键词：过程式语言；操作语义；可视化演示 a b s t r a c t f o r m a ls e m a n t i c si sa ni m p o r t a n ts u b j e c ti nc o m p u t e rs c i e n c e i ti st h et h e o r e t i c a l f o u n d a t i o no fp r o g r a ml a n g u a g ed e s i g n u s i n gm a t h e m a t i c s 弱t o o l ，i tu t i l i z e ss y m b o l sa n d f o r m u l a st od e f i n ea n di n t e r p r e tt h es e m a n t i c so fp r o g r a ml a n g u a g ea c c u r a t e l y i ti se s s e n t i a l t oi n c r e a s ep r a c t i c e sa n dp r o v i d eav i s u a l i z i n gt o o li ns u c hc o u r s e t h ei n t e n t i o ni st oh e l p s t u d e n tc o m p r e h e n dc o n c e p t sa n dm e t h o d s ，e n h a n c et h e o r e t i ca n dp r a c t i c a la b i l i t y t h i ss y s t e mi sd e s i g n e df o rs t u d e n t st oc o m p r e h e n df o r m a ls e m a n t i c so fp r o g r a m m i n g l a n g u a g e w ed e f i n e das e r i e s o fp r o c e d u r a ll a n g u a g e si nad i f f i c u l t y 。i n c r e a s i n gw a y , i n c l u d i n ge x p r e s s i o n s ，s t a t e m e n t s ，i n p u ta n do u t p u ts t a t e m e n t s ，v a r i a b l ed e c l a r a t i o n s ，b l o c k s t a t e m e n t s p r o c e d u r ea n df u n c t i o n ，e t c ，u s e dt h ea b s t r a c tm a c h i n et od e f i n et h eo p e r a t i o n s e m a n t i c so fp r o c e d u r a lp r o g r a m m i n gl a n g u a g e w ep r e s e n t e dt h e i ra b s t r a c ts y n t a xa n df o r m a l d e f i n i t i o n s ，d e s i g nt h e i ra b s t r a c ta n dd e m o n s t r a t et h ep r o c e s s i n go f t h i sa b s t r a c tm a c h i n ei na v i s u a l i z i n gw a y a n df i n a l l yv i s u a li m p l e m e n t e df o rt l l eo p e r a t i o ns e m e n t i c so r i e n t e d t ot h ep r o c e d u r e l a n g u a g e s t h i ss y s t e mc o u l db ea p p l i e dt ot h et e a c h i n ga n dn e t w o r kt e a c h i n go ff o r m a ls e m a n t i c s a sat e a c h i n ga s s i s t a n tt o o l ，a n di tc a ns u p p o r tt e a c h e r si nt h ec l a s s r o o mt e a c h i n ga n dp r o v i d e ag o o ds u p p o r t i n ge n v i r o n m e n tf o rs t u d e n t si ns e l f - s t u d y i n g t h e r e b y , i ts e t su pab r i d g e l e a d i n gt ot h em a s t e r yo fa b s t r a c tt h i n k i n gm e t h o d sf o rs t u d e n t sw i t ht h ev i s u a lg r a p h i c a l i n t e r f a c e k e yw o r d s ：p r o c e d u r el a n g u a g e ；o p e r a t i o n a ls e m a n t i c s ；v i s u a l i z e dp r e s e n t a t i o n h 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究工作所取 得的成果。据我所知，除了特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果。对本人的研究做出重要贡献的个人和集体，均已在文 中作了明确的说明。本声明的法律结果由本人承担。 学位论文作者签名：- 三至冱豳虹同期：2 卑l l 虹 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即： 东北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版， 允许论文被查阅和借阅。本人授权东：i v , n 范大学可以将学位论文的全部或部分内容 编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编本学位 论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 日期： 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名： 日期： 电话： 邮编： 侈口， 卿上 弛殍 东北师范大学硕士学位论文 第一章引言 本章主要介绍了本论文的研究背景、研究目的，目前研究的现状和本论文的主要工 作，以及本论文的组织结构。 1 1 论文研究的背景 形式语义学是计算机软件与理论专业的研究生学位课，在研究生计算机教育中 占有重要的地位。它是程序设计理论的组成部分，以数学为工具，利用符号和公式，精 确地定义和解释计算机程序设计语言的语义，使语义形式化的学科。由于该课程理论性 极强、内容抽象，教师上课使用常规的板书或幻灯投影均难以有效地展示其理论的抽象 性和动态性，学生在理解上存在一定困难，很难达到预期的教学效果。为了让学生能够 领会相关概念和方法，加深理论认识的同时提高实践能力，所以在该课程中增加实践环 节并提供可视化工具十分有必要。 本论文就是为了更好地帮助学生深入理解程序设计语言的形式语义而设计，定义了 一个面向过程的程序设计语言，以该语言为处理对象，实现该语言操作语义的可视化动 态演示。 1 2 论文研究的主要目的 本论文可以应用于形式语义学的教学当中，作为教学辅助工具，辅助教师进行课堂 教学，为学生自主学习提供良好的支撑环境，激发学生的学习兴趣，加深学生对程序设 计语言的理解，培养学生对程序设计语言的分析、设计、实现等方面的能力和提高抽象 能力，从而丌发高质量程序。 1 3 论文完成的主要工作 本论文采用抽象机方法定义过程式语言的操作语义。操作语义是用抽象的方法形式 地描述程序如何执行，从操作的角度定义语言的语义，给出程序的计算规则。抽象机方 法根据给定的语言，定义一个抽象机，并使得它能够按照规则执行将要定义的语言的程 序。由于抽象机根据语言成分的不同，抽象机的结构也不相同，语言难度越高，抽象机 越复杂，所以，本文采用递增的方式，按照不同难度级别定义一系列过程式语言，包括： 表达式、语句、输入输出语句、变量声明、嵌套语句、过程函数等级别，给出它们的 抽象语法以及形式定义，然后对其进行词法分析，语法分析，根据语法分析输出的抽象 语法结构定义相应语言的抽象机，实现抽象机的各个组成部分，并可视化抽象机的执行 东北师范大学硕士学位论文 过程。 1 4 论文组织结构 第一章主要介绍了本论文的研究背景、研究目的，目前研究的现状和本论文的主要 工作，以及本论文的组织结构。 第二章主要介绍了过程式语言形式语义的发展历史及现状、形式语义的研究方法和 研究操作语义学的重要性和操作语义学的产生背景、发展历史及操作语义学的概念，同 时介绍了操作语义学中用到的重要论域，及基于抽象机的方法定义程序设计语言的操作 语义。 第三章主要介绍了本论文定义的过程式语言s l 语言语法定义，并给出s l 语言源 程序示例。 第四章主要介绍了过程式语言操作语义的定义。按照不同难度级别，采用递增的方 式定义一系列过程式语言，包括：表达式、语句、输入输出语句、变量声明、嵌套语句、 过程函数等级别，给出它们的抽象语法以及形式定义。 第五章主要介绍了过程式语言操作语义可视化系统的总体设计，由词法分析系统、 语法分析系统、操作语义系统和演示系统组成。 第六章主要介绍了过程式语言操作语义可视化系统的实现。 第七章主要介绍了本论文的全文总结和学习体会。 2 东北师范大学硕士学位论文 第二章概述 2 1 过程式语言形式语义的发展历史及现状 程序设计语言是人们用来和计算机系统进行通讯、并控制其工作的人工语言。为了 正确、有效地使用程序，必须了解语言中各成分的含义，并且要求计算机系统执行这些 成分所产生的效果和其含义完全一致。但是程序设计语言的语义通常是由设计者用一种 自然语言非形式地解释，实施者和使用者依据各自的理解实现和使用这种语言。由于自 然语言本身存在歧义现象，非形式的解释又不严格，故用这种方法解释语义容易造成设 计者、使用者和实施者对语义的不同解释，影响语言的正确实施和有效使用。 人们对语义的精确解释的要求产生了形式语义学，形式语义学的研究开始于六十年 代初，在程序设计语言a l g o l 6 0 的设计中，第一次明确区分了语言的语法和语义，并 使用b n f 成功地实现了语法的形式描述，语法的形式化大大刺激了语义形式化的研究， 围绕a l g o l 6 0 的语义出现了形式语义学的早期研究热潮。 美国斯坦福大学j m e c a r c h y 教授在国际信息加工联合会一九六二年大会上作了著 名的报告一一“通往计算的数学科学”，系统地阐述了程序设计语言语义形式化的重要 性，和程序正确性、语言的正确实施等的关系，并提出在形式语义学研究中使用抽象语 法和状态向量等基本方法。 二十多年来，形式语义学 i - s 的研究取得了巨大的进步。它对程序设计语言的设计、 使用和实施产生了深远的影响，语言的形式语法和形式语义( 统称语言的形式定义) 已经 成为程序的必要组成部分。 2 2 过程式语言形式语义的主要研究方法 1 操作语义学 操作语义着重模拟数据加工过程中计算机系统的操作。用抽象的方法描述语言成分 的执行效果，模拟程序在执行过程中如何进行数据处理。通过语言的实现方式定义语言 的语义，将语言成分所对应的计算机的操作作为语言成分的语义。操作语义学使用抽象 机、抽象解释器和规约方法来定义程序设计语言的语义。 2 指称语义学 通过执行语言成分所要得到的最终效果来定义该语言成分的语义。指称语义学方法 认为语言成分的含义是语言成分本身固有的，不依赖于具体实现该语言成分的计算机。 对同一种语言成分，不同的计算机的执行实现过程可以不同，但所产生的最终效果应该 是相同的。这种最终效果被看作是语言成分所指称的外在物体，称作语言成分的指称物。 3 东北师范大学硕士学位论文 指称物多为数学对象，如整数、集合、函数等。指称语义学方法在定义语言的语义时， 先确定指称物，然后给出语言成分到指称物的语义映射，这种映射必须满足两个条件： 每个语言成分都对应有指称；复合成分的指称只依赖于它的子成分的指称。论域理论是 指称语义学方法的数学基础。 3 公理语义学 通过使用数学中的公理化方法，用公理系统定义程序设计语言的语义。另外，公理 语义学还研究和寻求适用于描述程序语义、便于语义推导的逻辑语言。例如，用时态逻 辑定义的语言的公理语义又称为时态语义。典型的公理语义方法是h o m e 公理系统。 4 代数语义学 用代数公理刻划语言成分的语义，只要研究抽象数据类型的代数规范。抽象数据类 型的代数规范通过构造算子和一组有关运算的代数公理刻划类型操作的行为。在论证这 种规范满足协调性和完全性的基础上，通过寻找适当的模型代数，可以定义一个抽象类 型的不同层次的语义，如初始语义、终止语义等。然后就可以用普通的代数方法论证规 范的正确性和实现的正确性。 2 3 过程式语言操作语义研究的重要性 操作语义学的基本思想是用抽象的方法描述语言成分的执行效果，从实现的角度， 通过程序的执行过程来定义程序设计语言的语义，模拟程序在执行过程中如何进行数据 处理，这种语义方法与语言的实现关系比较紧密，表示形式直观，便于理解，因此作为 对语言研究描述的基础语义，被科研者广泛使用。 2 4 操作语义学产生背景 操作语义的研究从6 0 年代初开始。当时，程序设计语言的兴起促进了编译程序的 发展，后者把程序设计语言的语义问题推到一个关键的位置上，每个编译程序加工一个 源程序后产生的目标程序能否符合该源程序的语义? 这里不但指形式上符合，而且包括 该目标程序在不同的显示计算机上运行时能否产生相同的效果，还包括多个编译程序对 同一个源程序的n - v _ 后产生不同目标程序的情形，即这些目标程序运行能否产生相同的 效果，这个问题导致了人们对编译程序及其所产生的目标程序标准化、形式化的愿望。 同时，六十年代又值自动机理论研究的兴旺时期，人们很自然地想到自动机研究中 使用的方法可以用来形式地描述一个程序的执行过程。于是产生了抽象机的思想。抽象 机是操作语义的核心，它既是现实生活中具体计算机的抽象化，又是理论研究中自动机 的高级化向着直接反映高级语言语义的方向靠近。 4 东北师范大学硕士学位论文 2 5 操作语义学的发展历史 操作语义学的基本思想来源于程序的实施。但第一次系统地、严格地陈述这一途径 是英国学者p j l a n d i n ，他于一九六四年一月发表了“表达式的机械化求值一文，文 中使用了“栈一环境控制一外存”抽象机器，定义了表达式操作语义。 i b m 公司维也纳实验室六十年代在研究程序设计语言( 简称v d l ) 。一九七四年欧 洲计算机制造联合会和美国国家标准局正式建议使用v d l 定义的p l i 的一种标准。 1 9 8 1 年，p l o t k i n 提出了一种新的操作语义描述方法，称为结构化的操作语义。p l o t k i n 的基本思想是：复合成分的操作语义应该可以归结为他的各个组成部分的操作语义。这 样，在证明语义j 下确性时就可以使用结构归纳法，因此，结构化操作语义的本质是公理 化方法引入操作语义中。 2 6 操作语义学概念 操作语义学【卜5 1 是用抽象的方法形式地描述程序如何执行；从操作的角度定义语言 的语义，给出程序的计算规则。主要实现方法有解释器方法、抽象机方法和归约方法。 2 7 重要论域 定义程序设计语言的形式语义要用到一些论域，在这些论域上的操作( 函数) ，是 程序设计语言形式语义的关键。重要论域有静态环境、动态环境和值。 2 7 1 静态环境 静态环境用来记录标识符的静态属性，如：类别，类型，地址，可由源程序得到， 不随着程序的执行而改变，用于进行记录、查找和检查标识符的静态属性信息； 根据程序设计语言的特点，静态环境的定义会有所不同， 通用的定义是：s e n v = i d e _ a t t r i b u t e( 映射类型) 语言不同，a t t r i b u t e 的定义会不同； 通常用符号作为表示静态环境的变量，s e n v ； 举例：i d e _ a t t r i b u t e a t t r i b u t e = c o n s t ( i n t ) + v a r ( t y p e ) + t y p e ( t y p e ) 常量变量类型 静态环境主要处理：标识符声明部分、建立新的局部静态环境、检查冲突、添加新 的信息、体( 程序体，函数体，过程体，分程序体) 、查询标识符信息、体结束和删除 局部静态环境。 5 东北师范大学硕士学位论文 2 7 2 动态环境 动态环境用来记录标识符的动态属性，主要是变量的值；动态环境随着程序的执行 动态变化的；用于进行记录、查找和检查标识符的动态属性信息； 根据程序设计语言的特点，动态环境的定义会有所不同， d e n v = i d e _ s v d e n v = l o c _ s v s v 表示可存储的值，其定义会有所不同； 通常用符号。作为表示动态环境的变量，1 3 d e n v ； 举例： i d e - s v s v = i n t v ( i n t ) + r e a l v ( r e a l ) + b o o l v ( b o o l ) 整数实数布尔值 动态环境主要处理：赋值语句、定义改变变量的值、其他变量的使用点、查询变量 的值、过程调用、建立新的局部动态环境、过程返回和删除局部动态环境。 2 7 3 值 值域分为两种：可指称值域( d v ) 和可存储值域( s v ) 。 在程序设计语言里，标识符主要有常量标识符、类型标识符、变量标识符、过程标 识符、和函数标识符等，因此可指称值域( d v ) 定义如下： d v = e o n s d v ( t y p e s v ) + t y p e d v ( t y p e ) + v a r d v ( t y p e l o c ) + p r o c d v ( p r o c ) 可存储的值( s v ) 是指在一个地址( 单元) 罩能存得下的值，用于动态环境，定义如 下： s v = i n t s v ( i n t ) + r e a l s v ( r e a l ) + b o o l s v ( b o o l ) 表达式的值e v ( 表达式的计算结果) 表达式的取值( 根据允许的表达式出现的不同位置) e v = e x p ( t y p e s v ) + v a r ( t y p e l o c ) 2 8 基于抽象机方法定义程序设计语言的操作语义 抽象机方法的主要思想根据给定的语言定义一个抽象机，并使得它能够解释执行将 要定义的语言的程序；抽象机的定义包括两个部分：一是抽象机组成的抽象定义状 态结构，二是执行机制的形式定义状态转换规则；当给定具体程序时，抽象机的初始 状态被确定，以后就根据状态转换规则进行转换，直至出现终止状态为止。针对不同的 语言，抽象机的定义也各不相同。 6 东北师范大学硕士学位论文 第三章过程式语言s l 语法定义 3 1s l 语言特点 s l 语言在数据类型上支持整型、实型和逻辑型，在语句上支持代表顺序结构的赋 值语句、输入语句和输出语句；代表分支结构的i f 语句；代表循环结构的w h i l e 语句以 及函数调用语句。它的关键字主要有i n t 、r e a l 、b o o l 、i f e l s e 、w h i l e 、r e a d 、w r i t e 等。 3 2s l 语言文法 p r o g r a m ：2s t m _ s e q u e n c e s t m _ s e q u e n c e ：= s t a t e m e n tl s t a t e m e n t s t a t e m e n t b l o c ks t m i f - s t m w h i l e s t m a s s i g n - s t m r e a d s t m w r i t e s t m e x p c o m p a r e 。o p s i m p l e e x p a d d 一0 p t e r m m u l - o p f a c t o r ：- b l o c k s t m i f - s t mlw h i l e - s t mla s s i g n - s t mir e a d - s t m1w r i t e s t m ：= p r o g r a m ：= i fe x pt h e ns t m _ s e q u e n c ee l s es t m _ s e q u e n c e ：= w h i l ee x pd os t m _ s e q u e n c e ：= i d e n t i f i e r ：= e x p ； ：= r e a di d e n t i f i e r ； ：= w r i t ee x p ； ：= s i m p l e - e x pic o m p a r e o ps i m p l e e x p ：= a t t r o p = t o k e n ； t2 p ； m a t c h ( t o k e n ) ； i f ( t i = n u l l ) t - c h i l d 1 】= s i m p l e _ e x p o ； r e t u r nt ； 识别s i m p l e _ e x p 文法规则的算法如下： t r e e n o d e s i m p l e _ _ e x p ( v o i d ) t r e e n o d e t = t e r m 0 ； w h i l e ( ( t o k e n = = p l u s ) o k e n m i n u s ) ) t r e e n o d e 幸p = n e w e x p n o d e ( o p k ) ； i f ( p ! = n u l l ) p c h i l d o 】= t ； p a t t r o p = t o k e n ； t2 p ； m a t c h ( t o k e n ) ； t - c h i l d 1 】= t e r m o ； r e t u r nt ； ， 识别t e r m 文法规则的算法如下： 1 7 东北师范大学硕士学位论文 一一 t r e e n o d e 幸