程序转换系统综述

理论计算机科学电子笔记57（2001）网址：http://www.elsevier.nl/locate/entcs/volume57.html35页程序转换系统埃尔科·维瑟乌得勒支大学信息与计算科学研究所Box 80089，3508 TB Utrecht，TheNetherlands http://www.cs.uu.nl/visser，visser@acm.org摘要程序转换被广泛应用于编译器构造、优化、程序综合、重构、软件更新和逆向工程。复杂的程序转换是通过对程序进行多次连续修改来实现的。变换规则定义基本的变换。转换策略是一种在重写关系中选择路径的算法，该重写关系由一组规则导出。 本文综述了程序转换系统中对策略定义的支持。 在讨论了程序变换的种类和程序表示的选择之后，讨论了策略系统的基本要素，并考虑了策略语言设计中的选择。然后分析了现有语言中提供的几种类型的策略系统。1介绍程序转换在软件工程的许多领域都有应用，如编译、优化、重构、程序综合、软件更新和逆向工程。程序转换的目的是通过自动化编程任务来提高程序员的生产力，从而使编程能够在更高的抽象级别上进行，并提高可维护性和可重用性。存在许多用于程序转换的系统，其通常专用于特定的对象语言和/或转换种类。所有这些系统共享许多关于程序转换的想法，并使用类似的技术，但在许多方面往往是特别的。 最终目标是实现一种用于程序转换系统的高级声明性规范的规范语言或规范语言族，在该规范语言中可以捕获通用的、与语言无关的转换模式，并且允许高效地实现那些可以扩展到大型程序的转换。c 2001年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。Visser2本调查的目的是通过分析现有系统的出版物的基础上，了解系统之间的相似性和差异性的程序转换。程序转换的许多方面，如解析，漂亮打印和制定基本转换都相当好理解。因此，本调查集中于转型战略，即，变换系统的控制部分，其确定基本变换步骤的应用顺序。本文件的结构如下。第2节介绍了程序转换的分类。第3节讨论了程序转换系统中可以使用的程序表示的选择。第4节讨论了一个系统的成分，为规范的程序trans-cation-形成规律和策略。第5节讨论了在一些专用的转换语言中实现程序转换。第6节总结并讨论了转换系统实现中的一些研究领域。2程序变换程序是一个具有语义的结构化对象。 这种结构使我们能够to transform变换a program程序.语义学包括程序的外延和内涵行为，并为我们提供了比较程序和推理转换有效性的方法。 编程语言是遵守相同的结构和语义规则集的程序的集合。这是一个相当广泛的定义，旨在涵盖适当的编程语言（具有操作解释），但也包括数据格式，特定于域的语言以及程序的各个方面，例如它们的控制或数据流。编程语言可以被聚类成具有结构和/或语义相似性的类程序转换的通用框架的目标之一是定义尽可能多的语言之间可重用的转换。例如，变量和变量绑定的概念被所有编程语言共享。处理变量的转换，如绑定变量重命名、替换和uni-阳离子可以一次以高度通用的方式为所有语言定义程序转换是将一个程序转换为另一个程序的行为。术语程序转换也用于实现程序转换的算法的形式化描述。被转换的程序和生成的程序所使用的语言分别称为源语言和目标语言。程序转换在软件工程的许多领域都有应用，包括编译器构造、软件可视化、文档生成和软件自动更新。在所有这些应用中，我们可以区分两种主要情况，即，一种是源语言和目标语言不同（翻译），另一种是源语言和目标语言相同Visser3翻译迁移合成联系我们编译逆向工程反编译结构提取文档生成软件可视化分析控制流分析数据流分析重新措辞正常化简化脱糖织造优化专业化内联融合重构设计改进混淆改造图1.一、程序转换的分类（rephrasings）.这些主要场景可以根据它们对程序抽象层次的影响以及它们在多大程度上保持了程序的语义而被重新划分为若干典型的子场景。这一调整产生了图1中2.1翻译在翻译场景中，程序从源语言转换为不同目标语言的程序。翻译场景可以通过它们对程序抽象层次的影响来区分。虽然翻译的目的是保留程序的扩展语义，但通常不可能在翻译过程中保留所有信息。翻译场景可以分为合成、迁移、逆向工程和分析。 它们之间的关系如图2所2.1.1合成程序综合是降低程序抽象层次的一类变换。在综合的过程中，设计信息被用来换取更高的效率。在响应[50]中，实现是从高级规范导出的，使得实现满足规范。阳离子编译[1，2，36]是一种综合的形式，其中程序在一个高级语言被转换为机器代码。这种翻译通常分几个阶段完成。通常，高级语言首先被翻译成与目标机器无关的中间表示。然后，指令选择将中间表示转换为机器指令。其他合成的例子是从上下文无关语法生成解析器和漂亮的打印机[1，11]。Visser4重新措辞方面语言分析高级别语言1迁移高级别语言2高水平的抽象合成反向工程低水平的抽象低级语言1图二. 各种程序变换2.1.2迁移在迁移中，一个程序被转换成另一种语言，在相同的抽象层次上。这可以是方言之间的翻译，例如，将Fortran 77程序转换为等效的Fortran 90程序，或者从一种语言转换为另一种语言，例如，将Pascal程序移植到C语言。2.1.3逆向工程逆向工程的目的[12]是从低级程序中提取逆向工程提高了抽象的层次，是综合的对偶逆向工程的例子是反编译，其中一个目标程序被翻译成一个高级程序，架构提取，其中一个程序的设计是派生，文档生成，和软件可视化，其中一个程序的某些方面是在一个抽象的方式来描述。2.1.4分析程序分析将程序简化为一个方面，例如它的控制或数据，哦因此，分析可以被认为是到子语言或方面语言的转换。2.2重新措辞换句是将程序转换为相同语言的不同程序的转换，即，源语言和目标语言是一样的。一般来说，改写试图用不同的词来表达同样的事情，从而旨在改进程序的某些方面，这意味着它们改变了程序的语义。改写的主要子场景是规范化、优化、重构和更新。Visser52.2.1正常化规范化将程序简化为子语言程序，目的是降低其语法复杂性。去糖化是一种规范化，其中语言的一些结构（语法糖）通过将它们翻译成更基本的结构而被消除。例如，Haskell语言定义[44]描述了许多构造如何将它们去糖到内核语言中。 其他例子是模块注意和纯BNF中EBNF结构的定义，SDF2标准化器中的示例[51]。简化是一种更一般的规范化，其中程序被简化为正常（标准）形式，而不必删除简化的结构。例如，考虑转换到标准形式的中间表示和代数简化的表达式。注意，范式不一定对应于相对于一组重写规则的范式2.2.2优化优化[2，36]是一种改进程序的运行时间和/或空间性能的转换。示例优化包括融合、内联、常量传播、常量折叠、通用子表达式消除和死代码消除。2.2.3重构重构[24]是一种转换，它通过重构程序来改进程序的设计，使其变得更容易理解，同时保留其功能。混淆[16]是一种通过重命名变量、插入死代码等方式使程序更难理解的转换。混淆的目的是通过使程序更难进行逆向工程来隐藏嵌入在软件中的业务规则。2.2.4改造在软件更新中，程序的扩展行为被改变，以修复错误或使其更新以适应变化的需求。例如修复Y2K错误，或转换程序以处理欧元。2.3程序转换系统一个程序转换系统是由它在程序表示和用于实现转换的编程范式中所做的选择决定的。下一节将讨论选择程序表示时的注意事项。其余部分考虑转换的实现Visser63程序表示虽然有些系统直接处理文本，但一般来说，文本表示不足以执行复杂的转换。因此，大多数系统都使用结构化表示。由于程序是由程序员以文本形式编写的，因此需要解析器将文本转换为结构，而需要解解析器将结构转换为文本。然而，这在未来可能会改变;在意图编程框架中，程序被存储，编辑和处理为源图。程序的编辑是通过结构编辑器完成的。在选择程序表示法时，应该考虑一些问题：使用解析树或抽象语法树、树或图，如何表示变量和变量绑定，以及如何在转换组件之间交换程序。3.1解析树或抽象树解析树包含语法信息，如布局（空格和注释）、括号和消除语法转换歧义所引入的额外节点。由于这些信息通常与转换无关，解析树通常被转换为不包含这些信息的抽象语法树。然而，对于某些应用（如软件更新和重构），有必要在转换后尽可能地恢复程序的原始布局。这需要将布局存储在树中，并在整个转换过程中保持不变。特别是后一方面是有问题的;在程序的转换片段中插入注释[20]这一点在这里可能是有用的对于其他应用（例如，某些优化和编译），有必要在树中携带类型信息。这需要扩展树格式来存储类型信息，并在整个转换过程中保持类型的一致性。3.2树或图程序结构可以用树、有向无环图（DAG）或带圈的全边图来使用纯树是昂贵的，因为复制树（例如，通过在构造新树时使用变量两次）需要创建完整的副本。因此，大多数系统使用DAG。当复制一棵树时，只有一个指向树的指针被复制，因此子树被多个上下文共享。共享的好处是减少内存使用。在ATSTOM库[8]中，这种方法被发挥到了极致，只为每个构建的子树构建一个实例，从而实现了最大的共享和最小的内存使用。共享可以节省内存，降低复制成本，而且在最大化的Visser7分享，平等的测试也很便宜然而，共享的缺点覆盖用新树改变的子树的根节点将更有吸引力然而，这在一般情况下是无效的。一个共享树的两个实例在语法上是相同的，但根据它们的上下文，它们可能有完全不同的含义。即使它们具有相同的含义，也不总是希望同时更改这两种情况。当将信息与节点关联时，也会出现同样的问题。当共享仅基于语法等价时，注释与树的所有出现相关联。考虑解析树中的位置信息和抽象语法树中的类型注释的例子，可以得出结论，这通常是不可取的。最后，全边图可以用来表示树中的反向链接，例如，控制流图中的循环[2，33，36]，或声明的链接[17]。可更新的图形可以轻松地将新信息附加到节点，例如分析结果。在进行转换时，破坏性更新与复制的问题在图中甚至更成问题由于子图可以具有到整个图的链接，因此如果还需要保持原始图，则可能需要在变换之后重建整个图。对于非常特殊的目的，例如函数程序的延迟评估，可以使这种图更新透明。3.3变量绑定程序转换的一个特殊问题是变量和变量绑定的处理。在一般的方法中，抽象语法树中的变量和变量绑定就像任何其他构造一样被处理，转换系统对它们没有特殊的知识。这需要实现重命名绑定变量、替换等操作。转换需要通过额外的条件来感知变量，以避免替换期间的自由变量捕获和将变量实例从绑定中提升出来等问题。透明地处理变量绑定是可取的。高阶ab-binding语法（hoas）[34，30，45]通过将变量绑定编码为lambda抽象来解决此类问题。除了处理变量捕获的问题外，Hoas还提供高阶匹配，为高阶变量合成新函数。高阶匹配的问题之一是，对于一个模式可能有许多匹配，需要一种在它们之间进行选择的机制。FreshML [46]提供了一种较弱的机制来处理变量绑定，它透明地刷新变量名，从而解决了捕获问题。变量的替换必须显式处理。Hoas和FreshML都需要对语法结构进行一些编码，以测试lambda抽象绑定方案。这Visser8规则内联F：letf（xs）=e in e'[f（es）]-> letf（xs）=e ine'[e[es/xs]] InlineV：letx=e in e'[x]-> letx=e in e'[e]Dead：letx=e in e'->e'where（x，e '）Extract（f，xs）：e ->设f（xs）= ein f（xs）起重机：令x=e1，令f（xs）=e2，令e3 ->令f（xs）=e2，令x=e1，令e3，其中，不（in）>（x，<自由变量>对于更复杂的绑定方案，可以变得与语法所描述的结构相当远离。所有重命名变量的方法都与保留原始名称的要求相冲突，这在重构和翻新等应用中是必需的。上面讨论的方法没有解决的问题是与声明信息相关联，例如，类型声明，以及用法。这通常需要在转换过程中维护一个符号表，或者在树上分配信息，用声明中的信息注释符号的使用情况。无论哪种方式，在转换期间都需要保持信息的一致性。3.4交换格式最后，一个程序表示应该由一个交换格式来支持，该格式使得在转换组件之间交换程序成为可能。示例格式是XML，它支持树形数据的交换，以及注释术语格式[8]，它支持DAG的交换，保持最大共享。见[28]关于交换格式的参考书目4程序转换一个复杂的程序转换是通过一个程序的一些连续的修改来实现的。 至少在设计层面上是有用的以区分转换规则和转换策略。 一条规则-是程序转换的基本步骤。 战略是一个计划，使用一组规则实现复杂的转换。例如，考虑图3中的转换规则。内联规则定义了函数和变量定义的内联。死亡法则消除了图三. 一些示例转换规则Visser9指定未使用的变量定义。提取规则将表达式抽象提升规则定义了如果函数中没有使用变量，则将函数定义提升到变量定义之外。使用这组规则可以实现不同的转换。例如，优化器中的常量传播策略可以使用InlineV和Dead规则来消除常量变量定义：设x=3，x+y-> 设x=3 in 3+y->3+ y另一方面，重构浏览器中的ExtractFunction策略可以使用Extract和Hoist规则将y的加法抽象为一个新函数，并将其提升到顶层。设x = 3，x + y->let x= 3 inlet addy（z）=z+ y in addy（x）->let addy（z）=z+ y inlet x= 3 in addy（x）程序员可以通过图形用户界面交互地应用规则。这种操作的问题在于转换是不可再现的，因为决策没有被记录。通过自动化转换过程，一系列基本转换可以重复应用于程序。通过推广变换序列，组合变换可以应用于许多程序。 这需要将规则组合成更复杂的转换的机制。本节讨论了规则和策略的基本要素。4.1转换规则规则基于语言的语义。规则通常保留程序的语义。也就是说，在应用规则之前和之后，程序具有相同的含义。通常，程序的可观察行为会被保留，但某些其他方面会被改变。例如，优化尝试减少程序的时间或空间资源使用。例如，应用常数传播可以减少对寄存器的需求。在重构过程中提取函数可以提高程序的可读性。一个规则包括识别一个程序片段来转换和构造一个新的程序片段来代替旧的。识别涉及匹配程序的语法结构，并可能验证某些语义条件。规则中的替换可以由一个简单的术语模式、一个构造新树或图的函数或一个具有任意边对象的语义动作组成。当使用树或术语表示时，可以使用术语模式匹配。一阶项模式可用于通过同时识别结构并将变量绑定到子项来分解项，否则子项将由测试标记并选择子项的嵌套条件表达式来表达。然而，一阶模式不被视为一阶类cit。Visser10见图4。变换规则构成中的现象：不一致、不一致、一致、不一致izens及其使用对模块化和重用造成了限制：没有提供模式上的抽象，因为它们可能只出现在重写规则的左侧、case的分支或子句的头部;模式匹配与抽象数据类型不一致，因为它暴露了数据表示;一阶模式只能从模式到它的叶子，这使得有必要从模式中单独定义数据结构的递归遍历，以获得所有需要的信息。由于这些原因，已经为几种语言实现或考虑了基本模式匹配特性的增强。例如，ASF+SDF [19]中的列表匹配用于将列表划分为可能由元素模式分隔的多个子列表。OBJ ，Maude [13] 和ELAN [4] 中的关联交换（AC）匹配支持将列表视为多集。Prolog [37，45]中的高阶union允许在任意上下文中对子项进行高阶匹配[22，29]，这反过来又允许使用高阶变量在任意深度级别匹配子项，而无需显式遍历所涉及的结构。Haskell的视图，如[57]中所提出的，提供了一种使用不同模式来查看数据结构的方法，而不是用来表示它们。Overlay [52]是伪构造函数，它使用实际的构造函数从底层表示中抽象出来4.2转型战略编程语言的一组转换规则会导致程序上的重写关系[18]。如果关系是连续的和终止的，则每个程序都有唯一的范式在这种情况下，问题是以最有效的方式应用规则以达到标准形式。然而，在程序转换中，情况通常并非如此。如图4所示，一组变换规则可以产生夜间分支（例如，通过内联递归函数），其中变换被撤销的逆（例如，通过分布或交换性规则），以及其中一个程序可以被转换成两个不同程序的不连续性。Visser11根据转换任务的目标，应该在重写关系中选择路径。对于一个特定的程序，总是可以找到一个特定的转换任务的最优解的最短路径。然而，对于大多数转换任务，需要自动化确定路径的过程，并且最佳解决方案可能仅是近似的。策略是在重写关系中选择路径的算法。给定一组在规则中，可以有许多策略，每一种策略都可以实现不同的目标。 另一方面，一般策略可以适用于许多不同的规则集。策略可以由转换引擎提供，也可以是用户自定义的.在这两个选项之间存在一系列可能性：固定的应用程序顺序。引擎根据内置策略彻底应用规则。例子是最内层和最外层约简。自动依赖分析。引擎基于对规则的分析来确定策略。例子是严格和懒惰的分析目标驱动。 发动机 总结了如何应用规则来实现用户- 定的目标。策略菜单。可以从一个小集合中选择一个策略。例如，在最内层和最外层的归约之间进行选择，或者用惰性信息注释完全可编程。应用规则的策略可以用策略语言编程。无论是由用户定义还是由引擎定义，策略都需要形式化地表达和实现。本节的其余部分将讨论语言中用于制定策略的成分。4.2.1顺序组合为了在重写关系中选择路径，应该将基本规则组合到转换中。可以通过连续应用两个变换、在两个变换之间有条件地选择以及迭代地或递归地重复变换来组合变换。4.2.2非确定性规划根据当前程序的属性在两条路径之间进行选择可能会受到太多限制。可能有必要在应用若干转换之后决定选择的适当性。一种方法是推测性地探索路径，直到找到可接受的解决方案，另一种方法是并行地探索所有路径并选择最佳解决方案。在投机性探索的情况下，需要在两条备选路径之间进行某种非确定性如果其中一条路径失败，则采取另一条路径。如果回溯是局部的，则在所选分支之一成功后进行选择。如果回溯是全局的，则在任何点Visser12在选择的内部或之后会导致回溯到备选路径。这允许探索整个搜索空间，直到找到可接受的解决方案。所有路径的并行探索需要基于某种成本函数比较解决方案的机制对于一些这样的问题，动态编程技术可以用来有效地应用所有的转换。在推测和并行探索之间是基于目标的探索，其中一组约束导致丢弃与约束不一致的路径。4.2.3结构运输重写关系包括在任何上下文中应用规则。这需要遍历程序表示结构以找到应用规则的位置，应用规则并重建上下文。除了应用的顺序和路径选择之外，应用规则的位置也由策略决定。 通过树中的路径来表示这些位置是没有吸引力的，因为遍历和重建每个规则应用程序的上下文是不必要的。通常，规则在树中彼此靠近地因此，需要某种机制来遍历语法树并在子树处应用转换规则。特定于语言的遍历机制需要为语言中的所有构造定义遍历。这可能会导致大型语言（具有复杂的抽象语法）的大型规范。一种语言类属遍历机制支持在抽象语法树上的类属遍历的定义。这需要公开底层的表示模型。遍历机制可以提供一组固定的遍历，如自顶向下和自底向上，或提供遍历原语，从这些遍历原语可以定义所有类型的遍历4.2.4信息承载策略策略可以携带信息，这些信息可以用于做出关于要采取的路径的决策以及将上下文敏感的信息传递给规则。4.2.5规则与策略虽然我们在概念层面上区分了规则，但在实施层面上，规则和策略可以交织在一起，即，规则可以在策略的定义中被硬连线。或者，规则和策略可以分开定义，这需要策略用一组规则参数化。规则和策略的单独定义导致更清晰的规范，允许单独推理较小的实体（规则，策略）。此外，单独的定义使得规则和策略的重用以及所有或一类语言所共有的转换系统的方面的通用实现成为可能。然而，出于效率原因，有时可能需要缠绕。在这些情况下，理想的是，Visser13由编译器而不是由指定程序来完成。4.2.6抽象为了实现一般策略的重用，特别是将规则与策略分离，需要一种允许对规则和策略进行抽象的抽象机制也就是说，应该能够命名和参数化规则和策略。5程序转换语言本节讨论一些专门为实现程序转换而设计的语言。将讨论以下主题：交互式程序转换，有意编程，树解析，项重写和基本项重写的一些扩展，解决标准重写策略的问题：策略注释，规范形式的序列，探索非确定性策略的归约空间，通过反射引导重写，用遍历函数重写和通用重写策略。5.1交互式程序转换Draco [39，40]是第一个支持将高级领域专用程序转换为可执行代码的系统。该系统支持为优化和修正定义转换规则，将高层结构转换为低层结构。变换规则和变换元素通过名称来标识。转换规则也有指定其相对优先级的应用程序代码。对域程序的转换和修改的应用由用户通过交互过程控制。在这个过程中，用户必须选择域，实例（抽象语法树中代表程序的区域）和区域（抽象语法树中的节点）。可以使用apply将转换直接应用于当前选定的区域设置。系统可以检查树并建议要应用的转换。使用transform命令可以自动应用特定范围内的所有变换规则。transform命令使用自底向上遍历树，在提供的代码范围内应用规则。具有较高代码的规则首先应用。在[38]中，也有自顶向下遍历和应用最佳规则rst的遍历的描述。可以使用尝试和使用单独应用。通过战术手段，这一过程的一定程度的自动化是可能的5.2有意编程Intentional Programming是一个由微软研究院开发的元编程系统。给出了意向规划的一个很好的描述Visser14在[17]中。在有意编程中，程序由源代码树而不是源代码文本表示。源树的每个节点都有一个对其声明的引用（从而使树成为源图）。例如，一个变量的出现有一个到它的声明的链接.同样，每一种语言结构或意图对应于一个定义它的树节点。意图可以通过链接到意图的定义来使用。例如，while语句是具有对应于条件和迭代语句的两个孩子的节点，以及到while意图的链接。领域特定的编程抽象可以通过定义新的意图来捕获。源代码树是通过只使用R代码意图将它们简化为源代码树来实现的。R代码意图是可以由代码生成器转换为某种形式的机器代码的基本构造。部分定义每一个意图都有一种方法将其简化为R代码。这些归约方法之间的依赖关系由国际编程引擎计算和解释，以将整个程序归约为其R代码。5.3简单树解析树解析类似于字符串解析;其目标不是在字符串中发现结构，而是通过用模式覆盖树来发现树中的结构Sorcerer[42，43]是antlr语言处理系统的树解析器生成器Sorcerer从树语法生成树步行者树文法是用于定义树结构的类似bnf例如，语法exp： #（加上expexp）| INT描述了由整数和加法组成的表达式树。树的翻译和转换是通过将动作与文法产生式相关联来实现的。文本输出的转换是通过打印操作实现的。例如，下面的语法打印使用in x表示法的表达式。exp： #（PLUS exp printf（“+”）;>> exp）| int <>树转换是通过重建树并将其作为结果返回来实现的。例如，下面的语法通过交换PLUS运算符的参数来转换表达式。exp：！ #（PLUSl：exp r：exp）<<#exp = #（PLUSr l）;>>| INT语法非终结符可以有可以在产生式中的动作中使用的参数。非终结符也可以返回结果。树文法Visser15产生了一组相互递归的函数，每个非终结符对应一个，它们一起定义了一个遍历树的一次遍历。模式可以嵌套，并且可以使用带有可选项、替代项和列表的正则树表达式。树文法中的转换规则嵌入在文法产生式中。巫师不支持规则和策略的分离以及通用树遍历。5.4基于动态规划的如果一个树语法是二义性的，那么一个树的多个解析是可能的。解析器需要决定采用哪个解析。通过将成本与每个生产相关联，消除歧义可以基于树的累积成本。动态编程技术可以用于在一次遍历中计算所有可能的解析。Burg[25，26，48]是一个从中间表示（IR）表达式树生成代码的系统利用树文法定义了IR树到机器指令的映射。形式n ->t（c）的产生式定义了树模式t到非终结n的代价为c的映射。与每个生产相关联的是在选择生产时要采取的操作。例如，Proebsting [48]在图5中给出了示例语法。根据该语法，项Fetch（Fetch（Plus（Reg，Int）具有两个覆盖，分别对应于成本为7和4的派生4（4（6（5（2，3）和4（4（8（2）如该示例所示，树的多于一个覆盖是可能的，对应于生成代码的不同方式。每个节点可以有几个不同的解析，因为重叠的模式和链规则。与生产相关的成本表示执行相关机器指令的成本。代码生成器的目标是找到最低成本覆盖（即，最低执行时间）。根据自下而上重写理论（burs），ir树可以使用以下策略转换为指令序列在自底向上遍历中，计算与每个节点匹配的所有最低成本模式并将其与该节点关联。这涉及到将产品的右侧与树进行匹配，同时考虑子树的早期匹配。然后，在由树的根的目标非终端驱动的自顶向下遍历中选择指令。这种有限的重写形式也可以应用于简单类型[48][1]目标->reg（0）[五]《中国日报》reg-> 加上（reg，reg）（二）[2]reg->Reg（0）[6]美国addr-> reg（0）[->Int（ [七] ad-> Int（Visser163]reg一）《中国日报》dr0）[4]reg->获取（地址）（二）[八]《中国日报》addr-> 加上（reg，Int）（0）图五. BURG规格示例Visser17-> x-> Or（Not（x），Not（y））：Not（Not（x））：Not（And（x，y））：And（或（x，y），z）->或（And（x，z），And（y，z））：And（z，Or（x，y））-> Or（And（z，x），And（z，y））：Or（And（x，y），z）-> And（OrDAOLDAORDOALDOARDNDMADMO：道具：String -> Prop：Prop -> Prop：Prop * Prop -> Prop：Prop * Prop -> Prop真原子非与或规则签名排序Prop构造函数错误：道具推理问题，用于检查树格式，以及用于树简化。5.5项重写术语重写[18]被OBJ [27]、ASF+SDF [19]、ELAN [5]等系统支持术语重写是程序转换的一种有吸引力的范例。一阶项可以用来描述程序的抽象语法。例如，考虑图6中命题公式的声明。形式为t1->t2的重写规则声明了项匹配模式t1到t2的实例化的变换。重写规则可以用来表达基本的转换规则，并且可以被认为是语言的代数定律的运算。例如，图6中的重写规则表示命题逻辑的基本定律，即，分配规则、双重否定规则和德摩根规则。使用更强形式的模式匹配，诸如等式匹配的各种实例AC匹配，列表匹配），模式可以捕获复杂的术语配置。此外，在条件重写规则中，可以声明对模式的附加测试。redex是与重写规则匹配的子项。如果一个项没有下标，则它是标准形式。用于术语重写系统的重写引擎相对于规范中的规则集来计算术语的范式。这包括对子条款详尽地应用规则，直到不再适用规则。重写引擎可以采用不同的策略来对规则的应用进行排序。在最内层重写中，在规则应用于术语本身之前，术语的所有子项都被规范化。在最外面的重写中，最接近项的根的redices被重写为rst。这意味着规则是自动应用的见图6。 命题公式的签名和重写规则。Visser18-> x-> Or（not（x），not（y））-> and（not（x），：not（Not（x））：not（And（x，y））：not（OrNOT1NOT2NOT3NOT4-> And（x，y）（默认值）：和（x，y）：and（或（x，y），z）->或（and（x，z），and（y，z））：and（z，Or（x，y））-> Or（andAND1AND2AND3-> True->错误-> Atom（x）-> not（dnf（x））-> and（dnf（x），dnf（y））：dnf（True）：dnf（False）：dnf（Atom（x））：dnf（NotDNF1DNF2DNF3DNF4DNF5DNF6签名构造函数dnf： Prop -> PropProp * Prop -> Prop不是Prop-> Prop规则并且不需要定义在语法树上的遍历。然而，重写的完全规范化方法证明不足以用于程序转换，因为用于编程语言的重写系统通常是非终止的和/或非并发的。一般而言，不宜同时适用所有规则，或在所有情况下适用所有规则。作为示例，再次考虑图6中的重写规则集。这个重写系统是非终止的，因为规则DAOL和DAOR启用规则DOAL和DOAR，反之亦然。如果我们想定义一个转换来将公式规范化为析取范式，我们可以放弃规则DOAL和DOAR。然而，如果在转换的另一部分需要合取范式，我们需要一个不同的重写系统。不可能将这些规则组合在一个重写系统中。这类问题的常见解决方案是引入额外的构造函数（函数），以在一组受限的规则下实现规范化。图7示出了图6中的重写系统如何能够转变为将规范化定义为析取范式（DNF）的终止重写系统。要将公式规范化为DNF，应对其应用函数dnf。规范化为合取范式需要类似的定义。图7.第一次会议。析取范式的函数化重写系统Visser19dnf函数通过循环遍历项来模仿最内层的规范化策略。辅助函数not和and用于应用分布规则和求反规则。在函数式编程中，这样的辅助函数被称为智能构造器[21]。在定义and andnot的规则时，假设这些函数的参数已经是析取范式。例如，如果和的参数都不是Or项，则该项本身被认为是DNF中在图7中的解决方案中，原始规则已经与dnf转换完全兼容。在合取范式的规范化定义中，否定规则不能重复使用。对于每个新的转换，必须定义新的遍历函数和新的智能构造函数。必须添加许多额外的规则来遍历该术语，和适用规则的地方而不是5条规则，总共有13条规则，needed.规则AND3和NOT4是默认规则，仅在其他规则不适用时适用。如果没有这种机制，甚至需要使用更多的规则来处理真正的转换规则不适用的情况ASF+SDF中引入了默认规则[19]。上面例子中的问题在所有类型的转换中经常出现。例如，将SDF 2语法定义规范化为Kernel-Sdf [51];编程结构的去糖化;以及重构，其中程序的某些部分可能必须简化，而其他部分可能必须去简化。一般来说，试图克服非终止性和非连续性的问题导致在额外的重写规则方面对控制进行编码（这与我们尽可能多地将规则与策略分离的目标不一致）。这通常会导致重写的函数式编程风格，签名中每个构造函数的遍历规则形式的开销，规则和函数定义的交织，所有这些都使得规则的重用变得不可能，并导致更难理解的规范5.6使用Traffic函数在ASF+SDF中，控制转换规则的应用一直是一个公认的问题。特别是对于大型语言（如cobol）的转换规范，定义遍历的开销被视为有问题的因素。首先，这是通过生成可以被普通规则覆盖的默认遍历规则[11，10]来解决的在这种方法中，通常只需要指定几个重写规则，对应于遍历的非默认行为。然而，生成的规则的数量仍然被证明是开销的来源，无论是编译器，而不是程序员。此外，提供新的遍历方案需要添加新的生成器。在最近的方法[9]中，重写引擎直接支持遍历函数，避免了生成规则的编译时开销。图-Visser20-> x-> Or（not（x），not（y））-> and（not（x），：not（Not（x））：not（And（x，y））：not（OrNOT1NOT2NOT3NOT4-> And（x，y）（默认值）：和（x，y）：and（或（x，y），z）->或（and（x，z），and（y，z））：and（z，Or（x，y））-> Or（andAND1AND2AND3：dnf（Not（x））-> not（x）：dnf（And（x，y））->DNF4DNF5签名构造函数dnf：Prop -> Prop {transversal（trafo，bottom-up）}和：Prop * Prop-> Propnot：Prop -> Prop规则图8.第八条。具有遍历功能的析取范式（版本1）图8说明了应用于标准化为析取范式的问题请注意，该示例不使用ASF+SDF语法。该规范与图7中的规范相同，但dnf函数已在签名中声明为属性遍历（trafo，bottom-up）声明dnf对其参数执行自底向上遍历。这意味着函数在应用于项本身之前首先应用于直接子项（因此递归地应用于所有子项）。只需要为那些被转换的构造声明规则默认行为是用原始构造函数重构项。在示例中，这将遍历的指定从6条规则减少到2条规则。一般来说，对于具有n个构造器的签名，其中只有m个构造器需要以特殊的方式处理，这节省了n m个规则。在图8中的规范中仍然存在一些开销，其形式是从遍历函数到智能构造函数的分派以及智能构造函数的默认规则。更简洁的规范如图9所示，其中没有使用智能构造函数。在这种风格中，每个原始规则只需要一个规则。然而，这种风格的问题是，规则右侧的递归调用将在应用其中一个规则之前完全重新遍历树（树的参数已经规范化）。ASF+SDF提供了一组有限的遍历。 对于遍历策略，可以在自顶向下和自底向上之间进行选择。后者已在上文解释。 自顶向下遍历树，并在规则应用后立即停止。此外，遍历可以是变换（trafo）和/或沿途累积信息的遍历（accu）。最后，遍历