理论计算机科学电子笔记137（2005）43-55www.elsevier.com/locate/entcs阿姆斯特丹语言考古学RalfLa？el阿姆斯特丹自由大学Centrum voor Wiskunde en Informatica，阿姆斯特丹摘要GRK -语法恢复工具包-说明了自动化和相应的工具支持的背景下，开发质量的语言参考，随时迎合解析器的派生选项GRK为两个概念提供了概念验证：（i）半自动语法恢复;（ii）语言引用重新设计。GRK对半自动语法恢复的支持意味着GRK可以用于从语言参考中获得相对正确、完整以及可实现的语法。GRK到目前为止，GRK特别适合Cobol考古学，更具体地说是IBM也就是说，GRK提供了一个完全机械化的过程，其中IBM（恢复需要数百个简单的转换步骤，以提供适合解析器推导的语法。作为副产品，GRK还生成一个缓慢的基于Prolog的解析器。通过导出到GRK这两个解析器都接受所有的VS Cobol II代码，我们的可用性（数百万行代码）。关键词：语法恢复，Cobol，语法转换，可视化语言解析，Grammarware工程，语法恢复工具包，语法部署工具包1进入语法恢复状态(Let我们假设...） 你将面临以下任务你的老板想让你分析和转换Cobol程序。你面前有几百万行Cobol代码，你应该演示一些相当简单的转换的可行性。时间紧迫。你是一位经验丰富的软件工程师，精通语言处理事务。所以你并不害怕语法错误，你计划使用Cobol解析器。所请求的转换是很容易实现的--如果您只有1571-0661 © 2005由Elsevier B. V.出版，CC BY-NC-ND许可下开放获取。doi：10.1016/j.entcs.2005.07.00444R. Lämmel/Electronic Notes in Theoretical Computer Science 137（2005）431有一个前端工作。 去过那里，做过。 不是Cobol！ 你先试着谷歌一下。那里不多！你找不到Cobol的yacc规范。为什么会这样？Cobol自1960年代初就已经存在了！一定有人想到了这一点！你下载了一些似乎是处理Cobol的软件包。你花了一个星期的时间在一个这样的软件包上，却发现Cobol语法从来没有完成过。预处理器在哪里？嵌入式SQL支持在哪里？如何使用此软件包进行软件转换？你花了一个月的时间在另一个包上--这次是一个研究原型。你声明应该早点让你开始恐慌。 你打电话给你的朋友，他为<<一个Cobol供应商工作，compiler>>. 他说你必须拒绝这个任务因为你只有五年的时间直到退休，没有人能在这么短的时间内完成这件该死的事情。你的老板拒绝了你的拒绝，最后期限是固定的：你还有三个星期。不可能的任务？O这个场景实例化了一个重要而困难的问题：为自动化软件分析和转换提供工具支持通常需要高质量的语法知识，以满足当前语言的解析器开发。我们在其他地方将这个普遍存在的问题称为GRK -语法恢复工具包是一个软件工具包，在这方面有所帮助。GRK解决了特定的Cobol赋值，并暗示了500种语言问题的通用解决方案2你好吗？GRK是一个用于半自动语法恢复和语言引用再工程的软件工具包。半自动文法恢复的基本思想是通过从语言参考中提取原始的语法描述片段，并根据需要改进这些片段，来支持导出相对正确、完整以及可实现的文法。语言引用再工程的基本思想是支持语言引用的修改和扩展，这些修改和扩展涉及到嵌入的语法知识以及引用的其他方面我们注意到，语法恢复的整个过程是有动机的，并在[13]中详细描述。在本出版物中，我们专注于GRK的机械化过程。到今天为止，GRK已经被驱动得足够远，以提供公众可访问的，语言考古学可行性的建设性证据。我们以前的出版物[13，12]依赖于我们不敢发布的特别工具特别是，GRK已经被制定到Cobol案例研究所需的程度，更具体地说是VSCobol II。VS Cobol II文法[11]的恢复过程和IBM应用程序编程参考[ 5 ]的修订过程1.一、为了给读者一个概念，让我们重新执行这个过程。为此，我们假设GRK很容易下载和安装。我们发布1 我们回到了1999年12月3日之前的历史。(This是我们在网络上发布第一个高质量的Cobol语法[11]的时候。R. Lämmel/Electronic Notes in Theoretical Computer Science 137（2005）4345图1.一、IBM VS Cobol II的恢复案例testgrk/grammars/vscobolii/> make testPatching section“COVER”.又补了548节... 撕碎部分“COVER”.粉碎了另外548个部分和174个图表...解析scratch/焦vi at ed-co mbi ne d-rel at ion-c on dit io n.d ia.解析另外173张图...解析脚本恢复/leafs.fst. 正在应用转换...解析并应用另外5个脚本进行恢复转换.Dumpingfilescratch/focus vi at ed-co m ine d-rel at io n-con dit io n. out.又丢了298张图...Pretty-printing file scratch/removated-combined-relationship-condition.out.再打印298张图表内联节“COVER”.另外还有548个部分和299个图表... 解析脚本部署/liberal.fst.正在应用转换...解析并应用另外5个脚本进行部署转换. DumpingDCGin fileibm-transformed.pl.解析了42行Cobol代码。46R. Lämmel/Electronic Notes in Theoretical Computer Science 137（2005）43也就是说，在最后，我们解析了一个小的Cobol程序。我们已经用数百万行VS Cobol II代码测试了相同的语法，但由于明显的原因，我们不能分发底层代码库3查阅语文参考资料我们现在将讨论与GRK一起机械化的VS Cobol II案例的重要细节。第一个问题是检索包含在IBM参考中的原始语法知识起点：HTML一种攻击方法是从IBM的BookManager BookServer Library [ 4 ]下载IBMGRK分发此下载：1763656个HTML文件。图2中显示了一个片段，即Cobol数据名和条件名的下标语法。图表和文本内容是混合的。左边距是IBM的专用元素，用于向ANSICobol（参见。“的|“）.有人可能会问，从HTML开始是否是最佳选择。是的，我知道是的语法恢复与其他逆向和重新工程的工作没有什么不同：必须使用可用的“代码”。IBM没有以任何更明确的结构形式发布该标准。IBM以印刷形式发布了该标准，但OCR（光学字符识别）比HTML/文本处理更复杂。事实上，OCR是不够的，因为打印的图表需要非平凡的视觉语言解析。修补和粉碎HTML标记暴露了符号异常，这类似于其生产过程中的一些低级，甚至可能是手动的细节。此外，HTML标记引用其他文档，IBM最终可能会移动或删除这些文档。因此，作为第一步，需要修补以确保：• 分段结构形成良好，• HTML链接只引用本地锚，• 所有语法图都完全符合预期的可视语法。这些补丁记录在脚本中。我们最终得到了原始文档的修补版本，并将其传递到粉碎阶段。切碎产生一个当我们稍后重新生成语言引用时，文档框架的表示允许轻松访问分段结构和重新插入修订的图。我们代表的是R. Lämmel/Electronic Notes in Theoretical Computer Science 137（2005）4347图二. 原始IBM参考-快照文档作为一个普通的Prolog术语。我们也可以使用XML，但是对于语法恢复的早期阶段，互操作性不是问题解析语法图为了正确访问VS Cobol II的原始语法，我们需要将语法图解析为某种语法表示格式我们在GRK中使用EBNF（的一种形式）事实上，在具体语法中支持EBNF，并且有一个基于术语的表示格式。IBM的HTML使用ASCII艺术作为语法图。我们基本上需要解析条形、下划线、小于号等等。当我们在1999年第一次尝试解析图表时，我们使用了普通的上下文无关语法（即，字符串语法）来定义视觉语法。这种方法是不合适的，因为在合成图的部分时必须执行复杂的操作。语法图的二维语法更容易用属性多集语法解析[3]。 这是GRK采用的方法。为了给出一个示例，下面的产品描述了替代堆栈中垂直层的视觉语法。48R. Lämmel/Electronic Notes in Theoretical Computer Science 137（2005）43图三. 重新设计的IBM参考（请参阅图2的堆叠替代方案。例如，请参见data-name-1图层。）产生式用Prolog的DCG 2表示法给出2DCG（Definite Clause Grammar）是一种与逻辑程序相结合的语法形式。Prolog系统为DCG提供了语法糖，它被编译成普通的Prolog。这允许简单的属性化自顶向下解析器。R. Lämmel/Electronic Notes in Theoretical Computer Science 137（2005）4349grammars，在GRK中使用：push（Xmin，Xmax，Ymin，Ymax，Ycenter，Yglue，Ast）-->select（（vline，Xmin，X1，Ycenter，Yglue，_）），list（X1，X2，Ymin，Ymax，Ycenter，Ast），select（（vline，X2，Xmax，Ycenter，Yglue，_）），{ Yglue >= Ycenter}.DCG生产说明层由两个垂直线段组成（参见vline）和介于两者之间的列表我们使用一个select谓词从剩余的token集中挑选token 列表和vline标记携带其二维位置的几何属性。 我们使用单位和条件，例如，Yglue>= Ycenter，用于约束视觉对齐。还有一个属性（cf。Ast）为基于Prolog的术语表示的语法图。事实上，DCG将可视化语法中的图映射为表示为Prolog项的EBNF产生式。图中的语法图2对应于以下Prolog项：dia（“subscripting”，concat（or（n（“condition-name-1“），n（“data-name-1“）），concat（nl，concat（t（“（“），concat（plus（or（n（“integer-1”），or（concat（n（“data-name-2”），or（n，concat（or（t（“+”），t（“-”）），n（“integer-2”）），concat（n（“index-name-2“），或（epsilon，concat（or（t（“+”），t（“-“）），n（“integer-3”）），t（“）我们注意到nl的出现，它编码一个换行符。EBNF表示将这些细节传输到稍后的重新生成，以便可以保留图的布局细节当前的GRK需要在相关上下文中做更多的工作;它没有保留一些细节，例如IBM特有的元素。4恢复转换提取的原始语法绝不是为解析器生成做好准备的。IBM从来没有打算让它的参考资料像那样容易使用。我们需要转换原始语法。为此，GRK的运营商们开始为语法转换提供一个框架GRK从[14，8]中重新使用了fstGRK允许我们在脚本中记录fstVS Cobol II的恢复需要将346个简单的fst转换应用于原始语法。慷慨的评论恢复脚本重构，完成和纠正计数2399行。一旦我们执行了这一堆脚本，我们就有了一个实际接受VS Cobol II50R. Lämmel/Electronic Notes in Theoretical Computer Science 137（2005）43代码.我们注意到，我们将需要进一步的转换，即吸引特定解析技术的部署转换下面是一个恢复转换的示例。我们重构子脚本图.我们提取了图中的实际下标部分，从而可以重用该部分：%识别短语，如在别处提及的。提取下标=integer-1|data-name-2 （（“+”|“-”）integer-2）？| index-name-1（（“+”|“-”）integer-3）？从订阅实际上，在IBM的参考文献的文本解释中就提到了下标为了避免在后续步骤中重复语法代码。我们注意到，每个转换都包括一个行注释（参见。“行注释以过去时态给出（参见。 因为这些注释应当作为参考中的变更日志条目而引起注意这是另一个转型的例子。这一次，我们完成了下标语法。虽然原始图以普通数据名（和索引名）的形式描述了下标，但从实际的Cobol源代码中可以明显看出，也可以使用合格的数据名甚至标识符。因此，我们认为， 原始语法不完整。下面的转换相应地概括了该图：%启用标识符而不是纯数据名称。用下标中的标识符替换数据名我们注意到，一般化被编码为一个简单的替代。 当前GRK的第一语言没有提供任何检查来区分语言限制和泛化与更任意的替换。我们计划（重新）实现[9，14]中更强的概念上面显示的许多小步骤（准确地说是346个）完成了VS Cobol II语法的恢复阶段。修改后的下标语法如图所示。3 .第三章。R. Lämmel/Electronic Notes in Theoretical Computer Science 137（2005）43515语言参考图3中HTML内容的生成很简单。我们再现了原始的分段结构，同时在正确的位置漂亮地打印了未更改的、更改的和新的语法图。在每一段中，我们都添加了一个免责声明（见图3的顶部），因为重新设计的文档不能与IBM授权的文档混淆GRK添加新产品的转换可以显式指定接收节。下面是一个相应的例子，我们在非正式描述此语法的部分中添加了一段缺失的语法%已执行文中给出的定义。添加simple-condition=class-condition|条件名条件|关系条件|符号条件|开关状态条件|“（“condition“）”到2.8.5.16语法部署GRK有一个朋友：GDK -语法部署工具包[8]，它可以帮助生成通用的解析器。GRK能够以GDK的首选语法格式LLL将语法导出到GDK。然后，GDK可以生成涵盖一系列解析技术的解析器。GRK本身只生成一个基于Prolog的原型解析器，速度不是很快，但它是一个有效的预言机--对于恢复和演化期间的语法调试来说足够好了。事实上，基于Prolog的原型解析器再次使用DCG符号来执行Prolog中的语法。以下DCG制作已经由GRK生成的下标图从图。第三章：下标-->（integer;标识符，（（@（“+”）;@（“-”）），整数;true）;index_name，（（@（“+”）;@（“-”）），integer;true））.52R. Lämmel/Electronic Notes in Theoretical Computer Science 137（2005）43我们看到GRK选择了Prolog的析取（参见。“;“）来表示EBNF的备选项和可选项。标记由谓词@/1扫描。Epilepsy选项可归结为true/0。重新设计的IBM参考中包含的语法不会立即用于解析器生成和语法导出到GDK。我们已经积累了另外158个fst转换，专门针对语法部署的准备。这些转换中有几个解决了歧义，或者简化了一些看起来像语法图，但在EBNF中太复杂的结果。其他一些转换消除了各种解析技术不容易支持的置换短语。然而，其他一些转换呼吁有限的回溯模型，我们应用于生成的DCG的执行。最终的语法，没有DCG特定的调整，被导出到GDK，它很容易生成一个可操作的btyacc[15]解析器。7问答精选问：市场上已经有十几个坚如磐石的Cobol解析器。那么GRK的贡献是什么呢？答：（我们不将GRK输出标记为GRK支持一个重要的见解：我们需要提高自动化，并采用工程技术，以恢复语法和部署它们作为解析器。的正常的手动过程太耗时且太容易出错[12]。世界上有成千上万种语言。一些相反的问题：为什么坚如磐石的Cobol解析器构建起来非常昂贵？Wouldn’t grammar transformation问：语言手册往往会有多个版本。这种方法将如何协调不同版本的出版手册之间的差异？回答：道路1：一旦语言参考提供了正确、完整和可实现的语法，语法恢复语法工具将语言参考）和语法的部署。道路2：恢复和部署转换很容易被采用，以适应给定语言参考的变化。可以在适当的模块化转换脚本中维护这些差异。问：在实践中，我们需要解析器来处理供应商扩展或过时的功能。我们应该如何处理这些问题？答：这种定制是通过适当的语法转换来适应的。在Cobol案例中，我们使用了部署脚本，R. Lämmel/Electronic Notes in Theoretical Computer Science 137（2005）4353在用于验证的代码库中找到的那些Cobol扩展。自定义语法的能力是语法工程的核心。问题：GRK通过用户提供的转换促进恢复。关于语法推理的研究呢...是否适用？答：语法推理在许多应用领域都是成功的。然而，已知的推断用于编程语言解析器的语法的方法在规模上是相当有限的;参见，例如，[16、6、1]。此外，我们认为语法转换专门满足（i）重用原始语法知识;（ii）表达牢固但非正式的语法知识;（iii）准确记录语法的演变。我们对改进我们的方法感兴趣，以便纳入推理概念问：我应该使用GRK吗？（... GDK？）它能伸缩吗？答：到目前为止，GRK是一个原型，说明了半自动语法恢复和语言引用工程的概念。（类似于GDK。）生成的Cobol解析器非常有用。但是，使用GRK进行其他恢复项目或定制VS Cobol II案例需要投资我们希望其他方面对语法工程产生兴趣。GRK和GDK应该被生产质量的工具所取代8总结发言GRK致力于解决500种语言的问题[12]，这是为自动化软件分析和修改提供工具支持的主要障碍。我们需要能够恢复语法并以合理的速度在前端实现它们，合理的排序，可预测的质量，所有这些都基于可重复和透明的过程。GRK的基本概念相当普遍。特别是，GRK的方法转换的语法是普遍使用的。一些特定的GRK工具偏向于IBM标准。(Most值得注意的是，GRK对语法图解析的工具支持在这个意义上是有偏见的。）希望GRK触发器能在更通用的语法（件）工程工具包上工作GRK是自由软件。1.0版本于2003年6月4日发布 GRK使用Prological语言处理在SWI-Prolog中实现[10]。 GRK可在www.example.com上在线获得 http://www.cs.vu.nl/grammarware/grk/ 。GRK 是 位 于 阿姆 斯 特 丹 的VUA CWI的一个更大的实验室的一部分，我们称之为语法软件工程[7];请参阅http://www.cs.vu.nl/grammarware/。软件考古学家Jean Marie Favre编写了一份关于语言逆向工程的深刻而易懂的演示文稿[2]，其中语法重新制定被置于历史背景中。法弗尔的演讲很热情54R. Lämmel/Electronic Notes in Theoretical Computer Science 137（2005）43推荐给所有怀疑Cobol和埃及历史之间的联系或语法工程和模型驱动开发之间的联系确认我非常感谢与Jan Kort在提供工具以将语法视为工程工件这一主题上的合作。GRK对gram软件工程的总体评价做出了贡献[7]。在这方面，我感谢与保罗·克林特、史蒂芬·克鲁塞纳和克里斯·费尔霍夫的合作。我也非常感谢与其他语法学家的互动，我为以下列表中的任何遗漏道歉：Mark van den Brand，Jim Cordy ， Kris De Schutter ， Jean-Marie Favre ， Jan Heering ， Niels Veerman ， Ernst-JanVerhoeven，Joost Visser。引用[1] A. Dubey，S. Aggarwal和P. Jalote。 一种从程序集中提取关键字规则的技术。软件维护与再工程会议（CSMR 2005）。IEEE Computer Society Press，2005.地出现。[2] J.M.法弗尔Metamodel（Driven）（Reverse）Engineering - Stories of the Dagktis Stone and ofthe Rosetta Stone，2004年3月。在Dagstuhl研讨会04101上的演讲[3] E.J.戈林一种视觉语言的规范和解析方法。 博士论文，布朗大学，1991年。[4] IBM BookManager BookServer 图书馆，1989年，1997年。1999年 和2000 可搭乘http://www.s390.ibm.com:80/bookmgr-cgi/bookmgr.cmd/library/网站。[5] IBM Corporation. VS COBOL II应用程序设计语言参考，4.出版物编号GC 26 -4047-07，1993年版。[6] F. Javed，B.R. Bryant，M.克雷皮内克湾Mernik和A.斯普拉格 使用遗传规划的上下文无关文法归纳。在ACM-SE 42中：第42届年度东南地区会议的论文，第404-405页。ACM Press，2004.[7] P. 克林特河 L？ammel和C. Verhoef. 这是一个新的语法问题。草稿; 2003年8月17日提交期刊出版。[8] J.K或t，R。 L？ammel和C.Verhoef.语法中的DeploymentKit。 在M. G。我的手臂和手臂。 Lüammel，编辑，Proc. 《第二世界语言描述、语言和应用》（LDTA 2002），ENTCS第65卷。Elsevier Science，2002年4月。七页。[9] R. 拉梅尔奶奶，我是一个普通人。 INJ。N. 我给他们和P。 Zave，editor，Proc. 欧洲标准方法（FME 2001），LNCS第2021卷，第550-570页。Springer-Verlag，2001.[10] R.我 叫 L 和 G 。去 吧 。PrologicalLa n guag e Processingng.我 在M.G.J.vandedenBrandandandandD.Parigot ， editors ， Proc. of the 1st Workshop onLanguage Descriptions ， Tools and Applications （ LDTA 2001 ） ， Volume 44 ofENTCS.Elsevier Science，2001年4月。[11] R. Lüammel和C. Verh oef.VSCOBOLIIgrarVersion1. 0的情况。1999年3月。 Availableat：http://www.cs.vu.nl/grammars/browsable/vs-cobol-ii/网站。[12] R. 我叫L和D。 Verrhoef. 解决500L的问题。IEEESoftware，第78-88页，2001年11月/12月[13] R. 我叫L和D。 Verhoef.半自动文法检索.Software-Practice&Experience，31（15）：1395R. Lämmel/Electronic Notes in Theoretical Computer Science 137（2005）4355[14] R. L？amm elandG. 什么事。SDF系统的转换在ASF+SDF元环境中定义。In M.G.J van denBrand and and Didier Parigot，editors，Proc. of the 1st Workshop on Language Descriptions，Tools and Applications（LDTA 2001），volume 44 ofENTCS. Elsevier Science，2001年4月。[15] 诉Maslov和C.多德 btyacc-回溯yacc，1995-2001。http://www.siber.org/btyacc/网站。[16] M. Mernik，G. Gerlic，V. Zumer和B.R.布莱恩特 解析器可以从例子中生成吗？在SAC 2003：Proc. of the 2003 ACM Symposium on Applied Computing，第1063-1067页中。ACM Press，2003.
我的内容管理
展开
