语言代数和转换实现的语法扩展方法

理论计算机科学电子笔记253（2010）19-35www.elsevier.com/locate/entcs基于语言代数和变换的句法语言扩展雅各布·安德森1丹麦奥胡斯大学计算机科学系Claus Brabrand2哥本哈根IT大学哥本哈根，丹麦摘要我们提出了一个代数的语言和转换的语法扩展语言的一种手段。代数提供了一个建立在语言（由上下文无关语法捕获）和转换（由构造性变形捕获）之上的高级抽象层。代数是自包含的，因为指定变换的代数的任何项都可以简化为一种变质作用，在转化之前。 因此，代数是“免费”的，没有牺牲构造变质的强安全性和有效性本文中提出的整个代数是作为香蕉代数工具实现的，用于通过先前定义的语言和转换的代数组合，以增量和模块化的方式对语言进行语法扩展。 我们通过几种方式演示和评估该工具的扩展。关键词：语言;变换;句法扩展;宏;上下文无关文法;变形;香蕉;代数。1介绍和动机我们提出了一个关于语言和转换的16个运算符的代数，作为一种简单的、增量的、模块化的方式，通过对先前定义的语言和转换的代数组合来指定安全有效的语法语言扩展扩展是简单的，因为我们基于一种经过良好验证且易于使用的形式主义，用于良好类型的语法导向转换，称为构造性转换1电子邮件：jacand@cs.au.dk2电子邮件：brabrand@itu.dk1571-0661 © 2010 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2010.08.02920J. 安德森角Brabrand/Electronic Notes in Theoretical Computer Science 253（2010）19变质作用这些转换是相对于源语言和目标语言而指定的，这些语言是通过上下文无关语法（CFG）定义的。以前已经研究过变形，并证明其作为通过转换扩展各种编程语言的一种手段具有足够的表达性[5，6，7]。因此，本文的主要重点不在于解决的表现力和转换可以实现的代数组合的语言和转换的结果，在高度模块化和增量的语言扩展。增量和模块化意味着任何先前定义的语言或转换都可以代数地组合以形成新的语言和转换。安全性意味着该工具静态地保证转换总是终止，并且只将语法上合法的输入项映射到语法上合法的输出项;高效性意味着任何转换都保证在线性时间内运行（输入和生成的输出的大小代数的一个重要性质是建立在退化之上的 它是这意味着所有由代数操作的高级构造（包括语言和转换的组合）可以在编译时处理，在转换运行之前，而不会牺牲强大的安全性和效率保证。本文中提出的一切都已实现的形式香蕉代数工具，作为参数，需要一个转换项的代数，然后分析安全性和减少到一个常数的变形，随后可以运行转换输入程序。该工具可以用于许多不同的转换目的，诸如不同语言之间的转换（例如，用于将Java程序翻译成JavaDoc风格的HTML文档或用于对轻量级领域特定语言编译器进行原型化），将给定语言（例如，CPS变换），格式转换（例如，将BibTex转换为BibTeXML）。然而，在本文中，我们将专注于语言扩展，我们考虑了以下使用场景：1）程序员可以用自己的宏扩展现有的语言; 2）开发人员可以在宿主语言中嵌入特定领域语言（DSL）; 3）编程人员可以只实现一个小的核心，并在外部指定其余部分;以及4）开发人员或教师可以通过将抽象堆叠在彼此之上来逐步定义语言。我们将在第6节中证实这些使用声明。这种方法抓住了第7节中列出的全面编译器生成器过于繁琐的利基，以及语法转换的简单技术不够表达或安全，或者没有足够的增量开发支持。我们的贡献包括一个代数的语言和transformations的增量和模块化的语法语言扩展的基础上的catamorphisms的设计;一个概念验证工具和实现能够与具体的语法;和评估的代数方法。J. 安德森角Brabrand/Electronic Notes in Theoretical Computer Science 253（2010）19212变质作用一种变质作用（又名，banana[16]）是从函数式编程语言中已知的列表折叠高阶函数的一般化，其处理列表并建立返回值。然而，它不是处理列表，而是处理任何归纳定义的数据类型。蜕变有一个很强的范畴理论基础[16]，我们在本文中不作探讨。一个变形与数据类型的每个构造函数相关联的替换求值函数用于转换。给定一个数据类型的输入项，一个变形然后在输入结构上执行递归下降，从而有效地解构它，并以自底向上的方式应用替换求值函数重新组合中间结果以获得最终输出结果。许多计算可以表示为退化。作为一个例子，让我们考虑一个归纳定义的数据类型，列表，定义非空的数字列表list =中国 | Cons N * list一个数列中的值的和可以很容易地通过一个变形来定义，通过用数上的恒等函数（λn.n）代替n-构造函数，用数上的加法（λ（n，l）.n+l）代替Cons-构造函数，对应于下面的递归定义：[[n]]=n[[Consn l]]= n+[[l]]退化的主要优点之一是，输入结构上的递归事实上，递归完全由输入数据类型决定，因此通常只隐式指定。由于上面的求和变形将类型列表的项映射到自然数N，所以它可以用它的替换求值函数唯一地标识;在这种情况下，对于N→N类型的n-构造函数和对于Cons类型的N×N→N类型的替换函数。异化现象通常被写在所谓的香蕉胸罩ckets“（|· · ·|）“[ 16 ]：（|λn.n，λ（n，l）.n + l|）2.1建设性变质作用构造性变形是变形的一种受限形式，其中仅允许输出类型的重构器作为替换求值器函数。重构器只是来自（可能不同的）归纳定义的数据集的构造器术语例如，我们可以将列表转换为树数据类型的二叉树树=无 | Leaf N | Node N * tree * tree利用构造变质作用：[[n]]=叶片n[[Consn l]]=节点n（Nil）[[l]]22J. 安德森角Brabrand/Electronic Notes in Theoretical Computer Science 253（2010）19虽然非常简单，能够平凡的递归，我们声称，这种建设性的蜕变提供了编程语言扩展的基础。我们将在下一节中研究这一主张2.2安全性和有效性构造性变形有很多有趣的性质;它们可以被静态地验证语法安全性，保证终止，并在线性时间内运行。一个构造性的变形，c，是用一个源语言ls和一个目标语言lt来类型化的，如 这些语言既可以作为一个数据类型（在抽象语法级别），也可以作为一个CFG（在具体语法级别）。一个构造性变形被称为语法安全的，如果它只产生语法有效的输出项，ωt∈ L（lt），给定语法有效的输入项，ωs∈ L（ls）：<$ω∈L（ls）<$c（ω）∈L（lt）除了语言类型（ls→lt）之外， 我们还需要一个非终结符类型τ，它对于输入语言的每个非终结符都映射到目标语言的非终结符上。如果我们分别命名上述示例的源语言和目标语言Lists和Trees，则语言类型变 为 “Lists -> Trees“ ， 非 终 结 符 类 型 τ 为 “[list ->tree]“。（尖括号约定的原因是可能有多个非终结符在起作用，在这种情况下，多个映射被写为括号内的逗号分隔列表。为了验证变质作用，|ls→lt[τ]c|）在策略上是安全的，则只需检查每个变质的重建器项（例如，“[l]]）是适当类型的有效语法（在这种情况下，l具有源类型列表，这意味着[l]]具有类型τ（列表）=树）。我们参考文献[1]中关于如何验证句法安全性的形式化处理。构造性变质作用是非常有效的。在输入和输出的大小上，它们以线性时间运行：O（|ω|+的|c（ω）|）.3语言扩展我们现在将使用故意简单的例子来说明如何使用构造性的同构来扩展编程语言，并激发编程语言扩展的想法为此，让我们考虑核心λ-演算（无类型，无常量），其语法结构可以由以下数据类型定义：exp=变量ID | Lam id * exp | App exp * expJ. 安德森角Brabrand/Electronic Notes in Theoretical Computer Science 253（2010）1923在下文中，我们将研究如何使用异化来扩展λ-演算;特别地，我们将研究两个著名的扩展，即数字和布尔。3.1扩展名：数字核心λ-演算的一个常见扩展是数字;演算扩展了表示零的构造，以及表示数字的后继者和前导者的一元构造这些构造可以组合以表示一元编码中的任何自然数并用于执行数值计算。然后，演算的语法被扩展到语言LN：exp=变量id|Lamid * exp|应用程序扩展 * 扩展|零|成功经验|预测值现在我们将展示如何使用一种变形来将扩展语言LN转换为核心λ-演算L，使用一种基本的数字编码，将零表示为单位函数（λz.z），并将数字n表示为：恩戈达斯λs。 λsx.“. . ...”零λzx`。z轴还有许多其他可能的数字编码，包括更常用的Church数字表示，但编码的选择不是这里的主要兴趣，所以我们只使用更简单的替代方案来说明这一点。我们现在可以用数字来扩展λ-演算，作为“LN -> L [exp -> exp]“类型的构造性变形[[V]]=Var[[V]][[LamV E]]=[[V]] [[E]][[应用程序E1E2]]为应用程序[[E1]][[E2]][[Zero]]=Lam z（Varz）[[SuccE]]=Lam s[[E]][[PredE]]=应用程序[[E]]（Lam z（Var z））前三个规则只是简单地递归输入结构，产生相同的输出结构。零成为恒等函数，后继者在参数的编码前添加一个“lambda s”，而前导者通过将其应用于恒等函数来例如，这将Succ Zero映射到其编码Lams（Lam z（Var z））。3.2其他扩展类似地，核心λ-演算可以很容易地用布尔值扩展（通过空值构造函数True和False，以及一个三元If），产生一个语法上扩展的语言LB，然后可以通过输入“LB -> L [exp -> exp]“的构造性变形转换为核心λ-演算[[真的]]=Lam a（Lam b（Vara））[[False]]=Lam a（Lam b（Varb））[[如果E1E2E3]]为App（App[[E1]][[E2]]）[[E3]]24J. 安德森角Brabrand/Electronic Notes in Theoretical Computer Science 253（2010）19+v）变换（L −> L）和（LN −> L）的“加法”产生完整的变换：（L+LN −> L）。IDXiv) 在语言“L”上的恒等变换（L −>L）exp =变量id|Lam id *exp|应用程序扩展 *扩展i) 核心语言：iii）变换（LN −> L）从扩展到核心语言。exp =零|成功经验|预测值ii）语言扩展名：Fig. 1. 语言扩展中的常见模式（这里用数字扩展λ-演算请注意，我们省略了变量、lambda抽象和应用程序的三行"身份转换"。沿着类似的思路，λ-演算可以进一步扩展为加法、乘法、否定、合取、列表、对等，最终收敛一个完整的编程语言。为了证实这是语言扩展的充分基础的说法，我们将λ-演算扩展到了以前用于函数式语言教学的语言;“乐趣”（参见。第6节）。4语言代数与变换研究以前关于句法宏和转换的工作[5，6，7]揭示了一个有趣的和反复出现的现象，即宏扩展遵循一定的模式。在这个方向上的第一个提示是在前三行的构造性变形中涉及的e_t，它们只是在那里指定核心λ -演算上的这个问题可以通过显式语言支持来缓解。事实上，每一个这样的语言扩展都可以分成相同的五个单元（其中一些是语言，其中一些是转换），如图1所示：i）要扩展的核心语言（例如，λ-演算）; ii）语言3语言扩展（例如，（带数字的扩展）; iii）核心语言上的恒等变换; iv）将扩展语言映射到核心语言的变换;以及v）恒等变换和语言扩展到核心语言的小变换的“添加”的概念。4.1代数上述五种成分可以直接用五种代数运算符来捕捉。首先，情况i）和ii）对应于可以由上下文无关语法（具有用于附加变换的“命名产生式”）建模的常量语言第二，情况iii）对应于常数变换，其可以[3]注意，我们称扩展语言为不包括核心语言。（|LN −> L [exp −> exp][零] = Lam z（变量z）[成功E]= Lam s [E][Pred E] = App [E]（Lam z（Var z））|）J. 安德森角Brabrand/Electronic Notes in Theoretical Computer Science 253（2010）1925→→→→→→→→→→→◦LL1LL2vL3L\LL4L+LL5src（X）L6tgt（X）L7设v=L，在L中→ L8letxw=XinL(a) 语言代数（L）XX1（一）|LL[τ]c|）X2WX3X\LX4X+XX5X XX6idx（L）X7设v=L在X中X8letxw=XinX(b) ...变换（X）。图二. 代数学的第二部分作为输出类型的构造性变形c给出，用转换的源语言和目标语言（以及非终结符类型τ）进行类型化。第三，情形iv）对应于一个算子取一个语言l，并把它转化为该语言上的恒等变换（l→l）第四，关于加法的概念变换，采取两个o变换ls→lt和lsJ→ltJ，产生一个trans-t。构词法：（lsllsJ）→（ltlltJ）其中“l“是语言上的加法。语言加法被定义为各个产生式的并集（变换加法被定义为分解重构器的并集），这在两种情况下都确保加法是幂等的、对称的、结合的和可交换的。关于加法在语言和变换上的形式定义，我们参考[1]。请注意，通过这些操作，很容易获得一个组合了数字扩展和布尔值的转换;只需将这两个转换“相加”。虽然上面的代数运算已经足够做上一章的所有扩展了，但我们还是想在语言和转换上再增加几个代数请注意，尽管操作符的设计和选择是通过迭代过程产生的，但我们试图将构造的动机分为两类;操作符分别适应模块化和增量语言扩展。图2给出了代数的完整语法。(The用于语言常量、变换常量、语言加法、变换加法和恒等变换的规则分别编号为L1、X1、L4、X4和X6。当然，可以向代数中添加更多的运算符;然而，我们已经证明，这些运算符足以方便地将λ-演算逐步扩展到Fun编程语言。这些想法是追求在其余的文件，其中还包括整个代数方法的评价。对于代数语义的形式化说明，参见附录（对于底层语言和转换的说明，参见[1]）。4.2模块语言扩展为了允许模块化语言开发并在转换中分离每个输入，我们通过标准let-in函数编程本地绑定器构造添加了本地定义机制。因此，我们在语言和转换的语法中增加了变量（图2，规则L2和X2）和局部定义（图2，规则L7和X7）。在实践中，它也被证明是有用的，能够定义（本地）transfor。→→→→26J. 安德森角Brabrand/Electronic Notes in Theoretical Computer Science 253（2010）19在指定语言时使用mations;以及，正交地，在指定转换时定义（本地）语言。因此，我们将局部定义L8和X8添加到图2中。4.3增量语言扩展转换经常根据先前定义的语言和转换来递增地指定。为了适应这种使用，我们添加了用于指定转换的源语言和目标语言的方法以及用于限制语言和转换的方法（即，限制转换的源语言 通过限制，我们采用“L1\L2“来产生一种与L1相同的语言，但是其中所有在L2中也被命名的产生式都被消除了。(The所提到的操作符被列为图2的规则L5、L6、L3和X3。而且，为了简单或易读，转换经常通过中间句法结构来表达。例如，注意3.1节的转换中的两个分解重构器都使用标识lambda抽象Lam z（Var z）。在这里，可以通过使用中间语言LI来增量地指定这种转换，该中间语言LI丰富了作为显式空值构造的身份exp=变量ID | Lam id * exp | App exp * exp |Id虽然在这样一个小例子中，在简单性和/或易读性方面几乎没有什么收获转换（[[Zero]]=Id[[SuccE]]=Lam s[[E]][[PredE]]=应用程序[[E]]（Id）它随后通过将身份丰富的语言去糖到核心λ-演算“li 2l：LI -> L“的微小转换组成[[Id]]=Lam z（Varz）毫不奇怪，当我们使用这个工具做这个实验时，变换“li2l li2ln“产生的为了实现这种增量开发，我们添加了组合作为转换的操作符（参见图2，规则X5）。请注意，没有一个运算符超越了构造性异化的表达能力，因为任何语言项都可以静态地归约为上下文无关文法;任何转换项都可以归约为异化。代数方法的一个重要优点是，几个代数定律成立，从而产生简化（例如，“(For一个正式规范的约简和语义的运算符，见附录）。J. 安德森角Brabrand/Electronic Notes in Theoretical Computer Science 253（2010）1927实验或：实验1“||“Exp;.exp1： Exp1;Exp1.and ：Exp2““Exp1;.exp2： Exp2;Exp2.add ：Exp3“+”Exp2;.exp3： Exp3;·E·x·p7.neg ：“！“Exp8 ;.exp8：Exp8;Exp8.par：“（“Exp“）”;.var：Id;.num： int;(a) Java语法片段。Stm.repeat =Stm.do（1>，01 - 022019 - 04 -22 01：03：032016 - 05 -25 01：05：0509 - 07陈晓（Exp8.par（2>）（））;(b) 抽象语法。标准品重复=' while（！（<2>））;';(c) 具体语法。图三.使用抽象与具体语法指定转换的示例。(For强调，我们已经强调了否定和括号结构。）5工具和实施为了验证代数方法，我们以香蕉代数工具的形式实现了所有内容，我们使用它来实验不同形式的语言扩展。5.1抽象与具体构建该工具的一个关键问题是选择使用抽象语法还是具体语法。到目前为止，我们所介绍的一切都是专门在抽象句法层次上进行的。然而，对于该工具的实际可用性而言，处理具体语法会更方便。请注意，由于代数的加法运算符，因此在并集下关闭解析算法的特定选择是很重要的。图3说明了使用抽象语法和具体语法指定转换之间的区别。 图3（a）描绘了用于执行以下操作的语法的片段：Java的一个子集，通过根据运算符优先级将运算符分解为几个不同的级别来处理表达式的结合性和优先级（在编程语言语法中常见）;在这种情况下，从Exp和Exp 1一直到Exp 8有九个级别。现在假设我们要通过添加一个新语句来扩展Java的语法repeat-until，语法为：“repeat”Stm“until”“（“Exp“）”“;”。这样的结构可以很容易地转换成核心Java，方法是将其去糖化为带有否定条件的do-while。图3（b）显示了如何在抽象语法级别上使用抽象语法树（AST）来实现这一点转换参数写在尖括号中;例如，<1>和<2>（稍后解释 由于求反位于第八优先级（在Exp7中），用于指定求反条件表达式的AST片段必须将我们从Exp一直带到Exp7，添加求反“Exp7.neg（... ）“，然后添加括号“Exp8.par（. ）<“和第二个参数“2>“（包含要求反的原始表达式）。图3（c）指定了相同的转换，但在具体的在这一层次上，没有必要明确处理这种低层次的考虑，28J. 安德森角Brabrand/Electronic Notes in Theoretical Computer Science 253（2010）19<经验>经验成功><实验>实验林><实验>实验林>成功零解析XS−u→gar exp.zero>/exp>/exp>转型X−S→LT exp.var>/exp>解剖析XS−u→gar\s。\ z.z/exp>/exp>见图4。 转化过程。由parser处理。有趣的是，如果一种语言的语法是明确的，我们选择了一个规范的unparsing，我们可以可逆地在抽象的语法树和具体的语法程序串之间移动。由于我们有这样一个最近的歧义分析[3]，我们选择了基于具体句法的工具但是，转换也可以用抽象语法编写，如图3（b）所示。5.2底层技术图4描述了转换过程。Banana Algebra Tool目前基于XSugar [5]和XNUMX4，但该工具很容易修改为使用其他底层工具（只有代码生成受这些选择的影响我们使用XSugar来解析源语言的具体术语（例如，“（XSugar使用Earley算法的一个渴望变体，能够解析任何CFG，以及保守的歧义分析[ 3 ]，可以用来验证所有涉及的语言的无歧义性。然后，我们使用转换器来执行从源AST到目标AST的异化转换。最后，XSugar将AST解解析为目标语言的输出术语5.3其他执行问题我们发现允许使用正则表达式来指定词法结构是很方便的，这在解析器/扫描器工具中经常遇到但是，该工具目前认为这是一个原子终端层，无法转换。我们通过允许定义一个名为“$“的特殊空白终端来处理空白其语义是，空格散布在所有结果的右侧的所有终结符和非终结符对于嵌入式语言，我们已经对此进行了更细粒度的控制，但我们的工具目前不支持这一点。在未来，添加alpha转换的方法也会很有趣在语法规范之上进行静态语义6实例和评价该工具可用于任何语法导向的转换，可以表示为catamorphisms（包括Metafront [7]和4hhttp：www.w3.org/J. 安德森角Brabrand/Electronic Notes in Theoretical Computer Science 253（2010）1929{设l=“λ.l”$=[\n\t\r]*;在letln=“数字1”中ID=[a-z]+;inletxln2l=exp.var ：ID;（|ln->l[exp -> exp]exp.lam ：“\\”Id“。“经验;exp.zero=exp.app ：（“expexp“）;exp.succ='\s.& lt;1>“;}exp.pred=“<（1> \z.z）”;|）Inln2l+idx（l）(a) 语言：λ-微积分（标准的白色-空间定义：“[ \n\t\r]*“）。(b) 转换：λ-演算扩展与numeral核心λ-演算（cf.图1）。图五、香蕉代数示例程序：一种语言和一种转换。XSugar [5]）。这包括不同语言之间的翻译，语言转换和格式转换，但在这里，我们将重点关注介绍中的“四种场景”中的每一种的语言扩展不过，在此之前，我们想展示一个具体的示例程序。我们现在将重新讨论用数字扩展λ-演算的例子，我们以前看到的是一种变形（在3.1节中），后来看到的是一种一般的扩展模式（在图1中），激发了代数方法。图5（a）显示了作为香蕉代数语言常量的λ-演算（带有标准空格，定义为：“$ = [ \n\t\r]*“）。图5（b）定义了从用数字扩展的λ-演算到核心演算的转换（参见，图1）。首先，文件“lambda.l“的内容（我们假设它包含图5（a）中的常量）被加载并绑定到程序其余部分中的香蕉代数变量l。然后，在该程序中，ln被绑定到包含扩展名的语言（假设驻留在文件“logda-num.l“中）。在此之后，ln 2l被绑定到将数字扩展转换为核心λ-演算的常数转换。最后，这个常数变换被加到idx（l）上，这是λ -演算上的恒等变换。类似地，香蕉代数工具可以用来扩展Java，其中包含许多可以被脱糖到Java本身中的语法结构;例如，for-each控制结构、枚举声明、设计模式模板等等。这里，我们只给出一个简单的Java扩展示例;图3（c）中的repeat-until：letjava=“java.l”在重复信中={ Stm.重复：“重复”Stm“直到”“（“Exp“）”“;”}在letxrepeat2java=（|repeat->java[Stm -> Stm，Exp -> Exp]Stm.repeat ='do 1> while（<！（<2>））;' ;|）在repeat2java+idx（java）尽管Java语法很大（更雄心勃勃的是，香蕉代数工具可以用来将整个DSL嵌入到宿主语言中。 我们已经使用该工具将标准SQL结构嵌入到[4]语言中;例如，the “stm.select=一旦定义，语言和转换都可以添加，组合或其他。30J. 安德森角Brabrand/Electronic Notes in Theoretical Computer Science 253（2010）19或者放在一起。因此，程序员可以使用该工具来基本上定制他自己的宏扩展语言;例如，“（java \ while）+ sql“。依靠工具的存在，我们已经使用工具本身来向代数中添加更多的运算符。我们可以很容易地在语言和转换（根据核心代数定义）上使用覆盖运算符[[L1L2]]L<<为 （L1\L2）+L2[[X1X2]]X<<为 （X1\src（X2））+X2为了测试代数和增量开发方法，我们构建了一个完整的现有函数式语言该语言扩展了λ-演算的算术，列表，对，局部定义，算术方面的数字，布尔和对方面的有符号算术，局部定义方面的定点迭代器，算术和对方面的类型。整个语言使用245个代数运算符（即，58个常量语言，51个语言包含，28个语言添加，23个语言变量，17个常量转换，17个转换添加，14个转换包含，10个局部定义，9个恒等转换，8个组合，4个语言限制，4个转换变量和2个源提取）。整个变换简化为大小为4MB的恒定（建设性变质）变换。（关于这种转换的更多信息，我们参考[1]。7相关工作我们的工作与语法宏、源转换系统和异化（从范畴论的角度来看）有许多共同点和目标，下面将概述它们的关系宏[6，21]提供了一种单向扩展“主机语言”的方法，在该语言之上，宏系统是硬连线的通过语法宏的扩展对应于仅对图1的“步骤iii）”具有控制相比之下，我们的代数方法可以用来扩展任何语言或转换的语法;而不仅仅是在一个方向上-扩展可以通过添加、组合或其它先前定义的语言或变换的模块化组装来实现。单向扩展只是我们代数方法中增量定义的一种形式。关于可扩展语法的工作[9]改进了定义的可扩展性，提供了一种增量定义语法的方法。但是，它只支持三种通用语言操作：扩展、限制和更新。编译器生成器工具，如Eli [12]、Elan [2]、Eplogo/XT [8]、ASF+SDF [18]、TXL[10]、JastAdd [13]和Silver [22]都可以用于源到目标语言的转换。它们都比我们的工作有更大的野心，支持全规模编译器的规范，其中许多还包括静态和动态语义J. 安德森角Brabrand/Electronic Notes in Theoretical Computer Science 253（2010）1931作为图灵完全计算的AST的源语言，这显然排除了我们的安全保证水平尽管许多工具都支持模块化语言开发，但它们都没有在其语言和转换之上提供代数基于属性语法的系统（例如，Eli、JastAdd和Silver）可用于间接表达源到目标转换。这可以通过对源语言的AST进行图灵完备计算来实现，该计算以向下或向上的方式（通过合成和继承的属性）或其组合来计算目标语言的术语。相反，异化仅限于目标AST的向上诱导重组。我们的转换可以很容易地推广到也向下构造目标AST，只要允许异化接受目标类型化的AST参数（如[7]，第17页所详述）。这对应于变形（anamorphisms）和类态（hylo- morphisms）的概念，但会损害编译时消除复合（因为变形和类态一般不能融合成一个变换，没有中间步骤）。基于项重写的系统（例如，Elan、TXL、ASF+SDF和EASGO/XT）也可以用来间接表达源到目标的转换。然而，从语言S到T的转换必须被编码为对组合类型的术语进行重写：ST或S×T。虽然工具可以在语法上检查每个重写步骤是否遵守语法，但形式主义带来了三种无法在任何工具中静态验证的终止问题;转换可能：i）永远不会终止; ii）过早终止（使用未处理的源项）;以及iii）能够产生输出AST森林，这意味着程序员有责任确保最终结果是一个单一的输出项。为了帮助程序员实现这一点，重写系统通常对重写策略进行更好的控制为了发布强安全保证，特别是终止，我们明确牺牲了可表达性，因为异化不能执行图灵完全变换。然而，以前的工作使用建设性catamorphisms的句法转换（例如，Metafront [7]和XSugar [5]）表明它们具有良好的表达能力，适用于广泛的应用。当然，可以通过函数式编程的规范风格来模仿变形，可能通过从数据库自动合成的遍历函数来辅助[15]，或者通过组合子库[17]。然而，由于在通用背景下，它不能提供我们的安全保证水平，能够编译时分解合成（尽管函数技术森林砍伐/融合[20，11，19]在某些情况下可以用来实现类似的效果）。在范畴理论的背景下，存在着大量关于蜕变的工作[14，16].然而，这些都是理论框架，还没有变成支持语言和转换上的加法概念的实际工具实现，这在图1和许多示例的扩展模式中起着至关重要的作用。32J. 安德森角Brabrand/Electronic Notes in Theoretical Computer Science 253（2010）198结论代数方法通过16个运算符来描述一个简单的，增量的，模块化的方法，通过先前定义的语言和转换的代数组合来指定语法语言扩展。代数是该工具可用于：1）程序员用自己的宏扩展现有语言; 2）开发人员将DSL嵌入宿主语言; 3）编译器编写人员仅实现一个小的核心语言（并在外部指定其余部分）作为扩展）;以及4）开发人员和教师构建多层语言。香蕉代数工具是可用的-作为3，600行http://www.itu.dk/people/brabrand/banana-algebra/确认作者感谢Kevin Millikin、Mads Sig Ager、Per Graa、Kristian Støvring、AndersMøller、Michael Schwartzbach和Martin Sulzmann提供的有用意见和建议。引用[1] 雅各布·安德森和克劳斯·布拉布兰德。通过语言代数和转换的语法语言扩展国际电联技术报告。可查阅：http://www.itu.dk/people/brabrand/banana-algebra/，2008年。[2] P. Borovansky，C. Kirchner，H. Kirchner，P. Moreau，and C.林盖森Elan的概述。在第二国际机场。重写逻辑及其应用研讨会，第15卷，1998年。[3] Claus Brabrand，Robert Giegerich，and Anders Møller. 上下文无关文法的歧义分析。第12届自动机实施和应用国际会议，CIAA'07，2007年7月[4] Claus Brabrand ，Anders Møller，and Michael I.施瓦茨巴赫

下载后可阅读完整内容，剩余1页未读，立即下载