warning: rule useless in parser due to conflicts: $@1: /* empty */

0
votes

I have this warning when I put code {printf("something");} in the middle of the rule, if I put at the end of the rule, I don´t have the error and everything works fine.

This throw the warning in the tittle and throw 1 shift/reduce conflict

sent_asig: ID {printf("something");} ASIG exp  {printf("sent_asig: ID ASIG exp \n");}
| ID ASIG CTE_STRING {printf("sent_asig: ID ASIG CTE_STRING \n");}
| ID ASIG CTE_STRING CONCAT ID {printf("sent_asig: ID ASIG CTE_STRING CONCAT ID \n");}
| ID ASIG ID CONCAT CTE_STRING {printf("sent_asig: ID ASIG ID CONCAT CTE_STRING \n");};

And this don't throw the warnings and 0 conflicts, works fine

sent_asig: ID ASIG exp  {printf("sent_asig: ID ASIG exp \n");}
| ID ASIG CTE_STRING {printf("sent_asig: ID ASIG CTE_STRING \n");}
| ID ASIG CTE_STRING CONCAT ID {printf("sent_asig: ID ASIG CTE_STRING CONCAT ID \n");}
| ID ASIG ID CONCAT CTE_STRING {printf("sent_asig: ID ASIG ID CONCAT CTE_STRING \n");};

if somebody wants to see the full rules because is probably in other part the origin of this error, here is

%token ID
%token CTE
%token ABREPAR
%token FINPAREN
%token AND
%token OR
%token COMA
%token ASIG
%token COMP
%token RESTASIG
%token CONCAT
%token SUMASIG
%token MULTASIG
%token DIVASIG
%token MENOR_IGU
%token MENOR
%token MAYOR_IGU
%token MAYOR
%token NOT
%token DIST
%token CTE_REAL
%token CTE_STRING

%token DO
%token IF
%token ENDIF
%token ELSE
%token PUT
%token GET
%token DECLARE
%token ENDDECLARE
%token BEGIN
%token ENDPROGRAM
%token INT
%token REAL
%token STRING
%token REPEAT
%token CONST

%left AND OR
%left OP_SUM OP_RESTA
%left OP_MULT
%left OP_DIV 
%right ASIG
%right SUMASIG 
%right RESTASIG 
%right MULTASIG 
%right DIVASIG 

%% 

programa: BEGIN declar sentencias ENDPROGRAM {printf("programa: BEGIN declar sentencias ENDPROGRAM \n");}
| BEGIN sentencias ENDPROGRAM {printf("programa: BEGIN sentencias ENDPROGRAM \n");};

sentencias: sentencia {printf("sentencia: sentencia \n");}
    |  sentencias sentencia {printf("sentencias: sentencia \n");};
sentencia:  sent_asig {printf("sentencia: sent_asig\n");}
    | sent_mult_asig {printf("sentencia: sent_mult_asig\n");}
    | sent_sum_asig {printf("sentencia: sent_sum_asig");}
    | sent_rest_asig {printf("sentencia: sent_rest_asig \n");}
    | sent_div_asig {printf("sentencia: sent_div_asig \n");}
    | asig_const {printf("sentencia: asig_const \n");}
    | entrada {printf("sentencia: entrada \n");}
    | salida {printf("sentencia: salida \n");}
    | sent_if {printf("sentencia: sent_if \n");}
    | sent_repeat {printf("sentencia: sent_repeat \n");};
sent_asig: ID {printf("something");} ASIG exp  {printf("sent_asig: ID ASIG exp \n");}
    | ID ASIG CTE_STRING {printf("sent_asig: ID ASIG CTE_STRING \n");}
    | ID ASIG CTE_STRING CONCAT ID {printf("sent_asig: ID ASIG CTE_STRING CONCAT ID \n");}
    | ID ASIG ID CONCAT CTE_STRING {printf("sent_asig: ID ASIG ID CONCAT CTE_STRING \n");};
exp:     exp OP_SUM ter {printf("exp: exp OP_SUM ter\n");escribirPolaca("+");}
    | exp OP_RESTA ter {printf("exp: exp OP_RESTA ter\n");escribirPolaca("-");}
    | ter {printf("exp: ter\n");};

ter: ter OP_MULT factor {printf("ter: ter OP_MULT factor\n");escribirPolaca("*");}
    | ter OP_DIV factor {printf("ter: ter OP_DIV factor\n");escribirPolaca("/");}
    | factor {printf("ter: factor\n");};
factor: ID {printf("factor: ID\n"); escribirPolaca(Simbolos[nosalemal][0]);}
    | CTE {printf("factor: CTE\n");escribirPolaca(Simbolos[nosalemal][1]);}
    | CTE_REAL {printf("factor: CTE_REAL \n");escribirPolaca("CTE_REAL");};
    | ABREPAR exp FINPAREN {printf("factor: ABREPAR exp FINPAREN\n");}
sent_sum_asig : ID SUMASIG ID {printf("factor: sent_sum_asig \n");}
    | ID SUMASIG CTE {printf("factor: ID SUMASIG CTE  \n");}
    | ID SUMASIG CTE_REAL {printf("factor: ID SUMASIG CTE_REAL \n");} ;
sent_rest_asig : ID RESTASIG ID {printf("sent_rest_asig: ID RESTASIG ID \n");}
    | ID RESTASIG CTE {printf("sent_rest_asig: ID RESTASIG CTE \n");}
    | ID RESTASIG CTE_REAL {printf("sent_rest_asig: ID RESTASIG CTE_REAL \n");};
