Java CUP解析器添加用户自定义变量类型时出现移进/归约冲突

我需要让语法支持用户自定义类型，但添加规则tvariable ::= ENTERO | ID后，Java CUP报出移进/归约冲突：

[cup] Warning : *** Shift/Reduce conflict found in state #21
      [cup]   between epsilon ::= (*) 
      [cup]   and     tvariable ::= (*) ID 
      [cup]   under symbol ID
      [cup]   Resolved in favor of shifting.
      [cup] Warning : *** Shift/Reduce conflict found in state #24
      [cup]   between epsilon ::= (*) 
      [cup]   and     tvariable ::= (*) ID 
      [cup]   under symbol ID
      [cup]   Resolved in favor of shifting.
      [cup]   Checking for non-reduced productions...
      [cup] Error : *** More conflicts encountered than expected -- parser generation aborted

对应的语法代码如下：

package compiler.syntax;

// Declaracion de importaciones 
//(No modificar las proporcionadas. Se pueden agregar mas)

import java_cup.runtime.Symbol;
import java.util.*;

import es.uned.lsi.compiler.lexical.*;
import es.uned.lsi.compiler.code.*;
import es.uned.lsi.compiler.intermediate.*;
import es.uned.lsi.compiler.semantic.*;
import es.uned.lsi.compiler.semantic.symbol.*;
import es.uned.lsi.compiler.semantic.type.*;
import es.uned.lsi.compiler.syntax.*;

import compiler.CompilerContext;
import compiler.lexical.*;
import compiler.syntax.nonTerminal.*;

import compiler.semantic.symbol.*;
import compiler.semantic.type.*;
import compiler.intermediate.*;
import compiler.code.*;

// Declaracion del codigo de usuario

action code {: 
    
    SyntaxErrorManager   syntaxErrorManager   = CompilerContext.getSyntaxErrorManager();
    SemanticErrorManager semanticErrorManager = CompilerContext.getSemanticErrorManager ();
    ScopeManagerIF       scopeManager         = CompilerContext.getScopeManager ();
    FinalCodeFactoryIF   finalCodeFactory     = CompilerContext.getFinalCodeFactory ();

:}  

parser code {: 
    SyntaxErrorManager syntaxErrorManager = CompilerContext.getSyntaxErrorManager();
    
    public void syntax_error(Symbol symbol)
    { 
        Token token = (Token) symbol.value;
        syntaxErrorManager.syntaxError ("Error sintactico", token);     
    }
        
    public void unrecovered_syntax_error(java_cup.runtime.Symbol symbol)
    {   
        Token token = (Token) symbol.value;
        syntaxErrorManager.syntaxFatalError ("Error fatal", token);
    }
:}

// Declaracion de terminales (Ejemplo)

terminal Token PLUS;
terminal Token MULT;
terminal Token MENOR;
terminal Token IGUAL;
terminal Token AND;
terminal Token NOT;
terminal Token AUTOINCREMENTO;
terminal Token ASIGNACION;
terminal Token ASIGNACION_CON_SUMA;
terminal Token ABRIR_PARENTESIS;
terminal Token CERRAR_PARENTESIS;
terminal Token ABRIR_BRACKET;
terminal Token CERRAR_BRACKET;
terminal Token COMA;
terminal Token PUNTO_COMA;
terminal Token DOS_PUNTOS;
terminal Token ABRIR_LLAVE;
terminal Token CERRAR_LLAVE;
terminal Token CASO;
terminal Token CONSTANTE;
terminal Token CORTE;
terminal Token ENTERO;
terminal Token ESCRIBE;
terminal Token ESCRIBE_ENT;
terminal Token ALTERNATIVAS;
terminal Token MIENTRAS;
terminal Token PORDEFECTO;
terminal Token PRINCIPAL;
terminal Token DEVUELVE;
terminal Token SI;
terminal Token SINO;
terminal Token TIPO;
terminal Token VACIO;
terminal Token DIGITOS;
terminal Token LIT_INTEGER;
terminal Token ID;
//terminal Token CONST;
terminal Token CADENA_CARACTERES;
terminal Token CADENA;
// ...


