4

我想了解解析器是如何工作的。我了解了 LL、LR(0)、LR(1) 部分、如何构建、NFA、DFA、解析表等。

现在的问题是，我知道在某些情况下，词法分析器应该只根据解析器的需求提取标记，因为不可能在一个单独的通道中提取所有标记。我不完全理解这种情况，所以我愿意接受任何解释。

现在的问题是，词法分析器应该如何工作？它是否应该基于当前的“上下文”，即应该解析的当前非终端来识别它？这是完全不同的东西吗？GLR 解析又如何：这是词法分析器可以尝试不同终端的另一种情况，还是只是一种句法业务？我还想了解它与什么有关，例如它与解析技术（LL、LR 等）的种类有关还是仅与语法有关？

非常感谢

4

2 回答 2

4

简单的答案是词位提取必须在上下文中完成。人们可能认为的语言中的词位在语言的不同部分可能会有很大差异。例如，在 COBOL 中，数据声明部分具有“PIC”字符串和位置敏感级别编号 01-99，它们不会出现在过程部分中。

因此，词法分析器以某种方式知道正在处理语言的哪一部分，知道要收集哪些词位。这通常是通过词法状态来处理的，每个状态都处理整个语言词位集的某个子集（通常在子集中有相当大的重叠；例如，在我的经验中，标识符往往非常相似）。这些状态形成一个高级有限状态机，当遇到相变词位时，它们之间会发生转换，例如，指示进入 COBOL 程序的数据声明或过程部分的关键字。Java 和 C# 等现代语言最大限度地减少了对此的需求，但我遇到的大多数其他语言确实需要词法分析器中的这种帮助。

所谓的“无扫描”解析器（您正在考虑“GLR”）通过完全摆脱词法分析器来工作；现在词法分析器不需要生成词位，也不需要跟踪词法状态：-} 这样的解析器通过简单地将语法写到单个字符的级别来工作；通常，您会发现语法规则与您为词位描述编写的内容完全相同。那么问题是，为什么这样的解析器不会对生成哪个“词素”感到困惑？这就是 GLR 部分有用的地方。只要选择最终得到解决，GLR 解析器就乐于处理输入的许多可能解释（“本地歧义解析”）。所以在“模糊标记”的情况下真正发生的是两个“标记”的语法规则

我的公司为语言构建了许多解析器。我们使用 GLR 解析器，因为它们非常适合处理复杂的语言；编写上下文无关语法，你就有了一个解析器。我们使用基于词法状态的词素提取器，并使用通常的词法正则表达式规范和由某些词素触发的词法状态转换。我们可以构建无扫描器的 GLR 解析器（通过让我们的词法分析器生成单个字符作为标记 :)，但我们发现基于状态的词法分析器的效率值得额外的麻烦。

作为实际的扩展，我们的词法分析器实际上将下推堆栈自动机用于高级状态机，而不仅仅是有限状态机。当一个人具有子状态相同的高级 FSA 时，这很有帮助，并且它有助于词法分析器管理嵌套结构（例如，匹配括号）以管理模式切换（例如，当括号全部匹配时）。

A unique feature of our lexers: we also do a little tiny bit of what scannerless parsers do: sometimes when a keyword is recognized, our lexers will inject both a keyword and an identifier into the parser (simulates a scannerless parser with a grammar rule for each). The parser will of course only accept what it wants "in context" and simply throw away the wrong alternative. This gives us an easy to handle "keywords in context otherwise interpreted as identifiers", which occurs in many, many languages.

于 2012-07-21T13:51:41.947 回答
3

理想情况下，令牌本身应该是明确的；您应该始终能够在解析器不做任何额外工作的情况下对输入流进行标记。

这并不总是那么简单，因此您有一些工具可以帮助您：

  1. 开始条件

    词法分析器操作可以更改扫描程序的启动条件，这意味着它可以激活不同的规则集。

    一个典型的例子是字符串字面量词法分析；当您解析字符串文字时，标记化规则通常与包含它们的语言完全不同。这是独占开始条件的示例。

    如果您可以为它们识别两个单独的开始条件并确保词法分析器在给定一些先前的上下文的情况下正确地输入它们，那么您可以分离模棱两可的词法。

  2. 词汇搭配

    这是一个花哨的名称，用于在词法分析器中携带状态，并在解析器中对其进行修改。如果解析器中的某个动作被执行，它会修改词法分析器中的某些状态，从而导致词法分析器动作返回不同的标记。必要时应该避免这种情况，因为它会使您的词法分析器和解析器都更难以推理，并使某些事情（如 GLR 解析器）变得不可能。

    好处是您可以做一些需要重大语法更改而对代码影响相对较小的事情；您可以使用解析中的信息来影响词法分析器的行为，这反过来又可以通过某种方式解决您所认为的“模棱两可”语法的问题。

  3. 逻辑、推理

    很可能可以在一次解析中对其进行词法分析，并且上述工具应该排在第二位，以考虑如何对输入进行标记化并尝试将其转换为词法分析的语言。:)

    事实上，你的输入是由标记组成的——不管你喜欢与否！——你需要做的就是找到一种方法让程序理解你已经知道的规则。

于 2012-07-21T13:04:34.153 回答