解析K定义的方法及其在计算机科学中的应用

可在www.sciencedirect.com在线获取理论计算机科学电子笔记304（2014）151-166www.elsevier.com/locate/entcs解析K定义RaduMereudaughta101GheorgheGrigora102计算机科学学院Alexandru IoanCuza UniversityIaBagrisi，Romania摘要本文介绍了我们在解析K定义的方法。这个问题的困难是由K框架的性质给出的，在K框架中，用户可以通过以自然的方式在K代码中插入具体语法来定义语言的操作语义。我们的主要贡献是展示了如何在K-框架的背景下使用SDF和消歧机制保留字：句法分析，K-框架，语法，歧义，消歧1引言K[14]是一个基于重写的语义定义框架，适用于定义编程语言和演算的语义，以及可执行环境中的类型系统或形式分析工具。拥有语言的可执行语义定义的一个主要优点是能够将其与分析工具一起使用来验证程序。MatchC [21]（正在开发中）给出了一个说明性的例子，这是一个基于Matching Logic [13]的工具，它使用C子集的K定义。K中的定义包括配置、语法声明、计算和规则。配置以XML风格将重写系统状态组织在单元中，可以嵌套的标记单元格。语法声明指定了语言的形式。通过在重写系统中嵌入原始语言的“计算意义”来获得计算。K（重写）规则通过明确它们读取、写入或不关心术语的哪一部分来概括常规重写规则[14]。1电子邮件：radu. info.uaic.ro2电子邮件地址：grigoras@info.uaic.rohttp://dx.doi.org/10.1016/j.entcs.2014.05.0081571-0661/© 2014 Elsevier B. V.保留所有权利。152R. 我是你的朋友G Grigoras/ElectronicNotesinTheoreticalComputerScience304（2014）151=K-Maude [15]，目前支持K的工具，被证明是非常可扩展的，适用于现实世界的编程语言，如Scheme [17]，Verilog [16]，Java 1.4 [8]和C [7]（其他正在进行中）。然而，由于K-Maude依赖于Maude解析器来解析K个定义，因此在某些情况下，新的定义会引入歧义。此外，为了在Maude中翻译，这些定义需要在语法上正确;因此，最好有一个能够处理K个定义的解析器。这样一个解析器的设计是一个复杂的任务，因为K的定义是相当复杂的，将K个语法结构与来自所定义语言的语法片段经过几次实验后，我们很快排除了在解析器之前使用扫描器的解析器，因为它们不具备解析相互嵌入的不同风格程序的通用性。解决方案以SDF [9]及其无扫描广义解析器的形式出现。我们为不同的目的生成了几个解析器：一个用于从定义中提取语法声明，另一个用于解析程序，最后一个用于解析语义规则（这是最复杂的，因为它必须同时处理两种语言的构造函数）。本文共分六节，第二节介绍了一个典型的例子来说明我们要解决的主要问题。在第3节中，我们提出了一个抽象的解决方案，作为处理嵌入其他语言的语言中的歧义的一种方式。第4节提供了一个更深入的看法所使用的技术，并解释了一些细节，导致选择的方法。第5节介绍了一些具有类似解决方案的工具。2解析K定义的挑战为了理解解析K定义的问题，让我们看一个例子：模块示例语法Exp：：= Id|Int|Exp“=”Exp语法Stm：：= Exp“;”|Stm配置T> k>.K/k> env>.Map/env>/T>rule [store]：I V=>V：IntI：Id|->（=>V）端模块每个K定义都由模块组成，模块以关键字“模块”和唯一的名称（按照惯例都是大写字母）开始每个模块可以包含三种类型的句子：语法声明，配置和重写规则。每个句子将以其相应的关键字开头，并限制在句子中使用关键字（如第4.1节所述）。在这种情况下，我们考虑一种小型语言，它接受标识符和整数的加法和赋值为了给重写系统提供结构，我们将声明一个由两<个单元组成的配置：用于计算结构的单元和用于绑定R. 我是你的朋友G Grigoras/ElectronicNotesinTheoreticalComputerScience304（2014）151153变量到值。我们用空的（身份）元素初始化它们。一般来说，细胞可以有K中使用的五个主要语法类别（或排序）之一：K、Bag、List、Set和Map。排序K被认为是特殊的，因为它可以从定义的语言中扩展新的语法结构，并且它主要用于匹配计算。上述句法结构的操作语义由K规则给出。它们描述了当这些构造被执行时，配置是如何改变的。例如，赋值运算符的语义由上面给出的“store”规则给出下划线表示匿名元变量。我们使用不同的字体样式来标记和展示这个简单的例子包括属于不同语言的语法结构。正常部分表示K的语法，粗体部分突出显示元变量声明，唯一实际上属于已定义语言语法的部分是装箱部分（这里由“=”给出）。赋值的左边和右边是元变量，范围在所定义语言的两个特定语法类别上。变量I和V一旦被声明，就在整个规则的上下文中保持其含义、排序和绑定。它们可以在其可见性范围内的任何地方声明。K工具的后端设计为接受表示为抽象语法树（AST）集合的K定义。AST是解析文本后得到的解析树的折叠表示使用AST使处理输入变得容易得多，因为在解析过程中消除了不必要的信息（例如，空白和注释--它们对语言没有语义意义）。为了获得AST，我们需要一个能够解析上述定义的工具，解决歧义，推断每个构造的类型，并将它们转换为纯K定义（使用AST），如下所示：规则（单元格（“k”，=>（=（IdVar（“I”），IntVar（“V”）），IntVar（“V”）），“k”），单元格（“env”，|->（IdVar（“I”），=>（IntVar（“_”），IntVar（“V”），“env”））所有的变量现在都应该有一个类型，匿名变量应该有一个推断的类型，运算符的优先级应该被解析，所有的语言结构都应该是一个可以被重写引擎处理的前缀形式K-tool [15]的当前实现有一个前端，它将语言的带注释的BNF定义转换为Maude[4]模块，稍后用于解析K重写规则。这种解决方案通常会导致二义性，因为mix fix运算符和需要满足的预正则性有序的排序最大的失败是缺乏对解决Maude提供的歧义和冲突154R. 我是你的朋友G Grigoras/ElectronicNotesinTheoreticalComputerScience304（2014）151语法安诺语义生成解析器消歧切向展平解析RO（D）GO（D）GO（L）G1（K）G1（D）纯KASTASF解析器G1（L）Fig. 1. 前端工作流程（摘要）3解析技术K定义由三个主要部分组成：所讨论语言的语法声明-在图1中表示为G0（L），扩展排序K的额外语法构造- G0（D）-以及给出语义的重写规则- R0（D）。我们提出的解决方案的工作流程如图1所示。Level 0代表K代码，是编译过程的入口点之一。这是第一个处理步骤的输入：基本语法分析，提取定义语言的语法，即G0（L）。为了生成完整定义的解析器，G1（L）和G1（D）将由G1（K）组成-初始K定义没有任何语法结构。在K语法中嵌入语言结构是在排序K的帮助下完成的。事实上，这就是该技术名称的来源。排序为K的项表示从解析角度来看是语言构造的计算。对于重写规则，我们还需要元变量，它可以代替语法结构中的非终结符。在实践中，把所有这些放在一起是很棘手的，因为我们希望让用户更容易访问具体的语法，但也要保持定义的合理性所选择的方法类似于ASF+SDF [19]中使用的方法，因为我们添加了新的转换来连接K的语法和用户给定的语法。对于用户定义的每个非终结符X，我们添加两个新的乘积：X->K和K->X。这种技术将允许在类型系统通常不允许的上下文中匹配语法构造的灵活性。这个想法是允许用户编写规则，就像他/她编写AST表示一样，但是使用具体语法（mix fix形式）的便利性，在某些情况下，这比编写构造函数更直观。关于如何解决这个问题的详细信息，请参见第4.2节。因为我们在运行时结合两种语法（没有用户干预），所以在解析时可能会出现一些问题。因此，需要后处理器来解决其中的一些问题。在这种情况下，我们将对上下文无关语言使用消歧过滤器（从一系列可能的句子分析中选择的过程，根据某些标准最合适的一个[6]）。 这种类型 消歧，基于后期类型检查，已在[3]中应用，其中R. 我是你的朋友G Grigoras/ElectronicNotesinTheoreticalComputerScience304（2014）151155作者从引用-取消引用机制中使用更多的信息歧义语法的消歧有很多方法，从简单的句法标准到语义标准[6]。某些类别的消歧规则对于声明式过滤器[1]（结合性，优先级）是足够的，但在K定义的情况下，需要一种更复杂的方法，使用声明式方法和使用语义信息的自定义过程。下面提出的消歧过滤器的每个主要步骤代表了可以在AST中找到的一种类型的歧义。以下规则应可以被视为重写规则，在这个意义上，如果左模式在AST中的某个地方匹配，那么如果满足where条件，则令≤表示子排序关系，其中语法A：：= B（或B-> A，SDF）意味着B≤A。在这种情况下，我们将认为关系是传递的关门了(i) 更新上下文相关信息(a) 收集配置信息，然后在每个规则中为每个单元格应用消歧过滤器：统治amb（T：{S1，.， Sn}）单胞菌统治amb（T：{Si|Si≤t yp e（ce ll）}）单电池换句话说，如果在解析后在单元格规则中找到构造函数，并且其排序不小于或等于配置中声明的类型，则该构造函数将被删除。(b) 收集变量声明，然后更新变量每次出现的类型：其中变量Var具有类型S'如果用户在规则中的某个地方输入了变量Var，则该变量在规则中的每个位置都将具有相同的类型。类型不一致将在接下来的步骤中解决(ii) 第二类型检查(a) 选择类型良好的术语（自上而下的类型检查）：term（...，amb（T：{S1，.，S n}），. ）term（...，amb（T：{S i|S1 ≤ originalSort}），. ）这个过滤器是从上到下应用的，它的行为方式与普通解析器类似，即它删除那些应该被删除156R. 我是你的朋友G Grigoras/ElectronicNotesinTheoreticalComputerScience304（2014）151原始语法中的类型系统。这里的区别在于，它仅在至少还有一个项时才应用该规则(b) 选择最佳拟合（自底向上类型检查）：amb（T 1，.， 其中T = bestF it（T1，.， Tn）自底向上应用，并选择具有最少类型冲突的树（在下一段中更详细地(c) 选择最大排序的其他歧义：amb（T：{S1，.，S n}）nT：max（{S 1，...，S n}）由于类型系统不是活动的，因此某些重载运算符可能会为每个声明生成二义性。此规则仅保留该运算符的最常规排序。第一部分将在4.4节中更详细地描述，但第二个类型检查在继续之前需要更多的解释。因为我们引入了新的产生式，将K产生式与用户定义的语法联系起来，所以可能会出现一些异常，这些异常通常会由类型系统处理。在这一步，还有更多关于元变量和单元格类型的信息。为了更清楚地说明这个问题，让我们看一个例子。首先，我们声明两个定义多态操作符的产生语法Int：：= Int“+”Int语法String：：= String“+”String为了与K语言建立联系，我们添加了以下结构：语法K：：= Int|字符串语法Int：：= K语法String：：=K此修改将允许在任何上下文中插入重写和元变量。这也意味着像下面这样的规则规则A：Int +Int B：Int=> A + B将生成以下抽象树森林（具有多个有效结果的AST）：int（int A，Int B，int C）;int A，int B（Int+Int（A，B），String+String（A，B）））R. 我是你的朋友G Grigoras/ElectronicNotesinTheoreticalComputerScience304（2014）151157在步骤（ii）-（a）中描述的bestFit规则使用来自原始文法的关于每个产生式规则的非终结符的类型的信息来消除可能发生的一些异常函数bestFit返回具有最少类型冲突的分支在上面的例子中，在我们更新上下文敏感信息（变量类型）的第一步之后，我们可以安全地删除String+String结果，因为在原始语法中Int™String（不处于子排序关系中）。4基于SDF的实现在这里，我们描述了上述解决方案的实现，该解决方案使用SDF [9]及其Spoofax [5]中的无扫描通用解析器。目前正在开发一个原型，它显示出有希望的结果。SDF使用此工具的一个显著优点是能够生成能够识别用户指定的语言的Eclipse插件。这涉及到语法着色、错误报告、代码折叠，以及查看解析步骤后的解析树。这使我们能够尝试几种可能非常接近预期最终结果的解决方案。由于解析K定义的解决方案在很大程度上取决于执行实际解析的工具，因此本章将详细描述编译的不同阶段如何与SDF和Cockgo工具交互[5]。每个定义的输入都是一个扩展名为“.k”的文本文件。这被传递到一个主解析器，它将定义的不同组成部分分成语法声明、配置和规则。在这一点上，只有关于语法声明的信息是完全可用的，因为它们对每个定义都有一个标准形式。配置和规则仍然存储为字符串，并将在稍后的步骤中进行处理。具体细节见第4.1节。第4.2节包含了选择这些技术的动机，并展示了如何从上一步的结果开始生成一个新的解析器。 它由两部分组成，因为生成了两种语法：一种用于定义中描述的编程语言，另一种用于定义本身，需要对用户指定的形式进行一些修改在第4.4节中，介绍了调用在前一步生成的解析器和消除抽象树森林歧义所需的基础设施。 到 为了能够消除歧义，需要一些关于配置中单元排序的额外信息，即子排序列表和来自原始语法的语法构造158R. 我是你的朋友G Grigoras/ElectronicNotesinTheoreticalComputerScience304（2014）1514.1基础解析对于编译的第一步，输入文件被发送到解析器，解析器将文本分成模块。K模块将包含以下形式的句子列表KModule：：=“module”ModName“是” KSentence*“endmodule”KSentence：：=“rule”隐藏+|“configuration”隐藏+|“语法”{SConstruct 1“>"}+SConstruct1：：={SConstruct 2“|“}+SConstruct2：：=String|ID隐藏：：=~[\n\r\t\]+-（“endmodule”|“规则”|“句法”|“配置”）这个语法足以进行初始解析，并且结果应该是无二义性的，因为语言构造被解析为气泡项以及K语法声明。这个想法来自Maude和ASF+SDF [2]，它们也在用户指定的具体语法上实现了术语重写。气泡词以一个关键字（这里我们有“rule”和“configuration”）开始，并继续匹配单词，直到找到下一个关键字。在SDF中，这是很自然的，因为解析器是无扫描的。在上面的语法中，Hidden构造匹配任何非空白标记，关键字除外。Moonen在[18]中使用这种技术从解析器没有完全定义的文本中提取代码。在K的情况下，我们将水（可能包括用户给定语言的语法的规则内容）与岛（分隔句子的关键字）隔离开来。K语法声明是SDF语法的重新排列，以更接近BNF样式。它从关键字语法开始，一个标识符指定了结构的排序和一个产生式规则列表生产规则列表可以用“>”分隔，以指定左侧的生产比右侧的生产具有更高的在一个优先级块中，可以指定由“|“并将被视为具有同等优先权。语法产生式和块可以使用典型的SDF消歧过滤器进行注释：左、右或非消歧。 也喜欢和避免非-可以提供图案以获得额外的可伸缩性。初级解析的最后一步是生成K中间语言（KIL）。这是一个通用的和简单的格式来表示K定义。在本例中，我们使用XML格式（稍后在编译过程中还有一个Java版本），因为它一个简单的访问者，用Spectrogo编写，匹配每一个语法结构，可以用更可读和更通用的格式打印抽象表示。为了能够为用户提供更好的错误消息，每个术语还用具有“（起始行，起始列，结束行，结束列）"形式的位置信息来注释。下一个模块示例：模块MOD-NAMER. 我是你的朋友G Grigoras/ElectronicNotesinTheoreticalComputerScience304（2014）151159语法Exp：：= Exp“*”Exp[left]>左：Exp“+”Exp[左]| Exp“-”Exp [left]> Exp“=”Exp[right]规则A+ B=> A+Int B端模块将转变为：<模块值=“MOD名称”loc="（1，0，8，4）"><语法loc="（2，1，6，37）"><优先级loc="（2，16，2，33）"><生产位置="（2，16，2，33）"><终端值="*”loc="（2，20，2，22）”/><注释>...

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