可视化语言的可视化规范和语法导向编辑器的生成与解析方法

电子笔记在理论计算机科学50第3期（2001年）。GT-VMT 2001网址：http://www.elsevier.nl/locate/entcs/volume50.html6页GenGEd1中的可视化语言解析R. Bardohl，T. Schultzke，G.坦策县计算机科学德国柏林工业大学摘要GenGEd支持可视化语言的可视化规范和语法导向编辑器的生成。然而，用户 并 不 总 是 期 望 语 法 指 导 的 编 辑 。 因 此 ， 我 们 通 过 解 析 工 具 扩 展 了GenGEd，这些工具也允许自由编辑。1引言由于缺乏一种易于使用和有效解析的标准语法定义形式，可视化语言的语法定义和可视化语言解析是一个困难的问题。迄今为止发表的大多数建议都依赖于上下文无关的语法规则，即，它们允许替换左手侧的单个非端子。使用这些方法并不总是能够在头脑中定义VL。因此，已经提出了 上 下 文 敏 感 的 图 文 法 ， 例 如 ， 分 层 图 文 法 （ Layered GraphGrammars，LGG）[11] LGG规则允许删除和创建多个元素和关系，表示为顶点和边。不幸的是，LGG仍然不足以方便地定义一般的VL，因为至少缺少否定应用条件（NAC）和规则的进一步条件因此，开发了一种新形式的LGG，称为这种方法包括保证解析过程终止的分层条件的定义。此外，静态分析技术，如关键对分析[10，9，12]，可以用来识别最大的规则集，可以解析而无需任何回溯。VLCC [3]和DiaGen [8]使用受限的上下文敏感规则来解析VL。这种规则成功地应用于相当简单的语言，1 研究得到德国研究理事会（DFG）以及APPLIGRAPH（ESPRIT基础研究工作组）和GRAPHIT（CNPq和DLR）项目的部分支持c 2001年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。2GT-VMT 2001 { R. Bardohl，T. Schultzke和G. 坦策在更复杂的情况下使用可能会很棘手。CLGG与保留图文法（RGG）有关，RGG是LGG的另一种限制和修改形式[13]。RGG也有某种嵌入机制，但不支持谓词（然而，在GenGEd中不使用）和NAC的定义。它们的规则必须是局部一致的，这样[11]中的多项式朴素LGG解析算法才能工作。不支持用于处理已识别的关键规则对的回溯。在第2节中，我们简要回顾了GenGEd环境的视觉规范的VL。GenGEd中的解析工具及其用法将在第3节中提出，并通过一个小例子（著名的UML类图的子集）进行说明虽然这个例子不是很有表现力，但它适合于说明概念。第四节我们总结一下。2GenGEd环境GenGEd环境实现了VL的可视化规范的概念[1]。一个VL-规范由一个视觉字母表和一个视觉文法给出。 在视觉字母表中，出现在VL中的符号和链接的类型被指定。视觉语法由一个开始表达式和一组上下文相关的语法规则组成。最初，语法规则定义了特定于语言的图形编辑器的语法指导的编辑命令，即，视觉语法不仅包括语言生成规则，而且还包括一组方便的编辑规则。在下文中，我们表明，VL-speci阳离子的概念可以很容易地扩展的speci阳离子的剖析。GenGEd基于代数图变换[4]和图形约束求解[7]。视觉字母表由属性图结构签名2和约束满足问题表示，该约束满足问题确定视觉元素的位置和大小。相应地，一个视觉语法表示的属性图结构语法的约束满足问题的每个视觉表达式是satised。此外，我们区分两个语法层次，即抽象的语法描述的逻辑部分的VL，和具体的语法表示的布局。根据VL规范的构成，GenGEd环境包括字母表编辑器和语法编辑器。指定的字母表是语法编辑器的输入，在语法编辑器中生成所谓的字母表规则，定义该编辑器的编辑命令。 这样就保证了只有正确的视觉表达才能被语言设计者所定义。对于根据抽象语法的视觉表达式的转换，使用Agg系统[6]。图形约束由约束求解器ParCon[7]求解。2 图结构签名是根据[5]的具有一元运算符号的代数签名3抽象语法包字符串在_CNCN a_CN在类开始端Assoc具体语法12分，赫尔夫。GT-VMT 2001 { R. Bardohl，T. Schultzke和G. 坦策文[2]中提出的语法分析算法（基于上下文分层图文法（CLGG）和关键对分析）现在已经用Agg系统实现，因此我们称之为Agg图分析器。在GenGEd中，我们集成了Agg图解析器，这样我们就产生了一个可视化语言的解析器。从这个意义上说，不仅语法指导的编辑，而且自由编辑是可用的在GenGEd生成的特定图形编辑器中，类似于[8]。和以前一样，字母编辑器支持视觉字母的定义，包括符号和链接的类型。基于视觉字母表，语法编辑器可以以两种方式使用：用于定义全面的语法指导的编辑规则以及用于定义分析规范。 后一种解释如下。3类图如前所述，视觉字母表描述了VL的符号（顶点）和链接（边）的类型。图1说明了UML类图子集的可视字母表。它包括所需的符号，并解释了这些符号是如何连接的。在顶部显示了抽象语法，其中词汇符号Package，Class和Asynchronous（关联）由矩形框起，而String类型的属性符号CN（类名）由圆角矩形框起。箭头指示符号之间的链接。符号的布局通过虚线箭头所示的所谓布局操作与抽象语法相连接。必须为每个（抽象）链接定义的约束由符号布局之间的虚线箭头表示。Fig. 1. 类图语言的可视字母表。视觉字母表是使用GenGEd语法编辑器定义解析规范的基础。基于Agg图解析器，解析规范由解析语法（可以使用VL的方法来定义）、层函数和关键对组成。出现在解析语法中的图规则由类型（标记）图的左侧（L）和右侧（R）组成。两个规则面的部分彼此相关。在图形变换期间，相关部分被保留。删除L的所有非相关图对象，创建R的所有非相关对象。此外，规则可以包含一组NAC，这些NAC精确地指定对于规则适用来说必须不存在的匹配情况的那些部分。4L删除Package（）Rx：包装z1：包装X：Classz：砷y：类别L删除阿斯彭Ry：类别X：Classz1：包装CNz1：包装CNx '：CNX：Classy：类别y '：CNz1：包装CNx '：CNX：ClassNACL删除RClass（）z1：包装GT-VMT 2001 { R. Bardohl，T. Schultzke和G. 坦策将规则以及顶点和边类型映射到层，以满足特定的分层条件（参见[2])规则（根据规则层）到给定终端图的逐层应用总是终止。粗略地说，如果每个规则删除来自较低级别（删除层）的至少一个顶点或边，并创建较高级别（创建层）的图形对象，则满足分层条件。关键对分析[10，9，12]可以用来使图变换的解析这意味着首先应用无冲突的规则，并尽可能地减少图。然后，通过为解析算法的回溯部分创建决策点来处理规则应用冲突。对于CLGG规则的关键对分析，逐层分析是足够的，因为只要较低层的规则仍然适用，就不应用上层的规则。在GenGEd语法编辑器中，关键对是从Agg图解析器自动生成的，但是语言设计者必须定义其余的成分对于我们的简化UML类图的例子，解析规则表示视觉符号的删除，使得对于视觉字母表的每个下面提出这些规则和层函数图2（a）说明了包的解析规则如果包为空，则可以如果应用规则的包不为空，则悬挂条件禁止应用此规则。允许删除关联符号的规则如图2（b）所示。这里我们只考虑同一个包的类通过关联符号联系起来(a)（b）第（1）款图二、包符号（a）和关联符号（b）的解析规则支持删除类符号的规则如图3所示根据视觉字母表，一个类符号总是必须与一个由规则的左手边L表示的包相关联。此外，我们期望用户总是插入一个类符号和一个类名，该类名由节点x '：CN表示，并保存变量cn表示的值。NAC规定类名在一个包中必须是唯一图三. 类符号和类名的解析规则。5GT-VMT 2001 { R. Bardohl，T. Schultzke和G. 坦策下面给出了我们的小例子的层函数。因此，我们使用缩写dl表示删除层，cl表示创建层，rl表示规则层。注意，规则层支持规则应用的排序，而删除和创建层对于解析算法的终止是必要的。请注意，语言设计者不能为链接定义创建层或删除层;这些层是根据链接在其域中的符号自动生成的，即，对应链接边的源顶点。类型DEP凹进层规则层dl（天冬氨酸）=氯（砷）= 0rl（DeleteAsploy（））= 0dl（类）=cl（类）= 1rl（DeleteClass（））= 1dl（包装）=cl（包装）= 2rl（DeletePackage（））= 2对于只需要执行一次的关键对分析，使用解析语法和层函数调用Agg生成的解析规范和可视字母表是图形编辑器的输入，用户可以在其中以自由编辑的风格操纵可视表达式（图）。为了对照视觉语法检查视觉表达式，Agg图解析器将解析规范与视觉表达式一起作为输入，并检查表达式是否正确。结果将显示在图形编辑器中。64结论基于关键对分析的图分析可以用于高效的VL分析。集成在GenGEd中的VL解析器基于Agg的一个新的图形解析组件。 自由编辑类图的第一次体验已经完成。我们将在未来考虑更复杂的VL，此外，实现的解析算法进行了比较，与有关的方法效率。引用(a) R.巴铎基于代数图变换的可视化语言的可视化定义。德国柏林工业大学博士论文，1999年。Verlag Dr.科瓦奇2000年(b) P. Bottoni，A. 史昌湖rr和G. 泰泽。基于临界对分析和上下文分层 图 变 换 的 视 觉 语 言 识 别 分 析 。 IEEESymposium on VisualLanguages，2000年9月。7GT-VMT 2001 { R. Bardohl，T. Schultzke和G. 坦策(c) G. Costagliola，A.D. Lucia，S. Ore ce，G.龙猫位置文法：视觉语言类LR解析的形式主义在K. Marriott and B. Meyer ， editors ， Visual Language Theory ， pages171{ 192，Springer，1998.(d) H.埃里格河Heckel，M. Kor，M.洛湖Ribeiro，A.瓦格纳和科拉迪尼。图变换的代数方法II：单推出法及与双推出法的比较在G. Rozenberg，编辑，Handbook of Graph Grammars and Computingby Graph Transformation，第1卷：基础，第247页。World Scientic，1997.(e) H. Ehrig和B.马尔代数规范基础1：Equations and Initial Semantics，第6卷，Escort Monographs onTheoretical Computer Science。施普林格，柏林，1985。(f) C. Ermel，M. Rudolf和G.坦策AGG方法：语言和工具环境。In H.Ehrig，G.恩格斯，J. J. Kreowski，以及G. Rozenberg，编辑，Handbook of Graph Grammars and Computingby Graph Transformation，第2卷：应用程序，语言和工具，第551页。World Scienti c，1999.(g) P. 格里贝尔。 Para a llelesL我的意思是，我的意思是，我的意思是， 博士论文，德国帕德博恩大学，1996年2月。(h) O. Koth和M. 米纳斯生成图表编辑器，提供自由编辑和语法指导编辑。在Proc. GRATRA'2000 - Joint APPLIGRAPH and GETGRATSWorkshop onGraphTransformationSystems ， 第 32 页 {39. TechnischeUniversit2000年3月，德国柏林。(i) M. Lo we和J. 微米的ller.单推出图重写中的临界对分析。In G.Valiente Feruglio和F. Rosello Llompart，编辑， Proc. Colloquium onGraph Transformation and its Application in Computer Science。TechnicalReport B-19，Universitat de les Illes Balears，1995.(j)德特勒夫·普朗普超图重写：临界对与连通性的不可判定性。在M.RSleep、M.J. Plasmeijer和M. CJ van Eekelen，编辑，术语图重写，第201页{214.Wiley，1993年。(k) J. Rek ers和A. 史昌湖RR. 用分 层 图 文 法定义和生成可视化语言。Journal of Visual Languages andComputing ， 8 （ 1 ） ： 27{55 ，1997.(l)T.舒尔茨克视觉语言解析器的概念与实现。硕士论文（德文），柏林工业大学，德国，2001年(m) D.- Q. Zhang和K.张某保留图语法：一个图形VPL的规范工具。在Proc. IEEE Symposium on Visual Languages （ VL'97 ），第288页{295.8IEEE ComputerSociety Press，1997.