22、高级解析技术：GLR与C++解析器深度剖析

高级解析技术：GLR与C++解析器深度剖析

1. GLR解析概述

解析器生成器（如yacc和bison）广受欢迎，原因在于它们生成的解析器比手写解析器更可靠。若将无冲突的语法规则输入bison，生成的解析器所接受的语言与语法规则描述的完全一致，不会像手写解析器那样存在漏洞，尤其是在诊断错误输入时。若谨慎使用优先级声明来解决已知场景（如表达式语法、if/then/else结构）中的冲突，也能确保解析器按预期处理语言。

GLR（Generalized LR）解析则不同，可将任何语法规则交给bison，它会创建一个解析器在解析时解决冲突。但冲突越多，解析的语言越可能不是预期的，解析器解决冲突的方式也可能不符合预期。切换到GLR解析前，需明确语法规则产生冲突的原因及解决方法，否则可能出现解析器在遇到未预料的冲突时意外停止，或因错误的冲突解决方式导致解析的语言与预期不符的情况。

GLR解析器理论上可能极慢，因为并行运行N个解析大约是单个解析速度的N倍，特别模糊的语法规则可能在每个标记处分裂。不过，实用的GLR语法规则通常只有少量模糊性，且能在几个标记内解决，所以性能尚可。

普通的bison LALR解析器无需处理移进 - 归约或归约 - 归约冲突，因为这些冲突在解析器构建时已解决。而GLR解析器遇到冲突时，会在概念上分裂并继续两种可能的解析，每个解析器并行处理输入标记。若有多个冲突，会创建部分解析的树，每次冲突时分裂。

若语法规则实际上是明确的，只是需要比LALR(1)提供的单个标记更多的向前看符号，大多数解析在无法匹配下一个输入标记时会失败。bison会默默丢弃失败的解析，只要还有其他活跃的解析就会继续。若所有可能的解析都失败，bison会按常规方