自动化建立DSL编程卫星操作语言翻译器的注释文法：理论计算机科学电子笔记

理论计算机科学电子笔记164（2006）121-137www.elsevier.com/locate/entcs从注释文法迭戈·奥多涅斯·卡马乔a，1，4金·门斯a，1马克·范登布兰德c，3尤尔根·温朱b，2aDe partmentofComputerSciencece，Universit'ecatholiquedeLouvain，Louvain-la-Neuve，Belgiumb荷兰阿姆斯特丹信息技术中心软件工程系c荷兰埃因霍温技术大学数学与计算机科学系摘要在本文中，我们提出了一种技术，自动化的过程中建立翻译器之间的操作语言，一个家庭的DSL用于编程卫星操作程序。我们利用这些语言之间的相似性，通过 使用注释语法。为了进一步改进整个翻译过程，降低其复杂性，我们还提出了一种适用于所有操作语言的中间表示。我们验证了我们的方法，半自动派生的翻译器之间的一些操作语言，使用原型工具，我们实现了这一目的。关键词：操作语言，语言翻译，语言转换，自动翻译，文法软件1介绍1.1动机与旨在解决任何领域中的计算问题的通用编程语言相反，特定领域语言（DSL）通常是专用于特定任务或应用领域的较小编程语言[21]。航天器就是这种特殊应用领域的一个例子1 {金.男装|diego.ordonez}@ uclouvain.be2Jurgen. cwi.nl3m.g.j.v.d. tue.nl4这项研究由比利时瓦隆地区和欧洲社会基金资助，在题为“Uneaprocheparam'etriqueder'eing'enierielogicielle-APPAREIL”的第一个Euro p e O bjectif3研究项目415748e n中。1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.10.009122D. Ordonez Camacho等人理论计算机科学电子笔记164（2006）121任务规划，航天器从所谓的操作员那里接收命令。这些命令在称为操作语言（OL）的DSL中描述。 OL的设计目的是将发送给航天器的命令重新组合成操作，这些操作是描述航天器有组织程序的专门程序。在航天器任务规划领域中，可能存在许多OL 就像太空船操作员一样。这些语言可以有非常不同的语法和语言结构。然而，由于它们都有相同的目标，并尊重已知的卫星建造和运行标准，它们都有许多共同的特点。更准确地说，所有OL都共享一个共同的语义基础和编程范式：它们都是命令式和命令行驱动的语言。为了使航天器程序的设计和测试更容易，许多运营商使用专门的软件应用程序。这些应用程序的设计者和实现者面临着使它们通用化的需要，这样它们就可以被尽可能多的操作者使用，而不管他们喜欢使用的实际操作语言。虽然这些应用程序已经允许操作员在任何OL中设计和编辑程序，但它们缺乏在OL之间翻译这些程序的能力。此外，这些应用程序应该易于扩展，以支持新的操作语言。1.2方法在本文中，我们提出的方法是一种通用的技术，半自动地从一个OL到另一个翻译，基于相应的上下文无关的语法，这些语言注释额外的信息，在生产和非终端的水平。所提出的技术不仅仅为语言翻译的老问题提供了一种替代解决方案。 它还有助于减少开发时间这是构建程序翻译器过程中相当耗时的一部分。此外，我们的技术的模块化，使未来重用的翻译模块时，编写或派生其他语言的新的翻译我们通过使用ASF +SDF[4，11]和ASF +SDF元环境[5]实现了半自动导出翻译器的算法的原型。总之，我们的技术的主要贡献是：(i) 一种基于语法件开发思想的机制，它自动化了在不同操作语言之间构建翻译器的过程[12];(ii) 所有操作语言的通用中间表示(iii) 派生工具的原型实现，可以作为库合并到ASF +SDF元环境中。虽然我们验证和说明我们的方法和算法只在操作语言的情况下，存在其他家庭的语言，有一个共同的语义基础，例如数据库设计语言或查询语言。我们推测，我们的技术也可以应用于这些领域D. Ordonez Camacho等人理论计算机科学电子笔记164（2006）121123log“PROCEDURE PlutoTest 45 03 Step1”; relVAR：= 3600 sec;return TRUE;while（bootNotRealised AND relVAR > 0 sec）dobootNotRealised：=（（获取DHT 30100的工程值）=ACTIVE）;如果（bootNotRealised），则wait1 sec;relVAR：= relVAR-1sec;endif;结束while;如果bootNotRealised，则启动并确认PHC 10117;结束，如果图1.一、Pluto操作语言中测试过程的代码片段本文件其余部分的结构如下。在第2节中，我们更详细地分析了研究问题，并仔细研究了卫星任务和程序的领域。注释语法技术，我们的研究问题的解决方案，在第3节中详细解释，并验证了操作语言的情况下。我们在第4节介绍了OL的公共中间表示。最后，在第5节和第6节中，我们介绍了使用我们的方法进行的第一次实验的结果，强调了我们的技术的优点和缺点，并总结了我们的贡献。2上下文2.1业务语言航天器任务操作是与卫星行为的规划、执行和控制有关的所有活动。任务行动的一个主要要素是直升机行动计划，其中包含执行行动所需的所有信息，包括所有直升机控制程序和应急恢复程序。 程序是执行一项活动的具体方式，是最终用户在执行一项操作期间控制空间系统所采用的主要机制。这些程序的编写取决于操作卫星的任务控制中心，使用现有的多种操作语言中的一种。作为一个例子，图1显示了用Pluto [10]语言编写的测试过程的一部分Pluto支持在许多其他语言中可以找到的指令，如控制命令行语句（while，if），变量赋值和日志记录。它还支持由大多数OL提供的专用指令，以直接与卫星通信。后者的示例是第5行的“获 取 DHT 30100的 工 程 值 ” 指 令 和第 11 行 的 “ 启 动 并确 认PHC10117”指令。OL之间的指令和语义的这种相似性使得以高度自动化的方式从一种语言翻译到另一种语言是可行的（即使从任何语言自动翻译到任何其他语言的124D. Ordonez Camacho等人理论计算机科学电子笔记164（2006）1212.2研究问题这项研究解决了两个相关的问题。一个是通用语言翻译的经典问题，这仍然是在积极的调查[14，19，20]。第二个问题是，当在同一语言家族中的许多不同语言之间定义翻译器时，许多翻译器将具有相似的片段。为了避免这种重复，模块化翻译技术是有益的。为了解决任意OL之间的翻译问题，为每个源语言和目标语言组合提供一个特定的翻译器显然会导致翻译人员的组合爆炸。 另一种方法--也是我们最终解决方案的一部分--是引入一种额外的语言，当在任何两个OL之间进行翻译时，它可以充当中间表示。 我们需要设计这种中间表示，以允许重用语言和转换组件，以便在向我们的翻译器集添加其他语言但是，即使通过这样一个中间表示，我们的翻译问题的核心仍然存在。虽然它大大减少了需要实现的翻译器的数量，但我们仍然需要构建大量的翻译器。考虑到我们领域中的所有语言都有许多共同的特征，我们假设翻译器本身在很大程度上也是相似的，我们可以利用这种相似性来自动构建它们。翻译器的这种相似性通过一个实验得到了证实，我们手工编写了一套翻译器。在那个实验中，我们观察到，在许多翻译者身上，某些编码模式反复出现。正是这种重复，我们希望利用它来进一步自动化在任何两个OL之间构建语言翻译器2.3我们的解决方案我们对多个OL之间过程的自动化翻译的解决方案由以下步骤组成，在后续部分中将更详细地解释每个步骤。(i) 我们自动化的过程中，两个OL之间的程序翻译器的建设，利用语言的相似性。我们通过注释它们的语法将源语言映射到目标语言，并将这些注释的语法提供给我们的系统，然后生成自动翻译器。这个自动翻译器是以模块化的方式构建的，并且可以很容易地通过进一步的转换规则来扩展以完成翻译器。(ii) 我们设计了一个中间表示共同的每一个OL。像这样，我们可以从这些语言中的任何一种翻译成这个表示，也可以从中间表示翻译成任何这样的语言。这种中间表示为OL家族提供了一个通用的语法和语义模型，根据这个模型来定义该家族中语言的翻译器D. Ordonez Camacho等人理论计算机科学电子笔记164（2006）121125→3注释语法语法导向翻译[1]是一种常见的机制，主要用于编译器构造，将源语言翻译为目标语言。这种技术的一个具体实例是使用语法导向转换[15]，它指定翻译的输入输出关系，并从该关系中推导出实际的翻译者。我们的方法建立在这些技术的基础上，以开发一种简单易用的机制来半自动地构建两种相关语言之间的源代码翻译器，将两种语言的语法作为输入，预先用构造函数和标签信息进行注释，以建立相应语言结构之间的映射[16]。该机制提供了一种方法来自动生成语法中某些产生式的翻译器，以及基本的支持来扩展该翻译器，并为剩余的产生式进行必要的转换。虽然许多现有的工具可以用来实现这个解决方案，例如[3，7，9，23]，我们选择了ASF +SDF和ASF +SDF元环境来实现我们的原型。SF+SDF是由代数规范形式主义（ASF）和代数定义形式主义（SDF）组成的一种规范形式主义，允许对程序的语法和语义进行综合定义语言[6]以模块化的方式。ASF +SDF的模块化使可重用性，在语法以及在语义水平，这是使用它作为我们的实现媒介的优势之一此外，ASF +SDF在输入端和输出端都有很强的语法导向翻译概念我们在3.1节中更详细地讨论了SDF，然后在3.2节中简要总结了ASF。3.1SDF语法定义形式主义是一种语法定义的形式主义，它结合了完全词汇和上下文无关的语法定义。它支持任意上下文无关语法，因为底层的广义解析算法，并提供了几种消除歧义的方法来处理歧义语法。它还支持语法定义的模块化和重用[22]。SDF和（E）BNF符号之间的一个重要区别是产生式规则的左侧和右侧被交换。BNF产品X：：=A B C的SDF等价物是产品A B C X。此外，SDF产品的右侧可以使用表示该产品的属性列表进行装饰。这种属性的一个例子是constructor属性cons，它在从解析树构建抽象语法树（AST）时使用：A B C→X{...，cons（ConstructorN ame），.. . }其中ConstructorN name将用作AST中的节点名称SDF的另一个重要特性是可以注释非终结符126D. Ordonez Camacho等人理论计算机科学电子笔记164（2006）121上下文无关语法if”Expr“then”StatsS“fi”“eval（“Expr“，”BlockT“）上下文无关语法f（IfS）变量“$Expr$”“$StatsS$”方程f（if$Expr$ then $StatsS$ fi）=-> IfS-> EvalT-> EvalT->快递-> StatsSeval（$Expr$，f（$StatsS$））图二、用ASF+SDF表示的简单转换函数的示例在带标签的产品的左手边标签a：A标签b：B标签c：C→X{...，cons（ConstructorN ame），.. . }最后一个特性特别方便，可以避免某些映射问题，例如，在源和目标产品中没有出现匹配的非终结符时同样的顺序。3.2ASFASF是定义条件重写规则的形式主义。 这些重写规则可以对于SDF部分中指定的语言，通过可以作为以下形式的重写规则执行的L= R时 ，C1，C2，.说明只要L匹配，它就可以重写为R，条件是C1，.，Cn都求值为true。 方程的一个简单形式是无条件的 一个L=R。在等式的左边、右边和条件中，可以使用变量。匹配等式的左侧意味着将变量绑定到具体语法树中的匹配子项。 见[6]。 更详细的描述。图2示出了条件语言构造的两个不同出现的上下文无关语法规则（即，IF语句和条件求值）以及用于将语言构造之一映射到另一个的重写函数F。 它说明了ASF中的无条件重写规则以及变量的使用3.3初步实验在一个初步的实验中，最终导致了本文中的工作，我们手动构建了从操作语言Pluto和UCL [2]到中间表示语言IRL的翻译器，在第4节中有更详细的解释。我们从这些语言的构造子集开始，主要由控制流结构组成，并编写了四个翻译器：Pluto到IRL，IRL到Pluto，UCL到IRL，IRL到UCL。我们必须实现的ASF转换数量的总和四个翻译器是91，但其中73个转换的实现（约80%）遵循可重复的模式。就好像重写规则D. Ordonez Camacho等人理论计算机科学电子笔记164（2006）121127EvalBlock{TrueBlock，FalseBlock}优惠条件优惠声明列表如果LaEvalLb如果然后其他（）{ iftrue（）otherwise（）}Eval块真块假孔迪阻塞状态项目列表状态项目列表如果共同Eval块真块假块IfEvalBlockthenTrueBlockelseFalseBlockpublic voidrun（）if true（statementList）otherwise（statementList）}图3.第三章。两种不同语言中的条件结构图四、图3中的等效非端子。图五. 抽象一个共同的结构。作为源语法和目标语法之间的桥梁，在产生式和非终结符之间几乎是一一对应的。只有18个转换（略低于20%）是“非平凡的”，需要更多的知识比可以从语法推导出来。这一观察使我们得出了3.4节中提出的解决方案。3.4语法注释现在我们已经解释了所有的语法，让我们回到问题的核心，即为构建操作语言的源代码到源代码转换器提供自动化支持。由于这些语言属于同一个家族，它们有许多共性，因此翻译器涉及许多可以自动生成例如，图3所示的语言结构属于两种不同的语言。虽然两个语句的语法结构不同，但它们具有相同的语义：它们计算布尔条件，并根据其真值执行其中一个语句块。在这个例子中，很容易确定这个构造的产生式是等价的，并且它们是它们的非终结符，如图4所示。128D. Ordonez Camacho等人理论计算机科学电子笔记164（2006）121“if”cond：EvalBlock“then”trueb：TrueBlock“else”falseb：FalseBlock->If{ cons（“If”）}“iftrue（“trueb：StatementList“）”“否则（“falseb：StatementList“）”“}“->Eval{ cons（“If”）}“eval（“cond：Condition“）”“{““if”EvalBlock“then”TrueBlock“else”FalseBlock->如果“eval（“Condition“）”“{““iftrue（“StatementList“）””否则（“StatementList“）””}“->评估图六、两个不同条件的SDF规则如图5所示，这样的等价可以被认为是两种语言中相应结构共享的AST。由于终端（在图中用八边形表示）在定义这种对应关系时我们不感兴趣，因此它们被排除在公共AST之外。这样，我们就在两种语言之间建立了一座桥梁，允许我们将一种语言中的构造的特定实例翻译成另一种语言中的对应实例。 图6显示了图3的语言结构。这些SDF产品的左侧也有等效项。 对于简单的情况，不需要额外的工作，因为一旦所有的产生式都匹配了，系统通常可以推断出在两个产生式的左侧出现的非终结符也可以匹配。仅仅是它们出现的顺序就足以建立一对一的映射。 但 这个一般规则可能有许多例外：两个产品中的非终结符数量不同，顺序不同，同一类型的非终结符不止一个，等等;需要更精确的解决方案见图7。两个带注释的等价产生式为了解决这个问题，我们将标签与产品左侧的每个非终结符相关联。图7给出了两个完全注释的等价产品的示例。由此产生的AST：If（cond，trueb，falseb）对于两种产品是等效的，尽管它们属于不同的语言。3.5方法概述总之，要使用我们的方法获得翻译器，这些是要遵循的基本步骤：(i) 分析语法并寻找具有相同含义的结果。 这是一个手动过程，需要对两种语言都有很好的了解，并完全依赖用户来匹配语法，从而建立语义映射或桥梁。(ii) 对于源语言中的每个产生式S，在目标语言中找到满足等价要求的产生式T，并用构造函数信息注释两个产生式。(iii) 链接两个产品的左侧。对于每对非终结符[A，X]，其中A在生产S中（在源中），X在生产T中（在焦油中），D. Ordonez Camacho等人理论计算机科学电子笔记164（2006）121129模块Target导入Expr上下文无关语法“start（“b：BlockT“）”eval（“e：Expr“，”b：BlockT“）“loop（“e：Expr“，”b：BlockT“）”if：EvalT |w：LoopT| e：Expr it：InstT*-> EvalT{ cons（“IfThen”）}-> StartT{ cons（“Start”）}-> LoopT{ cons（“While”）}-> InstT{ cons（“Stm”）}-> BlockT{ cons（“Block”）}模块Expr上下文无关语法“真”|“假”|“零”|“nil2”“not”Expr->快递->快递模块源导入Expr上下文无关语法“proc”b：StatsS“endproc”“if”e：Expr“then”b：StatsS“fi”“if”Expr“then”StatsS“else”StatsS“fi”“while”e：Expr“do”b：StatsS“od”if：IfS| w：WhileS |e：Expr it：StatS*-> StartS{ cons（“Start”）}-> IfS{ cons（“IfThen”）}-> WhileS{ cons（“While”）}-> IfS{ cons（“IfThenE”）}-> StatS{ cons（“Stm”）}-> StatsS{ cons（“Block”）}图8.第八条。部分源语法见图9。 目标语法图10个。 通用语法的一部分get），其中A等价于X，用相同的属性名标记两个非终结符。(iv) 继续这个过程，直到生产和非终结符之间的每一个可能的等价都被定义。(v) 向系统提供带注释的语法，结果是ASF +SDF将返回从源到目标的转换器系统(vi) 手动处理那些不能自动导出映射的情况，主要是通过向转换器添加转换3.6转换示例我们现在通过为图8和图9所示的两种语言派生一个翻译器来说明这种方法。请注意，在这些图中，我们已经执行了步骤（i）至(iv)我们的方法，所以语法已经由用户注释包含构造函数信息和标签。转换系统首先将源语法和目标语法中的产生式与相同的构造函数属性相关联。源语法中产生式右侧的非终结符成为翻译函数f的自变量，而目标语法中产生式右侧的非终结符成为该翻译函数的结果。例如，在一个示例中，对于具有构造器属性cons（“IfThen”）的产品，转换函数f（IfS）->将导出EvalT。转换系统的重写方程现在将基于130D. Ordonez Camacho等人理论计算机科学电子笔记164（2006）121f（proc $StatsS$ endproc）=start（f（$StatsS$））f（if$Expr$ then $StatsS$ fi）=eval（$Expr$，f（$StatsS$））f（while $Expr$ do $StatsS$ od）=loop（$Expr$，f（$StatsS$））f（$IfS$ $StatS*$）= f（$IfS$）f（$StatS*$）f（$WhileS$$StatS*$）= f（$WhileS$）f（$StatS*$）f（$Expr$ $StatS*$）= $Expr$f（$StatS*$）f（StartS）f（IfS）f（WhileS-> StartT-> EvalT-> LoopT-> BlockT见图11。 翻译功能见图12。 平移函数在两部作品的左手边平移函数f（IfS）-> EvalT将被表示为f（if$Expr$ then $StatsS$ fi）=eval（$Expr$，f（$StatsS$））其中每个非终结符NT都被变量$NT$替换。对于每个非终结符，调用相应的翻译函数，除了像Expr这样的非终结符，由于语言的相似性和环境模块化，由输入和输出语法导入-这个公共语法是如图10所示。对于图8和图9的语法，自动生成平移函数的签名（图11）和实际平移方程（图12）。3.7手动干预最后，我们说明了如何处理这些情况下，我们无法建立一个产品之间的映射。每当发生这种情况时，需要手动将额外的转换添加到自动派生的转换器中。例如，图8中具有构造函数属性“IfThenE”的产生式在图9的目标语法中没有等价物。需要手动干预针对该特定示例的可能解决方案是：(i) 我们通过改变结果类型的基数来修改IfS的转换函数：f（IfS）->EvalT+(ii) 我们再加上一个等式来重写这个模式：f（if$Expr$ then $StatsS$ else $StatsS2$ fi）=eval（$Expr$，f（$StatsS$））eval（not $Expr$，f（$StatsS2$））在此手动干预之后，我们已经获得了一个完整的翻译器，可以将源代码中的任何程序翻译为目标。例如，图13左栏中的程序被转换为右边的程序D. Ordonez Camacho等人理论计算机科学电子笔记164（2006）121131−%%If语句“if-step>”如果，如果，否则，否则？“/if-step>”-> M-If{ cons（“If”）}%%通用循环语句“loop>”“”|“”“”|“”cond：M-Expressionblock：M-Block“/loop>”-> M-Loop{ cons（“Loop”）}发件人：Procif true then nil else nil2 fiwhile true do nil nil 2 nil odendproc收件人：return（true，nil）eval（not true，nil2）循环（true，nil nil2 nil））图十三.翻译实例见图14。OL族的中间表示语言的语言定义片段4中间表示语言即使我们现在有了一个自动化的机制来派生任何两种操作语言之间的源代码翻译器，如果我们想从任何语言翻译到该家族中的任何其他语言，我们仍然有可能的翻译器的组合爆炸。为了解决这个问题，正如在2.2节中所宣布的，我们设计了一种中间表示语言（IRL），它抽象了我们的操作语言家族中所有语言的行为，并只为每种语言提供翻译器。因此，我们只需要构建2n个翻译器（而不是n（n1）），其中n是OL的数量，并且向集合中添加新语言只需要添加2个额外的翻译器（而不是2n）。为了设计我们的IRL，我们选择了具有代表性的OL样本，如冥王星5，UCL或Stol [18]。然而，我们的工作受到了一些阻碍，因为对于一些OL来说，没有描述其完整语法和语义的文档。此外，由于语言的不兼容性，在某些情况下，抽象语法之间的共同性可能导致信息的丢失。例如，由于只有一个OL允许将名称与每个“指令块”相关联例如，基于图1中遇到的语言结构，我们可以决定在IRL中包含以下结构：Log、Assignment、Loop、If、GetValue、InitiateCommand。IRL中If和Loop构造的部分描述如图14所示。请注意，在我们的SDF表示中，我们已经使用了标签和构造，提供了额外的语义信息。IRL具有类似XML的语法。5由于Pluto的目标之一是成为OL的未来标准，因此它是一种非常有代表性的语言。132D. Ordonez Camacho等人理论计算机科学电子笔记164（2006）121语言A语言BExt 1扩展核心Ext 2Ext 3语言C语言E语言D图十五岁中间表示语言结构我们认为我们的IRL是一个不断发展的系统。 在最初的设计中，我们考虑一组有代表性的语言，并从这组语言中得出共同点。然而，每当我们想添加另一个OL到这个“系统”中时，我们可能会发现那些已经考虑过的结构之外的结构。为了处理这样的构造，我们以分层的方式设计了IRL，如图15所示。大多数OL共有的语言结构都属于核心模块。 围绕着那个模块 一个额外的扩展层，我们可以在其中添加一些语言共享的结构，但这些结构不够通用，不值得成为核心的一部分例如，由于不是所有OL都提供For循环，我们更喜欢将此构造作为IRL的扩展添加，而不是添加到核心。 这个扩展仍然可以被所有提供这种构造的OL重用。 结合将此语言构造描述为IRL扩展的产品，我们提供了从该扩展到IRL核心层的转换：Ext1或Ext2到Core。这个转换将是一个重写规则，在3.2节中有更详细的解释。可能存在从扩展到核心不存在可能的转换的情况-如Ext 3所示-可能是因为它对某些语言或实现过于特定（例如，线程或异常处理）。这些“未链接”的扩展必须作为例外情况进行管理，仅由语言的一个子集，因此不能完全推广。IRL结构背后的基本思想是通过模块化获得重用。对于扩展模块中存在的每个语言构造，我们通过将其映射到核心模块中的更原始的构造来提供产生式的语法和语义。这种映射通常需要手工实现;但是，一旦定义了扩展，就可以直接通过addi使用它。D. Ordonez Camacho等人理论计算机科学电子笔记164（2006）121133%% While<循环>...一种表达...一个街区”%% While语句“while>”cond：M-表达block：M-Block“/while>”-> M-While{ cons（“While”）}图16. IRL内部的图十七岁核心IRL中的实现相同结构的函数语言。为了说明这些想法，下面我们给出一些具体的翻译示例，说明IRL的可扩展性，以及如何使用新的构造来扩展它，这些构造提供了到 最终用户，同时保持通用性。让我们重新审视图14中的这是一个通用的构造，可以表达不同类型的循环（例如，while-do、do-until），通过使用附加的终端符号来指定特定类型的循环的期望语义。 例如，通过选择非终结符checkbefore/>和我们可以表示我们想要一个典型的while循环，其中条件在执行语句块之前检查条件，并且仅当条件的计算结果为true时，循环才继续。这种紧凑循环构造的通用性也具有一些缺点。它可能会使使用这种通用结构的特定翻译器，例如，表达特定类型的循环，比IRL中存在更具体的结构时更难理解。但是没有什么可以阻止我们将这些更具体的构造（以及它们到IRL中更通用的构造的映射）作为IRL的扩展。在这样的扩展中，while构造可以例如更直接和自然地表达，如图16所示。然后，这个扩展将自动转换为核心IRL中的通用循环构造，生成如图17所示的结构。现在，让我们考虑一个稍微复杂一点的情况，我们希望通过IRL传递，从只提供“do-until”循环的语言A首先，正如我们已经解释过的其次，我们需要一个从语言A中的“do-until”语句到语言B中的“while”语句的转换方案 在图19中。（在这个特殊的例子中，这需要一个循环反转。）确实，这个转换链的重写规则需要手工编写，但是一旦编写完成，它们就可以很容易地在翻译中重用134D. Ordonez Camacho等人理论计算机科学电子笔记164（2006）121%%（A）<当>阿布尔康A-Stats-Block阿布尔康<循环><检查后/> A-Bool-Cond A-Stats-Block%%（B）<循环>A-Bool-CondA-Stats-Block%%（D）<如果步骤>阿布尔康<做直到>A-Stats-Block A-Bool-Cond%% Do - Until语句“do-until>”block：M-Blockcond：M-Expression“/do-until>”-> M-DoUntil{ cons（“Until”）}图18. IRL内部的图十九岁一个（简化的）转换链（从A到D）在IRL内部执行循环反转有着相似结构的语言之间的5讨论我们的方法的一个明显的局限性，如第3节所解释的，是语言翻译器的演绎不是完全自动的。在过程开始时需要手动干预，以注释语法，指示演绎算法如何映射构造。然而，这种用户干预不是额外的工作。即使在手动编写翻译程序时，也需要深入了解两种语言中相应的结构如何关联。在我们的方法中，我们只是明确地陈述这些关系，以自动化进一步的步骤。在过程的最后需要另一个手动干预，以便为那些无法提供初始映射的构造扩展额外的另一个问题是，为了更容易将一种语言的语法映射到另一种语言，它们具有相似的结构是很重要的。 在我们的例子中，我们并没有真正解决这个问题，因为对于每种语言，我们首先根据语言手册和文档中的信息，手工设计这些语言的语法。这自然导致了一组以非常相似的方式构建的语法。 If语法对于那些已经可用的语言，然而，首先执行规范化步骤是有意义的，正如[13]所建议的那样，以类似的形式引入不同的语法语言越相似，在这些语言之间推导翻译器的过程就越可以自动化。我们做了一些实验，D. Ordonez Camacho等人理论计算机科学电子笔记164（2006）121135Pluto和我们的IRL的轻量级版本，并观察到我们的方法是高度自动化的，能够推导出大部分的转换规则，从一种语言翻译到另一种语言，而不需要任何人为干预。在少数情况下，语言结构之间的映射无法直接定义，通常可以通过简单的语法操作（添加或删除额外的非终结符）来解决，以使语法更加相似，从而避免最后的人工干预更具体地说，我们在命令执行、对象定义、流控制结构和表达式之间的转换取得了良好的效果。然而，所有这些构造都是非常局部的，不需要比产品本身提供的更多的信息。处理更全局的结构，如goto语句，或从非类型化表示传递到类型化表示，不能用我们简单的转换模式来完成，并且需要手工编程更复杂的转换规则最后，我们的方法可能被视为过于关注语法，这在一定程度上是正确的，因为我们的特定问题（操作语言之间的翻译）主要是语法问题。但是，即使在那些问题更语义化的情况下，也需要考虑语法，至少在这方面可以考虑我们的方法。人们也可能会说，用我们的技术只能实现琐碎的转换，但由于我们选择的环境和我们中间表示的设计，我们可以很容易地添加更复杂的转换-正如我们在第4节中所说明的那样-这可以 以后在其他翻译器中重复使用，无需额外的编程插件。5.1相关工作在语言翻译领域有很多相关的工作，我们不打算在这里对该领域进行详尽的调查。我们只是提出一个 其他一些有趣的方法与我们的方法密切相关或互补。在[26]中，多语言翻译是通过一个最小的中心表示和一个有限形式的可逆语法来解决的。在[25]中提出了一种扩展机制，用于使用属性语法模块化地向语言添加新功能。图翻译器在[17]中进行了研究，其中通过额外的对应规则来描述关系。 最后，[24]提供了一种基于语法指导的规则集生成翻译器5.2今后工作由于我们的工作具有很强的实用性，因此下一个合乎逻辑的步骤是将我们的原型变成生产级工具，可以将其整合到1.1小节中提到的工业工具中。尽管目前的实验仅在该领域进行，我们相信这种方法足够通用，可以用于许多其他领域。 为了验证这一说法，进一步的实验将 将我们的方法与其他领域的语言（例如，的136D. Ordonez Camacho等人理论计算机科学电子笔记164（2006）121数据库域，如[8]）。6结论我们已经展示了带注释的语法定义如何支持自动生成不同语言之间的翻译器。虽然我们在本文中使用了操作语言家族作为案例研究，但我们相信我们的技术也会对其他特定领域的语言家族有所帮助，特别是在处理具有非常相似语义的多个表示之间的密集翻译程序时。我们还以操作语言家族为例，展示了中间表示结构如何提供可扩展、模块化和可重用的“翻译系统”。最后，我们指出了我们的技术的一些具体的优点和缺点，并提出了一些有趣的途径，为未来的工作在这个领域。确认我们感谢Paul Klint、Darius Blasband和Rob Economopoulos对本文的早期版本进行了校对和评论引用[1] A. V.Aho和J.D.厄尔曼 上下文无关文法的翻译。 在STOC '69：会议记录第一届年度ACM计算理论研讨会，第93-112页，美国纽约州纽约市，1969年。Press.[2] 阿斯特里姆。用户控制语言参考手册，2003年。[3] IRA D.巴克斯特实用可扩展软件演化的程序转换。 在IWPSEPress.[4] J. A. Bergstra，Jan Heering，and Paul Klint.Algebras specification. ACM Press，New York，NY，USA，1989.[5] M. vandenBrand，A.van Deursen，J.Heering，H.de Jonge，M.de Jonge，T.Kuipers，P.克林特，L. Moonen，P. Olivier，J. Scheerder，J. Vinju，E. Visser和J. Visser。ASF+SDF Meta环境：一个基于组件的语言开发环境。In R.Wilhelm，编辑，《建筑工程》2001（CC 2001），LNCS第2027卷，第365Springer-Verlag[6] M.范登布兰德和P. ASF+SDF Meta-Environment用户手册，2005年。[7] M. Clav e l，F. Dur'an，S. Eker，P. Lincoln，N. Mar t's-Oliet，J. Meseguer和J. 克萨达 Maude：Specification and Programming in Rewriting Logic. SRI International，1999年。[8] 安东尼·克里夫，让·亨拉德，让-吕克·海诺。信息系统再工程中的协同转换。在ATEM 2004年，ENTCS。Elsevier Science，2005年。[9] James R.科迪 Txl-编程语言工具和应用程序的语言[10] ECSS-E-70-32。太空工程。地面系统和操作程序定义语言，2004年。[11] J. Heering，P. R. H. Hendriks，P. Klint，and J. Rekers.语法定义形式主义SDF -参考手册。SIGPLANNotices，24（11）：43[12] 保罗·克林特，拉尔夫·拉梅尔，克里斯·弗霍夫。语法软件的工程学科。ACM Trans. Softw.工程师，Methodol。，14（3）：331D. Ordonez Camacho等人理论计算机科学电子笔记164（2006）121137[13] Jan Kort Ralf Lammel Chris Verhoef 语法部署工具包。 《理论计算机科学电子笔记》第65卷ElsevierScience Publishers，2002.[14] R. 我叫L和D。 我很抱歉。打破了500磅的问题。IEEESoftwarere，第78-88 页 ， 2001 年 11 月 /12月。[15] 下午2点。Lewis和R. E.斯特恩斯语法定向转导。J. ACM，15（3）：465[16] L.佩特隆上下文无关语言的语法导向映射。 第九届开关和自动机理论年会论文集，1