117理论计算机科学电子笔记65 No.3（2002）网址：http://www.elsevier.nl/locate/entcs/volume65.html7页GrammarDeploymentK it- 系统演示-Jan Kort1阿姆斯特丹大学RalfL mmel2CWI和自由大学Chris Verhoef3Vrije Universiteit摘要语法部署是将一个给定的语法规范转换成一个工作的语法分析器的过程。Grammar开发工具包（简称GDK）基于语法工程方法为这一过程提供了工具支持。我们主要感兴趣的是软件更新工具，即软件再工程和逆向工程工具的语法部署。当前版本的GDK针对Cobol进行了优化我们假设语法部署从初始语法规范开始，该规范可能仍然是模糊的甚至是不完整的。在实践中，语法部署绑定负担不起的人力资源，因为没有合适的语法规范，解析技术的多样性以及技术的局限性，集成问题的发展软件更新功能，以及缺乏工具和坚持坚定的语法工程方法。GDK有助于在很大程度上自动化语法部署，因为它提供了语法适配和解析器生成的工具支持。我们支持不同的解析技术，其中包括btyacc，即带回溯的yacc. GDK是自由软件。更多信息：语法工程页面：http://www.cs.vu.nl/grammars/GDK页面：http://www.cs.vu.nl/grammars/gdk/1 电子邮件地址：kort@science.uva.nl2 电子邮件地址：ralf@cwi.nl3 电子邮件地址：x@cs.vu.nlc2002年由Elsevier Science B出版。V. CC BY-NC-ND许可下的开放访问。Kort，Lammel和Verhoef1181GDK的结构语法部署工具包（GDK）是一个轻量级的基于ANSI-C的工具包，用于从语法规范到适合自动化软件更新的解析器。为Cobol或任何其他复杂的现实世界语言开发更新解析器并不容易，因为复杂的语法规则，现有方言和嵌入式语言的多样性，或者预处理和后处理问题[1]。 GDK基于几个原则和假设：（i）从语言参考或编译器等资源中恢复基线语法[3]，（ii）通过自动转换进行语法适配，以可跟踪的方式进行语法操作[2]，（iii）为各种解析技术生成解析器，（iv）为语法工程师选择合适的语法格式，（v）专注于革新解析器的语法部分，而不是特殊的扫描器，预处理器和后处理器。当前版本的GDK针对Cobol语法的部署进行了优化。GDK组件LLL：一种简单的基于EBNF的语法格式。FST：一个语法转换工具。G EN P ARSER：一个从语法生成语法分析器的工具。G DK L IB：用于解析、转换和解解析的库。VS C OBOL II：部署Cobol语法用于软件更新。我们将相应地讨论所有这些组件。在VS COBOL II部分，我们还将简要介绍一个用于处理数据扩展的说明性更新工具EXPAND。这种软件更新任务类似于Y2K或欧元转换的问题。2LLL语法格式LLL应读作“L-Cube”。这个名字暗示了LighterLL解析，它是GDK内置的解析技术LLL语法格式横切GDK中的所有组件，因为它被用作（i）导入恢复的语法规范以进行部署的主要格式，（ii）开发新的语法，(iii)在部署过程中转换语法，以及（iv）为各种技术生成LLL表示法中 LLL语法格式的EBNF语法：rule+;rule：sort“：“alts“;";alts：alt alts-tail*;alts-tail：“|“备选案文;int *;术语：基础重复？基础：文字|排序;重复：“*”|“加”|“怎么样？“;Kort，Lammel和Verhoef119VS COBOL II示例：MOVE-语句move-statement：move-statement-1|move-statement-2move-statement-1：“MOVE”cobword-or-literal“TO”标识符+;move-statement-2：“MOVE”对应标识符“TO”标识符+;对应：“CORRESPONDING”|“CORR”;合适的语法格式对于语法部署至关重要。常用的语法格式有三个主要问题（i）过于严格的格式，例如yacc基础上的简单BNF格式，需要对列表和可选项进行编码(ii)另一方面，使用过于自由的格式，例如，非平凡嵌套的短语使得语法不太适合抽象语法、调试和适配的问题。(iii)使用特定解析器生成器的输入语言进行语法恢复、开发、维护和其他操作，会迫使用户始终处理格式的特性。LLL支持EBNF在（i）的视图中启用正则表达式运算符，但它限制它们排除（ii）。此外，LLL是一个纯EBNF符号来补救（iii），也就是说，LLL不直接处理冲突解决，消歧，词法语法，和其他。我们在许多语法恢复、开发和部署项目中的经验产生了一种简单而可靠的语法表示法，特别适合于开发更新解析器。3使用FST进行FST代表SyntaxT transformation的缩写。FST工具支持通过逐步转换的方式调整语法需要对语法- mars进行适配面向命令行的工具FST的输入语言提供了11个转换运算符。这些转换步骤的顺序可以记录在转换脚本中。FST工具的调用方式如下：fsttrafo-scriptgrammar-in>grammar-outFST算子的示例性选择%rename sort %排序重命名非终结符%resolve规则提供缺少的定义%redefine规则替换非终结符的定义%include规则向定义添加替代项%exclude规则从定义中删除备选项FST强制所有这些操作符的前置和后置条件，以查看转换是否在某种程度上是合理的在[2]中描述了语法自适应的基础。FST操作符套件的设计经过优化，易于使用，与LLL语法格式非常匹配，并且易于安装。Kort，Lammel和Verhoef120FST的实现。在[4]中讨论了GDK的FST的一个更雄心勃勃的前身，4使用GENPARSERGDK的GENPARSER工具从LLL文法生成解析器。支持各种解析技术，其中包括btyacc。有人可能会说，GENPARSER是一个因此，我们说GEN PARSER请注意，GEN PARSER不仅导出语法以供某些解析技术使用，而且还生成用于解析树构造、扫描器模板的代码，对于基于C的解析器，还生成一级术语构建和匹配，支持在解析树上重写的简化形式。Cobol扫描仪是相当特殊的，其实现的手动工作是负担得起的。因此，我们只生成扫描仪模板。对于几种技术，我们还考虑了无扫描解析，然后提供了用于解析词法排序的空函数定义。GEN- PARSER工具调用如下：genparser -f格式选项语法格式选择解析技术，例如，可以使用-f btyacc。其他选项取决于解析技术。例如，可以为btyacc等回溯解析器发出回溯cut。一般来说，我们认为这种调整是必要的，因为语法是通过转换相应地准备好的。支持格式btyacc：btyacc解析器和一个flex扫描器模板。基于GDKLIB的组合子解析器和一个flex扫描器模板。slp：G DK L IB基于无扫描组合子分析器。precc：无解析树结构的无扫描precc解析器。antlr：没有构造解析树的antlr解析器。Haskell：基于Haskell的无扫描组合子解析器。sdf：基于SDF/pgen/sglr的解析器。accent：Accent解析器和Flex扫描器模板。使用太基本的解析技术，如LALR（1）被认为是有害的[1]。事实上，甚至我们最终的VS COBOL II语法也没有接近LALR（1）：有542个移位/归约冲突，62个归约/归约冲突，并不是所有的冲突都是严重的。要使一个语法能够与普通的yacc一起工作，并在需要调整语法时保持它无冲突，需要不断的努力。因此，我们在上面的列表中重点介绍了更强大的解析技术。我们已经对所有的技术进行了基准测试，并为VS COBOL II提供了一个2M的代码库.至于预处理，我们使用了一个没有随GDK分发的自制工具。让我们总结一下-Kort，Lammel和Verhoef121列出部署案例的最重要结果。(i)btyacc解析器需要的调整最少，它是最有效的解析器。请注意，btyacc需要商业许可证。（ii）基于GDKLIB的解析器只需要稍微多做一些调整，它们仍然比我们看到的所有其他技术都快（比btyacc慢2倍）。基于GDKLIB的解析器依赖于用于自顶向下解析器的组合子，其具有用于规则的备选项的局部回溯。支持保护替代的其他方法，以启用某种形式的解析器调整。(iii)大多数其他技术--事实上，我们查看的不止上面列表中的那些--暴露了语法类限制、消歧模型、解析树构造、安装、可用性、性能、可伸缩性、健壮性、集成等方面的问题。5GDK库GDK是一个用于语法部署的自包含工具包。这意味着不需要使用任何第三方组件来开发简单的软件更新工具。事实上，基于C的GDKLIB提供了用于解析、解析树构造、重写、遍历、解解析和漂亮打印的轻量级功能因此，不需要安装额外的软件来评估GDK的其他组件的适用性，特别是与GDK一起部署的VS COBOLII语法。此外，GDK LIB还用于实现FST和GEN PARSER。GDKV1.0中的模块（共1689个模块）模块意图LOCmt.c术语解释和检查270mtutils.c遍历、容器、解析功能622parselib.cLLL组合子分析245slp.c无扫描LLL组合子分析284pretty.c漂亮印花122token.c令牌化92stack.c通用堆栈54GDK LIB 功 能 可 用 于 实 施 简 单 的 翻 新 工 具 。 也 就 是 说 ， GDK LIB 是ASF+SDF、DMS或REFINE等更复杂技术的补充。为了给出GDK_LIB的当前限制的示例，由GDK_LIB提供的项格式MTerm不支持垃圾收集，并且重写规则和遍历的C编码不被类型检查，而这是支持的，例如，ASF+SDF 另一方面，对于GDK LIB来说，没有必要学习一种新的语言，这是更复杂的工具的情况。基于GDKLIB的组合子解析器的性能仅优于btyacc.在这里，我们利用语法类限制进行组合子解析。这些限制不一定适用于所有语言。Kort，Lammel和Verhoef122Spec.lllFSTFinalized.lll生成语法VSCParse.cGCClibvscoboliiparser.a变换其他.c文件6VS COBOL IIGDK的发行版附带了最初的VS COBOL II语法规范，如[3]中所提供的，以及所有的转换脚本，以进一步消除语法的歧义和重构语法，并为使用不同的解析技术做好准备为了说明所部署的语法的有用性，GDK的分发中包括软件更新工具EXPAND。在本节中，我们简要地指出了EXPAND解决的更新任务，我们描述了派生底层更新解析器的过程，最后我们勾勒了EXPAND的内部结构。这个工具演示了如何使用生成的更新解析器进行再工程任务。用EXPAND修改前后的 VS COBOL Ⅱ程序标识D IIVDIESNITOINF。电信部门。程序ID。LIPTRTOLGER-AYM2-KI-DT. ELSITT。TLE-Y2K-测试。数据部。数据部。工作- -第二部分。01SEEK-NAMEPI C091 9. 第999章.01OTHER-NAME-10P 1ICO9 T9 H.ER-NAME-1PIC999.01OTHER-NAME-201POITCH9E9R9-9N9A.ME-2PIC99999。01OTHER-NAME-30P 1ICO9 T9 H.ER-NAME-3PIC99.程序司。程序司。......移动搜索-N A M OEVTEOSOETEHKE-RN-ANMAEMTEO-1O。THER-NAME-1.移动搜索-N A M OEVTEOSOETEHKE-RN-ANMAEMTEO-2O。THER-NAME-2.如果OTHER-NAME-2> 99......这个例子说明了我们想把某些两位数的字段扩展为三位数，也就是说，PIC99变成PIC 999。该范围扩展还触发文字的适配，即用新值299替换最大值99。受影响的字段由种子和传播算法确定。种子集合元素的识别是基于名称命名学。传播依赖于使用类型分析。一个Cobol语法分析器最 初 的 语 法 规 范 Spec.lll 由 许 多 FST 脚 本 转 换 ， 生 成 语 法Finalized.lll。该语法被传递给GENPARSER以发出解析器生成。图的其余部分是基于C的解析器专用的. GEN PARSER的输出（可能经过“解析器生成器”的处理这个过程被捕获在Makefile中。为了在不同技术之间进行简单的切换，所有解析器都作为一个库提供，其中包含一个顶级函数MTermparseCbl（FILE *f），用于读入文件并生成解析树。Kort，Lammel和Verhoef123EXPAND工具的主要功能#include“parsecbl.h”//基于btyacc或gdklib的Cobol解析器#include“cobpp.h”// Cobol漂亮的打印机#include“expand.h”//转换函数int main（int参数，字符 ** 参数）FMTerm pt;//解析树pt=parseCb/l/（sptadrisne）;程序COBPPdump（stdout，expand（pt））; // expand并漂亮地打印返回0;G也就是说，库函数parseCbl被调用，从而产生解析树pt。翻新任务被编码在功能扩展中，其结构如下。(i)种子集已确定。(ii)执行传播。(iii)受影响字段的图片掩码被扩展。(iv)受影响的文字被改编。这些步骤基本上相当于遍历，只针对少数Cobol模式。我们使用GDK LIB提供的通用遍历功能。转换后的程序最后用COBPPdump打印出来。EXPAND工具的完整C代码为241 KB。7结论GDK是从半自动语法恢复[3]到软件更新中的实际语法部署GDK说明了工具支持的语法恢复和部署是执行实际更新任务的一种现实而有用的手段，而无需首先手工构建解析器因为GDK是轻量级的和自包含的，所以您可以很容易地查看用于软件更新的底层工程思想，而不必安装额外的工具。引用[1] M.G.J. van den Brand，M.P.A. Sellink和C.维尔霍夫 目前的解析技术在软件更新中被认为是有害的。In S. Tilley和G. Visaggio，editors，Proceedings of IWPC[2] R. 我来了 语法适应。在FME'01的出版物中，Springer-Verlag，2001.[3] R. L ammel和C. 维尔霍夫半自动语法检索。Software-Praction&Experience，31（15）：1395[4] R. L mmel和G. Wachsmuth。在ASF+SDF元环境中转换SDF语法定义在M.G.J.van den Brand和D. Parigot，editors，Proceedings of LDTAElsevier Science，2001年4月。
我的内容管理
展开
