基于图变换的可视化语言的规范和分析

14的GG GEN GED：基于图变换的可视化语言R.巴多尔角埃尔梅尔岛温霍尔德部德国柏林计算机rosi，lieske，bone cs.tu-berlin.de摘要GENGED概念和环境允许对视觉语言（VL）进行视觉定义editingfeatures捕获语法指导的编辑和/或徒手编辑。在后一种此外，行为图可以被模拟，即可以验证由图GEN GED对VL的规范和分析是基于AGG系统实现的代数图变换概念。本文对AGG和GEN GED作了简要介绍。1介绍图和图文法在计算机科学的不同领域都有应用，例如.用于软件规范或作为底层形式主义来指定可视化语言（VL）。结合适当的控制机制，图语法可以在非常高的抽象层次上描述特定的情况这被用于AGG/GEN GED方法和增强 中 的 VL 的 规 范 和 分 析 。 此 外 ， GEN GED （ Generation of GraphicalEnvironments for Design的缩写）允许分别对VL和环境进行视觉定义这包括定义在特定于VL的环境中可用的编辑操作（称为语法导向编辑或结构化编辑），以及分别由解析语法和模拟语法给出的分析功能的可视化定义。从视觉定义中，生成VL规范，该规范确定VL特定的环境。研究得到德国研究委员会（DFG）和GRAPHIT项目（CNPq和DLR）的部分支持。c2002年由Elsevier Science B出版。诉 在CC BY-NC-ND许可下开放访问。15收音机闹钟模式报警设设时间模式日期显示选择设选择设置：模式选择通常，语言层包括语言在GEN GED中，图的转换及其分析由图转换引擎AGG [16，32]关于抽象语法支持图的转换对于语法指导的编辑以及解析和模拟（即，对于分析）是必要的。最初由AGG [8，9]（Attributed GraphGrammarsystem的缩写）提供的强大的语法分析功能已经被GEN GED [7，6]所采用。虽然AGG提出了一个图形编辑器来编辑图形语法，但VL只能通过图形的常用方法来定义。然而，使用GENGED，可以指定具有任意具体布局的VL：一旦定义了VL的符号和链接（VL字母表），就可以建立语法语法，解析语法和模拟语法。在[5]中，我们已经展示了如何定义一个简单的模拟文法，并将其用于模拟自动机。然而，需要为GRACE [2，23]引入的变换单元所支持的控制机制来模拟更复杂的VL，如状态图，如图所示。1.一、Fig. 1.状态图示例在下面的两个部分中，我们对A GG/GEN GED进行了简要的总结。一些概念是沿着分层状态图的规范来解释的。由于篇幅所限，我们没有给出[10]中的全部说明。在第4节中，我们讨论了一些相关的方法，在第5节中，我们做了一些最后的评论。2一个GG图变换概念在AGG中，由顶点和有向边组成的类型（标号）图和属性图图2示出了对图1所示的无线电时钟的行为进行建模的状态图的AGG（抽象语法）图。该图形由GEN GED编辑规则构建并由AGG导入。图在图2中，所有矩形表示属性顶点（VL的符号），并且箭头表示边缘（VL符号之间的我们使用缩写S表示状态，H表示层次结构，T表示转换。每个状态和转换都配备了一个String属性，即每个状态都有一个特定的状态名称（SN），每个转换都包含一个事件（EV）。Java对象和表达式对顶点和边的属性遵循[26]中介绍的属性图语法的思想。两个图之间的关系并且由图态射它映射了的顶点和边。这些映射G EN GED不使用边的属性。16tTT TTsn1 SN 1：S2：SSNEVSNsn1 SN 1：S2：SSN sn21：S 1：SN SN1：S 1：SN SN图二. AGG中的示例抽象语法图。必须是类型兼容的，属性值也必须一致图图3示出了两个图和一个图态射，图态射由顶点所注释的数字来说明，例如，1：Sin被映射到1：Sin。G H图三. AGG中的态射示例。图变换定义了基于规则的图操作。一般来说，图文法（由一个开始图和一组规则组成）将乔姆斯基文法从字符串推广到图。开始图表示系统的初始状态（这里是一个图），而规则集描述可能的变化。图形规则包括两个图形：和右手侧命名规则态射，以及可选的一组参数。此外，一个规则可能包含一组NAC，精确地指定那些匹配情况的分数，这些情况对于一个规则是适用的来说必须不存在。图4示出了支持将状态与状态名称（参数）一起插入的图形规则。NAC要求具有给定状态名称的状态不在应用规则的图中插入状态（String sn）NAC L R见图4。使用NAC的图形规则示例。将规则应用于图需要从规则的左侧到该图的态射（也称为匹配.匹配标记工作图中参与规则应用的顶点，即匹配图像中的顶点。在A GG中实现了两种变换概念，即单推出（SPO）和双推出（DPO）方法。在SPO方法中应用规则，隐式地删除所有悬挂边，而在DPO方法中，如果结果图将具有悬挂边，则禁止应用规则（参见图1）。[15]了解更多详情）。[8]中提出的解析算法（基于上下文分层图文法（CLGG）和关键对分析）已经在AGG中实现。这个组件被称为GG图解析器：17Alphabet语法VL规范机级别图解析器图形转换系统PARCON约束求解器AGG<<用途>><<用途>>工具级别<<用<<用链接编辑器符号编辑器VL环境规范编辑器语法编辑器字母编辑器顶点和边类型到层，使得[8]中的分层条件得到满足，规则对给定终端图的逐层应用总是终止。粗略地说，如果每个规则删除至少一个来自较低级别（删除层）的顶点或边，并创建较高级别（创建层）的图形对象，则满足分层条件 在GG中，层的定义由相应的对话框支持;用户被告知分层条件的满足情况。关键对分析[31，27]用于通过图转换更有效地进行解析：冲突规则应用程序之间的决策尽可能延迟。这意味着首先应用非冲突规则，并尽可能减少图。然后，通过为解析算法的回溯部分创建决策点来处理规则应用冲突。对于CLGG规则的关键对分析[8]，逐层分析是足够的，因为只要较低层的规则仍然适用，就不会应用上层的规则。到目前为止提到的所有AGG功能都被GEN GED使用，这将在下面的章节中解释。3GEN GED中的VL规范和验证GEN GED环境实现了虚拟L的视觉定义概念。基于视觉字母表（其中VL中出现的符号和链接的类型由语言设计者定义），可以给出几种视觉语法，即用于语法指导编辑的语法、解析语法和模拟语法。因此，GEN GED环境分别包括字母表编辑器和语法编辑器字母表是语法编辑器的输入，在语法编辑器中生成所谓的字母表规则，定义该编辑器的编辑一旦一个字母表和可能的一些语法被定义，一个规范编辑器支持成分的组合。如果给出了一个语法分析器，它可以通过由AGG图分析器提供的分层功能来扩展。也可以计算临界对。此外，为了控制图行为的执行，可以在模拟语法之上定义模拟步骤。AGG系统用于在语法编辑器和特定于VL的环境中转换图的抽象语法。相对于具体语法（布局）定义的图形约束由约束求解器PAR CON [19]求解。图5说明了GEN GED组件、数据流和使用关系。图五. GEN GED环境的组成部分。18incl重叠抽象语法一PD法paPD字符串EVTbH超HSSNinit字符eInit=重叠为上博尔德（P（PPA（P与其中类型（标记）图在前的AGG相比，在GENGED中实现了通过根据布局的约束满足问题扩展的类型图。这些扩展的类型图描述了视觉字母表：像状态（S）这样的符号或像String类型的状态名（SN）这样的数据属性表示（抽象语法）顶点。这些顶点通过表示布局的图形属性来增强。视觉符号的定义由符号编辑器支持;链接编辑器允许定义链接。根据抽象语法，每个链接由两个符号之间的有向边表示。图形约束指定了如何根据具体语法连接符号布局。图6说明了我们的状态图语言的视觉字母表;对于抽象语法，我们使用与图6相同的符号3和4根据具体的语法，顶点由图形对象（虚线箭头）增强，并且图形由PH表示的图形描述了占位符符号，这些占位符符号在特定于VL的环境中是不可见的矩形。这里，使用层次符号（H）是为了允许嵌套状态图。我们省略了并行状态的建模，由于空间限制，我们不考虑最终状态标记。相反，我们已经介绍了模拟语法所需的符号，这些符号由阴影椭圆包围。活动状态由A符号表示，并由红色圆角矩形可视化另外两个符号PA和PD是逻辑辅助符号。模拟语法需要它们来跟随初始标记并触发转换。见图6。一个州的字母表。字母表是使用语法编辑器来定义不同种类的语法的基础图7示出了在句法语法中出现的一些语言生成编辑规则。这些规则在GEN GED语法编辑器中通过应用从视觉字母表自动生成的字母表规则来视觉地定义。使用这些语言生成规则，建立了如图2所示的抽象语法图。它们通过定义每个抽象顶点的图形属性这意味着，基于由单个状态符号给出的开始图，可以通过应用规则InsertSubState插入子状态，并通过规则MarkInit将状态标记为初始状态。每两个状态符号可以通过应用插入转换规则来连接。关于类型图和类型图之间的差异的一些讨论，读者可以参考[20]。19MarkInit（）Lsn1 1：SN1：S SuperH1：HsubHsn1sn22：SN2：SN2SN11：SN 1：初始化初始化sn2R1：S SuperH1：HsubH2：SN1SN2开始SN1：SN1：SinsertSubState（StringLsn1 1：SN1：SSN11 ：SN1：H subH2：SNsn2RSuperH1：2：SNSN1sn1sn2Integer（String）Lsnl 1：SN1：S2：SN2：SN2SN11：SN EV1：S TRBeev 2：SN sn22：SSN1SN2SN1EVSN2图7.第一次会议。一些生成语言的编辑操作。很明显，状态的初始标记可以通过应用规则MarkInit任意执行，即编辑不符合常见的状态图语义。为了允许图的语法检查，必须定义一个解析语法此外，过渡符号的插入不受相应规则的限制。读者可以参考[6]，以便更仔细地了解解析语法，识别不允许带有转换符号的状态图。重要的是，解析语法以及语法和模拟语法也是可视化定义的。然而，解析语法可以扩展的分层功能的定义是由类似于AGG图解析器的相应对话框也就是说，在VL分析领域，在AGG中的图解析和GENGED中的语法检查之间没有区别作为我们对图表进行算法操作的唯一手段，规则应用构成了模拟概念的基础。因此，一个仿真规范，一个所有仿真相关数据的容器，由一个仿真语法和可选的一组仿真步骤组成，这些步骤指定了如何应用语法规则模拟步骤描述了在模拟过程中要执行的atomar步骤它是参数化的和不可分割的，因此在将值绑定到参数并将步骤应用于给定图之后，生成的结果图没有任何中间结果。模拟步骤的核心是模拟表达式，即在应用步骤时执行的一种程序给定一个图和一个模拟表达式中使用的变量的赋值，它的求值结果是一个新的图和一个布尔值。记住这一点，模拟表达式的语法和语义的归纳定义是直接的。基本的模拟表达式是规则表达式。它有两个参数，一个规则的模拟语法和分配规则的参数后者将参数绑定到具体值或变量，确切地说，20模拟表达式所属的模拟步骤的参数当评估一个规则表达式时，它的规则被应用于给定的图.如果应用程序成功，则计算将生成派生图和值true，否则将生成未更改的图和值false。两个模拟表达式和可以逻辑地复合到和或或。在这两种情况下，首先进行评估，然后使用结果图进行评估。因此，对完整表达式的求值产生了与和或相同的图，但是布尔值是对的求值所产生的值的逻辑和或的和 . 的和和ORC变体的特征在于条件求值，即，仅当分别产生真或假时才被求值。最后实现了控制流表达式。并给出了模拟表达式，如果然后其他而当 做 代表这些。 首先评估if then else f表达式，如果它产生true，则随后评估，否则，请执行以下操作。 一会儿做完表情，被求值，如果结果为真，则也被求值，然后再一次求值整个表达式。如果为false，则计算终止，计算结果为图，如果循环体至少执行过一次，则布尔结果值为true，否则为false如前所述，在GEN GED中，仿真步骤和示例的定义基于给定的仿真语法，因此它由规范编辑器支持（参见。图5）。和前面一样，我们的状态图语言的整个模拟规范的介绍和讨论不在本文的范围之内读者可参考[10]进行全面调查。4相关工作在文献中，可以找到许多用于指定和生成VL特定环境的概念和工具（参见[28、11、22]）。这个事实使得比较非常困难。例如，大多数工具都不允许像GEN GED这样的可视化另一个标准是由特定于VL的环境中支持的编辑模式（徒手或语法指导）以及内部表示模型（如果可用）的类型给出的。与AGG/GEN GED密切相关的是非商业性的基于图的方法和工具，它们允许指定和分析通用VL。这意味着像Fujaba [17]（从UML到Java再回来）这样的专用工具不在比较的范围内。大多数用于创建自由编辑器的工具直接分析图，避免创建像图这样的内部表示模型。例如，在VisPro [36]、Penguins [30]和VLCC [12，33]中，没有考虑内部模型。Vlcc使用位置文法和类似LALR（1）的解析器。此外，在[13]中，引入了扩展位置文法，使得这种方法不再限于上下文无关文法。在企鹅约束多集文法和21使用Prolog类解析器，而在VisPro中，考虑了保留的图形语法和图形解析器[35]。然而，在VisPro中，VL的集合被限制为图解VL，即，符号只能用线和箭头连接。VLCC [12，33]（扩展位置语法）和DIAGEN [24，14]（超图语法）使用受限的上下文敏感规则来解析VL。在一些出版物中提到，所有VL都可以通过相应的方法捕获。然而，关键对分析，因为它是由AGG/GEN GED支持尚未考虑。然而，在解析之后，在DIA GEN生成的编辑器中，不正确的图表部分用特定的颜色标记，而在GEN GED生成的编辑器中，用户仅被告知图表中的错误。可能需要自由编辑，因为用户可以不受限制地创建和修改图;但这些图可能包含错误。相反，纯语法指导的编辑提供了一组编辑命令，可以将正确的图转换为其他正确的图;但是用户仅限于这些命令。文[1]提出了两种编辑模式的集成，但尚未实现。结合两种编辑模式的想法是由DIA GEN[14]也是GEN GED。此外，DIAGEN在完成时考虑了内部表示模型（图）[25]《礼记·乐记·乐记·乐记·乐记》但是，Kogge只允许语法定向编辑。另一个重要的标准是由布局处理给出的，因此，由相应的工具实现的约束求解技术的性能到目前为止，GEN GED认为没有有效的约束求解处理，这降低了VL特定环境中的性能。特别是，如果考虑像statecharts这样的图形语言，对于每个箭头的位置，需要所谓的或约束，以便找到正确的开始和结束点。对于每个或-约束，整个约束满足问题被复制和解决。这是更好地实现了DIA GEN，其中几个布局算法实现了不同种类的VL考虑。然而，如果绘制大型图表，DIAGEN也存在一些关于约束求解的性能问题。此外，DIAGEN仅支持文本规范，而在GEN GED中，VL的视觉规范处于前列。关于具体的语法，即布局，VL-Eli [34]可能给出了一种有前途的方法，它提供了一个预定义的视觉模式库（列表，表格，表单，线条等）。可以组合用于定义VL的布局。 布局的计算依赖于一些抽象的语法属性（属性语法是底层的形式主义）。然而，在其当前状态下，必须在文本上指定VL，并且在生成的编辑器中仅支持语法指导的编辑5结论在本文中，我们概述了由工具AGG [3]和GEN GED [18]提供的VL的规范和验证技术（两者都是important）。22在Java中实现）。GENGED是专门为视觉定义的VL，包括视觉字母表和不同种类的语法，即语法，语法分析和模拟语法。在给定语法的基础上，图分析和AGG提出的关键对分析可以用于GENGED中的VL的语法检查。 第一次尝试解析类图[7]和状态图[7，6，10]。我们将在未来考虑进一步的VL解析。此外，必须将实现的解析算法与有关效率的方法进行比较。文中简要提出的仿真概念已经在GEN GED中实现。我们使用与本文描述的语法规则相同类型的图重写规则来指定视觉行为模型的操作语义。活动状态通过用特定的活动符号标记它们来建模。 在这个意义上，模拟规则的应用模拟状态图行为。此外，模拟表达式支持受控执行。可视化行为模型，如状态图或Petri网，如果它们的行为显示在特定于应用程序的布局中，通常会更好地一方面，状态图的行为可以建模为标记的变化另一方面，定义状态和转换的新布局，行为应该在隐藏底层结构的应用程序特定布局中可视化。这种可视化行为模型的动画方法已经在[4]中针对Petri网进行了描述这意味着我们将实现相应的动画概念，同时我们必须改进约束处理概念。GG将通过[21]中提出的图约束进行扩展，以确保条件图文法的一致性：图约束可以将条件（甚至图部分）表示为某些顶点和边的存在性或唯一性。这样的条件可以转换为必须由每个转换步骤的结果满足的后置条件由于在GEN GED中，抽象语法的转换是由AGG完成的，因此GEN GED将来也可以利用这一特性。谢谢。我们要感谢匿名评论者对本文以前版本的宝贵意见。引用[1] M. Andries，G. Engels，and J. Rekers.如何表示一个可视化程序？在[28]中，第245[2] M. Andries，G.Engels，A.哈贝尔湾霍夫曼，H.J. Kreowski，S.Kuske，D.丰满，A. 是的，还有G。塔恩泽河为规范和程序进行快速转换。计算机程序设计科学，34：1[3] AGG主页，http://tfs.cs.tu-berlin.de/agg23[4] R.巴尔多赫Ehrig，和C.厄梅尔可视化建模语言的通用描述、行为和动画。集成设计和工艺技术（IDPT 2000），达拉斯（德克萨斯州），美国，2000年6月。[5] R. Bardohl ， K. 埃 里 希 角 Ermel ， A. Qemali 和 我 。 温 霍 尔 德 G 在 H.- J.Kreowski ， 编 辑 ， 应 用 图 形 转 换 的 APPLIGRAPH 研 讨 会 论 文 集 （ AGT2002），第71- 82页[6] R. Bardohl和C.厄梅尔使用GEN GED可视化指定和解析状态图变量。在[29]中。[7] R. Bardohl，T. Schultzke和G.坦策GEN GED中的可视化语言分析。Proc.国际研讨会上的图形转换和可视化建模技术（GT-VMT50，2001年。[8] P. Bottoni，A. 是的，G。 塔恩泽河基于关键对分析和上下文分层图变换的虚拟语言有效分析IEEESymposium on Visual Languages，2000年9月。长版本可作为技术报告SI-2000-06，罗马大学。[9] P. Bottoni和G.坦策基于上下文分层图变换的状态图变体的解析和语义。在[29]中。[10] R.巴铎和我。温霍尔德可视化语言的规范和分析技术。技术报告2002/13，柏林工业大学，2002年。ISSN 1436- 9915。[11] M. 伯内特视觉语言研究参考书目，http://www.cs.orst.edu/burnett/vpl.html[12] G. Costagliola，A.D. Lucia，S. Ore office和G.龙猫位置文法：视觉语言类LR解析在[28]中，第1711998年[13] G. Costagliola和G.波兰人扩展位置文法。在Proc. IEEESymposium on Visual Languages，第171-192页[14] DIA GEN主页，http://www2.informatik.uni-erlangen.de/DiaGen/[15] H. 埃里格河 Hec kel，M. Korff，M. 卢韦湖 R ibeiro，A. 等等，还有克拉迪尼。图变换的代数方法II：单推出法及与双推出法的比较。In G. Rozenberg，编辑，Handbook of Graph Grammars and Computing by Graph Transformation，第1卷：基础，第247-312页。世界科学，1997年。[16] C. Ermel，M. Rudolf和G.坦策AGG方法：语言和工具环境。In H. Ehrig，G.恩格斯，H. J. Kreowski和G. Rozenberg，编辑，Handbook of Graph Grammars andComputing by Graph Transformation，第2卷：应用程序，语言和工具，第551-603页。世界科学，1999年。[17] Fujaba主页，http://www.upb.de/cs/fujaba/[18] GEN GED主页，http://tfs.cs.tu-berlin.de/genged[19] P. 格里贝尔。 ParallelesL？ senvongra fissch enC onstraints. 博士论文，德国帕德博恩大学，1996年2月。[20] R. Hec kel，A. C orradini，H. 埃里希，和M。 我爱你。类型化图变换系统的结构化与验证。数学。斯特吕克。在Comp. Science，6（6）：613- 648，1996中。另见技术报告96-22，柏林工业大学，1996年。24[21] R. Heckel和A.瓦格纳 条件文法的一致性保证一种建设性的方法。“图的重写与计算”，国立台湾科技大学，1995年[22] B.易 卜 拉 欣 VisualLanguagesandVisualProgramming，http://cui.unige.ch/eao/www/Visual/[23] H.- J. Kreowski，G. Busatto和S.库斯克GRACE是基于图变换的规范化的统一方法 。 InProc. of Int. Workshop on Uniform Approaches to Graphical ProcessSpecification Techniques（UNIGRA[24] O. KoéthandM. 米纳斯生成 Diagra mEditorsProvidinggFree-HandEditinggas 以及语法指导编辑In H. Ehrig和G. Gratra柏林工业大学，2000年3月25日至27日。[25] Kogge 主页，http://www.uni-koblenz.de/ist/kogge.en.html[26] M. 罗维，M. Korff，andA. 瓦涅河属性图变换的一个代数式在核磁共振室。睡吧，M.Plasmeijer和M.C.van Eekelen，编者，术语图重写：理论与实践，第185Wiley Sons Ltd，1993年。[27] M. 洛和J。 穆勒河在单个P中进行关键P分析时，应采用G RR R。在G. Valiente Feruglio和F. Rosello Llompart，编辑，Proc. Colloquium on GraphTransformation and its Application in Computer Science。Technical Report B-19，Universitat de les Illes Balears，1995.[28] K. Marriott and B.迈耶，编辑。视觉语言理论Springer，1998年。[29] M.我和我的朋友。 很好，编辑们。2001年在意大利斯特雷萨举行的“视觉 语 言 与 形 式 方 法 国 际 研 讨 会 ” 上 的 国 家 计 算 机 建 模 会 议http://www2.informatik.uni-erlangen.de/VLFM01/Statecharts/的网站。[30] 企鹅主页，http://www.csse.monash.edu.au/css/projects/penguins/[31] D. 丰满。超图重写：连通性的临界对和不可判定性在M.R Sleep、M.J. Plasmeijer和M.C. van Eekelen，编者，术语图重写：理论与实践，第201-214页。Wiley Sons Ltd，1993年。[32] G.坦策 AGG：一个代数图变换的工具环境。在LNCS 1779，第481[33] VLCC主页，http：www.dmi.unisa.it/people/costagliola/www/home/ricerca/vlcc/vlc c c.htm[34] VL-Eli主页，http://www.upb.de/fachbereich/AG/agkastens/forschung/vl-eli/[35] D.- Q. Zhang和K.张某保留图语法：一个图解VPL的规范化工具。In Proc. IEEESymp.《视觉语言》，意大利卡普里，第288-295页，1997年。[36] D.- Q. Zhang和K.张某VisPro：一个可视化语言生成工具集。在Proc. IEEESymposium on Visual Languages，第195-202页