22、GLR 解析与 C++ 解析器的深入剖析

GLR 解析与 C++ 解析器的深入剖析

1. GLR 解析概述

解析器生成器（如 yacc 和 bison）广受欢迎的一个重要原因是，它们创建的解析器比手写解析器更可靠。如果将一个无冲突的语法规则输入给 bison，那么生成的解析器所接受的语言将与该语法规则描述的完全一致，不会出现手写解析器常见的漏洞，尤其是在诊断错误输入时。在已知情况下，如表达式语法和 if/then/else 结构中，适度使用优先级声明来解决冲突，也能确保解析器按预期处理语言。

然而，GLR 解析则有所不同。使用 GLR 解析时，可以将任何语法规则交给 bison，它会创建一个解析器来解析内容，并在解析时解决冲突。但冲突越多，解析的语言就越可能不是你想要的，解析器解决冲突的方式也越可能不符合预期。在切换到 GLR 解析之前，必须清楚语法规则中存在冲突的原因，以及如何解决这些冲突。否则，可能会遇到尴尬的情况，比如解析器在遇到未预料到的冲突时意外放弃，或者由于错误的冲突解决方式，导致解析的语言并非预期的语言。

理论上，GLR 解析器可能会非常慢，因为并行运行 N 个解析的速度大约是单个解析的 N 倍，而且特别模糊的语法规则可能会在每个标记处进行分支。不过，有用的 GLR 语法规则通常只有少数模糊性，并且能在几个标记内解决，因此性能通常是足够的。

正常的 bison LALR 解析器无需处理移进 - 归约或归约 - 归约冲突，因为这些冲突在解析器构建时就已解决。但当 GLR 解析器遇到冲突时，它会在概念上进行分支，并行继续两种可能的解析，每个解析器并行消耗输入标记。当存在多个冲突时，它会创建一个部分解析的树，每次遇到冲突时都会进行分支。

如果语法规则实际上是明确的，只是需要