parsingcompiler-constructionbisonyacc

Yacc - Rules are never reduced, why is it?


I am learning to work with YACC and there are some errors that, although I think I know what may cause them, I can't solve. The errors that I get are: -Useless nonterminal -Useless rule

For what I have read in other posts this is due to the rules not being reachable, but after checking it again I'm not able to see the problem. For what I see all the "rules" appear on both sides.

%{

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

extern int nLineas;

void yyerror(const char* msg) {
    fprintf(stderr, "%s\n", msg);
}
int yylex(void);
FILE *yyin;

%}

%start programa

%union {
    int tipo;
    char nombre[30];
}

%token <tipo> NUM
%token CARACTER
%token CADENA
%token <nombre> ID
%token INT
%token DOUBLE
%token CHAR
%token FLOAT
%token IF
%token MAIN
%token ELSE
%token SCANF
%token PRINTF
%token DEFINE
%token INCLUDE
%token FOR
%token WHILE
%token DO
%token IGUAL
%token DIFERENTE
%token MAYOR
%token MENOR
%token ESIGUAL
%token ESDIFERENTE
%token MAYORIGUAL
%token MENORIGUAL
%token '(' ')'

%left '+' '-'
%left '*' '/' '<' '>'
//%left ">=" "<=" "==" "!=" "&&" "||" "!"
%left UNARIO

%%
//PROGRAMA
programa: DECLARACIONCONSTANTES DECLARACIONVARIABLES FUNCIONMAIN {printf("\nTodo correcto numero de lineas %d.\n",nLineas);}
    ;
//SECCIONES DEL PROGRAMA
//Declaracion de constantes
DECLARACIONCONSTANTES:          /*Vacia*/
                            |DECLARACIONCONSTANTE
                            DECLARACIONCONSTANTES
                            ;
DECLARACIONCONSTANTE:           '#' DEFINE ID NUM {printf("\nDeclaracion constante númerica.\n\n");}
                                |'#' DEFINE ID '"' CADENA '"' {printf("\nDeclaracion constante cadena.\n\n");}
                                //'#' DEFINE ID "'"  "'" {printf("Declaracion constante cadena.\n");} Ver como hacer letra sin que lo incluyan en otro tipo
                                ;

//Declaracion de variables
DECLARACIONVARIABLES:           /*Vacia*/
                                |DECLARACIONVARIABLE
                                DECLARACIONVARIABLES
                                ;
DECLARACIONVARIABLE:            INT ID ';' {printf("\nDeclaracion variable int.\n\n");}
                                |FLOAT ID ';' {printf("\nDeclaracion de variable float.\n\n");}
                                |CHAR ID ';' {printf("\nDeclaracion de variable char.\n\n");}
                                |CHAR ID '[' NUM ']' ';' {printf("\nDeclaracion de variable cadena de caracteres.\n\n");}
                                ;

//Funcion Main



FUNCIONMAIN:                    CABECERAMAIN '{' DECLARACIONVARIABLES INSTRUCCIONES '}'
                                ;
            
CABECERAMAIN:                   MAIN '(' ')' {printf("\nCabecera main.\n\n");}
                                ;

INSTRUCCIONES:                  /*Vacio*/
                                |INSTRUCCION
                                INSTRUCCIONES
                                ;
                
INSTRUCCION:                    DECLARACIONVARIABLES
                                |ID '+' '+' ';' {printf("\nInstruccion -> incremento.\n\n");}
                                |ID '-' '-' ';' {printf("\nInstruccion -> decremento.\n\n");}
                                |ASIGNACION
                                |VISUALIZACION
                                |CONDICIONAL
                                |MIENTRAS
                                |LECTURA
                                |EXPRESION
                                ;

CONDICIONAL:                    IF '(' EXPRESION ')' '{' INSTRUCCIONES '}' {printf("\nInstruccion condicional -> estructura if.\n\n");}
                                |IF '(' EXPRESION ')' '{' INSTRUCCIONES '}' ELSE '{' INSTRUCCIONES '}' {printf("\nInstruccion condicional -> estructura if/else.\n\n");}
                                ;
        
