上下文无关语言上的函数的实用类型检查

本文介绍函数式语言LFC的一种类型检查方法。LFC语言是为支持软件形式规约的获取和检验工作而开发的一个通用的形式规约语言。该语言使用并结合了形式语言和递归函数这两种功能的强大的数学工具。由此，LFC语言在保持很强的表达能力的同时，也使得在规约获取过程中使用机器学习和其他机器辅助技术成为可能。LFC语言的理论基础是一种新的递归函数，即定义在上下文无     

一类递归函数的多态类型

以上下文无关语言上的递归函数为基础的语言LFC(1anguage for context free recursive function)是一种形式规约语言,适于处理短语结构.LFC也是函数式语言,具有函数式语言的许多特点.LFC已经在形式规约获取系统SAQ(specification acquisition system)中实现,为其最初设计的类型系统不支持多态类型.引入类型变量和相应的类型检查方法,就可以将其类型系统扩充为多态类型系统.对多态类型系统实现中的一些问题也进行了讨论.在实现多态之后,LFC     

基于最小序句子的上下文无关语言句子枚举

形式规约获取系统SAQ和一些形式化验证系统中常常需要枚举上下文无关语言的句子，现有的枚举方法较少且效率较低，以上下文无关语言L(G)的最小序句子和最大序句子为基础，从最小序句子开始按照一定的顺序扫描字符串，直至扫描到最大序句子为止，对被扫描的字符串进行判断取舍，在扫描的过程中采用削减和前瞻策略，很大程度上减少了被扫描的字符串个数，可以取得较好的时空性能，实验数据表明，基于最小序句子的枚举方法比其他上下文无关语言句子枚举方法具有更高的效率。     

面向对象的形式化规约语言GOOZ

在总结和评价现有Z语言面向对象扩充的基础上，设计了一种新的扩充语言GOOZ，该语言克服了Z＋＋，Object_Z等语言的一些缺点，其书写规约具有简洁，明确，接口定义清晰，模块无整，结构良好，易于验证的特点。     

一种特殊的上下文无关文法及其语法分析

SAQ系统是一个进行软件规约获取、检验和复用的实验系统，其中以上下文无关文法表示的概念是规约的一部分.SAQ要求将概念的词法和句法定义结合在一个上下文无关文法中.如果用常规的上下文无关文法描述诸如程序设计语言和自然语言等一些复杂概念的语法，则需要把诸如空格和回车等没有实质意义的分隔符包含到语法中去(这种描述方法称为朴素表示法),使得语法描述很累赘.为此，作者设计了一种特殊的上下文无关文法,它把通常上下文无关文法定义中的非终极符集合和终极符集合进行细化.用这种文法可以相对简洁地描述程序语言和自然语言等复杂概     

DFA模型及其语言的结构化代数规约

本文首先阐述了利用ＤＦＡ模型技术进行状态转换系统描述存在的主要问题,提出了利用代数规约技术解决这些问题的可行性,然后介绍了新一代具有松散语义的代数规约语言ＳＰＥＣＴＲＵＭ及其主要规约操作符的语法和语义,并根据ＤＦＡ模型及其语言的数学定义,给出了它们的结构化代数规约,为基于ＤＦＡ模型的状态转换系统的形式化设计和开发奠定了基础。     

代数语言规约的ML原型翻译系统

形式化的规约说明对于提高软件开发的正确性和效率有很大作用,一个形式化的规约说明语言开发环境如图1所示。目前有的原型系统是用常规高级语言,即一般的过程语言来写的,如C。这种原型环境涉及大量低层细节.程序繁琐冗长,且和计算机状态相联系,破坏了原有规约的证明特性。     

一个面向网络并行环境的需求规约语言

提出了一个面向网络并行环境的需求规约语言ＯＯＲＳＬ。ＯＯＲＳＬ支持面向对象的分析方法,可以定义并行成分一进程,可以使用前后断言来表达用户的功能需求,允许将非经和半形式化的需求定义嵌入形式化的需求定义中。因此,ＯＯＲＳＬ语言是一个半形式化的语言,它为网络并行环境下的软件自动化和软件形式化开发提供了支持介绍了ＯＯＲＳＬ的设计思想和主要语法成分。给出了一个实例。     

基于TLA＋的BRP协议规约及验证

BRP协议是为不可靠信道上传送大数据包文件设计的工业协议。该协议的正确性依赖于各部件实时方面的假设。本文主要阐述了使用时序规约语言TLA＋对BRP协议进行规约和验证的过程。首先通过自然语言非形式化地描述BRP协议的基本原理和需求，在此基础上建立了BRP的形式化模型，利用TLA＋先对不考虑实时要求的BRP进行规约，然后添加实时约束获得BRP完整的规约，最后使用模型检验器TLC验证BRP协议的各种性质。     

HB协议的形式规约与验证

形式化方法是确保安全协议设计正确性的重要工具,利用形式化方法已经发现了许多安全协议的设计错误.首次利用形式规约语言Z对RFID安全协议HB进行形式规约, 并对HB协议应该满足的安全性质进行形式化描述,使用Z模式推理从协议及其运行环境两个方面验证了协议的关键安全属性,发现了HB协议在设计方面的缺陷,提出了HB协议的一种改进方法.     