sent_mult_asig : ID MULTASIG ID {printf("sent_mult_asig: ID MULTASIG ID \n");}
    | ID MULTASIG CTE {printf("sent_mult_asig: ID MULTASIG CTE \n");}
    | ID MULTASIG CTE_REAL {printf("sent_mult_asig: ID MULTASIG CTE_REAL \n");};
sent_div_asig : ID DIVASIG ID {printf("sent_div_asig: ID DIVASIG ID \n");}
    | ID DIVASIG CTE {printf("sent_div_asig : ID DIVASIG ID \n");}
    | ID DIVASIG CTE_REAL {printf("sent_div_asig: ID DIVASIG ID \n");};
declar: DECLARE declaraciones  ENDDECLARE {printf("declar: DECLARE declaraciones  ENDDECLARE \n");};
declaraciones: dec {printf("declaraciones: dec \n");}
    | dec declaraciones {printf("declaraciones: dec declaraciones \n");};
dec: REAL var {printf("dec: REAL var \n");} 
    | INT var {printf("dec: INT var \n");} 
    | STRING var {printf("dec: STRING var \n");} ; 
var: ID {printf("var: ID \n");}
    | ID COMA var {printf("var: ID COMA var \n");};
asig_const: CONST ID ASIG CTE {printf("asig_const: CONST ID ASIG CTE \n");}
    | CONST ID ASIG CTE_REAL {printf("asig_const: CONST ID ASIG CTE_REAL \n");} 
    | CONST ID ASIG CTE_STRING {printf("asig_const: CONST ID ASIG CTE_STRING \n");};
entrada: PUT CTE_STRING {printf("entrada: PUT CTE_STRING \n");}
    | PUT ID {printf("entrada: PUT ID \n");};
salida: GET ID {printf("salida: GET ID \n");};
sent_if: IF ABREPAR condicion FINPAREN sentencias ENDIF {printf("sent_if: IF ABREPAR condicion FINPAREN sentencias ENDIF \n");}
    | IF ABREPAR condicion FINPAREN sentencias ELSE sentencias ENDIF {printf("sent_if: IF ABREPAR condicion FINPAREN sentencias ELSE sentencias ENDIF \n");}
condicion: cond {printf("condicion: cond \n");}
    | cond AND cond {printf("condicion: cond AND cond\n");}
    | cond OR cond {printf("condicion: cond OR cond \n");}
    | NOT cond {printf("condicion: NOT cond \n");};
cond: exp MENOR exp {printf("cond: exp MENOR exp \n");apilarPilaIteracion(posicionVectorPolaca);escribirPolaca("CMP");posicionVectorPolaca++;}
    | exp MAYOR exp {printf("cond: exp MENOR exp \n");}
    | exp MENOR_IGU exp {printf("cond: exp MENOR exp \n");}
    | exp MAYOR_IGU exp {printf("cond: exp MENOR exp \n");}
    | exp COMP exp {printf("cond: exp MENOR exp \n");escribirPolaca("CMP");}
    | exp DIST exp {printf("cond: exp MENOR exp \n");}
sent_repeat: DO sentencias REPEAT ABREPAR condicion FINPAREN {printf("sent_repeat: DO sentencias REPEAT ABREPAR condicion FINPAREN \n");};
%%

Sorry my bad english (if you can answer in spanish, better)

2
parsingsyntaxbisonyaccshift-reduce-conflict

2 Answers

2
votes

This situation is explained in the bison manual. Basically, using Mid-Rule Actions (MRAs) -- that is, an action in the middle of a rule -- reduces the ability of the parser to defer reduction decisions to the end of the rule. In effect, at that point in the parse, the grammar must be predictable as if it were an LL(1) grammar. For this reason, MRAs should only be used if strictly necessary.

Concretely, consider just the following two alternatives (truncated):

sent_asig: ID {printf("something");} ASIG exp …
         | ID ASIG CTE_STRING …

Now, suppose the parser just recognized an ID and the next token in the input stream is ASIG. At this point, the parser needs to decide whether to perform the MRA { printf("something"); }. Behind the scenes, performing a MRA is the same as reducing a marker non-terminal (a terminal whose right-hand side is empty), so the parser has to decide whether or not to perform a reduction. But it doesn't yet have enough information; the decision cannot be made until it sees whether or not the token following ASIG is CTE_STRING or not. So resolution requires two lookahead tokens.

That's a shift/reduce conflict: the parser cannot decide whether to shift ASIG or reduce the marker (to execute the MRA). Since bison/yacc parsers always resolve shift/reduce conflicts by shifting, the reduction will never happen; the MRA cannot be executed and the right-hand side containing it is effectively blocked. Hence the warning.

Note that you cannot fix the problem by inserting the same MRA at both points:

sent_asig: ID {printf("something");} ASIG exp …
         | ID {printf("something");} ASIG CTE_STRING …

Even though the MRAs are identical, bison/yacc inserts a different marker for the two rules, which would create a reduce/reduce conflict. Reduce/reduce conflicts are resolved by choosing the reduction which appears earlier in the input file, so that resolution would be different from the default resolution in your file, but it would still block one (or more) rules so you would still see the same warning.

If you are only trying to see what the parser is doing, I strongly suggest that you remove all of those printfs, and rely instead on bison's built-in trace facility, which is extremely easy to enable (and disable), and which gives a much more complete view of how the parse is progressing.

0
votes

An elegant way to resolve that kind of conflict, especially when both actions are the same, is to use an empty production with a single action called a subroutine.

subroutine:
  %empty  { prepare_for_local_variables (); }
;

compound:
  subroutine '{' declarations statements '}'
| subroutine '{' statements '}'
;

Here is more info: https://www.gnu.org/software/bison/manual/html_node/Mid_002dRule-Conflicts.html#Mid_002dRule-Conflicts