MIENTRAS:                       WHILE '(' EXPRESION ')' '{' INSTRUCCIONES '}' {printf("\nInstruccion condicional mientras -> estructura while.\n\n");}

ASIGNACION:                     ID IGUAL NUM ';' {printf("\nInstrucción de asignacion: idVariable ->expresion numerica.\n\n");}
                                |ID IGUAL CADENA ';' {printf("\nInstrucción de asignación: idVariable -> cadena.\n\n");}
                                //|ID '=' '"'  '"' {printf("Instrucción de asignación: idVariable -> cadena\n");} Ver como hacer letra sin que lo incluyan en otro tipo
                                ;
            
VISUALIZACION:                  PRINTF '(' ID ')' ';' {printf("\nInstruccion de visualizacion -> printf de una variable.\n\n");}
                                |PRINTF '(' CADENA ')' ';' {printf("\nInstruccion de visualizacion -> printf de una cadena.\n\n");}
                                ;
                
LECTURA:                        SCANF '(' VARIABLE ')' ';' {printf("\nInstruccion  de lectura -> scanf.\n\n");}

EXPRESION:                      VARIABLE OP_BOOLEANOS VARIABLE {printf("\nExpresion -> booleana.\n\n");}
                                |VARIABLE OP_NUMERICOS VARIABLE {printf("\nExpresion -> numerica.\n\n");}
                                ;

VARIABLE:                       TERM VARIABLE
                                ;

TERM:                           NUM
                                |CADENA
                                |ID
                                |OP_NUMERICOS
                                |OP_BOOLEANOS
                                |','
                                |'('
                                |')'
                                ;
    
OP_BOOLEANOS:                   '&&'
                                |'||'
                                |IGUAL
                                |DIFERENTE
                                |MAYOR
                                |MENOR
                                |ESIGUAL
                                |ESDIFERENTE
                                |MAYORIGUAL
                                |MENORIGUAL
                                ;

OP_NUMERICOS:                   '+'
                                |'-'
                                |'*'
                                |'/'
                                ;
                
                            
%%

int main()
{
    yyin = fopen("Pruebas.c", "r");
    if(yyin == NULL){
        printf("ERROR de apertura de fichero.\n");
        return 1;
    }
    yyparse();
    return 0;
}

This are some of the errors shown in the terminal.

yacc.y: warning: 8 useless nonterminals and 33 useless rules
yacc.y:93.1-11: warning: useless nonterminal: CONDICIONAL
yacc.y:97.1-8: warning: useless nonterminal: MIENTRAS
yacc.y:108.1-7: warning: useless nonterminal: LECTURA
yacc.y:93.40-48: warning: useless nonterminal: EXPRESION
yacc.y:108.43-50: warning: useless nonterminal: VARIABLE
yacc.y:114.33-36: warning: useless nonterminal: TERM
yacc.y:110.42-53: warning: useless nonterminal: OP_BOOLEANOS
yacc.y:111.43-54: warning: useless nonterminal: OP_NUMERICOS
yacc.y:93.33-135: warning: useless rule: CONDICIONAL: IF '(' EXPRESION ')' '{' INSTRUCCIONES '}'
yacc.y:94.34-168: warning: useless rule: CONDICIONAL: IF '(' EXPRESION ')' '{' INSTRUCCIONES '}' ELSE '{' INSTRUCCIONES '}'
yacc.y:97.33-150: warning: useless rule: MIENTRAS: WHILE '(' EXPRESION ')' '{' INSTRUCCIONES '}'

Solution

  • These all come from the rule

    VARIABLE: TERM VARIABLE ;
    

    Since there's no base case for VARIABLE (no rule that can match something that does not recursively contain another VARIABLE), this rule can never be matched or reduced, which means in turn that every other rule that must contain a VARIABLE can never be reduced.

    If you change this to

    VARIABLE: TERM | TERM VARIABLE ;
    

    then the 'useless' warnings will all go away, but you have a very large number of conflicts (for a variety of reasons).

    You also have a lot of rules that are (pointlessly) right-recursive. For yacc and bison (and LR parsing in general), you should prefer using left-recursive rules, as they are more efficient.