属性NCE图文法应用于表格编辑问题的算法讨论

电子笔记在理论计算机科学50第3期（2001年）。GT-VMT 2001网址：http://www.elsevier.nl/locate/entcs/volume50.html7页属性NCE图文法在句法编辑表格形式TOMOKAZUARITAA;1KiYonobuTOMIYAMAa;2KenseiTSUCHIDAb;3TakeoYAKUa;4a部。Comput. Sci.日本东京世田谷樱城水，日本，156-8550b部Inf. and Comp. Sci.，东洋大学2100，Kujirai，Kawagoe，Saitama，350{8585，Japan摘要本文讨论了基于一种特殊的图文法HNGG [2]编辑程序说明书表格的问题。首先，我们通过将Cornell Program Synthesizer [8]的概念扩展到属性NCE图语法来形式化语法指导的编辑方法（参见。[1]）。接下来，我们讨论编辑方法的算法。关键词：图文法，可视化编程，软件开发，语法指导编辑器1引言表格的机械化编辑是软件工程方法学中的重要问题之一。Cornell程序合成器是众所周知的，通常被称为结构化和基于文本的编辑器，它成功地使用了属性语法[8]。表格形式由几个不同的模型表示（例如，[6]）。我们将表格形式中的每一项分配给一个属性节点。这种分配自然表示表格形式中的项的顺序和项的位置。由于表格中项目的数量通常是不受约束的，并且项目的顺序具有某些有效的含义，因此表格形式由图语法表示[2]。因此，机械1 电子邮件地址：arita@cssa.chs.nihon-u.ac.jp2 电子邮件地址：tomiyama@cssa.chs.nihon-u.ac.jp3 电子邮件地址：kensei@eng.toyo.ac.jp4 电子邮件地址：yaku@cssa.chs.nihon-u.ac.jpc 2001年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。2GT-VMT 2001 {T.Arita，K.富山湾Tsuchida和T.雅酷节目名称：河内字幕：图书馆编号：cs-2001-02版本号：1.1作者：K.Tomiyama发布时间：2000/06/10批准人：当前版本：2000/10/01关键词：河内塔CR代码：语言：简体中文软件要求：海合会操作方式：硬件要求：功能说明：范例：图1.一、Hiform文档中的表格形式及其对应的图形。表格形式的编辑应该通过某些语法编辑方法来执行。在本文中，我们考虑一个编程文档，Hiform，作为表格形式的一个例子。Hiform文档是17种表格形式的集合，包括ISO 6592指南中定义的所有项目[9]，[2]。应该注意的是，某些ISO 6592表格形式被视为表格形式，因为它们具有模块化结构。这种表格形式用图形表示。图1示出了Hiform形式及其对应的图。该图的构造如下：（1）图的节点标签示出表格形式的项目的类型。 (2)边标签显示项目之间的关系。“lf”表示“left of”的意思，“ov”表示“over”的意思，in表示within的意思。本文认为，表格形式的机械处理可以通过图形的句法操作来有效地在文献[2]中，Hiform中每个形式的内部结构都是由一个属性NCE图文法定义的。形式形式是由其语法生成的图形所规定的本文的目的是利用文[1]和[2]中的结果将Cornell程序合成器机制推广到图上，并形式化了一种图的语法编辑机制。HNGG [3]中的插入被定义为使HNGG的并发[7]有效地执行此操作第二节给出了初步定义。 第三节利用实例序列给出了编辑机制的形式化定义[1]。并以HNGG为例说明了本文定义的正确性。第四节是我们的结论。2预赛2.1[7]第七话设是节点标签的字母表，是边标签的字母表。字母表上的一个图，是一个三元组H =（V; E;），其中V是一个结点的nite非空集合，Ef（v;;w）j v; w 2 V; v 6= w; 2 g是一个边的集合，并且V！是一个节点标记函数。在在超过OVOVLFOVLFLF在超过OLFLFOVLFOV例如功能操作语言A1关键词批准人作者库代码字幕程序名头硬件要求软件要求CR代码当前版本原始发行版本3GT-VMT 2001 {T.Arita，K.富山湾Tsuchida和T.雅酷定义2.1 edNCE图文法是6元组G =（;P; S），其中是节点标签的字母表，是终端节点标签的字母表，是边标签的字母表，是最终边标签的字母表，P是产生式的集合，S2是初始非终结符。一个产品用形式p：X表示！（D; C），其中X 2，D是一个图，和，和CVD fin; outg是连接关系。22.2生产副本的组成[1]edNCE图文法的生产副本的复合表示是用于表示用于将期望结构的子图嵌入到图中的图重写规则的理论和实践方法。定义2.2 [1]设G =（，P，S）是一个edNCE图文法。设 p1：X1 ！（ D1，C1）（ D1 =（VD1，ED1，D1））和p2：X2 ！（D2，C2）（D2=（VD2，ED2，D2））是G. 如果u2VD1 X2=D1（u），且D1与D2不相交，则有一个（具有连接关系的）复合生产函数p ： X1！（D; C） 的定义 如下： D 是一 个图： VD=fVD1-fugg[VD2 a boutn odes. C=f（，=，！，d）2C1j！2VD1 -fug g [f（，=u，y，d）j92，（，=，u，d）2C1，（，=u，y，d）2C2g由p1和p2组成的复合生产副本p，记为p1= p 222.3Conuence属性[7]Conuence性质保证了推导的结果不依赖于产生式的应用顺序[7]。连续性是一个非常重要的属性，因为它保证了复合生产副本应用的有效性。在开发高效的语法分析算法时，这种一致性也很重要。定义2.3[7]一个edNCE图文法G =（;P; S）是动态连续的，如果对于由yG生成的每个中间图H以下成立：如果H）u1;p1 H1 ）u2;p2H12 和H）u2;p2 H2 ）u1;p1 H21（p1;p22P）是G的导子，其中u1;u22VH且u16=u2，则H12=H21.22.4属性NCE图文法[2]我们回顾了一个属性图文法的机械制图表格形式。属性NCE图文法给出如下。定义2.4[2]属性NCE图语法是一个3元组AGG= G; Att; F >其中G =（; P; S）是上下文无关的edNCE图文法，称为AGG的底层图文法。这里Att是AGG的属性集，F是AGG的语义规则集。24[客户端]GT-VMT 2001 {T.Arita，K.富山湾Tsuchida和T.雅酷P2内-语义规则PH5头上[列]语义规则[结构]0在在[ head ]1之上[正文]2x（1）= x（0）y（1）= y（0）x（2）= x（0）y（2）= y（0）+height（1）width（0）=max（width（1），width（2））height（0）=高度（1）+高度（2）0OV压头部在[scalar]1低频磁头lflf[列]超过2OVx（1）= x（0）y（1）= y（0）x（2）= x（0）+width（1）y（2）= y（0）宽度（0）=宽度（1）+宽度（2）高度（0）=max（height（1），height（2））图二、HNGG的部分作品内部结构[头]在OV[正文]图三. 一个应用生产P2的例子.2.5 [3]第二届世界卫生大会我们回顾了一个用于表格形式的属性NCE图语法。这种语法被称为Hiform嵌套表格形式图语法（HNGG）。HNGG =，它生成称为Hiform form form的模块化表格形式，其中GN =（N;N;N;N; PN; SN）是底层的NCE图语法。每个产生式都有一个用于绘制信息的语义规则。HNGG包括280个产生式和1248个属性规则。图图2给出了HNGG的一部分具有属性规则的产生式我们编写了类似于edNCE图语法风格的产品。图3是应用生产P2的示例。通过应用产生式P2，将标记为\inner{struct”的节点替换为P2的右侧的图。3模块表格的编辑在这一部分中，我们利用HNGG的产生式实例给出了编辑操纵的形式化定义，并利用HNGG的概念验证了我们定义的有效性。3.1生产实例编辑操作由生产实例定义如下。定义3.1生产实例（简称\instance”）是一个三元组（！，pi ，Hpi） ， 其 中 （ 1 ）！ 在 推 导 Di1） piDi 时 ，（ 2 ） pi ：Xpi！（Hpi;Cpi）2P是一个乘积，（3）Hpi 是一个 同构于H pi 的 边 补 图在Di1）piDi期间。我们记为Di1！H PI）pi如果Di，则Di直接从DI1通过应用在P25实例（！;pi;H pi）。26F1G1eiG1（x1，p1，H1）.q=q 1 Q 2 ...Qm*F2G2XIq（y1，q1，D1）.X***可插入？是的（x1，p1，H1）.（y1，q1，D1）... （ym，qm，Dm）.（xn，pn，Hn）G没有F误差**Qn我！H qi=1）我pn）nGT-VMT 2001 {T.Arita，K.富山湾Tsuchida和T.雅酷见图4。 插入过程的流程。如果存在一个生产序列p=（p1;;pn）和实例（！i;pi;H pi）对于每个产生式p i（1 i n），实例序列是（（！ 1;p1;H p1）;;（！n;pn;Hpn））。edNCE图语法的推导由推导树表示。然而，推导序列作为处理模型的推导的表示是方便的。因此，我们用产生式序列表示一个派生。3.2句法插入在这一节中，我们定义了句法插入。这种操纵是基于HNGG。语法指导的编辑是通过使用实例序列来定义的定义3.2对于导出序列D0！1例H p1）p1！i1Hpi1）pi1D！HP Ii1）piDi！i+1Hpi+1！nHpn）pi+1）pn Dn，具有实例（pj：Xpj ！（Hpj;Cpj）;1jn），we假设q是可插入的（对于pi），如果存在实例（！;q; H q）（q：X q！（Hq;Cq）2PN），则Di1 如果存在一个导序列，！H！ 0HP！i+1Hp！HDi1 ）qQpi0i+1ipi+1）pn0在哪里！0 是Q中的一个n ode，一个n odela be l of！0 是p的左边。2定义3.3对于产品q：X q！（H q; C q）2 P N，可插入对于pi：Xpi！（Hpi;Cpi ）和 SnDD7HPI\Hq=，实 例序列S通过插入实例（！;q; Hq）转化为实例序列def（（！1;p1;H p1），，（！n;pn;H pn）），S=（（！1;p1;Hp1），，（！i1;pi1;Hpi1），（啊！;q;Hq），（！;pi;H pi），，（！n;pn;H pn））。实例序列S是给定的8我nqHGT-VMT 2001 {T.Arita，K.富山湾Tsuchida和T.雅酷如下(1)用实例Dn跟踪推导序列回到Di1。(2) 应用实例（！; q; Hq）到Di1，并得到结果图Q。(3) 应用实例序列（（！0; p;H），（！一期+1;pi+1 ;Hpi+1 ），，（！n; pn;Hpn））到Q，得到结果图D0 .2将一些实例插入到实例序列中会产生一个新项。也就是说，它们对应于将新项插入Hiform文档中允许的位置的操作。注3.4以与通过使用产品实例的编辑相同的方式，我们可以进一步通过复合产品副本来定义可插入。2定义3.5A图H0 是通过图A在图H的边x处的句法插入得到的，如果下列条件成立：（1）存在图A和边x的合成产生副本q. （2）存在q的实例序列iq和H的实例序列iH实例序列S是通过将i插入到实例序列i中而获得的。(3)图H0是从实例序列S导出的2命题3.6设H是由G依次将图a和图b分别插入HNGG的边x和边y而得到的图。LetH0通过在y和x处插入b和a，特别是在HNGG中。那么，H=H0。我的律师。 HNGG有一个连续的优势。 在我们看来，这个提议是有根据的。2命题3.7在HNGG中的插入在线性时间内执行。证据生产实例的插入点在嵌入生产序列长度的线性时间内找到。设n是目标图中的节点数。在我们的HNGG的推导中，目标图中的任何节点都可以通过最多ve个应用程序变为终端节点。因此，目标图的实例序列的最大长度为5n。由于HNGG是优先edNCE图文法[2]，因此语法分析是在线性时间内执行的[5]。属性求值也是在线性时间内执行的[2]。2图4中给出了插入的示例。在这里，我们将表单F2插入表单F1. 设G1是关于F1的图，G2是关于F2的图. 然后，在G1的边e处插入G2的句法结构如下：（1）从e和G2得到G2的合成产生式拷贝q.(2)q的实例序列iq和实例序列iG1存在过 如果q对于p在iG1中是可插入的，则通过将iq插入到实例序列iG1中来获得n实例序列iG。（3）从该实例序列iG生成图G。 G是一个新的形式，它是由F2插入F1得到的.四、结论电子表格和软件文档被广泛用于软件可视化。我们的研究结果是这样的可视化的理论模型的建议pi9GT-VMT 2001 {T.Arita，K.富山湾Tsuchida和T.雅酷我们提出了一种编辑方法，基于属性NCE图语法的表格具有均匀的单元格大小。该方法包括机械制图的属性规则。它能准确地编辑由edNCE文法定义的有效表格。提出了一种基于属性规则的图元图形线性时间编辑算法。这些语法编辑方法可用于电子表格语言的语法处理。我们正在为更复杂的绘图重建属性规则。我们正在研究其他编辑操作，如分割操作，组合操作等。此外，我们现在正在开发一个表格编辑系统。确认感谢K教授。感谢杉田先生提出的宝贵意见。感谢S先生。金井在准备手稿的过程中提出了建议。我们还要感谢S先生。Nakagawa和K.为他们宝贵的讨论感到骄傲。引用[1] 足立，Y.，王文，等.基于属性图语法的层次化程序图编辑器.北京：计算机科学出版社，1996，205-213.[2] Arita，T.，K. Tomiyama，T. Yaku，Y. Miyadera，K. Sugita，K.张文，以图形文法处理图形的方法，国立成功大学计算机科学研究所硕士论文，2000年。[3] Arita，T.，K. Sugita，K. Tsuchida，T.王志荣，以属性图为基础的句法表格处理方法，国立台湾科技大学应用资讯学研究所硕士论文，2001年。[4] Arita ， T. ， Hiform的 优 先 属 性 NCE 图 语 法 ， （ 2000 ） ， URL ：http://www.hichart.org/或http://www.cssa.chs.nihon-u.ac.jp/~yaku/keyaki/archive/HC00-001[5] Franck，Reinhold，A Class of Linearly Parsable Graph Grammars，ActaInfomatica10（1978），175-201.[6] P.， F. 作 者 ： John ， Myers ， Tabular and Textual Methods for SelectingObjects from a Group，Proc.2000 IEEE Symp. On Visual Language（2000），157-164.[7] Rozenberg，Grzegorz（Ed.），《图形语法与图形变换计算手册》，世界科学出版社，（1997）。[8] Teitelbaum ， Tim 和 Thomas Reps ， The Cornell Program Synthesizer ： AC++-DirectedProgrammingEnvironment ， Comm.ACM ， Vol.24（1981），563-573.[9] ISO 6592{1985}，基于计算机的应用系统文件编制指南，（1985）。