YACC Bison GLR解析器reduce/reduce冲突下未触发解析拆分问题咨询
问题原因
你的GLR解析器没有触发分支拆分,核心是默认LALR分析表的静态剪枝把你需要的归约动作提前删除了:
GNU Bison默认使用LALR(1)算法生成分析表,会合并相似状态、删除它判定为"不可能出现"的动作。你当前文法里{}既可归约为PrimaryExpression也可归约为ObjectAssignmentPattern的归约/归约冲突,在LALR分析阶段被错误判定为不存在,所以分析表里仅保留了归约为PrimaryExpression的动作,运行时自然不会拆分分支,归约完成后遇到=就直接报错。
解决方案
按以下步骤修改文法即可触发预期的GLR分支拆分:
- 替换默认LALR分析表为规范LR分析表,避免静态剪枝删除合法动作,在文法声明段添加以下配置:
%define lr.type canonical-lr
- 确认冲突被识别:编译文法时添加
-v参数,会生成.output的状态表文件,检查对应{}完成移进的状态(你当前的状态12),如果看到前瞻token为=时存在两个归约动作的reduce/reduce冲突,说明配置生效。 - (可选)配置分支优先级:如果需要后续自动过滤无效分支,可以给两个冲突的归约规则添加
%dprec优先级声明,例如:
PrimaryExpression: '{' '}' { $$= 42; } %dprec 2 | PrimaryExpressionNB { $$ = $1; } ; ObjectAssignmentPattern: '{' '}' %dprec 1;
数字越大优先级越高,解析到歧义点时会优先保留高优先级分支,也可以保留两个分支到解析结束自行选择。
修改完成后重新运行解析器,就能看到GLR拆分栈的调试日志,两个解析分支会分别尝试后续匹配:归约为PrimaryExpression的分支后续匹配失败会被自动丢弃,归约为ObjectAssignmentPattern的分支会正常完成整个输入的解析。
内容的提问来源于stack exchange,提问作者Evgeniy Yakovich
相关产品推荐
相关产品推荐