// Declaracion de no terminales
// no modificar los propuestos

non terminal            program;
non terminal Axiom      axiom;
non terminal            epsilon;
non terminal            declaraciones;


non terminal            declaracionConstantes;
non terminal            constantes;
non terminal            constante;
non terminal            fconstante;

non terminal            declaracionVariables;
non terminal            variables;
non terminal            tdvariable;
non terminal            ftdvariable;
non terminal            tvariable;
non terminal            dvariable;
non terminal            Fid;
non terminal            asigvariable;
non terminal            fasigvariable;

non terminal            vector;

non terminal            expresion;
non terminal            expresion2;
non terminal            expresion3;
non terminal            expresion4;
non terminal            expresion5;
non terminal            expresion6;
non terminal            expAutoincremento;

non terminal            sentencias;
non terminal            sentencia;
non terminal            sentenciaDevuelve;
non terminal            sentenciaSalida;
non terminal            sentenciaAsignacion;
non terminal            sentenciaSuma;
non terminal            sentenciaAutoincremento;
non terminal            cadenaSalida;
non terminal            sentenciaSalidaEnt;
non terminal            cadenaSalidaEnt;
non terminal            tipoReferencia;

non terminal            funcionPrincipal;
// ...


// Declaracion de relaciones de precedencia
precedence left         PLUS, MULT, MENOR, AND, NOT, AUTOINCREMENTO, IGUAL, COMA, ABRIR_BRACKET, 
                        CERRAR_BRACKET, ABRIR_PARENTESIS, CERRAR_PARENTESIS;


// Declaración de reglas de produccion


start with program;

program ::= 
  {: 
        syntaxErrorManager.syntaxInfo ("Starting parsing..."); 
   :}
  axiom:ax
  {:        
        syntaxErrorManager.syntaxInfo ("Parsing process ended.");
   :};

axiom ::= funcionPrincipal;
   
epsilon ::= ;

declaraciones ::= declaracionConstantes;

// DECLARACION DE CONSTANTES
declaracionConstantes ::= constantes | epsilon  {: syntaxErrorManager.syntaxInfo ("Reconocida una declaración de CONSTANTE"); :};
constantes ::= constante fconstante;
fconstante ::= constantes | epsilon;
constante ::= CONSTANTE ID DIGITOS PUNTO_COMA;

// DECLARACION DE VARIABLES
declaracionVariables ::= variables | epsilon;
variables ::= tdvariable ftdvariable;
ftdvariable ::= variables | epsilon;
tdvariable ::= tvariable dvariable;
tvariable ::= ENTERO | ID;
dvariable ::= ID Fid;
Fid ::= asigvariable fasigvariable;
fasigvariable ::= PUNTO_COMA | COMA dvariable;
asigvariable ::= ASIGNACION DIGITOS | epsilon;

// DECLARACION DE FUNCIONES
// Funcion principal
funcionPrincipal ::= declaraciones VACIO PRINCIPAL ABRIR_PARENTESIS CERRAR_PARENTESIS ABRIR_LLAVE declaracionVariables sentencias CERRAR_LLAVE;

// EXPRESIONES
expresion ::= DIGITOS | ID | expresion2;
expresion2 ::= expresion PLUS expresion | expresion3;
expresion3 ::= expresion IGUAL expresion | expresion4;
expresion4 ::= expresion MULT expresion | expresion5;
expresion5 ::= expAutoincremento | expresion6;
expresion6 ::= ABRIR_PARENTESIS expresion CERRAR_PARENTESIS;

// Expresión vectorial
vector ::= ID ABRIR_BRACKET expresion CERRAR_BRACKET;

// Expresión autoincremento
expAutoincremento ::= tipoReferencia AUTOINCREMENTO;


// SENTENCIAS
sentencias ::= sentencia sentencias | epsilon;
sentencia ::= sentenciaDevuelve
            | sentenciaSalidaEnt
            | sentenciaSalida
            | sentenciaAsignacion
            | sentenciaSuma
            | sentenciaAutoincremento;

