词法分析器如何提取歧义语言中的标记？

Question

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

现在的问题是，我知道词法分析器应该仅在某些情况下根据解析器的需求提取标记，当不可能在一次单独的传递中提取所有标记时。我不太明白这种情况，所以我愿意接受任何解释。

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

多谢

Answer 1

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

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

所谓的“无扫描器”解析器（您认为是“GLR”）通过完全摆脱词法分析器来工作；现在词法分析器不需要生成词位，也不需要跟踪词法状态:-}这样的解析器通过简单地将语法写到单个字符的级别来工作；通常，您会发现与您为词位描述编写的语法规则完全相同的语法规则。那么问题是，为什么这样的解析器不会对生成哪个“词位”感到困惑？这就是 GLR 部分有用的地方。GLR 解析器很乐意处理输入的许多可能的解释（“局部模糊解析”），只要选择最终得到解决。因此，在“不明确标记”的情况下真正发生的是两个“标记”的语法规则为它们各自的“词位”生成非终结符，并且 GLR 解析器继续解析，直到解析路径之一消失或解析器终止带有歧义的解析。

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

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

我们的词法分析器的一个独特功能：我们还做了一些无扫描器解析器所做的事情：有时当识别出关键字时，我们的词法分析器会将关键字和标识符注入解析器中（使用语法规则模拟无扫描器解析器每个）。解析器当然只会接受它想要的“上下文”内容，并简单地丢弃错误的选择。这为我们提供了一种易于处理的“上下文中的关键字，否则解释为标识符”，这种情况出现在许多语言中。