语言分析和歧义输入流工具的设计与分析

理论计算机科学电子笔记110（2004）75-96www.elsevier.com/locate/entcs语言分析和歧义输入流工具1作者：Andrew Begel，Susan L. 格雷厄姆2计算机科学部-摘要编程语言自动生成的词法分析器和语法分析器有着悠久的历史。尽管它们非常适合许多语言，但许多广泛使用的生成器，其中包括Flex和Bison，无法处理嵌入式语言、遗留语言和语音编程中出现的输入流歧义。我们开发了Blender，一个结合了词法分析器和解析器的生成器，使设计人员能够描述许多嵌入式语言的类，并处理口语输入和遗留语言中的歧义。我们在Harmonia框架中增强了增量词法分析和解析算法，以分析词法、句法和语义歧义。更好的语言描述和增强的分析相结合，为构建下一代语言分析工具提供了一个强大的平台。保留字： GLR，嵌入式语言，Harmonia，语音编程1介绍自动生成的词法分析器和语法分析器一直是构建语言分析环境的重要工具。许多广泛使用的词法分析器和解析器生成器，其中包括Flex [10]和Bison [3]，非常适合描述一类被设计为明确的编程语言。这些工具不适合处理由遗留语言、1这项工作得到了NSF Grant CCR-0098314和IBM Eclipse Innovation Grant的部分支持。2电子邮件：{abegel，graham}@ cs.berkeley.edu1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2004.06.00976A. Begel，S.L.Graham/Electronic Notes in Theoretical Computer Science 110（2004）75非基于键盘的输入，例如通过语音编程和来自嵌入式语言的输入。歧义可以是词汇的、句法的或语义的。本文所报告的贡献有两个方面：(i) 用于处理这些类型歧义的语法分析的改进方法(ii) 一个新的组合词法分析器和解析器生成器和进一步的解析器增强，便于嵌入式语言的描述和分析语音编程是一种新的用户界面形式，使用户能够使用语音识别软件编辑、导航和口述代码，是一种最近的编程技术，得到了台式计算机精确处理语音的能力的增强然而，口语输入包含许多词汇，歧义，如同音异义词、3个误识单词，以及无法识别无法发音或连接的单词。 当输入为英语或其他自然语言文档，可以通过语音识别供应商提供的隐马尔可夫模型来消除歧义。然而，当输入是计算机程序时，自然语言消歧规则不适用。这些歧义不仅影响了基于语音的程序员一些遗留语言，如PL/I和Fortran，对基于Flex的词法分析器和基于LALR（1）的解析器都提出了挑战。特别是PL/I没有保留关键字，这意味着IF和THEN可能既是关键字又是变量。词法分析器无法区分它们;只有解析器和静态语义有足够的上下文可供选择。Fortran例如，DO57I可以指定单个标识符或DO57 I，DO循环的初始部分没有语法支持，一个特定的字符序列可以使用几组标记边界来解释嵌入式语言，其中一种语言的片段可以嵌入到另一种语言中，广泛用于常见的应用领域，如Web服务器（例如嵌入XHTML的PHP），数据检索引擎（例如嵌入C的SQL）和结构化文档（例如嵌入Java的Javadoc）。文档中语言之间的边界可以是模糊的，也可以是严格的;检测它们可能需要词法、句法、语义或手写分析。嵌入式语言Flex和Bison描述缺乏模块化，使得对每个组件语言的独立维护和组合分析变得困难。3 同音异义词是发音相似但拼写不同的词。A. Begel，S.L.Graham/Electronic Notes in Theoretical Computer Science 110（2004）7577本文描述的方法处理四种输入流，其中三种是二义性的;我们的解决方案在第3节中总结。这些歧义的组合出现在不同形式的嵌入式语言中。第4节至第7节介绍了这类输入流的处理。其中一些模糊性也在相关工作中得到了解决，在第8节中进行了总结。单一拼写;单一词汇类型这 是正常的、明确的词法分析（即，一个字符序列产生一个唯一的标记序列）。我们举例说明这个案例来展示词法分析和解析在Harmonia分析框架中是如何工作的。多种拼法;单一词汇类型。语音编程会给编程带来潜在的歧义，而这些歧义在键入程序时不会发生如果用户说出对应于多个词素（例如，i和eye）的同音字，并且所有词素都具有相同的词汇类型（令牌IDENTIFIER），则使用一个或另一个同音字可以改变对应于多个词素（例如，i和eye）的同音字。节目的意义。单个词汇类型的多个拼写也可以用于对语音识别错误或类型化词素的词汇拼写错误进行建模（例如，标识符计数器出现为conter）。单一拼写;多种词汇类型。大多数语言都很容易通过将词位分成单独的类别来描述，例如关键字和标识符。然而，在某些语言中，语言定义并不强制区分。例如，在PL/I中，不保留关键字，引导-将一个简单的词素，如'IF'或'THEN'，解释为关键字和标识符。在这种情况下，词法分析器将单个字符流解释为唯一的词素序列，但某些词素可能表示多个交替标记，每个标记都有唯一的词法类型。多种拼法;多种词汇类型 有时用户可能会说同音字（例如，，'for'，'4'和'fore'），不仅有一个以上的拼写，但有不同的词汇类型（例如，关键字、数字和标识符）。嵌入式语言在嵌入式语言的分析中出现了两个问题 一旦确定了边界，内部语言和外部语言中的任何歧义都可以被处理，就好像没有嵌入一样。然而，识别边界的模糊性导致在分析后续输入时应用哪种语言的规则的模糊性。 几乎所有的编程语言都允许简单的嵌入，不-78A. Begel，S.L.Graham/Electronic Notes in Theoretical Computer Science 110（2004）75注意字符串和注释。在Java中的Javadoc等示例中的嵌入更加复杂。这些嵌入通常由特设技术处理。如果描述得当，它们可以以一种更有原则的方式被识别。本文中描述的结果需要对传统的词法分析器和解析器进行修改，无论是在交互式环境中使用的批处理版本还是增量版本。我们的方法是基于GLR解析。即使没有输入歧义，使用GLR而不是LR解析也能够支持输入流分析中的歧义。GLR通过派生多个解析器来容忍局部歧义，但由于解析器的公共部分是共享的，因此是高效的。此外，对于大多数编程语言的语法规范，产生的歧义量是有限的，而且相当小。 我们的贡献是推广这种歧义的概念，以及GLR解析方法，以解析局部不同的输入（无论是由于语言的嵌入，同音异义词的存在还是其他词汇识别的歧义）。我们已经加强了Harmonia分析框架的语言分析能力[2，5]，以处理这些类型的歧义。我们在语音编程方面的研究需要对输入流歧义进行交互分析。Harmonia现在可以识别语音输入中的歧义词素。此外，Harmonia这种新的输入语言将把以结构化的自然语言风格编写的命令语言与程序员正在编码的编程语言的代码摘录结合起来。为了实现这些额外的功能，解析器需要额外的数据结构来维护额外的词法信息（例如它自己的私有looka- head标记和它自己的私有lexer状态），以及到lexer的增强接口这些变化使增强的GLR解析器能够解决词法分析器必须增加一些额外的控制逻辑。开发了一个全新的词法分析器和解析器生成器Blender。Blender提供了一个词法分析器、解析表和语法树节点C++类，用于表示解析树中的语法树节点。它使语言设计人员能够轻松地描述许多类嵌入式语言（包括递归嵌套语言），并在分析的每个阶段支持多种词法，结构和语义歧义。在下一节中，我们将总结在Harmonia中实现的增量词法分析和GLR解析的结构支持输入模糊性和Blender设计的更改如下。A. Begel，S.L.Graham/Electronic Notes in Theoretical Computer Science 110（2004）75792Harmonia中的词法分析和语法分析Harmonia是一个开放的、可扩展的框架，用于构建交互式的、语言感知的编程工具。程序可以根据它们的结构和语义特性。高级转换操作可以在程序表示中创建和维护。Harmonia为XEmacs [25]和Eclipse [4]编程编辑器提供了交互式的在线服务，供最终用户在程序合成，编辑和导航期间使用。对每种用户语言的支持由一个插件模块提供，该模块由词汇描述、语法描述和语义分析定义组成。该框架维护了一个版本化的、带注释的解析树，该树保留了用户（或其他工具）所做的所有编辑以及曾经执行过的所有分析[21]。当用户进行基于键盘的编辑时，编辑器查找词素（即，树的终端节点）已经被修改并更新了它们的文本，由于未分析更改，因此暂时使树无效。如果输入是语音输入，则来自语音识别器的单词将被转换为一个新的未分析的终端节点，并添加到解析树中的适当位置。这些更改构成了最近编辑的版本（也称为最后编辑的版本）。这个版本的树和预编辑的版本被增量词法分析器和解析器用来分析和协调树中的更改。Harmonia采用增量版本的词法分析和语法形式的GLR解析[20，22，23，24]，以保持良好的交互性能。对于那些不熟悉GLR的人来说，可以将GLR解析视为LR解析的变体。在LR解析中，解析器生成器产生一个解析表，将解析状态/先行标记对映射到解析器自动机的动作：移位，使用特定语法规则减少或声明错误。对于每个解析状态/前瞻对，该表仅包含一个操作。多个潜在的操作（冲突）必须在表构建时解决。除了解析表和驱动程序之外，LR解析器还包括一个输入标记流和一个堆栈，在堆栈上可以移动语法终结符和非终结符。在每一步中，当前的先行标记与当前的解析状态配对，并在解析表中查找。该表告诉解析器要执行哪个操作，如果没有错误，还告诉解析器应该转换到哪个解析状态Harmonia中使用的GLR算法与Rekers [12]和Visser [19]描述的算法相似。在GLR中，冲突解决被推迟到运行时，所有操作都放在表中。当每次查找遇到多个操作时，GLR解析器分叉为多个解析器，这些解析器共享相同的自动机、相同的堆栈初始部分和相同的当前状态。每个分叉的解析器执行其中一个操作。解析器以伪80A. Begel，S.L.Graham/Electronic Notes in Theoretical Computer Science 110（2004）75并行地，在输入被推进之前，每一个执行用于下一个输入标记的所有可能的解析步骤（并且如果必要的话，分叉附加的解析器），并且每一个维护其自己的附加栈。当一个解析器在它的表查找中找不到任何动作时，它被终止;当所有的解析器都没有取得进展时，解析失败，错误恢复启动。当解析器在reduce或shift操作之后达到相同的状态时，它们将被合并。因此，从概念上讲，分叉解析器要么在一个公共子树根下构建多个子树，表示对公共输入的一部分的替代分析，要么最终消除所有替代分析。图1显示了GLR算法的基本非增量形式（在我们进行任何更改之前）。4在GLR解析中，每个解析器堆栈都表示为链接结构，以便共享公共部分。解析器列表中的每个解析器状态不仅包含记录的当前状态在顶部条目中，但也指向它是其最上面的元素在图1中，算法被抽象化，只显示了我们的方法改变的那些方面。特别是，解析堆栈共享是隐式的。因此，在堆栈p上推送q意味着将所有具有当前状态p的指定解析器推进到当前状态q。当前lookahead标记保存在全局变量lookahead中。在批LR或GLR解析中，与解析器在任何阶段相关联的初始形式是其堆栈上的符号序列（从下到上读取），后跟剩余输入标记的序列。从概念上讲，它们表示构建到单个解析树中的解析森林。在增量解析器中，堆栈上的符号和输入中的符号都可以是解析（子）树-可以将它们视为潜在的非规范的解析形式。增量分析或基于更改的分析的目标是在更改之前尽可能多地保留解析，仅在需要合并更改时进行更新。词法分析和解析的结果有时是由所有可能的解析树组成的解析森林必须使用语义分析来消除任何在语言语义方面不正确的有效解析的歧义。例如，为了消除应该连接的标识符的歧义（但由于它们来自语音识别器而作为单独的单词输入），语义阶段可以使用符号表信息来识别适当类型的所有范围内的名称（方法名称，字段名称，局部变量名称等）。匹配语义上正确的标识符的级联序列如果内部语言可以访问外部语言的语义（例如， JavaScript可以从HTML代码中引用对象，[4]增加增量对于理解此处所做的更改并不重要，因此未显示。A. Begel，S.L.Graham/Electronic Notes in Theoretical Computer Science 110（2004）7581GLR-PARSE（）initactive-parserslist to parse state 0initparsers-ready-to-actlist to emptywhilenot donePARSE-NEXT-SYMBOL（）如果在输入结束之前接受，则调用错误恢复接受PARSE-NEXT-SYMBOL（）lexonelookahead标记初始化shiftable-parse-states列表为空复制活动解析器列表到分析程序准备就绪表whileparsers-re ady-to-actlist/= 从列表DO-ACTIONS（p）中移除解析状态p移位符号DO-ACTIONS（解析状态p）查 找 每 个 动 作 的 动 作[p×lookahead]如果动作被切换到状态X将p，x>添加到shiftable-parse-states如果操作是按规则Y减少如果规则Y接受归约如果在输入结束时返回ifparsers-ready-to-actlist=0调用错误恢复返回DO-归约（p，规则y）如果没有解析器准备动作或移位，则调用错误恢复并返回如果action为ERROR且没有解析器准备好执行或转换调用错误恢复并返回DO-REDUCTIONS（parse state p，ruley）对于解析状态p的堆栈上RHS（规则y）以下的每个解析状态p-设q= GOTO状态，actions[p−×LHS（ruley）]如果解析状态q∈活动解析器列表如果对于解析状态q，p-pushqon stackp-对于每个解析状态r，使得r∈active-parserslist且r∈/parsers-re ady-to-actlistDO限制还原（r）其他创建新的解析状态qpushqon stackp-将q添加到活动解析器列表将q添加到parsers-ready-to-act列表DO-LIMITED-REDUCTIONS（解析状态r）查找操作[r×lookahead]对于每个REDUCE by ruley操作如果规则Y不接受减少DO-归约（r，规则y）移位符号清除活动分析程序列表对于每个p，x> ∈shiftable-parse-states，如果解析状态x∈活动解析器列表在堆栈p上压入x其他创建新的解析状态x在堆栈p上压入x将x添加到活动解析器列表图1. GLR解析算法的非增量版本。82A. Begel，S.L.Graham/Electronic Notes in Theoretical Computer Science 110（2004）75它是嵌入式的）。语义分析技术是有趣的和重要的，但深入讨论这个主题超出了本文的范围3Ambient Lessons和代币在第1节中，我们将标记歧义分为四种类型（包括unam-biased标记）。接下来，我们将解释如何处理这些情况。3.1单一拼写非编译的词法分析和解析是我们分析框架的常态编程语言大多有直接的语言描述，只有在使用GLR描述时才包含有界的二义性。因此，词法分析器和解析器的典型过程如下。增量解析器识别出被编辑的节点在最后一个被编辑的解析树中的位置，并调用增量词法分析器。增量词法分析器查看以前计算的回看值（存储在每个标记中），以确定有多少个标记返回到输入流中以开始词法分析。5开始标记的字符被馈送到基于Flex的词法分析器直到正则表达式被匹配为止。与正则表达式相关联的操作创建一个明确的标记，该标记返回给解析器用作其先行符号。作为对解析器请求标记的响应，词法分析继续进行，直到下一个标记是已经在语法树的编辑版本中的标记。(The解析器递增性的细节对于该讨论不是必需的，并且为了简洁而被省略。请注意，必须在每个树节点中存储附加信息以支持递增性）。3.2单一拼写如果单个字符序列可以指定多个词法类型，如PL/I中，则为每个解释（包含相同的文本，但不同的词法类型）创建标记，并将其全部插入AmbigNode容器中当词法分析器/解析器接口看到一个AmbigNode时，即多个交替的to- kens，该AmbigNode表示解析器的移位-移位连接。为每个标记创建一个新的词法分析器实例，并为每个词法分析器实例创建一个单独的解析器。因此，每个解析器都有自己的（可能是共享的）词法分析器和自己的先行标记。GLR解析像往常一样执行，只是解析器具有本地lookahead，而不是全局lookahead标记，5Lookback的计算方式是，当标记被词法分析时，批词法分析器使用的lookahead字符数的函数。[20个]A. Begel，S.L.Graham/Electronic Notes in Theoretical Computer Science 110（2004）7583一个共享的代表。由于这一变化，合并解析器的标准不仅包括解析状态相等，而且还包括每个解析器的词法分析器实例的前瞻标记和状态在图2中，是对PARSE-NEXT-SYMBOL（）函数的重述，该函数已根据上述更改进行了修改。请注意，lex和lookahead现在都与解析器p相关联，而不是全局的。没有显示的是对DO-REDUCTIONS（）中解析器合并标准的更改，以及对新解析状态（应该与当前lex和lookahead相关联）的创建的更改。此外，每个查找都必须引用关联的前瞻– for example,3.3多种拼写Harmonia词法分析器在每个单词上被调用来发现它的词法类型，并创建一个to- ken来包含它。如果所有的替代项都有相同的词法类型（例如，都是标识符），它们将被返回到一个称为Mul- tiText的容器标记中，解析器将其视为单个词法类型的单个明确标记一旦被合并到解析树中，就可以使用语义分析来在同音异义词中进行选择。PARSE-NEXT-SYMBOL（）对于每个解析状态p∈活动解析器列表lexponelookaheadp内标识如果先行P是不明确让Q1.. qn=复制解析状态p对于每个解析状态q∈q 1.. Qn从先行p到q分配一个备选方案将q添加到活动解析器列表初始化shiftable-parse-states列表为空复制活动解析器列表到解析器准备动作列表whileparsers-re ady-to-actlist/= 从列表DO-ACTIONS（p）中移除解析状态p移位符号图2. GLR解析算法的一部分被修改以支持歧义词素。类似的机制可以用于自动语义错误恢复。用户在键盘上打字时很容易拼错标识符。翻译者长期以来一直支持用拼写相似（或语音相似）的单词来代替不正确的标识符。在增量设置中，84A. Begel，S.L.Graham/Electronic Notes in Theoretical Computer Science 110（2004）75程序、解析和符号表信息是持久的，错误恢复可以用包含原始标识符以及可能的替代拼写的模糊变体来替换用户的错误标识符。进一步的分析可能能够根据活动符号表自动选择适当的替代方案。我们还没有调查这个应用程序。3.4多种拼写如果口语单词的替代拼写（如上所述）具有不同的词法类型（例如4/for/fore），则它们将作为分组在上述相同AmbigNode容器中的单独标记当lexer/parser接口看到一个AmbigNode时，它会分叉解析器和lexer实例，并为每个lexer实例分配一个标记。每一个的状态词法分析器实例必须重置为在词法分析其分配的替代项之后遇到的词法状态，因为每个拼写变体都可能通过词法分析器自动机遍历不同的路径。6.一旦每个标记被重新编译，它将被返回到其关联的解析器，用作其先行标记，并被转移到解析树中。4嵌入式语言使用Blender，构成嵌入式语言的外部和内部语言可以由两个完全独立的语言定义来指定嵌入式语言描述可以是任意嵌套和相互递归的。提供适当的边界描述是语言描述编写者的工作。4.1边界识别在嵌入式语言中，语言之间的边界可以由上下文指定（例如，，C的printf实用程序中的格式控制他们之间的关系，或许可以说是不一样的，或许可以说是不一样的，或许是不一样的。在语言上，它们可能有或可能没有其他含义。外）语言。我们将这些分隔符称为左边界标记和右边界标记。旧的遗留语言，通常是那些由手写的词法分析器和解析器分析的语言，往往有更多的模糊边界，6注意，我们不会在单个拼写上重置词法状态-多个词法类型歧义，因为每个备选项的文本（以及词法分析器通过其自动机的路径） 都是一样的，最终都是一样的词汇状态A. Begel，S.L.Graham/Electronic Notes in Theoretical Computer Science 110（2004）7585这些边界标记中的任一个可能不存在或与空白混淆例如，在Flex使用的描述格式中，正则表达式和其词法规则中基于C的操作之间的边界只是一个空格字符，后跟一个可选的左花括号。识别边界的一种技术是使用一种特殊的程序编辑器，它理解划分两种语言的边界标记（例如，，嵌入在XHTML中的 PHP），并强制执行高级文档/子文档编辑结构。边界标记是固定的，一旦插入，在不删除整个子文档的情况下无法编辑或删除。这两种语言可以独立分析。另一种技术是使用正则表达式匹配（或简单的词法分析器）来识别文档中的边界标记，并将它们用作将分析服务切换到内部语言或从内部语言切换的指示。这些服务通常限于基于词汇的服务，例如语法突出显示或不精确的缩进。基于语法分析的更复杂的服务不容易使用，因为正则表达式不够强大，无法准确地确定边界标记。一些较新的嵌入式语言维护了可识别的词法边界（例如，PHP的起始标记是<？php和它的结束标记是什么？>）。其他一些包含的边界仅在结构上或语义上可检测（例如，JavaScript<的左边界是script language=javascript >）。4.2词法嵌入语言词汇嵌入式语言是那些内部语言几乎没有结构，可以通过有限自动机进行分析的语言举个例子，Java语言的典型词汇描述包括关键字、标点符号和标识符的标准正则表达式。最复杂的正则表达式用于字符串和注释。字符串是由两边的两个双引号字符限定的字符序列.注释是一个字符序列，左边是/*，右边是*/。右边在这些边界标记中，Java词法分析的传统规则被暂停-没有关键字，标点符号或标识符。大多数描述编写者在看到左边界标记时会当右边界标记为如果检测到关键字，则将状态改变回初始词法分析器状态以再次开始检测关键字。7条件状态是在Flex的词法描述中显式声明的自动机状态。它们通常用于切换子语言。86A. Begel，S.L.Graham/Electronic Notes in Theoretical Computer Science 110（2004）75从嵌入式语言的角度来看，很明显，字符串和注释构成了Java语言中使用完全不同的词法规则的内部语言。使用Harmonia，我们可以将它们拆分为模块化组件，并在过程中清理Java词法规范。对于Java程序中的字符串，两个边界标记是相同的，并且可以通过一个简单的正则表达式进行词法识别。但是，除了双引号不能在字符串中以未转义的形式出现的规则之外，构成边界的双引号不是字符串数据的一部分。对于注释也是如此--边界标记向解析器标识注释，但不构成注释数据。4.3句法嵌入语言句法嵌入式语言是那些内部语言有自己的语法结构和语义规则的语言。语法嵌入式语言的编译器通常使用许多特殊技术来处理它们。一种常见的技术是忽略内部语言，例如，就像PHP中嵌入的SQL一样。PHP分析工具对SQL的词法或语法结构一无所知，实际上，作为一个字符串，不执行其正确性的静态检查。8这种分析的缺乏使程序员处于运行时解析错误的风险中，这些错误应该在编译时被捕获。类似地，在Flex中，C代码由Flex分析器作为文本传递，随后打包到C程序由传统的C编译器编译在下一节中，我们将展示如何在Blender中编写语言描述，Blender是我们的组合词法分析器和解析器生成器工具。5面向嵌入式语言的Blender语言描述词法描述是以Flex使用的格式的变体编写的。头部包含一组令牌声明，用于命名将由此描述中的操作返回的令牌。规则的开头是一个正则表达式（前面可以有一个词法条件状态），当匹配时，它会创建一个所需类型的标记，并将其返回给解析器。8这种不完整和不适当的词法分析迫使程序员在嵌入式SQL查询中转义字符，而这些字符在单独使用SQL时是不必要的。A. Begel，S.L.Graham/Electronic Notes in Theoretical Computer Science 110（2004）7587语法描述是以Bison格式的变体编写的。每个文法都由一个包含优先级和结合性声明的头部组成，后面是一组文法产生式。为了支持概念模块化，编写了一个或多个%import-token声明来指定要加载的词法描述（其中一个被指定为默认值）以便找到在此语法中使用的标记。除了导入到- kens之外，语法还可以使用% import语法声明。语法产生式没有关联的动作。运行时解析器的唯一动作是从输入生成解析树/森林。语言设计者编写一个遍历树的语义分析阶段来表达任何想要的动作。导入的（非缺省）终结符和非终结符在本文中被称为符号语言。导入的符号会导致内部语言嵌入外部语言。Java程序中嵌入注释的一个例子是：/* 只是一个评论 */要将注释语言嵌入到外部Java语法中，可以添加以下规则：评论→SLASHSTARCOMMENTDATAcomment-langSTARSLASH在Blender中，内部语言的边界标记由外部语言指定，因此外部分析器可以检测边界。内部语言的数据是用不同的规范写的，名为comment-lang，它被导入到Java语法中。在这个简单的例子中，嵌入是词法的。注释边界标记由检测标记/*和*/的正则表达式描述。它们被放置在主要的Java词汇描述中（描述关键字，标识符和文字的描述）。注释数据可以通过下面的Flex词法规则来描述，该规则匹配输入中的所有字符，包括回车符。.| [\r\n]{ yymore（）; break;}然而，这种指定将超出注释的右边界标记。我们的解决方案专门针对基于Flex的词法分析器的特点（在不同的词法分析器生成器中可能不同），它是在任何想要的词法描述中引入一个特殊的关键字END LEX。嵌入到外部语言中END LEX将代替常规表达式，它将检测*/。Blender将根据COMMENTDATA终端后面的右边界标记自动插入这个正则表达式对于那些熟悉Flex的人来说，最终的描述看起来像比如：%{intcomment_length; %}88A. Begel，S.L.Graham/Electronic Notes in Theoretical Computer Science 110（2004）75{%token COMMENTDATA%%END_LEX{yyless（comment_length）;RETURN_TOKEN（COMMENTDATA）;}.| [\r\n]{ yymore（）; comment_length = yylen; break;}由于Flex的规则优先属性（匹配多个正则表达式的词素与第一个正则表达式相关联），我们必须小心地在另一个正则表达式之前插入这个新的END LEX规则，否则Flex将错过右边界标记。此外，由于COMMENTDATA词素只有在看到右边界标记时才会返回，因此其文本会意外地包含边界标记的字符。我们使用Flex的 yy l e s s （ ） 构 造 将 右 边 界 标 记 的 字 符 推 回输 入 流 （ 从 而 可 以 由 外 部 语 言 的 词 法 分 析 器 进 行 匹 配 ） ， 然 后 返 回CO M M E N T D A T A 词 法 位 。这种词法嵌入使人们能够在几种编程语言中重用公共语言组件。例如，即使Smalltalk和Java对字符串使用不同的边界标记（Java使用"和小客户），他们的交易具有相同的法律效力。我很抱歉-嵌入一种语言（比如这个String语言）使语言设计者能够重用那些创建起来可能相当复杂的词汇规则，如果它们被复制，可能会导致维护问题。由于上下文无关语法的表达能力更强，所以句法嵌入更容易执行一个简单的方法是在外部语言中使用内部语言的非终结符以下是Flex词法规则的语法示例规则→REGEXPRooTregexpWSPCccoDE科科-德 →LBRACE公司新闻|co MP o UNDSTMTc NEWLINEFlex规则由一个正则表达式和一个带括号的C复合语句组成.正则表达式由regexp语法中的REGEXP根非终结符表示。符号WSPC表示空白字符。复合语句由C语法中的复合STMT表示。我们现在可以展示与遗留嵌入式语言相关的词汇歧义之一。在Flex和C中，左大括号标记都是由字符描述的。C语言中的复合语句可以用一组花括号括起来，也可以不用 当看到左大括号时，它可能属于Flex的外部语言，也可能属于内部C语言。选择正确的语言通常需要只有解析器才能获得的上下文信息。即使是解析器，也只能在两者同时出现时才能正确地选择A. Begel，S.L.Graham/Electronic Notes in Theoretical Computer Science 110（2004）7589选项、Flex左大括号标记和C左大括号标记。这是另一个具有多个词法类型的单个词素的例子;它的解析需要对词法分析器和解析器生成器进行增强，以及对解析器进行增强。在下一节中，我们将展示如何将嵌入式终结符和非终结符合并到工具中。6嵌入式语言当Blender语言描述包含多个语言的语法时，这些语法将被合并。9每个语法符号都标有其语言名称，以确保其唯一性。解析器的生成与GLR解析器的生成一样正常进行（即LALR（1）与GLR解析）。当一个Blender语言描述包含多个词汇描述时，所有的词汇描述都会被合并。在每个描述中，声明的任何条件状态（包括默认的初始状态）都用它们的语言名称标记，以确保它们的唯一性。然后，将所有规则合并到一个规则列表中。每个规则的条件状态没有被显式声明，现在被声明为属于其语言的标记的初始条件状态。默认的词法描述的初始条件状态是组合规范的初始条件状态。宣布的规则应用于所有条件状态（在规则的开头用*>只适用于那些宣布使用该特定语言的州。这种状态重命名方案避免了规则的重新排序可能对每种语言的词法规范的语义造成但是，现在每个嵌入的词法描述的初始条件状态都与新的初始状态断开连接。解析器在每个标记被词法化之前设置词法化器状态。对于由GLR解析器生成器创建的每个解析状态，确定移位和归约前瞻终端所属的词汇描述。此信息被写入一个表中，该表将解析状态映射到一组词法描述ID。在运行时，当解析器分析由嵌入式语言描述描述的文档时，它使用该表在识别先行标记之前将词法分析器实例切换到适当的词法状态。如果一个特定的解析状态有多个词法状态，解析器必须告诉词法分析器实例切换到所有指示的词法状态。但是，9GLR在工会下关闭。90A. Begel，S.L.Graham/Electronic Notes in Theoretical Computer Science 110（2004）75具有多个词法状态会导致输入流变得不明确。下一节将对这种歧义进行分析7嵌入式语言的词法分析和语法分析嵌入式语言通过使词法分析器和解析器能够同时分析具有许多逻辑语言描述的输入，增加了第3我们对GLR算法再做两处修改，以处理嵌入式语言，并在图3和图4中演示完整的算法。在PARSE-NEXT-SYMBOL（）中为每个解析器词法分析前，在活动解析器列表中查找与每个解析状态相关联的词法语言。如果语言发生了变化，解析器的词法分析器实例的状态将重置为该语言的初始词法状态（通过Blender生成的查找表）。当有一个以上的词汇语言与解析状态相关联时，这意味着在语言之间的边界上存在词汇歧义。这种情况的处理方式与其他输入流歧义相同：为每种词法语言创建一个新的词法分析器实例（并设置为该语言的初始词法状态），并为每个词法分析器实例创建一个单独的解析器每个forked lexer实例将从输入流中读取相同的字符，但将以不同的方式解释它们，因为它处于不同的词法状态。接下来，如果每个解析器都有自己的私有词法分析器实例，并且每个词法分析器实例在读取输入流时处于不同的词法状态，则输入流可以在它们的令牌边界处发散，其中一些流产生较少的令牌，一些流产生较多的令牌。这可能会导致每个解析器在输入流中的位置与其他解析器不同，这与传统的GLR解析算法不同，在传统的GLR解析算法中，所有解析器都保持同步，在每个主要迭代期间移动相同的前瞻令牌。除非我们小心，否则这可能会对解析器的合并能力产生严重影响，如果一个解析器被迫重复另一个解析器的工作，也会对性能产生影响为了解决这个问题，我们观察到任何两个已经分叉的解析器只有在它们的解析状态、词法分析器状态和lookahead令牌相同时才能合并。对于不同步的解析器，只有当语言边界二义性被解决后输入流再次收敛时，才会发生这种情况。但是，在图1和图2中给出的GLR算法中，只在活动解析器列表中搜索可合并的解析器。如果一个解析器p比另一个解析器q领先一个以上的输入标记，那么当p准备好与它合并时，q将不再在活动解析器列表中。A. Begel，S.L.Graham/Electronic Notes in Theoretical Computer Science 110（2004）7591GLR-PARSE（）initactive-parserslist to parse state 0initparsers-ready-to-actlist to emptyinitlookahead-to-parse-statemap清空虽然没有完成PARSE-NEXT-SYMBOL（）如果在输入结束之前接受，则调用错误恢复接受PARSE-NEXT-SYMBOL（）SETUP-LEXER-STATES（）对于每个解析状态p∈active-parserslistlexp一个lookaheadptoken如果lookaheadp是二义性的让Q1.. qn=对于每个解析状态q∈q 1. qn从先行p到q分配一个备选方案将q添加到活动解析器列表对于每个解析状态p∈活动解析器列表添加先行p×p>lookahead到parse-state映射初始化shiftable-parse-states列表为空复制活动解析器列表到分析程序准备就绪表whileparsers-re ady-to-actlist/= 从列表DO-ACTIONS（p）中移除解析状态p移位符号SETUP-LEXER-STATES（）对于每个解析状态p∈ active-parserslistlet langs=lexer-langs[p]if|langs|> 1个让Q1.. qn=复制解析状态p对于每个解析状态qi∈q 1.. Qniflangsi/=lexerlanguageoflexp将lexstateoflexqi设置为init-state[langsi]将qi添加到活动解析器列表elseiflangs0=/lexerlanguageoflexp将lexp的lex state设置为init-state[langs0]DO-ACTIONS（解析状态p）查找每个动作的