// SENTENCIA DEVUELVE
sentenciaDevuelve ::= DEVUELVE PUNTO_COMA;

// SENTENCIA SALIDA
sentenciaSalida ::= ESCRIBE ABRIR_PARENTESIS cadenaSalida CERRAR_PARENTESIS PUNTO_COMA {: syntaxErrorManager.syntaxInfo ("Reconocida una sentencia de SALIDA"); :};
cadenaSalida ::= CADENA | epsilon;
sentenciaSalidaEnt ::= ESCRIBE_ENT ABRIR_PARENTESIS cadenaSalidaEnt CERRAR_PARENTESIS PUNTO_COMA;
cadenaSalidaEnt ::= expresion | epsilon;

// SENTENCIA ASIGNACION
sentenciaAsignacion ::= tipoReferencia ASIGNACION expresion PUNTO_COMA;
tipoReferencia ::= vector | ID;

// SENTENCIA ASIGNACION CON SUMA
sentenciaSuma ::= tipoReferencia ASIGNACION_CON_SUMA expresion PUNTO_COMA;

// SENTENCIA AUTOINCREMENTO
sentenciaAutoincremento ::= expAutoincremento PUNTO_COMA;

冲突原因分析 #

冲突本质是语法歧义：ID既可以作为自定义类型名匹配tvariable ::= ID，也可以作为变量名出现在其他规则中。同时，规则中大量嵌套的epsilon可选分支（比如ftdvariable、fconstante）让parser在遇到ID时，无法判断应该归约epsilon结束当前分支，还是移进ID来匹配自定义类型。

具体修改方案 #

方案1：重构变量声明规则，消除结构歧义 #

把变量声明的递归可选结构改为更清晰的迭代式结构，明确类型和变量的位置关系，去掉多余的epsilon分支：

替换原来的变量声明相关规则：

// DECLARACION DE VARIABLES
declaracionVariables ::= variables | epsilon;
variables ::= tdvariable ftdvariable;
ftdvariable ::= variables | epsilon;
tdvariable ::= tvariable dvariable;
tvariable ::= ENTERO | ID;
dvariable ::= ID Fid;
Fid ::= asigvariable fasigvariable;
fasigvariable ::= PUNTO_COMA | COMA dvariable;
asigvariable ::= ASIGNACION DIGITOS | epsilon;

改为：

// DECLARACION DE VARIABLES
declaracionVariables ::= variables | epsilon;
// 一个类型后跟一组变量（以分号结尾），支持多组声明
variables ::= tvariable variable_list PUNTO_COMA | tvariable variable_list PUNTO_COMA variables;
// 变量列表：单个变量或多个变量用逗号分隔，每个变量可带初始化
variable_list ::= ID asigvariable | ID asigvariable COMA variable_list;
tvariable ::= ENTERO | ID;
asigvariable ::= ASIGNACION DIGITOS | epsilon;

重构后，parser能明确识别：tvariable（内置/自定义类型）后面必须跟变量列表，结构无歧义，彻底解决移进/归约冲突。

方案2：简化递归可选分支 #

如果不想大幅重构，可先简化递归中的epsilon使用，减少状态混淆：

把原来的：

variables ::= tdvariable ftdvariable;
ftdvariable ::= variables | epsilon;

改为：

variables ::= tdvariable | tdvariable COMA variables;

同时调整tdvariable的结尾规则，确保每个声明以分号结束，避免和其他分支混淆。

方案3：语义辅助验证（可选） #

如果语法层面无法完全覆盖所有场景，可在parser的action代码中加入语义检查：当归约tvariable ::= ID时，查询符号表确认该ID是否已被定义为自定义类型，若未定义则抛出语义错误。但此方法需先解决语法冲突，仅作为补充验证。

验证修改 #

修改后重新生成parser，测试以下场景：

1. 内置类型变量声明：ENTERO x;
2. 自定义类型变量声明：MiTipo y;
3. 多变量声明：ENTERO a = 5, b; MiTipo c, d = 10;

确保所有场景都能正确解析，且无移进/归约冲突。

内容的提问来源于stack exchange，提问作者Aarón