ScalaBison解析器生成器：递归上升-下降解析工具文件研究摘要

理论计算机科学电子笔记253（2010）65-74www.elsevier.com/locate/entcs工具文件：ScalaBison递归上升-下降解析器生成器1约翰·博伊兰2 丹尼尔·斯皮瓦克2美国威斯康星州密尔沃基大学电子工程系摘要ScalaBison是一个解析器生成器，接受bison语法并在Scala中生成解析器。生成的解析器使用了“递归上升下降解析”的思想，即直接编码的广义左角解析。有趣的是，解析器是从bison创建的LALR（1）表中生成的，因此可以隐式地处理诸如优先级之类的扩展保留字：解析，递归上升下降解析，解析器生成器，scala1介绍递归上升下降解析是由Horspool [4]提出的。其思想是将LR解析的强大功能与LL解析中可用的小表大小和易于插入语义操作相结合。此外，生成的解析器可以被直接编码，因为控制是通过可执行代码来处理的，而不是间接地通过然后被解释的表来处理的。在本节中，我们将更详细地描述这些概念。1.1左角句法分析Demers [3]引入了“广义左角解析”，它（大致）结合了LL和LR解析技术的优点。当使用自顶向下或预测解析（LL）来解析给定非终结符的产出时，需要解析器识别（左递归文法不能1部分由国家科学基金会（CCF-0702635）支持的工作。 这里表达的观点不一定是国家科学基金会或美国政府的观点2电子邮件：{boyland，dspiewak}@ uwm.edu1571-0661 © 2010 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2010.08.03266J. Boyland，D.Spiewak/Electronic Notes in Theoretical Computer Science 253（2010）65因为可能需要无限的前视来确定应该选择哪个生产。另一方面，自底向上（LR）解析器可以跟踪多个产生式，只要在我们到达任何产生式的末尾时解决了歧义。直观地说，LL解析器要求在产生式的开始就做出决定，而LR可以等到结束。因此，LR理论允许确定性地解析更多数量的语法LR的强大功能是由解析器的更大复杂性、生成的更大表以及语法中语义动作发生的限制决定的。最后一项有点转移注意力，因为现代解析器生成器，如基于LR（1）（或其简化LALR（1））的bison，允许语义动作出现在LL（1）解析器生成器可能出现的任何地方，假设语法确实是LL（1）。3.对于今天的计算机来说，表的尺寸越大问题然而，解析器的复杂性越大，就意味着解析器生成器的用户越难理解发生了什么现代LL解析器生成器通过允许语法编写者包括代码来帮助消除歧义，克服了LL解析的一些限制这是可能的，因为自顶向下解析技术是直观的。缺点是语法开始增加模糊其清晰性的实现细节。相反，bison，特别是它的优先级扩展，使得语法能够以一种干净的、声明式的风格编写广义左角分析背后的直觉是，在LR分析期间，很少有产生式必须等到最后才能解决歧义。通常，将被使用的产品在其结束之前很久就被确定了。因此，在左角解析中，一旦识别出正确的产生式，解析器就从自底向上转换到自顶向下。与直接LR解析相比，这有两个好处：表更小，预测更容易生成有用的错误消息-如果预测了一个终端，那么在遇到不同终端的情况下，很容易在错误消息中指出预期执行左角分析的关键技术是确定语法中每个产生式的识别点，即解决歧义的点Horspool将识别点概括为自由位置，这些位置是可以插入语义动作的点。识别点总是自由位置，但反之亦然，因为在某些不寻常的情况下[4]，非自由位置出现在较早的自由位置之后。在本文中，我们选择最早的自由位置，没有后续的非自由位置作为识别点。1.2递归上升下降分析递归下降解析是预测解析的一种众所周知的实现技术解析器直接编码为一组相互递归的函数，每个函数解析一个特定的非终结符。递归上升解析使用递归函数直接编码底部-[3J. Boyland，D.Spiewak/Electronic Notes in Theoretical Computer Science 253（2010）6567up解析器。这组相互递归的函数由每个LR解析状态的一个函数组成。Pennello [8]给出了一个直接编码的LR解析器的汇编语言实现。这个概念似乎是后来由Roberts[10]和Kruseman Aretz [5]独立发明的。直接编码可以导致更快的解析，原因与编译通常导致比解释更快的执行相同。Horspool [4]解释说，递归上升解析并不被认为是实用的，因为代码大小很大（大表）和技术的不直观性。递归上升解析器对于手工编写来说太乏味了，并且生成的解析器不适合人工注入语义例程。广义左角分析Horspool [4]表明，其优点是real-解析速度几乎是yacc的三倍，并且仍然可以手动编辑语义动作。1.3优先级和其他扩展bison工具（及其前身yacc）包括声明终结符的优先级和结合性的能力，使带有运算符的语法具有更小的表。该技术提供了一种方法来解决移位-归约和归约冲突，而无需添加新的状态。任何剩余的解析表冲突都以可重复的方式解决。（这两种解析都不总是有益的--结果解析器可能会拒绝语法生成的字符串。）最后，bison包括一个错误符号，用于检查错误恢复。这些扩展一起改变了解析问题的理论性质因此，任何试图复制bison2ScalaBison的架构ScalaBison背后的关键设计决策是将表构造委托给bison。 这使我们能够匹配bison的语法和语义（包括其解析表消歧技术），而不需要复制功能。另一方面，这个决定是有限制的，因为我们不能任意创建新的解析状态-我们只能重用（和适应！）就是野牛给我们的此外，它还意味着我们的工具与解析表的特定文本表示相关联。幸运的是，bison我们已经能够使用bison版本1.875以及2.3。ScalaBison执行以下任务：(i) 实现了bison解析器生成器;(ii) 读入语法并从bison生成LALR（1）表;(iii) 为每一个产品确定一个识别点;(iv) 识别明确的非终结符集：在某个产生式的识别点之后出现的非终结符68J. Boyland，D.Spiewak/Electronic Notes in Theoretical Computer Science 253（2010）65(v) 对于每一个明确的非终结符，识别野牛状态以适应左角（LC）状态，并执行适应;(vi) 写出解析器样板;(vii) 为每个终端（匹配或错误）和明确的非终端（在LC状态开始递归上升解析(viii) 编写一个函数，使用前面的每个符号的函数，(ix) 为每个LC状态写一个递归上升函数在本文中，我们不加评论地跳过了这些任务中的大部分。有趣的步骤是步骤iii和步骤v。然而，我们简要地注意到，由于生成元添加的人工产生式SJ→S$，起始符号S将始终在步骤iv2.1识别点产生式的识别点是通过在每个产生式中找到最左边的位置来确定的，该位置是空闲的，并且所有后续位置都是空闲的。回想一下，“自由”位置是可以插入语义动作而不引入解析冲突的位置。在最坏的情况下，识别点是在生产结束后。本文对Purdom和Brown [9]的算法2进行了改进，使之能确定自由位置。已发布的算法对每个状态和每个潜在的先行检查的图形进行计算，检查每个相关项是否主导给定先行符号的动作。相反，我们对每个LALR（1）状态使用单个图。我们检查每一项，在这个图中，它是否支配它可以到达的每个解析动作如果bison使用优先和结合声明来解决某些移位-归约冲突，以支持归约（而不是移位）。所谓的"非结合性"声明甚至会引入解析错误。因此，通过适当的优先级声明，解析为（a-b）-c，a-B-Ce ==f== g这是一个parse error。通常，二元运算符的识别点直接在运算符之前，但是解析器的递归下降部分需要是上下文敏感的，以便以b开始的表达式立即终止，而不是像通常那样错误地扩展到因此，为了正确性，我们强制将任何使用优先级的产生式的识别点放在最后。每当移位-归约冲突以归约的方式解决时（在bison中，这只会发生在优先级上），都需要这种安全措施。J. Boyland，D.Spiewak/Electronic Notes in Theoretical Computer Science 253（2010）65697 class_decl：CLASS TYPEID形式化超类“{”feature_list。 “}”12 feature_list：feature_list. 特征';'13|feature_list. 错误“;”14|feature_list. NATIVE ';'15|feature_list. “{'block'}”16 功能：。opt_override DEF格式“：”TYPEID“=”expr17|. opt_override DEF PROTECTID formals '：' TYPEID NATIVE18| .变量“类型ID”=“表达式”19| .VAR PROTECTID '：' NATIVE20 opt_override：. 覆盖21|. /* 为空*/错误移位，并转到状态49本地移 位 ， 并 转 到 状 态 50 超 控 移位，并转到状态51VAR移位，并转到状态52'{'移位，然后转到状态53“}”移位，并转到状态54DEF使用规则21（opt_override）功能转到状态55opt_override转到状态56Fig. 1. 由bison生成的（增强的）LALR状态。2.2生成LC状态LC解析器使用LR解析技术，直到它已经确定使用哪个产生式，如当它到达识别点时所确定的。在这一点上，产品是“宣布”和生产的其余部分是使用LL技术解析。最迟，在LR解析器将减少它的时候（在最后）宣布产生。因此，LC解析器没有reduce操作，而是一旦宣布产生式，解析器依次预测每个剩余的符号。终结符的处理只需检查下一个输入符号是否匹配。非终结符是通过调用专门为解析这个非终结符而生成的例程来处理的。在这里，我们回到LR风格的解析，因此我们需要一个解析状态来解析这个非终结符。在Horspool之后，我们生成这个解析状态，用于围绕由单个项N →► ·N表示 一个新的人工非终结子N.这个标记用于确保该项目将被视为一个类似的人工非终结符和项被用于LR解析器生成的开始状态（单独）;当到达这个生成的结尾时，解析器考虑一个“接受”动作。对于LC解析器，为了避免自己确定解析动作，我们找到了一个包含项N0→α·Nβ的现有LALR状态。然后，我们调整LALR状态的操作（见下文）以获得LC状态的操作。在创建LC状态的过程中，我们可能需要创建新的状态来接收shift/goto操作。该过程继续，直到不需要创建新的LC状态。然后，我们继续处理下一个需要自己的解析状态的非终结符（每个图1示出了其动作适于图2所示的LC状态的示例LALR状态。对于LC状态，我们从所示的五项开始。 然后，我们70J. Boyland，D.Spiewak/Electronic Notes in Theoretical Computer Science 253（2010）65feature_list#：|-feature_list.12 feature_list：feature_list. 特征';'13|feature_list. 错误“;”14|feature_list. NATIVE ';'15|feature_list. “{'block'}”误差转到状态14原生公告规则14覆盖公告规则12VAR公告规则12我的天公告规则15“}”接受功能列表DEF宣布规则12$default accept feature_list图二、通过调整图1中的LALR状态形成的LC状态1.一、只要LC包括一个项目，其中NJ紧接在点之后，只要识别点出现在项目中的点之后，则NJ→α这最后一个条件将该过程与传统的LR状态生成区分开来。在图2中，没有添加新的项，因为规则（产生式）12、14和15的项都在它们的识别点上，并且规则13的项在点之后具有人为的非终结符在将点移动到适当的符号上之后，移位动作导致（潜在地）新的LC状态，再次假设这不会将点移动经过识别点。否则，对于一个移位操作，我们需要确定此时什么样的“announce”操作是合适的（见下文）。在图2中，唯一保留的shift/goto是用于错误的。当从LALR状态调整reduce操作时，我们还需要确定什么样的announce动作是适当的-它并不总是LALR状态要减少的那个，因为相应的项目可能不处于LC状态。因此，对于经过识别点的shift操作（例如OVERRIDE）和reduce操作（例如DEF），我们都需要确定是否应该执行announce操作。我们通过跟踪与动作对应的项来找到它是如何被添加到LALR状态的。对于OVERRIDE，我们跟踪在LALR状态关闭期间从规则16和17的项（依次来自规则12的项的关闭）发生的规则20的项的移位操作最后一项处于LC状态，因此我们对该输入使用“announce rule 12”操作。对VAR的移位操作给出了相同的结论。NATIVE和“{”上的移位动作通过该过程的更简单应用分别映射到“announce rule14”和“announce rule 15”动作。“}”的移位操作导致不同的结果。当我们追溯它时，我们得到了规则7的项，它是LALR状态的核心项，但在LC状态中不存在。因此，不会为“}”生成任何通告操作. 我们回到下面这个案例对于DEF上的reduce操作，我们将该操作追溯到规则16J. Boyland，D.Spiewak/Electronic Notes in Theoretical Computer Science 253（2010）6571private def yystate13（yyarg1：Features）：Int= { var yygoto： Int= 0;尝试{yycur匹配{caseYYCHAR（'}'）=>yygoto=2;yynt=YYNTfeature_list（yyarg1）;case NATIVE（）=> yygoto =1;yynt = YYNTfeature_list（yyrule14（yyarg1））caseYYCHAR（'{'）=>yygoto=1;yynt=YYNTfeature_list（yyrule15（yyarg1））case DEF（）=> yygoto =1;yynt = YYNTfeature_list（yyrule12（yyarg1））case OVERRIDE（）=> yygoto =1; yynt = YYNTfeature_list（yyrule12（yyarg1））case VAR（）=> yygoto =1; yynt = YYNTfeature_list（yyrule12（yyarg1））案例_=>yygoto = 2; yynt = YYNTfeature_list（yyarg1）;}} catch {case YYError（s）=> yynt = YYNTerror（s）;}while（yygoto == 0）{ yynt match {case YYNTerror（s）=> yyerror（s）yypanic（{ t：YYToken=>tmatch{caseYYCHAR（';'）=>truecase_ => false}}）于戈托return（）;case _：YYNTfeature_list => return 0;}}yygoto-1}图三. 从图中生成LC状态的Scala代码。二、/** 识别点后递归下降解析器*feature_list：feature_list。 特征';'*/private def yyrule12（yyarg1： Features）：Features= {var yyresult： Features= null;val yyarg2： Feature= parse_feature（）;parse_YYCHAR（';'）;{ yyresult = yyarg1 + yyarg2; }yyresult}图四、规则12的识别功能和17，并因此返回到规则12，并因此生成DEF的如果LC状态包含人工项N→N·（如示例中所示，其中N是feature_list），则我们添加默认操作“接受”非终结符N.此默认操作也用于之前未定义的任何操作（与“}”的操作一样）。虽然这种适应需要一些工作，通过使用bison图3显示了为图2中的LC状态生成的Scala代码。try块用于处理解析错误（因为状态可以处理伪非终结符错误）。我们通过将返回值放在字段yynt中并返回仍必须弹出的帧数（yygoto）来72J. Boyland，D.Spiewak/Electronic Notes in Theoretical Computer Science 253（2010）65def parse_feature（）：Feature={ yystate17（）;yynt匹配{case YYNT feature（yy）=> yycase YYNTerror（s）=> throw new YYError（s）}}图五、 非终结符的示例分析例程图4显示了规则12的识别功能（预测解析例程）。当实现一个“announce”动作时调用这个函数（如图2所示）3）。它包括语义动作：在本例中，从{$$=$1 +$2;}翻译而来。生成函数的最终类型是开始递归下降的函数解析给定的非终结符。图5显示了“feature”非终结符的解析函数这个例程是从图4中的代码调用的。这样的函数不是私有的，因此可以由与生成的解析器接口的代码使用。生成的解析器有一个到扫描器的简单接口：解析器通过传递一个返回标记的迭代器3相关工作使用LL或（LA）LR技术的解析器生成器的数量很大。生成递归上升解析器的工具较少[6，2，11]，据我们所知，只有Horspool以前写过递归上升下降解析器生成器。Scala标准库中包含的文本解析的主要机制是解析器组合子[7]。解析器组合子是Scala中的一个嵌入式DSL可执行代码直接由Scala编译器生成，不需要外部工具（如ScalaBison）来处理语法描述。在一个非常高的层次上，解析器组合子是LL（*）解析的一种表示，而不使用表。相反，输入由解析器使用，解析器根据是否或者输入没有被成功解析。 一般来说，组合子使用回溯这对效率有负面影响。任意复杂度的文法可以通过组成更小的解析器来表示。4评价递归上升解析器的一个常见问题是，大量的状态会导致代码大小很大 事实上，Veldema [11]正是出于这个原因决定不使用纯粹的直接编码解析器，而是选择了一种可以被视为表驱动的方法。 另一方面，Bhamidipaty和Proebsting [2]发现，使用goto语句而不是递归例程的直接编码（递归上升解析器）生成的解析器只有yacc的两倍大小。递归J. Boyland，D.Spiewak/Electronic Notes in Theoretical Computer Science 253（2010）6573发生器编译尺寸（K）good.cl时间（毫秒）空间（MB）large.cl时间（毫秒）空间（MB）组合子35054 3.1275 3.3ScalaBison200十七点二36 2.1海狸70八点二十九点五表1将ScalaBison与其他生成器进行比较。上升下降解析被认为是为了缓解大小问题，事实上，我们发现状态的数量明显减少了：对于大量使用LR特征的语法来说，状态的数量减少了大约40%。例如，Java1.1中发布的LALR（1）语法（其中可选元素被扩展为将一个结果分成两个，导致语法具有350个结果）在bison中产生621个状态，但在ScalaBison中只有378个状态。我们还测试了一个Cool方言的语法，它大量使用了优先声明（67个结果）：bison有149个状态，ScalaBison有100个状态。状态的减少是值得欢迎的，但可能还不足以使递归上升-下降对那些被递归上升所排斥的人有吸引力。Cool生成的解析器仍然超过100K字节的Scala，而Java 1.1超过600K字节。通过比较，bison生成的解析器分别是53 K和120 K的C源代码;bison在压缩表方面做得很好，而直接编码的解析器为了衡量性能，我们将ScalaBison Cool解析器与使用解析器组合子的一个这种比较并不我们还将ScalaBison与Beaver（beaver.sourceforge.net）进行了比较，后者生成了最快的基于LALR（1）JVM的解析器。表1显示了所有三个生成器针对Cool输入文件（good.cl）实现的Cool解析器的测试结果，该文件由大约3，100个标记组成，每个标记都执行语法的生成。large.cl文件只是重复这个文件十次。第一列显示编译后的代码大小。“空间”列显示运行期间的最大内存使用量（“高水位线”）。所有测试均使用MacBook Pro，2.4Ghz Core 2 Duo，4 GB DDR3内存，使用Apple的JDK 1.5.0 16和Scala 2.7.3. final进行。每个测试运行12次，最好和最差的结果下降，其余10次平均。每次测试之间都会触发垃圾收集Beaver生成的代码明显更快。部分差异是由于ScalaBison的数据包括运行扫描器，这大约花费了报告时间的一半，而（不同的）扫描器只花费了Beaver少得多的时间的三分之一。然而，即使从解析时间中减去扫描时间，Beaver一个因素是ScalaBison使用74J. Boyland，D.Spiewak/Electronic Notes in Theoretical Computer Science 253（2010）65match子句（参见图3），Scala编译器使用线性搜索实现，而Beaver使用（常量时间）数组查找。5结论ScalaBison是Scala的一个实用的解析器生成器，它基于递归的上升下降技术，接受bison格式的输入文件。这实现了直接编码的好处，同时从纯递归上升解决方案减少了代码大小。它使用bisonScalaBison生成的解析器使用比bison生成的解析器更多的错误信息。解析速度和空间使用都比Scala内置的解析器组合子好得多，但比最快的基于JVM的SDG引用[1] 亚历山大·艾肯Cool：一个用于教学编译器构造的便携式项目。 ACM SIGPLAN Notices，31（7）：19[2] Achyutram Bhamidipaty和Todd A. Proebsting。非常快的YACC兼容的解析器（用于很少的电子邮件）。软件实践与经验，2（28）：181[3] 艾伦·德默斯广义左角分析。第四届ACM程序设计语言原理研讨会会议记录，美国加利福尼亚州洛杉矶，第170-182页。ACM Press，New York，January 1977.[4] R.奈杰尔·霍斯博。 递归上升下降分析。 Journal of Computer Languages，18（1），1993.[5] F. E. J. Kruseman Aretz.递归上升分析器。Information Processing Letters，29（4）：201-206，1988.[6] 你不是莱尔玛的人。非确定性递归加速分析。在计算语言学协会欧洲分会的文件中，第63-68页。计算语言学协会，美国新泽西州莫里斯敦，1991年。[7] 阿德里安·摩尔斯，弗兰克·皮森斯，马丁·奥德斯基。Scala中的解析器组合子。技术报告CW491，计算机科学系，K.U.Leuven，2008年2月[8] 托马斯·J·佩内洛。 非常快速的LR解析。 ACM SIGPLAN通告，21（7）：145[9] Paul Purdom和Cynthia A.布朗语义例程和LR（k）解析器。Acta Informatica，14：299[10] G. H.罗伯茨递归上升：LR对递归下降的模拟。ACM SIGPLAN通告，23（8）：23[11] 罗纳德·维德玛Jade，一个递归的LALR（1）解析器生成器。 技术报告，荷兰阿姆斯特丹自由大学，2001年。