您好、欢迎来到现金彩票网!
当前位置:2019跑狗图高清彩图 > 先行指令站 >

构建自定义的语法分析器

发布时间:2019-07-07 18:03 来源:未知 编辑:admin

  developerWorks 中国 正在向 IBM Developer 过渡。 我们将为您呈现一个全新的界面和更新的主题领域,并一如既往地提供您希望获得的精彩内容。

  如果您在从事开发语法分析器或编译器的工作(实际上大多数人认为这种工作是魔术),那么您必须解决若干技术问题。最近,ANother Tool for Language Recognition (ANTLR) 作为用于创建语言语法分析器的首选工具,已获得了许多人的关注。本教程将深入地研究在创建自定义语法分析器时会遇到的一些典型问题,以及如何使用 ANTLR 来解决这些问题。

  在本教程中,您将了解如何在 ANTLR 的帮助下创建自定义语言语法分析器。此外,您将了解如何处理在编译器和语法分析器创建过程中出现的常见问题。

  关于 ANTLR,如果理解了某些事情的话,可以帮助更快地调试,并提供对该工具工作方式更完整的理解。有了此知识,您将能够设计更加智能化的语法分析解决方案。下面是您必须知道的两个基本的 ANTLR 基础信息。

  ANTLR 是一个 LL(k) 语法分析器——也就是说,它遵循自顶向下的语法分析算法,具有从左至右地分析输入流的先行分析k标记。如何决定 ANTLR 中的语法分析需要多少个先行标记呢?请考虑一个必须支持大于 () 和大于或等于 (=) 运算符的简单语法规则。在遇到输入流中的字符时,词法分析器(lexer)必须决定要为语法分析器创建哪一个标记。存在两种处理这种情况的方法:

  ANTLR 接受一个语法文件(通常为具有.g文件扩展名的文件),并生成C++或 Java 代码。随便浏览一下所生成的代码可以发现,ANTLR 同时为词法分析器和语法分析器创建了单独的类。每个语法规则现在实现为一个C++或 Java 方法,此方法是语法分析器类的一部分,并且每个词法标识符同样是词法分析器类的一个方法。考虑以下代码片段,其中针对单个语法规则和词法标识符说明了这一事实:

  将为上面的代码片段生成两个类:TParser和TLexer。生成的代码具有一个名为TParser::declaration的方法,此方法对应于语法规则声明;同样地,为词法规则SEMI生成了TLexer::mSEMI。下面查看一下为TLexer生成的代码:

  运行上面的示例,并检查所生成的源代码。在TLexer::mSEMI方法中,match例程特别重要。match的代码是在 ANTLR 源代码中预定义的,并且是CharScanner类的一部分,所生成的代码将从该类派生TLexer。这非常容易理解,它只是验证特定字符在输入流中的存在性。下面是来自 ANTLR 源代码的match的代码:

  (请注意此代码在不匹配的情况下引发的异常。稍后在讨论错误处理策略时将使用到此概念。)

  TParser::declaration的代码完全是自定义的。该代码对两种标记类型进行匹配,如果匹配结果是否定的,则引发异常。请注意,最初在词法分析器中定义的INT和ID对应于所生成的代码中类型为integer的标记。下面是语法分析器的match例程的代码。请注意,语法分析器中的LA(先行)方法查找标记类型,而不查找任何字符或字符流:

  这些代码片段对于确认您已经知道的知识也大有益处:在词法分析器级别,代码处理单独的字符,而在语法分析器级别,则要处理标记及其类型。您不必完全理解上面的代码在做什么,但是大致的概念有助于您了解 ANTLR 中的错误处理程序是如何工作的。

  在计算机程序中,源代码文件包含其它源代码或头文件是极其常见的现象。诸如C和C++等软件编程语言具有#include指令以包含其它文件;甚至诸如 Verilog 等硬件描述语言也具有include指令,起着相同的作用。

  相反,请注意语言标准并没有为include构造提供任何特殊支持:语言的语法始终建立在一个假设的基础上,即语法分析器会从词法分析器接收连续的标记流。这个假设使得编译器开发人员的工作变得非常艰巨。显然,在实际的语法分析之前,必须存在单独的预处理步骤,从而展开所包含文件的内容,然后再将展开的文件作为输入提供给词法分析器。所包含的文件也可能是嵌套的。例如,在C++中,您可以有一些包含某些头文件的 .cpp 文件,这些头文件又可能潜在地包含一些其他头文件——所有这些文件来自不同的文件夹。

  使用 ANTLR,不需要单独的预处理步骤。下面是作为潜在语法的一个非常小的C++代码子集。此代码只允许int和long声明以及#include指令。在为这个小子集提供语法文件之前,应该指出的是,您的语法可能与基于预处理的 flex/bison 或 lex/yacc(举例而言)的类似语法文件不同。更明确地说,您的语法将具有一个用于include指令的词法标记,并且会在遇到该指令时采取操作。清单 1显示了该基本语法文件。

  最简单的做法是创建词法分析器和语法分析器类TLexer和TParser的一个新副本,在遇到INCLUDE指令时,为词法分析器提供所包含的文件,然后将词法分析器信息传递给语法分析器。这里的逻辑非常简单:所包含文件的语法应该与当前正在进行语法分析的文件的语法相同(C头文件和源文件具有完全相同的巴克斯-诺尔范式 [BNF] 符号)。因此,只需创建一个分析所包含文件并将控制返回给当前语法分析器的新词法分析器-语法分析器组合,即可完成这项工作。这样还会自动处理嵌套的包含文件(即本身包含#include指令的包含文件)。

  清单 2中的代码是不言自明的。但是此代码存在一个问题。您能发现具体的问题吗?

  清单 2 中的代码工作正常,但问题在于,对于每个所包含的文件,都需要创建一个新的词法分析器-语法分析器对,这决不是对可用内存的高效利用。在最错综复杂的形式下,N个#include指令将在内存中产生N个TParser和TLexer副本,从而导致非常大的内存占用空间。幸运的是,存在一种在 ANTLR 中处理此问题的智能方法:使用内置的TokenStreamSelector类。可以参见清单 3中的代码。

  那么,这里发生了什么呢?与直接连接词法分析器和语法分析器不同,此代码将一个TokenStreamSelector类型的对象连接到语法分析器。相应地,使用词法分析器对象来对TokenStreamSelector对象进行了初始化。

  这一切说明了什么呢?语法分析器始终查找下一个标记,并且不管是谁提供的。相反,可以将多个词法分析器流连接到TokenStreamSelector类,并且始终可以使用被定义为TokenStreamSelector类的一部分的select方法来切换到所需的输入流。对于每个include指令,可以创建一个新的TLexer对象,并相应地切换输入流;在遇到流的文件结束 (EOF) 标志时,则切换回前一个流。清单 4显示了源代码。

  做出一些说明是适宜的,但在此之前,让我们首先分析一下该代码带来的影响。即使是在具有N个嵌套#include指令的最坏情况下,也仅具有N个TLexer副本和一个TParser副本。这种方法显著地节省了内存。

  语法分析器始终查找下一个标记以匹配语法规则,词法分析器一直提供某个标记,直到遇到输入流结束。在内部,ANTLR 类CharScanner(TLexer从其派生)和TokenStreamSelector都派生自TokenStream类,并且已定义了它们自己的nextToken方法版本,此方法不断从输入流中返回下一个标记。TParser类并不真正关心输入流,对输入流已切换的事实绝对毫无感觉,并不断调用关联的TokenStream对象(可以是TLexer或TokenStreamSelector)的nextToken方法。

  理解这一点之后,再看一下清单 4中的代码。首先,使用一个TokenStreamSelector对象来初始化语法分析器,该对象又使用一个创建用于分析第一个源文件的TLexer对象进行初始化。在遇到INCLUDE指令时,则创建一个新的Lexer对象来分析所包含的文件,将前一个TLexer(及其输入流)压入一个作为TokenStreamSelector对象的一部分来维护的堆栈中,并将新创建的TLexer连接到TokenStreamSelector以便提供下一个标记。(实际上,push方法执行此任务。)

  这个问题的最后一部分是定义为词法分析器一部分的uponEOF方法。实际上,如果观察所生成的 ANTLR 代码,您将看到自己实际上是在为TLexer类重新定义uponEOF方法,该方法在派生TLexer的CharScanner类中具有一个空方法体。当遇到输入流结束时,将从TLexer类的nextToken方法中调用此方法。(查看 ANTLR 生成的代码以更详细地了解这一点。)

  那么,uponEOF做什么呢?它只是在遇到当前输入流结束时,通过调用pop方法切换回前一个输入流。仅只是这样吗?不是:请记住,此方法是从词法分析器中调用的,语法分析器又调用词法分析器以提供下一个标记。因此,必须为TokenStreamSelector::nextToken做好安排,以从已切换的流中返回下一个标记。

  不需要对nextToken方法做任何事情;其职责只是为TLexer正确定义uponEOF方法,创建流选择器对象,并将其连接到语法分析器。此方法的美妙之处在于,上面的代码中的input现在是已切换的流,并且已经无缝地为语法分析器提供了下一个标记。

  TokenStreamSelector对象方案工作正常,但是您仍然要为每个include指令创建一个新的词法分析器。使用单个词法分析器-语法分析器组合完成同样的事情,从而使代码极其简洁紧凑,这是值得花一番功夫的。

  注意:这里描述的技术特定于 ANTLR Version 2.7.2。将来的 ANTLR 版本可能已经修改了内部数据结构,此方法将无效。但是,了解此方案将使您更好地掌握 ANTLR 的内部工作原理。始终可以调整此方法以适应将来的 ANTLR 工具生成。

  每个 ANTLR 词法分析器都维护用于文件名、当前行号、列号和输入流(派生自std::ifstream)的内部字段。要跨文件使用同一个词法分析器,必须拥有某种方法,以在遇到include指令时保存此数据,重置内部词法分析器字段,然后继续处理所包含的文件。在遇到所包含文件的 EOF 时,可以通过将先前保存的数据恢复到词法分析器来切换回前一个文件。显然,需要定义一个维护这四个字段的结构和这些结构的堆栈。还需要一个全局输入流指针,以跟踪当前输入流。下面是初始的代码:

  您仍然遗漏了一个重要的前提:语法分析器不知道流切换。必须做两件事情,以便让语法分析器即使在已切换流之后也能正常工作:

  标记的语法规则。需要某种方法来跳过此标记,并继续处理已切换的流中的下一个标记。

  当您遇到所包含的文件结束时,以对语法分析器不透明的方式切换回前一个流。您已经知道语法分析器仅知道词法分析器的

  方法,因此必须对其进行调整。在 ANTLR 生成的代码(已在前面讨论过)中,词法分析器类已经具有一个

  方法不是一个好主意,因为该方法在每次对语法文件运行 ANTLR 时被重写。最好直接从

  要解决问题 1,可以在INCLUDE的词法分析器规则中添加以下代码片段:

  此代码确保所生成的代码中的词法分析器nextToken方法不会将INCLUDE标记返回给语法分析器,并重新查看输入流以查找下一个标记。实际上,它跳过了INCLUDE标记。

  要解决问题 2,可以从现有的TLexer派生一个新类MLexer,然后相应地重写uponEOF和nextToken方法,如清单 6所示。

  还必须修改 main 例程。与创建一个TLexer对象不同,现在将创建一个MLexer类型的对象。源代码和语法文件的其余内容保持不变。清单 7显示了 main 例程。

  在良好的调试器中运行清单 7中的代码。特别是观察nextToken方法是如何工作的。

  错误处理无疑可视为业余和专业编译开发人员之间的关键区别。用户通常预期编译器分析整个输入流,而不是在第一次遇到用户代码中的错误时退出。对于编译器,这意味着必须在遇到某个错误标记时从错误中恢复,并且语法分析器必须保持接收标记,直到达到某个已知状态。

  ANTLR 具有若干内置的异常,以减轻程序员的负担。但在此之前,下面首先介绍基本形式的异常处理程序。

  该语法与C++异常处理策略相似。语法规则可以将异常作为整体来替代某条语法规则或带标签的语句。以这种方式设计异常处理策略的原因是非常容易理解的:生成的代码中的每条语法规则在生成的C++代码中实现为语法分析器类的一个方法。在每个这样的方法中,有一个实现异常处理功能的try...catch块;该代码是几乎逐字地从语法文件中复制过来的。

  缺省情况下,在 ANTLR 生成代码时,异常处理是启用的。但是如果希望创建自定义异常处理程序,您可以使用和扩展可用的异常类层次结构来实现。这意味着,在缺省情况下,生成的代码获得了try...catch块和在引发异常时处理异常所必需的代码。要禁用缺省的错误处理,可以将defaultErrorHandler=false;添加到语法分析器的options部分:

  请注意,无论defaultErrorHandler选项是否存在,都始终会生成针对 I/O 异常 (TokenStreamIOException) 的代码。如果defaultErrorHandler选项为 False,并且语法分析器中没有遵守任何错误处理策略,则会将异常一直传递回调用代码。这样就必须在调用例程中提供try...catch块,如下面的代码片段所示:

  关于 ANTLR 异常处理,要了解的第一件事情在于,异常处理机制并不仅限于语法分析器。词法分析器使用同样的异常处理方案,并且在本教程的前面,您充分地使用了TokenStreamRetryException。语法分析器及其语法规则使用RecognitionException和TokenStreamException类,而词法分析器则使用该异常的所有三种变体。下面几个部分将提供语法分析器在缺省模式下使用的两个最常用异常的基本描述。

  注意:假设 incl.h 在相同目录中存在并具有单个包含int x, z, y的行。

  与遇到分号(标记SEMI)不同,语法分析器在已处理err的标记以后,遇到了一个整数声明(来自词法分析器的INT标记)。这显然是标记不匹配的情况。相应地,您将获得以下 ANTLR 输出:

  通过在语法分析器中允许paraphrase选项,可以使上面的错误消息稍微详细一点。下面是重新编写后的SEMI的语法分析器规则:

  当语法分析器在对某条语法规则的当前替代规则发出调用并发现意外标记时,将引发antlr::RecognitionException::NoViableAltException异常。请注意,此异常与标记不匹配异常类似,它们都是在语法分析器中遇到意外的标记;然而,此异常是在该意外标记为一系列标记中的第一个标记时引发的,而不匹配异常则是在流中遇到任何意外标记时引发的。可以考虑前面讨论的错误输入的一种稍微变化的形式:

  在此情况下,语法分析器的startRule指令预期遇到一个INT或LONG类型的标记,但最终却遇到一个不属于其中任一种类型的标记。显然,不存在任何语法规则的可行替代规则;因此引发了NoViableAltException异常。输出的错误消息如下:

  同样,如果提供一个空文件作为输入,这也会导致引发NoViableAltException,因为在查找startRule中的替代规则时,不存在 EOF 标记的匹配项。这次输出的错误消息如下:

  由于词法分析器没有预期遇到#,因此引发了不匹配异常。类似如此的异常的错误消息如下:

  那么,当 ANTLR 在缺省方案中已经能够很好地处理异常的时候,为什么要为异常而费心呢?一个典型原因在于,与 ANTLR 提供的消息相比,您可能需要更加特定于工具的消息。例如,在分析语言和报告错误的时候,指出用户输入违反了语言标准的部分始终是个好主意。

  但是,为什么有时重写缺省方案有意义呢?要了解更微妙的原因,您必须观察生成的代码。使用清单 1和清单 2中的代码,观察前面从词法分析器中用于NoViableAltException的错误文件,及其在启用缺省 ANTLR 异常处理时的输出:

  您似乎没有获得任何有关a、b和c的声明的消息。要了解为什么是这种情况,可以查看为startRule生成的代码:

  最后,consumeUntil方法不断接收标记,直到到达 EOF。正是在这个标记接收过程中,词法分析器遇到了INCLUDE标记,从而又打印了x、z和y的声明。显然,在遇到err的标记以后,需要某种方法来恢复对输入流的语法检查。

  那么,您在这里做了什么呢?在接收错误标记以后,您不断查找int声明。当您找到一个该声明时,就重新运行startRule以再次分析输入流。通常,用户错误处理程序是这种策略的变体;这种策略的唯一目的是提供更详细的错误恢复。

  本教程介绍了 ANTLR Version 2.7.2 中的包含文件处理和错误处理。请注意,将来的 ANTLR 版本可能以不同的方式处理相同的问题;因而应该严格遵守所使用的 ANTLR 版本的文档。

http://deafbook.net/xianxingzhilingzhan/284.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有