视觉语言图表定义与DIAGEN超图语法

理论计算机科学电子笔记148（2006）19-40www.elsevier.com/locate/entcs用图来马克·米纳斯1德国慕尼黑大学计算机科学系摘要对视觉语言的重新定义是精确定义视觉语言所必需的;它是自动创建处理语言图表的工具的要求本文介绍了作者于2004年5月在德国达格施图尔宫的SegraVis暑期学校的一次讲座和一次练习本文以类似教程的方式介绍了DIAGEN用超图和超图语法定义视觉语言语法的方法。关键词：定义，超图，图论1介绍一种语言的语法描述了该语言的句子是如何由它们的成分组成的。可视化（建模）语言（VL）的句子是图表，例如，状态图和图由基本图组件（如箭头或圆圈）以及文本标签组成。因此，语法检查对于精确地指定语言是必不可少的，但是大多数应用程序还需要语法检查程序，该程序允许区分属于该语言的图和不属于该语言的图。此外，必须自动确定正确图的结构。因此，VL设计者和应用程序开发者在处理文本语言和编写编译器或其他自动处理特定语言句子的工具时遇到了同样的问题。1 电子邮件：Mark. unibw.de1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.12.01120M. Minas/Electronic Notes in Theoretical Computer Science 148（2006）19至于语篇语言，我们可以区分具体的同义词和抽象的同义词.具体语法确定图及其图组件的视觉外观，而抽象语法表示可以使用的图的整体结构，例如， 用于计算美化的布局或作为语义描述的第一步。工具可以通过两种不同的方式强制在工具中或由工具创建的图的语法正确性：语法导向编辑器提供一些编辑操作，将语法正确的图转换为另一个语法正确的图。因此，用户无法使用语法指导编辑创建语法错误的图表。徒手编辑遵循不同的方法。它们允许在屏幕上任意排列图表组件，从而为用户提供最大的编辑自由。但是，可能会产生语法不正确的图表。虽然语法导向的编辑器可以在通过预定义操作更改图时维护图的抽象模型（抽象语法），但这对于徒手编辑是不可能的。每当需要检查图的正确性或需要其抽象语法时，在文献中，已经提出了许多不同的方法用于VL的语法指定。[11]对这些方法进行了很好的总结。实际上，可以区分两种主要的方法：使用图作为内部数据结构的方法（即使VL不包含普通图）和不使用图的方法。后一种方法的例子是VLCC，基于位置文法的VLDESK[5，6]和基于约束多集文法的PENGUINS[3]。它们都提供了无需语法指导的自由编辑。前者的一些示例是基于元建模的工具ATO M3[7]、基于图模式的KOGGE[9]、使用断言的MOSES[10]、使用图变换的GEN- GED[2]、基于并发图gram- mars的VIS PRO[19]、VL-ELIresp.它的后继者DEVI L使用基于模式的方法进行规范和树的内部结构[17]，DIA GEN[12，13，14]使用超图语法。本文介绍了DIAGEN。他们所有除了VIS PRO和DIA GEN仅支持语法指导的编辑V是 P。支持徒手编辑，而DIA GEN支持这两种编辑方法。避免图作为内部模型是有吸引力的，因为语法规范直接作用于图;没有额外的开销，即，内部的图形模型，必须被维护。另一方面，使用图作为图的内部模型有很多好处：语法导向的编辑器需要这样的内部模式，语义规范和与其他语言的集成是更容易等等。本文描述了一个讲座连同一个练习，M. Minas/Electronic Notes in Theoretical Computer Science 148（2006）1921作者于2004年5月在达格斯图尔宫的SegraVis暑期学校发表了这篇文章。本文介绍了在一个教程一样的方式DIA GEN的方法定义视觉语言的语法，实际上是超图。属于讲座的练习，其中包括指定Statechart图的语法，已被用作本文中的一个运行示例。下一节将简要介绍DIA GEN框架，该框架允许从正式语言规范自动生成徒手编辑器，同时也允许语法指导编辑器。使用超图作为正式的图模型来定义是这种规范的主要部分。第3节介绍超图的概念，超图基本上是有向图概念的扩展。超图被用作内部图模型。这种超图模型以与传统编译器构造非常相似的方式进行词法分析。简化的超图模型是该处理步骤的结果。第4节然后描述了如何di-agram语言可以指定的超图语法在这种减少超图模型。最后，第五部分对本文进行了总结。2迪亚根DIA GEN为图表编辑器的快速开发提供了一个环境[13，14]。本节概述了这个环境，以及如何使用它创建一个为特定图表语言定制的图表编辑器。DIA GEN可用于创建各种图表语言的编辑器，例如，有限自动机，控制流程图，Nassi-Shneiderman图，消息序列图，视觉表达图，顺序功能图和梯形图[12，13]。实际上，我们并不知道有一种图表语言是不能被指定的，这样它就可以用DIA GEN来处理。2.1DIAGEN结构DIA GEN完全用Java实现，由编辑器框架和DIA GEN设计器组成。图1说明了DIAGEN的结构，以及如何使用它来开发图表编辑器。作为Java类的集合，DiaGen编辑器框架提供了所需用于编辑和分析图表。此外，委员会认为，DIAGEN由DIA GENdesigner，一个基于GUI的规范工具和代码生成器。为了为特定的图表语言创建编辑器，编辑器开发人员使用DIA GEN设计器并指定图表的所有方面2DIA GEN是免费软件，可从http://www.unibw.de/inf2/DiaGen获得。22M. Minas/Electronic Notes in Theoretical Computer Science 148（2006）19规范编辑器开发人员DIAGEN操作写道DiaGen编辑器框架生成的程序代码附加程序代码DiaGen设计师图编辑器Fig. 1.使用DIA GEN生成图表编辑器。语言，即，图语言组件的视觉外观、语言语法、语义、布局和复杂的编辑操作。此规范在内部由XML文档表示，该文档由DIA GEN设计器的代码生成器转换为Java代码。也可以提供“手动”编写的附加程序代码。这对于处理问题域的对象可能是必要的，例如，当编辑器用作另一个软件系统中的组件生成的类与编辑器框架和人工编写的代码一起实现了特定图表语言的编辑器。该编辑器既可作为独立程序使用，也可作为软件组件使用，因为编辑器框架和生成的程序代码符合JavaBean标准，即Java的软件组件模型使用DIA GEN开发的图表编辑器（以下我们称之为• DIAGEN编辑器始终支持徒手编辑，以便编辑器用户可以任意创建、删除和修改图组件（例如，矩形和箭头表示状态图中的状态和转换），就像使用现成的绘图工具一样。在每次编辑操作之后，编辑器根据图表语言的语法分析• 格式良好的图可以被翻译成语义或外部表示，例如，表示其结构的XML文档。 这个过程是由句法分析驱动的。• D IA G EN编辑器的开发者还可以为语法指导的编辑指定复合操作。这些操作中的每一个都是为了修改图的含义（例如，对于树，一个节点可以被删除，连同它的传入边和它的整个子树）。M. Minas/Electronic Notes in Theoretical Computer Science 148（2006）1923收集修改布局-信息收集收集图超图模型简化超图模型派生结构修饰修饰阅读阅读解析器减速器Modeler拉约标记语法正确的子图超图Transformer读取读取编辑器用户图二. 基于DIA GEN的图形编辑器的体系结构。• 自动布局是D IA G EN编辑器的另一个可选功能。当语法定向编辑操作被指定时，它是强制性的。自动布局机制调整图的布局（即， 其部件的位置、尺寸等）。自动布局还有助于徒手编辑：在用户每次修改布局 后 ， 布 局 机 制 都 会 更 新 图 ， 使 其 结 构 保 持 不 变 。 D IA G ENobenchers的约束，指定布局机制，在一个声明的方式，和一个编程接口，用于插入其他布局机制，anisms。2.2DIA GEN编辑器架构图2示出了所有DIAGEN编辑器共有的结构，下面将对其进行描述。圆角矩形是数据结构，矩形代表功能组件。灰色矩形是编辑器框架的一部分-已调整的工作基于DIA GEN的程序生成器关于图表语言的规范。箭头表示信息流。如果没有标签，信息流意味着阅读。创建相应的数据结构。编辑器支持徒手编辑的方式包括绘图工具，这是编辑器框架的一部分，但已调整的程序生成器。有了这个绘图工具，编辑器用户可以创建，属性评价语义表示选择操作绘图工具选择操作24M. Minas/Electronic Notes in Theoretical Computer Science 148（2006）19安排和修改特定于图表语言的图表组件由DIA GEN设计师的程序生成器根据语言规范创建的编辑器专用程序代码负责这些语言专用组件的可视化表示。示例是状态图中的圆角矩形或箭头。绘图工具将图的数据结构创建为一组图组件及其属性（位置、大小等）。从建模器开始到属性评估结束的处理步骤序列实现了自由编辑所必需的图分析：建模器首先将图转换为内部模型，即超图模型。该模型用超图的方法完整地表示了图超图模型和超图的概念作为有向图概念的推广将在下一节中介绍。对于这个简短的概述，知道超图已经被证明是一种合适的数据结构，用于表示图分析超图模型的以下任务与熟悉的编译器技术非常相似：reducer（对应于编译器的扫描器）对超图模型进行词法分析，并创建一个简化的超图模型，然后由超图解析器对其进行该处理步骤识别（语法上）正确的图的最大部分，并通过用不同的颜色给每个正确的子图着色来向用户提供视觉反馈。因此，正确的图表完全用单一颜色着色，错误则由缺失的颜色表示。由每个子图的语法结构驱动，类似于编译器的语义分析步骤，属性评估然后用于为这些子图中的每个创建语义（或仅外部）表示。layouter修改图组件的属性，从而通过使用由reducer和parser或属性评估收集的信息来修改diagram布局。布局器负责diagram美化[4]并在用户交互后维护图结构。后者是必要的，例如，用户改变一个图形组件的尺寸，这迫使其它组件也改变它们的尺寸。当然，如果图的结构发生变化，故意的语法定向编辑也需要布局器：语法定向编辑操作由编程的超图转换指定（参见。[13]由用户选择。每个编辑操作都由超图转换器Transformer执行，它直接修改超图模型M. Minas/Electronic Notes in Theoretical Computer Science 148（2006）1925主要是每个操作可以利用来自简化的超图模型或在先前的图分析步骤期间已经生成的导出结构的信息。该操作也可以修改图。但是，添加或删除其组件超边分别被添加的图表组件受到限制。通过转换到HGM来移除。3如图2所示，超图变换并不直接对图进行变换。相反，常规的图分析是在HGM已经被归约器、解析器和属性评估处理之后开始的。 布局师的任务是请注意，通过HGM变换添加或删除的任何分量超边缘都伴随着添加resp。删除相应的图表组件。3超图与超图模型如前所述，图被转换为超图模型，然后转换为简化的超图模型，然后通过一个语法分析器。因此，简化的超图模型是图的主要模型;可视化语言的语法是根据这个模型来指定的本节描述超图的概念，因为它用于以简洁的方式建模图，超图模型和将超图模型转换为简化模型的过程下一节将讨论视觉语言的简化超图模型的语法定义。3.1超图超图是有向图的扩展;超图由有限的节点集和有限的超边集组成。每个超边都连接到一些节点;这些节点称为超边访问的节点也不允许访问任何节点。超边的附件被标记，使得不同的附件可以通过它们的标签来区分。有向图可以被认为是一个特殊的超图，其中每个超边通过它们的附件源和目标访问两个节点（可能是相同的）。此外，超边是在给定的排序字母表上键入的。由超边访问的节点的数量（超边的arity）由其类型的秩确定，即，相同类型的不同超边访问相同数量的节点。3请注意，这并不提供额外的功能;添加resp.移除图组件是相当需要的，使得随后的图分析步骤不移除RESP。再次添加组件hyperedges26M. Minas/Electronic Notes in Theoretical Computer Science 148（2006）19超图如图3所示：节点由黑点表示。超边被绘制为矩形，可能带有圆角，通过带有附件标签的细线连接到其附加节点。二进制超边，即，具有参数2的超边可以被绘制为连接所附接的节点的粗箭头。超边缘类型写在靠近箭头或（圆角）矩形内部3.2超图模型图表组件（例如，圆形矩形和Statechart图中的箭头）具有连接区域，即，允许连接到其它组件的组件的部分（例如，箭头的端点以及可以“连接”到其注释的箭头本身）。这种组件的最一般但最简单的形式描述是超边;组件的连接区域由组件这些节点和分支超边首先组成一个不连通的超图。如果相应的连接区域以特定的方式相关，则建模器通过附加的关系边连接节点，这在规范中进行了描述以下段落将更详细地描述超图模型和创建它们的过程。状态图被用作运行示例。状态图本质上是由状态和状态之间的转换组成的有限状态机。初始状态和最终状态分别用点表示。圆点和周围的圆圈。其他状态由带有可选文本标签的圆角矩形表示。状态之间的转换圆角矩形可能包含其他状态图。 一个状态被称为与状态，如果相应的圆角矩形被虚线分成几个隔间（参见。图3）。如果状态不包含任何虚线，即，如果只有一个隔室（参见图1），图6）。没有包含任何状态图的状态称为普通状态。由于本文只讨论语法定义，我们省略了这些不同状态的语义。状态图用超图模型以如下方式建模：初始状态、最终状态和作为状态的圆角矩形分别由点、圆点类型的单个超边表示。 rect. 这些可视组件中的每一个都具有覆盖组件区域的单个附接区域，即，dot、circledot和rect超边访问单个节点。请注意，普通状态、与状态和异或状态并不通过它们的视觉组件来区分。分量超边这些国家M. Minas/Electronic Notes in Theoretical Computer Science 148（2006）1927将通过超图模型的分析来区分。转换由访问三个节点的箭头超边表示。相应的连接区域分别是端点。箭头本身。后一个附加区域用于附加注释。箭头超边缘的附件分别标记为from、to和sp。label. 文本超边（图3中未使用）表示过渡注释。它们还访问表示文本可视区域的单个节点。最后，虚线由虚线超边表示，其也具有单个附着区域。Statechart组件之间的空间关系由at和in边缘表示。一个状态在另一个状态中的包含由开始于前一个状态的超边的节点的内边表示（其可以是点、圆点或矩形超边），并在后一状态的矩形超边的节点处结束虚线的包容性以相同的方式表示。at边将转换的端点节点与转换开始或结束的状态节点连接起来。Atedges也用于表示附加到过渡的注释。超图建模器以如下方式从图创建超图模型：对于每个图组件，将表示超边及其访问的节点添加到超图，在此步骤之后，超图构成未连接的超图。关系边将在下一步中添加到节点之间。图语言规范必须描述特定节点必须通过某种类型的关系边连接的条件。这是通过为每对附着区域类型分配一些关于其参数（如位置和大小）和关系边的条件来完成的，这些关系边必须连接表示满足条件的指定类型的附着区域的节点。让我们再次考虑状态图的例子，让一个圆角矩形包含另一个，即，外部矩形的连接区域包含内部矩形的连接区域，如图3所示。然后，建模者必须在连接区域的相应节点之间添加入边。类似的规则必须指定用于箭头4附近的注释，箭头开始和结束于状态等。图3显示了一个Statechart图及其对应的超图模型。状态图由一个与状态组成，其中包含两个简单的子状态图。与状态由最顶端的矩形超边表示。与状态包含由虚线超边表示的虚线，其节点通过关系边连接到与状态4实际上，注释的情况更复杂：规范，例如，必须处理接近几个过渡的注释。这些复杂的规则可以在DIA GEN中详细说明，但在这里省略。28M. Minas/Electronic Notes in Theoretical Computer Science 148（2006）19在在在在在在从到在从到点标签标签rectrect箭头箭头虚线rect点图三. 一个简单的状态图（上图）及其超图模型（下图）这四种状态的遏制也是以同样的方式表现出来的。and- state包含四个状态和两个转换。 请注意，状态的包容性由边中然而，遏制转型不是由对应的关系边表示的。这是因为转换可以跨越状态图中的层次结构，即，转换可以在XOR状态内开始并且在XOR状态之外的状态处结束。还请注意，如图3所示的超图模型并不完全表示状态图，例如，关于虚线的位置和所包含的状态的相对位置的信息似乎丢失了。实际上，这样的附加位置信息存储在节点和超边缘属性中，为了简单起见，这里省略了这些属性3.3简化超图模型超图模型以非常直接的方式表示图表。每个组件超边缘表示单个图组件，并且每个关系边缘描述两个组件之间的关系。这样的超图模型不太适合句法分析.这种情况基本上与文本语言的编译器相同：编译器不对字符流进行语法分析。相反，对字符流进行词法分析，产生一个令牌流;每个令牌表示一个字符序列，如标识符或关键字。其他字符可以在令牌流中完全省略，例如，评论或空白。词汇分析在句法分析之前进行，因为标记的数量少于字符的数量两个分析步骤的组合是M. Minas/Electronic Notes in Theoretical Computer Science 148（2006）1929在一在在B在虚线一内外B嵌套见图4。状态图的归约规则。因为词法分析可以以比句法分析更有效的方式实现此外，具有有限前瞻性的高效解析算法（例如，LALR（k）[1]）不能应用于字符流，例如，可以包含任意长度的标识符和注释。然而，高效的解析器可以成功地用于令牌流。由于没有真正高效的解析器，对超图的简化对于超图解析来说更加必要鉴于编程语言的核心是上下文无关的，解析器具有线性或至少三次时间复杂性，一般超图语言的解析是NP完全的，而上下文无关超图语言的解析是多项式的[8]。然而，只有很少的图语言5的超图模型构成了上下文无关的超图语言。因此，产生简化的超图模型的简化超图模型具有两个主要原因：解析较小的简化超图模型更快。减速器，即，词法分析的超图模型，比解析器更高效至于分析文本语言，结合词法和句法分析可以更快地进行图表分析。而且，更重要的是，减少超图模型会导致超图的结构更简单，从而允许更快的解析算法。对于Statechart图也是如此。例如，在关系中，每当一个状态包含在另一个状态中时，就会添加边。这意味着不仅在状态和直接包含的状态之间存在关系边，而且在内部状态的所有包含状态之间也存在关系边，即，在关系边表示状态之间的包含关系的传递闭包，这使得具有深层次结构的超图模型很大并且难以解析。简化超图模型可以避免这些问题。reducer是根据类似于图变换规则的归约规则来指定的，这将在下一节中更详细地讨论约简规则和图变换规则之间的区别在[13]中详细描述图4显示了Statechart图的归约规则。如果左手5实际上，我们只知道很少的这样的语言，例如，树和Nassi-Shneiderman图[15]。30M. Minas/Electronic Notes in Theoretical Computer Science 148（2006）19空闲send_no（n）send_off（）说话send_off（）发送_on（）称为图五.电话示例的接口Phone2Line的协议状态图（顶部）及其简化的超图模型（底部）。规则的右侧可以在超图模型中找到，右侧被添加到简化的超图模型中。左手边主要由两个节点a和b以及a连接的边组成。灰色的、被划掉的部分是子超图（所谓的负应用条件），其必须不存在，即，它们的存在使这一规则无法适用。上面的一个包含两个在边缘。因此，如果关系中的匹配边不表示状态的直接包含，则不能应用该规则。如果外部状态包含虚线，则另一个否定应用条件阻止应用该规则，即，如果这个状态是一个AND状态。因此，该规则适用于异或状态及其直接包含的状态。图5显示了一个没有嵌套状态的简单Statechart图及其简化的超图模型。状态图取自本卷其他地方描述的电话示例。每个常规状态由一个状态超边缘表示;初始状态由initState超边缘建模。在简化的超图模型中不显示状态的文本名称。转换由访问三个节点的超边表示：from节点和to节点表示转换的源和目标。访问相应过渡超边的标签节点的-符号超边表示过渡的文本注释。请注意，简化超图模型使用与超图标签从标签标签到到从从到到从从到标签标签状态状态注释过渡注释过渡过渡注释过渡注释状态过渡initStateM. Minas/Electronic Notes in Theoretical Computer Science 148（2006）1931外外内内外外部外部外内内部内部内从到从到标签标签状态initState过渡嵌套嵌套状态initState过渡嵌套嵌套和和状态外外内内从到标签状态initState过渡嵌套嵌套状态图六、一个简单的异或状态图和相应的简化超图模型。见图7。图1中状态图的简化超图模型。3模型，以避免与超图模型的任何混淆作为第二个示例，图6示出了由具有简单包含状态图的异或状态及其简化的超图模型组成的状态图。它的嵌套超边是使用图的规则创建的。四、作为第三个例子，图。图7示出了用于图3中的状态图图及其超图模型的简化超图模型。请注意，图中的简化规则4在这里不适用，因为包含状态是AND-状态而不是XOR-状态。和状态的不同分区由和超边表示，并且所包含的状态图再次由嵌套边建模，这些嵌套边连接到那些和超边访问的节点，而不是状态边。4超图文法图的简化超图模型的语法分析图模型DIA GEN使用了一种基于语法的方法，32M. Minas/Electronic Notes in Theoretical Computer Science 148（2006）19：：=一标签状态P1|P2P3SC：：=初始化Init节点P4|P5Nodes：：=State状态节点P6|P7P8|P9国家：：=a a一finalState状态状态一 状态回路状态一 状态回路标签注释P 10|P11见图8。无嵌套状态图的超图文法的产生式。P1、P2、. . .，P9是上下文无关产生式，而P10和P11是嵌入产生式。类似于文本编程语言的编译器。超图文法是Chomsky文法的直接扩展，用于指定图语言的语法。4.1上下文无关超图文法上下文无关超图文法（也称为超边替换文法[8]）是上下文无关文法的一个扩展。它们由两个有限的、非空的、不相交的超边类型集合组成，即终结符和非终结符。其中一种非终结超边类型称为起始类型。一个上下文无关的超图文法也由以下形式的有限个产生式集合组成：产生式的左手边和右手边各由一个超图组成。左边的一个有一个超边，其类型是非终结符，以及相应数量的被这个超边访问的节点。右边是一个任意的超图。它的超边可以有终结符和非终结符类型。最后，在左手侧的所有节点和右手侧节点的子集之间存在一一对应关系右手侧必须具有至少与左手侧一样多的节点。Init：：=从到状态过渡initState状态B：：=状态状态一一B一B标签标签注释过渡testa过渡testa状态从到从标签到M. Minas/Electronic Notes in Theoretical Computer Science 148（2006）1933空闲send_no（n）说话SCInit节点图9.第九条。简单状态图的简化超图模型的推导（上）（下）图8显示了一组上下文无关的产品。左侧和右侧由符号：：=分隔。对于Chomsky gram-mars，L：：=R1|R2| · · ·|Rn被用作n个产品L：：=R1，L：：= R2，.，L：：= Rn. 具有终端类型的超边绘制为矩形，角，那些非终端类型为圆角矩形。左侧和右侧的对应节点用相同的斜体字母标记。请注意，arity为0的超边不会访问任何节点。图8中的示例是SC、Init和Nodes类型的超边。请注意，P10和P11不是上下文无关的作品。他们 稍后再考虑产生式是一个图（或者更确切地说是超图）的变换规则，如果可以在超图G中找到左手边，则可以将其应用于超图G。左手边的出现，即，匹配的超边从G中删除，并插入产品右侧的副本。左侧和右侧节点之间的对应关系描述了右侧的副本如何连接到G的其余部分。当插入右侧时，右侧的节点实际上没有被复制，G的其余部分的对应节点，即，被删除的超边访问过的那些节点反而被“重用”。所得到的超图GJ称为从G导出，G<$GJ。从到状态节点过渡initState从到状态状态过渡initState从从从t0到从到从到到标签状态状态状态过渡initState注释状态标签状态过渡过渡initState注释状态过渡过渡initState标签标签标签标签标签34M. Minas/Electronic Notes in Theoretical Computer Science 148（2006）19图9示出了从超图开始的推导序列，超图仅由没有任何节点的非终端SC超边6在第一个推导步骤中，这个超边被两个非终结的超边Init和Nodes使用产品P2替换。下一个派生使用产品P3替换Init超边缘。最后一个推导使用了P10，它还没有被描述，因为P10不是一个上下文无关的产生式。超图文法在类似于乔姆斯基文法的派生方面指定超图语言一个超图H属于一种文法语言，如果它不包含任何非终结超边，并且如果存在一个导子序列，即，一系列的推导步骤，从一个开始hypergraph到H。一个起始超图由一个超边及其访问节点组成，文法的起始类型为超边类型。在图语言的上下文中，一个高效的上下文无关超图语法分析器已经在[12，13]中描述。4.2具有嵌入的上下文无关超图文法事实证明，上下文无关的超图语法是不够的表达指定图语言语法。大多数图表语言本质上是上下文敏感的。然而，虽然有多项式时间的上下文无关超图文法的解析器[8]，有没有有效的解析器可用于非上下文无关超图语言。7然而，[12，13]中提出的上下文无关超图语法的解析器可以很容易地扩展到一种表达能力稍强的超图语法，其表达能力已被证明对所有类型的图语言都是足够的，远了这些超图文法可以有嵌入产生式作为另一种产生式。一个嵌入产生式在其左侧由一个任意超图组成，在右侧由同一超图组成，但有一些额外的超边。通过使用这种产生式，这些超边被嵌入到左手边的上下文中，因此这种产生式类型的名称。这种产品有一个应用条件：上下文，即， 左手侧的匹配必须不是从另一个嵌入的边缘导出的。86为了简单起见，我们使用术语非终结超边来代替具有非终结超边类型的。[7]有一个分析相当一般的图文法的语法分析器，它很容易通过RekersandS churr[16]扩展到超图文法，但它具有时间复杂性。Zhannghas提出了一个用于非上下文无关超图文法的多项式时间解析器[19]，这种语法必须是一致的，这对语言设计是一个严重的限制。8.这似乎是一个严格的限制。通常，语法类由它们的产生式来区分。对于乔姆斯基文法，我们区分常规，上下文无关，或上下文相关的产品。嵌入产生式还限制了派生M. Minas/Electronic Notes in Theoretical Computer Science 148（2006）1935图8的产生式P10和P11是嵌入产生式：P10将单个终端过渡超边缘嵌入到上下文中，P11嵌入附加注释超边缘。4.3没有嵌套状态的图8示出了上下文无关超图语法的产生，其具有用于没有嵌套状态的状态图的所有简化超图模型的语言的嵌入，即，没有XOR状态和AND状态。该产品具有SC、Init、Nodes和State作为非终端超边缘类型。SC是起始类型 。 终 端 类 型 包 括 initState 、 finalState 、 state 、 transition 、 loop 和annotation 。 请 注 意 ， 这 些 终 端 超 边 必 须 由 reducer 创 建 。 生 产 P1 ，P2，...，P7负责创建所有状态和从初始状态（由状态图中的黑点表示）的唯一转换。生产P8和P9创建循环，即，从一个状态再次转换到相同的状态。循环由循环超边表示，而从一个状态到另一个状态的转换由转换超边表示。这样，如果变迁超边也必须表示循环，它们就不必访问同一个节点两次。reducer的任务是区分这两种过渡。P10和P11是在任意两个状态之间添加转换的嵌入产生式。转换目标可以是普通状态或最终状态，因为嵌入的转换超边的to节点被非最终状态超边访问。然而，源状态必须是普通状态，因为来自节点被终端状态超边缘访问。P8和P10创建不带任何注释的过渡，P9和P10创建带注释的过渡图9显示了Phone2Line接口的协议状态图的简化超图模型的推导，如图5所示，也如本卷其他地方描述的示例所示。这个推导证明了简化的超图模型是由所提出的超图文法生成的语言的一员。作为从嵌入边导出的超边的过程必须不参与嵌入产生的后续应用的上下文中。然而，这种限制也可以以以下方式不同地建模：存在两组非终端超边缘类型;每个嵌入产生的上下文由来自一组的非终端超边缘组成，而嵌入的超边缘来自另一组或终端超边缘。上下文无关的产品必须在两侧使用来自同一集合的超边。36M. Minas/Electronic Notes in Theoretical Computer Science 148（2006）19节点状态节点一我内O外部的嵌套P12P13|P14国家：：=a aSC'状态SC'一：：= 初始化一初始化“节点”aP15P16|P17恩内尔嵌套尤塔一见图10。带异或状态的Statechart图的超图语法（以及图84.4使用XOR状态的现在让我们考虑带有xor-状态的Statechart图，但是还没有and-states。这种状态图的简化超图模型类似于没有嵌套状态的超图模型。然而，直接嵌套的状态由嵌套的超边指示，如前所述并在图1中示出6，即，简化超图模型是状态图的一种简化版本，其通过嵌套超边显式表示层次结构。这种状态图的语法定义与没有嵌套状态的状态图所讨论的语法相同，但是有一些额外的产生式，如图10所示。生产P12是如何导出非终结状态超边的第三种替代方案。P12定义了一个异或状态，其中有一个完整的状态图，由非终结SC非终结符SC“嵌套”版本访问一个节点，该节点也被表示制作P13，P14，...，P17是产品P1，P2，.，P5。新的产生式负责将具有嵌套超边的每个新节点连接到包含状态超边的节点。“旧”产品P8、P9、P10和P11也可以在嵌套状态中使用，也可以4.5具有XOR状态和AND状态的最后，我们将语法定义扩展到可能包含和状态的状态图。和状态的互补性由和超边表示，如图所示图7：终端状态超边缘对普通状态进行建模，初始化：：=从一到内状态嵌套过渡嵌套内initState标签外外M. Minas/Electronic Notes in Theoretical Computer Science 148（2006）1937P18P19|P20图十一岁超图文法（连同图1中的产生式）8和图10）对于具有xor- and and-statesXOR-状态，现在还有AND-状态。一个与状态与其他状态的区别在于，与超边连接状态超边的节点与新节点。这些新节点充当包含完整状态图的与状态图11显示了图8和图10中的产生式，它们定义了完整的Statechart图语言的语法。生产P18是如何导出非终结状态超边的第四种备选方案P18、P19和P20定义了至少两个包含完整嵌套状态图的隔室的与状态。所包含的状态图由非终端SC'超边缘指示，该超结果P8、P9、P10和P11可以在嵌套状态中使用，也可以用于跨层次的转换。然而，在带有and-状态的状态图中，有一些禁止的转换，例如，从一个COM中的状态到同一AND状态的另一个隔间中的状态。这种限制与普通的语法形式主义是难以解释的。因此，DIA GEN允许在解析某些产品时指定附加的应用条件。在具有and-状态的状态图示例中，对结果P10和P11的解析必须以这样的方式进行限制，即连接状态不包含在同一个and-节点的不同隔室中。通过检查从节点a到节点b是否存在满足以下路径表达式的路径，可以容易地检测到这种情况：（嵌套（内部，外部）|and（inner，outer））+·and（inner，outer）·and（outer，inner）·（nested（outer，inner）|和（外部，内部））+这个表达式需要沿着和或嵌套的超边（第一行）在层次结构中向上运行的路径，然后在一个和超边上运行，在另一个和超边下运行（第二行），最后在层次结构中向下运行任意数量的和或嵌套的超边（第三行）。中的附件名称国家：：=一a个外部- SC内SC'和状态a：：= a外a个外部和-SC和-SC内部内部SC'SC'和和38M. Minas/Electronic Notes in Theoretical Computer Science 148（2006）19SC（）Init（）Node（）国家（b）国家（d）状态（d）状态（b）注释过渡（b、d、e）过渡（a，b，c）initState（a）见图12。简化超图模型的导出DAG和图1所示的导出。9 .第九条。圆括号表示必须遍历指定边的方向操作者|表示选择，·顺序组成，+至少重复一次。4.6派生树和派生DAG如图9所示的简化超图模型的推导序列证明简化超图模型（以及因此所表示的图）在语法上是正确的，但是在上下文无关超图语法的情况下，其语法结构最好由推导树（图2中的推导结构）表示。导出树的根表示起始超图的非终端超边，而简化超图模型的（终端）超边表示为树的叶子。每个内部节点及其子节点通常代表一个派生步骤。 与上下文无关Chomsky文法的导出树的唯一区别是节点不仅仅是符号，而是访问超图节点的超边。使用嵌入产生式的派生步骤不能由节点及其子节点一起表示;每个嵌入超边都是其上下文超边的子节点。有向无环图（DAG）是语法分析的结果，而不是树。图12示出了用于图9所示的推导的该DAG。作为DAG的节点的超边被写为它们的边标签，连同它们的访问节点的标签一起被写在括号中。实线DAG边表示使用上下文无关的产生式的派生步骤，而虚线DAG边表示嵌入的产生式派生。派生DAG是可视化DIAGEN编辑器的语法分析结果，并且它是进一步处理步骤的起点，即，自动布局和语义分析方面的属性评价。有关这些步骤的详细信息可以在[12，13]中找到。