如何修复YACC的“2移进/归约冲突”错误及递归调用问题排查

先帮你拆解一下遇到的两个问题，再给出针对性的修改方案：

问题根源分析 #

1. 递归调用未生效的原因 #

你定义的s产生式混合了右递归（SKIP { ... } s）和左递归（s exps），同时还包含了exps作为单独分支，这种混合的语法结构让解析器在处理连续SKIP文本时，无法明确选择走SKIP s的递归分支——解析器可能因为冲突优先选择了其他产生式路径，导致连续文本只能被处理一次。

2. 移进归约冲突的来源 #

冲突来自两处歧义：

• 当解析完一个s后，遇到括号（OPEN_PAREN），解析器不知道该移进括号继续解析exps，还是先归约当前的s
• 当exps解析完成后，后续的SKIP既可以被归约到exps : exp SKIP，也可以被当作s的新分支，导致解析器无法抉择

修改后的代码 #

我重构了语法结构，明确拆分了元素类型，消除了歧义，同时保留了你想要的所有功能：

%{ import java.io.*; %}
%token OPEN_PAREN;
%token CLOSE_PAREN;
%token <sval> SKIP;
%start s
%%
// 括号表达式规则：支持空括号或包含s的嵌套括号
parens : OPEN_PAREN s CLOSE_PAREN | OPEN_PAREN CLOSE_PAREN

// 单个表达式就是括号结构
exp : parens

// 表达式可选后跟文本（对应你原来的exps规则）
expr_with_opt_text : exp | exp SKIP { System.out.println("S: "+$2); }

// 纯文本元素处理（对应你原来的SKIP递归分支）
text_element : SKIP { System.out.println("txt: "+$1); }

// 主规则：s是多个元素的序列，用左递归更高效（YACC对左递归有天然优化）
s : s text_element 
  | s expr_with_opt_text 
  | text_element 
  | expr_with_opt_text
%%
void yyerror(String s) {
    System.out.println("err:"+s);
    System.out.println(" :"+yylval.sval);
}
static Yylex lexer;
int yylex() {
    try {
        return lexer.yylex();
    } catch (IOException e) {
        System.err.println("IO error :"+e);
        return -1;
    }
}
public static void main(String args[]) {
    System.out.println("[Quit with CTRL-D]");
    Parser par = new Parser();
    lexer = new Yylex(new InputStreamReader(System.in), par);
    par.yyparse();
}

关键优化点 #

1. 拆分元素类型：把纯文本（text_element）和带可选文本的表达式（expr_with_opt_text）拆分成独立规则，让解析器能明确区分不同的输入类型，不会再混淆递归路径
2. 统一左递归：主规则s使用左递归处理序列，YACC对左递归有天然优化，既避免了栈溢出风险，也消除了混合递归带来的冲突
3. 消除歧义：每个规则的职责更单一，没有重叠的语法分支，彻底解决了移进归约冲突

额外调试建议 #

如果以后再遇到类似冲突，可以用YACC的-v参数生成y.output文件，里面会详细列出每个状态的移进/归约选项，以及冲突的具体位置，能帮你快速定位语法歧义点。

内容的提问来源于stack exchange，提问作者Gello