属性文法语言处理器的Prolog原型框架

理论计算机科学电子笔记164（2006）19-36www.elsevier.com/locate/entcs一个用于属性文法语言处理器Jos'eLuisSierra1AlfredoFern'andez-Valmayor2，3Dpto. SistemasInforma′ti cosyP rogramacio′nFac. 为了我的爱。西班牙马德里康普顿斯大学摘要在本文中，我们描述了PAG（属性语法原型），一个框架，用于从基于属性语法的规范构建Prolog原型，我们已经开发了用于支持语言处理器入门课程中的快速原型活动。这个框架适用于具有任意底层上下文无关语法的一般非循环属性语法，包括嵌入在Prolog中的规范语言，该语言与引用的课程中解释的属性语法符号非常相似，并让学生以直接的方式从他们的规范中产生可理解的原型。关键词：属性文法，语言原型框架，语言处理器教育，Prolog1引言属性文法已经被认为是非常有价值的工件，可以将编程语言的设计和其处理器的构建结合在一起[13][15][20]。我们还采用了属性语法的方法作为我们的教学策略的基础上，在马德里大学（西班牙）的研究生水平的介绍课程的语言处理器。 在本课程中，我们鼓励明确区分源语言的规范及其翻译，以及处理器的后续实现。在指定过程中，学生被迫使用属性语法，随后1电子邮件：jlsierra@sip.ucm.es2电子邮件：alfredo@sip.ucm.es3西班牙科学和技术委员会（TIC 2002 -04067-C 03 -02、TIN 2004 -08367-C 02 -02和TIN 2005 -08788-C 04-01）部分支持了这项工作。1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.10.00220J.L. Sierra，A.Fernán-Valmayor/Electronic Notes in Theoretical Computer Science 164（2006）19应用系统化的技术，转向一次通过的自上而下或自下而上的实现。我们还促进了中间原型阶段，学生在Prolog中编写一个原型，该原型密切反映了规范。 这一阶段建立在技术基础（例如，让学生验证和改进规范的质量）和教学基础（例如，激励学生们不得不做一些不愉快的事情）。我们选择Prolog而不是更具体的环境[14][20]是因为我们的学生将逻辑编程作为核心本科主题进行学习，因此他们熟悉 使用这种语言开发中小型编程项目。多年来，我们一直在推广Prolog虽然DCG是一种非常有用的机制，可以让学生理解语法指导翻译技术背后的主要概念，甚至是逻辑编程背后的许多基本概念，但我们也发现了一些实际限制：缺乏对左递归规范的支持，以及需要了解语义方程的求值顺序。为了克服这些限制，我们开发了PAG（属性语法的Pro-totyping），这是一个Prolog框架，用于从基于属性语法的规范中快速原型化语言处理器。PAG包括一种规范语言，它与我们在课程中使用的属性语法的通常符号非常相似。通用解析算法与简单的属性评估技术相结合，使PAG能够接受具有任意（甚至是模糊的）底层上下文无关语法的通用非循环属性语法，这是成功的原型活动所必需的本文的结构如下。在第2节中，我们描述了PAG出现的教学背景。在第3节中，我们概述了PAG。在第4节中，我们描述了它的实现。最后，第5节提出了一些结论和今后的工作方向。2教学环境在这一节中，我们描述了目前工作的教学背景，集中在我们的课程语言处理器在康普顿斯大学。款所2.1 我们简要地概述了这门课程的主要方面。在2.2小节中，我们描述了我们如何使用Prolog的DCG来解决快速原型设计问题，以及它们在教学上的优点和缺点。 最后，在第2.3小节中，我们建立了一个原型框架，保留的优点，克服了基于DCG的方法的局限性，我们证明了PAG的设计和建设的基础上，这些要求的初始要求。2.1语言处理器语言处理器是康普顿斯大学计算机科学研究生学位的一门两学期的课程。我们的主要教学目标是让学生学习计算机语言的系统描述和处理器的系统开发方法。因此，在本课程中，我们教J.L. Sierra，A.Fernán-Valmayor/Electronic Notes in Theoretical Computer Science 164（2006）1921如何系统地指定计算机语言及其处理器，以及如何使用不同的标准技术系统地实现这些处理器：手工编码和自动生成的预测递归自顶向下翻译器，自动生成的表驱动自顶向下翻译器，以及自动生成的LR自底向上翻译器[2][8]。在我们的教学方法中，我们采用基于问题的学习方法，学生以小组为单位，逐步解决规范和构造类Pascal语言的解释性编译器所带来的问题。 为了促进语言及其处理器的维护和发展，我们提倡明确区分规范和实现。 如前所述，在规范化过程中使用的中心描述形式主义是基于属性语法的，尽管我们也使用其他补充资源（例如，正则表达式和/或有限自动机用于描述词汇方面，以及半形式化算法规范用于描述目标机器及其支持的对象语言）。在本课程的教学过程中，我们注意到学生们不愿意接受将具体化和实现分开的便利性。为了使他们相信这种关注点分离的好处，我们采取了以下策略：• 我们使语言处理器构造中通常遵循的增量式开发过程模型显式化。事实上，我们首先提出了一个最小的语言（两个原始类型，表达式语言，涉及不同的优先级和关联规则，变量和赋值语句的声明的基本操作符的处理器的实现）。一旦学生构建了这个处理器，我们提出了基本语言的连续扩展：控制语句，用户定义类型和递归子程序。• 我们需要几个替代的实现。最小语言的处理器最初是手工编码为预测递归后代翻译器。一旦我们向学生介绍了更高级的实现技术，他们就必须根据介绍的技术重构翻译器，使用合适的特定于域的支持工具。此外，他们将连续扩展的语言建议，无论是在手工编码的处理器，cessor或通过使用测试的工具之一• 我们引入快速原型活动。虽然增量开发和替代实现对于理解精心准备的规范在开发过程中的价值是有用的，但我们已经意识到，它们不足以说服学生相信它们的好处。事实上，看到优秀的学生被要做的工作淹没，专注于编程任务而放弃具体活动并不罕见。这种情况已经通过快速原型化得到了很大程度的缓解. 事实上，这项活动是高度激励学生，因为他们能够在开发过程的早期阶段就获得一个运行的处理器。因此，学生们觉得他们在专业化过程中做的工作是有价值的，22J.L. Sierra，A.Fernán-Valmayor/Electronic Notes in Theoretical Computer Science 164（2006）19（一）exp：：= exp+ termexp0.v = exp1.v + term.vexp：：= termexp.v= term.vterm：：=numterm.v = num.vterm：：=（ exp）项v =实验v（b）第（1）款exp（Vo）--> term（V1），rexp（V1，Vo）.rexp（Vho，Vo）--> [+]，term（V1），{Vh1is Vho+V1}，rexp（Vh1，Vo）. rexp（V，V）-->[].term（V）-->[num（V）]。term（V）-->Fig. 1. (a)一个非常简单的属性文法;（b）从（a）得到的基于DCG的原型。 左递归已经被消除，并且已经选择了用于语义方程的显式求值顺序他们专注于这项活动。这件事在整个过程中产生了非常积极的影响。下一小节集中讨论我们教学方法中的快速原型。2.2使用定义子句文法的快速原型Prolog DCG在很大程度上被认为是原型语言翻译器的有价值的工件[5][24][25]。我们也意识到这一事实，作为我们教学经验的一部分。事实上，如前所述，我们采用DCG作为基本的原型技术已经有好几年了，因为我们的学生在本科教育中有很好的Prolog工作经验。这使我们能够介绍的技术作为语法糖的直接Prolog编码的翻译模式 在一两个一小时的课堂上。正如我们在使用该技术时所意识到的，我们的学生发现，DCG的使用对于理解语言翻译背后的主要概念非常有价值。DCG比属性语法更具体，也帮助他们中的许多人更好地理解更抽象的基于属性语法的规范背后的操作机制。此外，我们惊喜地发现DCG如何帮助我们的一些学生更好地理解逻辑编程的一些更重要的特征：非确定性执行和使用统一来处理不完整的结构[24]。尽管有这些优点，该方法也表现出一些限制，正如引言中所揭示的那样。Prolog此外，通常的DCG风格促进分析过程中的属性评估，这迫使学生意识到语义方程的评估顺序。因此，基于属性语法的规范的主要精神被打破了。实施例2.1在图1中，我们举例说明了DCG在构建亲-J.L. Sierra，A.Fernán-Valmayor/Electronic Notes in Theoretical Computer Science 164（2006）1923基于属性语法的类型。请注意，为了将规范转换为适合原型化的形式，学生必须进行一个类似于将属性语法转换为面向自顶向下递归下降实现的语法指导的翻译模式的尝试。暴露的局限性可能会让普通学生感到沮丧，从而使他/她无法接受一般属性语法作为思考编程语言设计和实现的好方法。事实上，我们已经意识到，许多学生专注于产生在底层语法中避免左递归的规范，这可以很容易地转换为基于DCG的原型类型，但在某些情况下，这是相当不自然的，不适合产生某些类型的实现（例如，基于LR翻译器）。2.3一个更好的原型替代方案在原型设计过程中使用DCG检测到的局限性使我们考虑替代方法。在对合适替代品的初始要求中，我们确定了以下内容：• 简单性要求。 所选方法应保持DCG的简单性。它应该很容易被我们的学生吸收，对目前的课程安排的影响应该最小化。理想情况下，这种方法应该提供一种非常简单的形式，接近我们课程中用于属性语法的符号（参见图1a中这种符号的示例• 语法自由要求。该方法应该能够处理任意上下文无关语法。• 语义自由要求。该方法应处理一般的非循环属性文法。事实上，在我们的入门课程中，我们没有处理循环属性语法的可能性，我们认为循环是一个错误的条件。• 可理解性要求。生成的原型应该很容易理解的学生，谁应该能够跟踪他们的行为时，需要的。• 部署要求。支持工具应便于携带和安装。此外，它应该是模块化的，易于集成到基于网络的学习场景中，如[22]，以及基于学习对象范式的学习场景[21][23]，因为我们正在密集使用电子学习解决方案，以便将我们的教学方法顺利迁移到即将到来的欧洲高等教育空间[7]。在寻找满足所有这些要求的合适解决方案时，我们考虑了以下替代方案：• 使用像Elegant [11]或ALE [4]这样的编程语言，这些语言是从属性语法形式主义中派生出来的，或者与之密切相关。然而，这种替代方案显然违反了简单性的要求，因为我们必须花相当多的时间向学生教授新语言24J.L. Sierra，A.Fernán-Valmayor/Electronic Notes in Theoretical Computer Science 164（2006）19• 使用现有的基于属性语法的环境，如FNC-2 [12]，Eli [9]鸡尾酒[10]其中一些，如LISA [17]被认为特别适合教育目的[18]。然而，这种环境通常被认为是开发工具，而不是原型开发工具。它们通常集成用于上下文无关文法的确定性类（例如LL（1）、LALR（1）等）的解析器生成器， 这违反了句法自由的要求。此外，它们还面向生成高效的静态属性赋值器，这违反了语义自由的要求，更重要的是，违反了可理解性的要求（尽管可理解性可以通过使用适当的GUI支持来增强，如LISA [18]）。最后，这些系统将规范语言与强大的功能（例如属性模式，多重继承，模板规则等）集成在一起。虽然这些功能在开发过程中非常有价值，但它们违反了我们教育环境中的简单性要求此外，所有这些第三方替代品也可能使部署在基于Web的学习场景中比我们自己的工具更困难。当我们完成了这项探索而没有找到完美的候选人时，我们决定进行PAG的设计和建造本文的其余部分描述了由此产生的框架的技术3原型框架PAG从属性语法规范和所需语义函数的适当Prolog实现中产生工作原型。 在本节中，我们将概述框架。在3.1小节中，我们描述了PAG中规格的结构。在3.2小节中，我们描述了在原型设计过程中如何使用框架。3.1PAG中的质量标准PAG中的规范由两部分组成：• 属性文法的具体化。这种规范是在Prolog中给出的-嵌入域特定语言，非常类似于语言处理器构造的典型入门课程中使用的属性语法的基本符号。• 语义功能的定义。这个定义可以独立于属性语法，并将语义函数的签名与用于计算它们的Prolog目标PAG属性语法规范语言的语法如图2所示。这种语法嵌入在Prolog中，具有引入用户定义运算符的常用功能，其特点如下：• 非终结符必须使用nt/3谓词声明。第一个论点是符号本身。第二个参数表示继承的属性，而第三个参数声明合成的属性。J.L. Sierra，A.Fernán-Valmayor/Electronic Notes in Theoretical Computer Science 164（2006）1925规范：：=符号公理（规则）+Symbols：：=（|t‘(’）+的Axiom：：=Rule：：=head-nt正文：：= [ ]|symbol（，symbol）* Equations：：= Equation（，Equation）*Equation：：= Attribute=定义Attribute：：= att-name of symbol图二. 规范语言的定义。• 可以使用t/2谓词声明终结符。第一个参数是终端名称，而第二个参数是一个包含词法属性的列表。注意，没有词法属性的终端不需要声明。• 语法的公理是用公理/1谓词来区分的。• 附加到语法符号的属性使用of运算符来引用。当一个产品中出现多个符号时，可以指示出现编号（默认情况下，它是第一个）。• 语法规则是用：：=运算符构建的。λ用空列表[]指定，就像在DCG中一样。有了这些规则，还可以附加一组语义方程，这些方程使用=运算符指定• 语义等式的左侧必须是属性引用。 语义等式的右边可以是任意的Prolog项，它通常包含对其他属性的引用。 该术语将被解释为 用于计算属性值的表达式例3.1在图3中，我们展示了一个基于DESK的简单计算器语言的属性语法，DESK是在[20]中介绍的示例语言。这种语言还使我们能够将常量绑定到值，并在绑定作用域中使用这些常量。属性语法将合适的值与每个表达式相关联。除了指定属性语法之外，还需要为计算属性值时使用的语义函数提供定义。PAG为此建立了defun/2钩子。在这个谓词中，第一个参数必须是其函子标识函数名的项，并且其参数与函数输入相关联。defun/2的第二个参数与函数result相关联。在其定义中，相应子句的主体将函数与结果的Prolog计算联系起来。默认情况下，所有声明的函数都是严格的（即在应用函数之前，它们在语义方程中的参数将被评估）。这个默认行为可以通过区分函数签名和nonstrict/1钩子来改变。在这种情况下，必须在定义中定制评价战略。最后，任何未声明的语义函数都将被解释为声明为defun（F，F），因此被解释为26J.L. Sierra，A.Fernán-Valmayor/Electronic Notes in Theoretical Computer Science 164（2006）19nt（prog，[]，[val]）。nt（exp，[envh]，[val]）。nt（fact，[envh]，[val]）.nt（constPart，[]，[env]）。nt（constDefs，[]，[env]）。nt（constDef，[envh]，[env]）。t（num，[val]）。t（id，[lex]）。公理（prog）。prog：：= exp，constPart，val of prog =val of exp，exp的envh = constPart的env。exp：：= exp，+，fact，val of exp（1）=val of exp（2）+valoffact， envh of exp（2）=envh of exp（1），事实的envh= exp（1）的envh。exp：：=事实，val of exp= val offact，envh of fact= envh of exp。fact：：= id，val of fact = valueOf（lex of id，envh offact）. fact：：= num，val of fact = val of num。constPart：：=其中，constDefs，env of constPart= env of constDefs。constPart：：=[]，constPart的env= emptyEnv。constDefs：：= constDefs，env of constDefs（1）= env ofconstDef，envh of constDef = env ofconstDefs（2）.constDefs：：= constDef，env of constDefs = env of constDef，envh of constDef = emptyEnv。constDef：：=id，=，exp，env ofconstDef=makeEnv（envh of constDef，lex ofid， val ofexp），envh of exp = envh of constDef.图三. PAG属性语法。长期建设者。 PAG在序言文件中定义了几个效用函数，可以 每种规格都要装上defun（X+Y，R）：-R是X+Y。defun（emptyEnv，[]）. defun（makeEnv（Env，Id，Val），[（Id，Val））|Env]）。defun（valueOf（Id，Env），Val）：-member（（Id，Val），Env），！.图四、图3的属性语法的语义功能的定义。例3.2在图4中，我们包括了图3的语法中使用的语义功能的定义。+算术函数已经在序言中定义了，我们只是为了说明的目的而包含它。emptyEnv、mkEnv和valueOf函数用于管理将变量绑定到其值的简单环境。3.2使用PAG进行PAG允许学生自动处理前面小节中介绍的规范以生成原型。PAG能够以简单的方式处理具有任意底层上下文无关语法的一般非循环属性文法，J.L. Sierra，A.Fernán-Valmayor/Electronic Notes in Theoretical Computer Science 164（2006）1927路上了生成的原型结构如图5所示，其特点如下：图五. 使用PAG构建的原型结构。• 解析器将标记序列解析成解析树。• 语义表达式的构建器遍历这些树，并将合适的语义表达式与每个节点中的每个属性相关联。语义表达式是语义函数签名的基础项，它们将用于计算属性值。• 评估器组件执行语义表达式的评估。实际上，它只需要计算附加到解析树根请注意，属性的计算进一步分为两个独立的阶段。第一个步骤，可以被认为是求解语义方程的替换步骤，由语义表达式的构建者执行。在第二阶段，计算器实际上对结果表达式进行计算。另外，请注意，一个句子可以被解析成几个解析树（这将是歧义语法的情况）。在这些情况下，原型将非确定性地产生几个结果。这些原型可以通过使用以下PAG预定义组件4从规范自动生成：• 解析内核。该组件包含将句子解析为解析树所需的机制。• 评估内核。该组件用于评估与语义属性相关联的表达式。4从实现的角度来看，在本文的上下文中，组件由一组子句和可选的底层Prolog引擎的指令组成。28J.L. Sierra，A.Fernán-Valmayor/Electronic Notes in Theoretical Computer Science 164（2006）19• 发电机该组件将属性语法规范转换为生成最终原型所需的几个工作组件• 前奏。如前所述，这个组件定义了几个可以在不同规范中重用的语义函数。见图6。原型工作流程在PAG中进行。预定义的零部件将被阴影化。生成的零部件用虚线表示。用+表示子句集合的并集整个过程如图6所示，该图还突出显示了框架中的不同组件。这样，当学生指定原型，提供属性语法并定义所使用的语义函数时，这个过程就开始了。这些语义函数、prelude和求值核的联合产生原型的求值器。反过来，属性语法规范由生成器处理以产生：• 对底层上下文无关语法的描述，添加到解析内核后将生成解析器组件。• 最终原型的语义表达式的构建器• 一个将所有原型组件粘合在一起的驱动程序。 此驱动程序将让学生来运行原型。4实现原型框架PAG基于两个简单的原则，为学生提供原型设计过程中所需的表达自由：J.L. Sierra，A.Fernán-Valmayor/Electronic Notes in Theoretical Computer Science 164（2006）1929OO• 一方面，该框架能够处理任意上下文无关语法。这是通过在解析内核中使用Earley算法[ 6 ]的适当实现来实现的• 另一方面，系统使用一种简单的技术来处理任何非循环属性语法。通过解释Her-brand域中的语义功能（即通过将它们解释为术语构造器），获得了逻辑一遍属性语法（在[19]的意义上）。事实上，语义表达式的构建器可以被认为是这种语法的一次求值器。所产生的语义表达式随后由求值器求值。因此，代替交错解析、树遍历和求值，它们被保持为分离的过程。解析和评估的分离也在[3]中提出，其中lambda演算被用作语义表达式的符号，循环依赖被转换为lambda演算定点计算。它也在定义子句翻译语法（DCTG）[1]的上下文中提出，其中解析产生用Horn类语义规则装饰的解析树。PAG还分离了解析和树遍历，以支持任意上下文无关语法。此外，一个简单的技术是用来避免重新评估的共同子表达式的语义表达式产生。以下小节将探讨实现细节。4.1小节介绍了解析内核。第4.2小节描述了这个内核是如何在特定的语法中被特殊化的，以产生针对这些语法的解析器。4.3小节描述了语义表达的构建者所遵循的模式款4.4描述了评估内核的实现。最后，第4.5小节概述了生成器的实现4.1解析内核如前所述，解析内核基于Earley该算法适用于任意（甚至是模糊的）上下文无关的语法和句子 最坏情况下的时间复杂度为（n3），空间复杂度为（n2）。由于测试句子通常很小，这些开销是可以接受的。该算法简单直观，学生易于理解和跟踪，便于调试语法。 在下文中，我们简要地总结了算法的主要方面和我们的实现。Earley算法的核心概念项目是形式的对象，指示预期的情况，其中：(i) 解析器位于输入上的位置i(ii) 产生式X：：= αβ用于分析从位置j开始的输入片段。(iii) 一个α结构已经被识别出来，解析器正在等待一个β结构图中的规则7描述上下文无关文法的所有可能项30J.L. Sierra，A.Fernán-Valmayor/Electronic Notes in Theoretical Computer Science 164（2006）19init：1， 1，SJ：：=.S， []>∈IG<闭包：∈IG;;Y：：=γ∈PG∈IGshift：∈IG;;wi=a∈IGreduce：∈IG ;;∈IG∈IG见图7。规则表征集Earley的项目IG的上下文无关文法G的一一个句子。在这个特征化中，我们还用第四个分量丰富了项，以产生具有形式的对象。这里τ是对应于解析符号α的解析树的序列。解析树被表示为具有以下形式的项：t（root，[Child1，...，子k]）。这些规则的预期含义是：• init规则建立解析器初始化。在这个规则中，S表示原始文法因此，项1， 1，SJ：：=.S，[]>意味着解析器正在等待根据给定的语法识别整个输入<• 当等待非终结符时，闭包规则使得激活这个非终端的所有产品• 移位规则允许识别输入端上的端子• reduce规则允许所有等待非终结符的规则在以下情况下前进：该非终端的生产已经完成。形式为表示输入的完整解析，其中t是相应的解析树。注意，可以根据输入位置对项进行分组，以生成解析器列表。对于长度为n的输入，将有n+1个这样的列表。Earley• 通过应用init规则初始化第一个列表• 对每个列表中的项应用闭包和归约规则，直到达到平衡。• 通过应用移位规则移动到下一个列表此外，通过融合具有共同核心的项目（即具有相同的三个第一J.L. Sierra，A.Fernán-Valmayor/Electronic Notes in Theoretical Computer Science 164（2006）1931元素）合并为一个，并通过巧妙地使用指针来跟踪解析树，有可能克服基于图7规则的简单实现的潜在指数复杂性。5 此外，我们使用前瞻信息 以实现效率的进一步改进。4.2专门化解析内核如前一节所述，要为具体语法生成解析器，必须将该语法的适当描述添加到解析内核。这一说明包括：• 语法的公理。 这用公理/1谓词表示。• 对每一个产品的描述这适用于prod/3同品种器械。prod/3的第一个参数是生产的唯一标识符。第二个论点是生产头。第三个论点是生产主体中符号的顺序。这些符号被封装在一个带有body函子的项中，以使在常数时间内访问参数成为可能。空短语λ用主体常数表示。生成的解析器对标记列表进行操作。虽然可以将词法属性附加到这些标记上，将它们表示为术语，但在移位过程中只考虑它们的函子。示例4.1图8a显示了图3中与解析内核一起使用的底层上下文无关语法的表示。 这些事实的结合并且解析内核产生解析器，如图8所示。这个解析器可以应用于句子，如图8b所示，以便产生具有图中所示的格式8c.4.3语义表达式语义表达式的构建器在解析树上操作，并充分利用逻辑编程中的统一机制，在单个自上而下、从左到右的遍历过程中自动解决属性之间的依赖关系。如前所述，它们可以被认为是非循环属性语法的求值器的直接实现，其中所有的语义函数都被解释为术语构造器。这些组件的结构按照以下共同模式进行：• 每个非终结符产生一个谓词。这个谓词的最后一个参数对应于解析树。其他参数对应于语义属性。• 非终结符的谓词由每个语法规则的子句定义。身体是由下面的右侧生产5考虑grammarli k e A：：=λ|aA |Aa withanaéve implemente ntation.32J.L. Sierra，A.Fernán-Valmayor/Electronic Notes in Theoretical Computer Science 164（2006）19见图8。(a)图3中用于解析内核的底层上下文无关语法的描述;（b）将由结果解析器处理的句子;（c）与该句子相关联的单个解析树的列表。• 主体中的每个非终结符都被转换为对相应谓词的调用。在这个调用中，最后一个参数被绑定到解析树中相应的子元素。此外，新的变量引入每个se-mantic属性。• 通过将相应的子项绑定到合适的术语来翻译每个终端，每个词汇属性都有一个新的变量• 每个复制方程a of s=aJof sJ被转换为X=Y，其中X是a of s的变量，Y是aJofsJ的变量。• 任何其他s=t的方程a都可以转换为X=#（，tJ）。X是与s的a相关联的变量，在t中，所有对属性的引用都被相应的变量替换，从而产生tJ。此外，一个新的变量与结果项相关联。这个变量称为备份变量，它将用于避免重复的重新计算，如下一小节所示生成的构建器以深度优先、从左到右的方式遍历解析树，将属性变量绑定到它们可能不完整的语义表达式。J.L. Sierra，A.Fernán-Valmayor/Electronic Notes in Theoretical Computer Science 164（2006）1933实际上，当与具有其他属性的右依赖性的属性相关联的变量被绑定时，与这样的属性相关联的变量保持未绑定，直到到达它们为止。然后统一将免费填补漏洞。该模式适用于一般的非循环属性语法。prog（A，t（prog，[B，C]））：-exp（D，E，B），constPart（F，C），A=E，D=F.exp（A，B，t（exp，[C，D，E]））：-exp（F，G，C），D=+，fact（H，I， E），B=#（J， G+I），F=A，H=A.exp（A，B，t（exp，[C]））：-fact（D，E，C），B=E，D=A.fact（A，B，t（fact，[C]））：-C=id（D），B= #（E，valueOf（D，A））。fact（A，B，t（fact，[C]））：-C=num（D），B=D。constPart（A，t（constPart，[B，C]））：-B=其中，constDefs（D，C），A=D。constPart（A，t（constPart，[]））：-A=#（B，emptyEnv）.constDefs（A，t（constDefs，[B，C，D]））：-constDefs（E，B），C=constDefs（A，t（constDefs，[B]））：-constDef（C，D，B），A=D，C= #（E，emptyEnv）.constDef（A，B，t（constDef，[C，D，E]））：-C=id（F），D=（=），exp（G，H，E），B=#（I， makeEnv（A，F，H）），G=A。见图9。用于图3中的语法的语义表达的构建器，例如它在PAG中自动生成。例4.2图9显示了PAG根据图4中的规范生成的语义表达式的生成器。3 .第三章。4.4评价核心其代码如图10所示的求值内核以应用顺序对语义执行进行求值，除了那些不严格的函数（对于它们，参数被传递给函数而不被求值，允许定制任何其他合适的求值策略）。内核在定义时调用语义函数，或者使用函子作为项构造函数。这个过程中唯一棘手的方面是使用备份变量来避免重新计算表达式中重复的术语。实际上，当计算形式为#（V，E）的表达式时• 如果V是自由的，则表达式E实际上被求值，并且V被绑定到结果值。• 如果没有，则使用备份值例4.3在图4中， 11prog的val属性的语义表达式并且对于输入[ id（x），+，id（x），其中，id（x），=，num（5）]示出。注意，在这个表达式中，用于查找x值的子表达式是重复的。然而，每个重复的表达式只计算一次，因为所有重复的表达式共享相同的备份变量。还应注意，图中所示的术语11是相应结构的外部化，可以通过共享公共子结构来34J.L. Sierra，A.Fernán-Valmayor/Electronic Notes in Theoretical Computer Science 164（2006）19eval（#（Val，Exp），Val）：-var（Val），！，eval（Exp，Val）.eval（#（Val，_），Val）：-！.eval（Exp，Val）：-nonstrict（Exp），！，doResult（Exp，Val）.eval（Exp，Val）：-Exp =.. [F| Args]，evalArgs（Args，VArgs），Funcall =..[F| VArgs]，doResult（Funcall，Val）.evalArgs（[]，[]）. evalArgs（[Exp| Exps]，[Val| Vals]）：-eval（Exp，Val），evalArgs（Exps，Vals）.doResult（Funcall，Val）：- defun（Funcall，Val），！.doResult（Funcall，Funcall）.见图10。 评估内核。#（A，#（B，valueOf（x，#（C，makeEnv（#（D，emptyEnv），（x，5）+#（E，valueOf（x，#（C，makeEnv（#（D，emptyEnv），x，5）见图11。具有重复子表达式的语义表达式。4.5发电机生成器处理属性语法规范以产生上下文无关的语法描述、语义表达式的构建器和驱动器。语法描述和解析内核产生解析器，解析器连接到引用驱动程序中的构建器和评估器规范中的所有元素，包括规则，都被生成器视为Prolog事实。事实上，通过正确定义：：=和of运算符，规范语言的语法很容易嵌入到Prolog中。通过使用在许多Prolog实现中发现的静态元编程设施，可以将gener- ator与Prolog系统集成。这让学生可以直接将PAG规范加载到Prolog引擎中5结论和今后的工作在本文中，我们提出了PAG，在Prolog语言处理器的快速原型的框架。该框架旨在支持语言处理器入门课程学生的学习过程让他们测试他们的规格。 该框架能够处理gen-以可理解的方式在任意（可能是模糊的）上下文无关语法上实现所有非循环属性语法，这是所提到的应用上下文中的主要要求。为了处理任意语法，EarleyJ.L. Sierra，A.Fernán-Valmayor/Electronic Notes in Theoretical Computer Science 164（2006）1935采用一般的非循环属性文法是通过首先将语义函数解释为术语构造器来管理的。然后，考虑语义功能的实际定义，对所产生的语义表达式进行定义性评估。所引用的关注点分离所产生的开销在原型环境中是可以接受的，在原型环境中，对于普通学生来说，技术的简单性和可理解性先于效率的考虑目前，我们正在使用基于语义方面组合的简单模块化工具扩展PAG，如[13]中所建议的。这与我们的教学方法是一致的，因为我们引入了完整属性语法的不同观点：一个用于符号表的构建，另一个用于检查源语言的上下文约束，第三个用于处理翻译问题。我们也在考虑扩展PAG来处理循环属性文法。这个扩展是面向我们的博士生。在线学习课程，我们在不同的在线学习规范中提出的标记语言处理中推广使用语言处理器技术（例如，见[16]）。其基本思想是使用循环Prolog术语来管理循环定义。有了这个，我们希望为属于几个学科的学生提供一个比基于定点计算的知识要求更低的选择[3]。我们亦计划在系统中加入特定领域的视觉追踪功能。 作为未来的工作，我们希望在计算语言学的入门课程中使用PAG。我们还希望利用模块化的方法来建立一个完整的学习场景的基础上的学习对象的范例和支持部署在我们大学的基于Web的电子学习系统引用[1] 艾布拉姆森，H。Dahl，V，[2] Aho，A.塞西河Ullman，J. D，[3] Arbab，B，Compiling Circular Attribute Grammars into Prolog，IBM Journal of Research andDevelopment30（3）（1986），294[4] 卡彭特湾Penn，G，[5] Clocksin，W.F. 梅利什角S，[6] Earley，J，An Efficient Context-free Parsing Algorithm，Communications of the ACM13（2）（1970），94-102.[7] “关注2004/2005年欧洲高等教育结构。博洛尼亚进程中的国家趋势[8] 费希尔角N.勒布朗河J. J，《制作一个餐具》，本杰明/卡明斯出版公司，1988年。[9] 格雷河W.