[科普中国]-扩展状态变迁模型语言

概述

Estelle是一种基于扩展有限状态自动机的形式化描述语言，是由ISO/TC97/SC21/WGI/SUBGROUP B定义的。它的主要思想是将系统分成许多互连的模块，每个模块都是一个扩展有限状态自动机，利用Pascal语言成份来处理交互活动的参数和状态变量以及其上的操作，可用于描述一般的分布式并发信息系统，特别适于OSI环境下通信协议的服务定义和协议描述，目前已处在DIS(DRAFT INTERNATIONAL STANDARD)阶段。由于易于理解，对实现具有直接的指导意义等优点，Estelle是目前ISO/OSI的一个重要的形式描述语言。1

基本模型Estelle的基本模型是扩充的有限状态自动机。系统的结构描述为由模块(MODULE)组成的层次形结构。模块之间通过交互点(IP)之间的双向通道(CHANNEL)交换信息。模块之间的层次关系以及通道的结构均可随时间变化，因此可以描述结构动态变化的系统。

每个模块都有自己的状态空间，由一组变量的值决定。在这组变量中，有一个特别的变量称作“主状态(STATE)”，相当于传统的自动机中的状态，其它变量则往往称为“上下文变量”。一般，主状态用来标识连接的状况(例如关闭，打开等)，上下文变量用来存贮序列号，服务等级，数据等．模块的转换(TRANSATION)也是在主状态之间定义的。一个转换依赖于若干因素，例如，不同的输入，上下文变量的值，以及动作的优先级等。在Estelle中，这些因素均以一定的转换子句(TRANSITION—CLAUSE)来表示。只有当子句中表达的条件满足时，才进行指定的动作，实现状态转换。

模块之间通过通道发送或接收交互作用。模块和环境的作用只能通过通道进行。“通道”概念的引入，使得模块可以从其环境中独立出来。一个通道类型定义指定了在该通道上传送的交互作用原语集合。例如通道类型可用来定义运输层的服务原语，它所连接的双方是运输层的用户和服务提供者。

在Estelle中使用上述概念，系统可分解为一组模块，模块与其环境(如其它模块，系统)之间通过一组通道建立联系，通道两端的交互作用点分属不同的模块，而模块本身的结构则由状态转换来描述。1

编译器Estelle编译器是开发协议的支持工具之一，主要用来辅助实现用Estelle描述的通讯协议。

编译器主要包括词法分析，语法分析和代码生成等部分。在UNIX环境下用C语言和其它软件工具辅助实现。

词法分析程序用Lex工具辅助实现，较为简单，识别106种终结符号。

语法分析程序用Yacc工具辅助生成，识别105个非终结符号，276条产生式。

定义Estelle语言的国际标准草案ISO/DIS 9074中给出了Estelle的形式语法，它要经过改写才能被Yaec接受。改写有三种：

(1)大括号表示重复要改为用左递归表示。

(2)删除、合并产生式以提高编译器的质量。

(3)修改文法并构造一个功能更强的词法分析器，和语法分析器交换信息，以此处理上下文有关的约束；同时解决分析方法中的归约/归约冲突问题。

语法分析的主要任务是做静态检查和建立语法树。为语法树设计了两种结点结构。一种是通用的二叉树结构。它适用于任意的非终结符。这样可以减少结点类型。第二种是为复杂的非终结符专门设计的结点结构，它的特点是清晰直观，对子树的访问方便。

代码生成部份选用Pascal作为目标语言。由于Estelle中含有许多Pascal的语法结构，它们可以不加改动地作为目标程序输出。

在目标程序中，除了用户在Estelle语言中使用的标识符外，还有编译器产生的标识符，使用保留首字符的方法避免标识符冲突。2