Facilitating formal specification acquisition by using recursive functions on context-free languages

Although formal specification techniques are very useful in software development, the acquisition of formal specifications is a difficult task. This paper presents the formal specification language LFC, which is designed to facilitate the acquisition and validation of formal specifications. LFC uses context-free languages for syntactic aspect and relies on a new kind of recursive functions, i.e. recursive functions on context-free languages, for semantic aspect of specifications. Construction and validation of LFC specifications are machine-aided. The basic ideas behind LFC, the main aspects of LFC, and the use of LFC and illustrative examples are described.     

运算构造和检验系统FC的设计和实现

运算构造和检验系统FC(function constructor)是形式规约获取系统SAQ(specification acquisition)的一个子系统.在SAQ系统中,运算用于表示规约的语义.FC提供了对运算的交互式归纳定义方式和运算的施用,支持运算的联立递归定义.详细介绍FC的功能、结构和实现技术,并讨论了下一步的改进方向.     

Recursive functions of context free languages (I)--The definitions of CFPRF and CFRF

It is intended to establish the recursive function theory on context free languages (CFLs). In this paper, the function class CFRF and its proper subclass CFPRF were defined on CFLs; it is quite straightforward to use them for describing non_numerical algorithms. In fact, they are respectively the partial recursive functions and primitive recursive functions of context free languages. The structure induction method for proving CFPRF function properties was presented. A method for CFL sentence enumeration was given, the minimization operator was defined. Based on CFL sentence enumeration, the minimization operator evaluation method was given. Finally, the design and implementation principles of executable specification languages with the CFRF as theoretical basis were discussed.     

Translating VDM specifications into ABC programs

Declarative languages such as Miranda and Prolog have often been used to prototype specifications written in the formal notation of VDM, but they have no destructive assignment commands thus making it difficult to model VDM state changes. Imperative languages like C and Pascal allow state changes to be modelled naturally but lack the expressive power to make prototyping feasible. ABC, on the other hand, is a simple yet very powerful imperative language that has a great expressive power making it suitable as a prototyping language. This paper describes the process of translating VDM specifications into ABC programs.     

Recursive functions of context free languages (Ⅰ)——The definitions of CFPRF and CFRF

It is intended to establish the recursive function theory on context free languages (CFLs). In this paper, the function class CFRF and its proper subclass CFPRF were defined on CFLs; it is quite straightforward to use them for describing non-numerical algorithms. In fact, they are respectively the partial recursive functions and primitive recursive functions of context free languages. The structure induction method for proving CFPRF function properties was presented. A method for CFL sentence enumeration was given, the minimization operator was defined. Based on CFL sentence enumeration, the minimization operator evaluation method was given. Finally, the design and implementation principles of executable specification languages with the CFRF as theoretical basis were discussed.     

Pattern Matching Compilation of Functions Defined in Context—Free Languages

LFC is a functional language based on recursive functions defined in context-free languages.In this paper,a new pattern matching algorithm for LFC is presented,which can represent a sequence of patterns as an integer by an encoding method.It is a rather simple method and produces efficient case-expressions for pattern matching definitions of LFC.The algorithm can also be used for other functional languages,but for nested patterns it may become complicated and further studies are needed.     

The Specification of Assemblers

The problem of applying formal techniques of program specification and verification to large complex programs is considered. It is argued that a practical solution requires a variety of techniques, including both procedural and nonprocedural specifications, hierarchical program organization, and the use of program transformations. In particular, a case is made for flexible problem-oriented choice of specification techniques and languages. These ideas are expanded by specifying a load-and-go assembler in three parts: a transduction grammar describing the correspondence between concrete and abstract syntax for assembly language programs; a set of transformations of the abstract form; and a nonconstructive axiomatic specification of the result of core assembly and loading of transformed abstract programs.     

Recursive functions of context free languages (I)

It is intended to establish the recursive function theory on context free languages (CFLs). In this paper, the function class CFRF and its proper subclass CFPRF were defined on CFLs; it is quite straightforward to use them for describing non-numerical algorithms. In fact, they are respectively the partial recursive functions and primitive recursive functions of context free languages. The structure induction method for proving CFPRF function properties was presented. A method for CFL sentence enumeration was given, the minimization operator was defined. Based on CFL sentence enumeration, the minimization operator evaluation method was given. Finally, the design and implementation principles of executable specification languages with the CFRF as theoretical basis were discussed. This paper is based on the Technical Report ISCAS-LCS-2k-03 (SAQ Report No. 30): Recursive Functions Defined on Context Free Languages (I), August 2000, with minor revisions.     

基于企业流程的需求形式化说明语言

需求说明是对需求分析结果所进行的文档化工作,其工作结果—需求规格说明在系统开发、测试、质量保证、项目管理中起着重要的作用。现有的需求规格说明绝大多数是采用自然语言来编写,由于自然语言在严密性上的缺陷,从而导致需求规格说明普通存在着三个严重的问题:模糊性、不准确性和不一致性。该文提出的基于企业流程的需求形式化说明语言,是以四元组作为描述机制,不仅能描述各活动之间的逻辑关系,而且能表达活动对信息流的操作形式,即将控制流和数据流合为一体。