Yacc左递归文法解析时在左递归后缀匹配前提前归约报错如何解决？

报错触发原因 #

• 你的文法存在移进/归约冲突：当分析器解析完KW_CHAR并依次归约为char、type后，下一个待匹配 token 是ASTERISK，此时分析器面临两个合法选择：
  1. 移进ASTERISK，后续匹配pointer: type ASTERISK的产生式，完成指针类型的归约
  2. 将当前栈中的type归约为start，结束语法匹配
• Yacc处理移进/归约冲突的默认规则是归约优先，所以会优先尝试将type归约为start，但此时输入流中还有未处理的ASTERISK，不符合起始符号匹配完整输入的要求，因此直接触发语法错误。你看到的日志刚好对应归约到type后报错的过程。

解决方法 #

方案1：修改起始规则强制匹配完整输入 #

给起始规则添加输入结束符匹配逻辑，让分析器只有确认后续无剩余token时，才会将type归约为start，遇到ASTERISK时会优先移进匹配指针规则：

%%
/* EOF为词法分析器返回的输入结束标记，也可以用Yacc内置的$end表示 */
start: type EOF {
        printf("Reduced to start.\n");
    };

type: pointer {
        printf("Reduced pointer to type.\n");
    } 
    | char {
        printf("Reduced char to type.\n");
    };

char: KW_CHAR {
        printf("Reduced to char.\n");
    };

pointer: type ASTERISK {
        printf("Reduced to pointer.\n");
    };
%%

该方案改动最小，不需要调整原有类型规则结构。

方案2：显式设置优先级消除冲突 #

通过优先级声明，让ASTERISK的移进优先级高于type归约为start的优先级，强制分析器遇到*时先移进：

%nonassoc REDUCE_TYPE
%left ASTERISK
%%
start: type %prec REDUCE_TYPE {
        printf("Reduced to start.\n");
    };
/* 其余规则保持不变 */
%%

该方案适合不希望修改文法结构的场景。

方案3：调整文法结构从根源避免冲突 #

将类型拆分为基础类型和派生类型，重写文法彻底消除移进/归约冲突，同时天然支持多级指针（如char**）匹配，是类C类型文法的推荐写法：

%%
start: type {
        printf("Reduced to start.\n");
    };

type: pointer
    | base_type
    ;

base_type: KW_CHAR {
        printf("Reduced to char.\n");
    };

pointer: base_type ASTERISK
       | pointer ASTERISK {
            printf("Reduced to pointer.\n");
        }
       ;
%%

内容的提问来源于stack exchange，提问作者Daniel F.