22、解析器技术：GLR 与 C++ 解析器深度剖析
解析器技术：GLR 与 C++ 解析器深度剖析
1. GLR 解析概述
在解析器生成领域，像 yacc 和 bison 这类工具备受青睐，原因在于它们生成的解析器比手写解析器更可靠。当你向 bison 提供一个无冲突的语法时，能确保生成的解析器所接受的语言与该语法描述的完全一致，避免了手写解析器常见的漏洞，尤其是在诊断错误输入时。不过，若使用 GLR 解析，可将任意语法交给 bison，它会创建一个解析器并在解析时解决冲突。但冲突越多，解析的语言越可能偏离预期，且解析器解决冲突的方式也可能并非如你所愿。
在切换到 GLR 解析之前，务必明确语法冲突的原因以及解决方法。否则，可能会遭遇尴尬局面，如解析器在遇到未预料的冲突时意外放弃，或者因错误的冲突解决方式导致解析的语言并非预期的语言。
理论上，GLR 解析器可能会非常慢，因为并行运行 N 个解析大约比单个解析慢 N 倍，特别是在语法存在大量歧义时，每个标记都可能导致解析分支。不过，实用的 GLR 语法通常只有少数歧义，且能在几个标记内解决，所以性能通常是可以接受的。
普通的 bison LALR 解析器在构建时就解决了所有冲突，无需处理移进 - 归约或归约 - 归约冲突。而 GLR 解析器遇到冲突时，会在概念上进行分支，并行执行两种可能的解析。当存在多个冲突时，会形成部分解析的树结构，每次遇到冲突都会进行分支。
如果语法实际上是无歧义的，只是需要比 LALR(1) 提供的单个标记更多的前瞻信息，大多数解析在无法匹配下一个输入标记时会失败。Bison 会默默丢弃失败的解析，只要还有其他活跃的解析就会继续。若所有可能的解析都失败，bison 会按常规方式报告错误。对于这类语法，GLR 解析器的工