Conflicts in Bison

3
votes

I'm trying to make a small compiler using Bison and Flex, but I constantly shift/reduction errors. I suspect that the problem is about the rule "assignacion" and rules, "booleano", "comparacion", "expresionArit", "termino", "potencia". Probably the grammar is not defined correctly. I looked to solve this by using "%prec" but I have not succeeded.

Then I put the code Bison and errors:

...
%start programa
%token <id> IDENTIFICADOR
%token <intvalue> ENTERO
%token <floatvalue> FLOTANTE
%token <boolvalue> BOOLEANO
%token <stringvalue> CADENA
%token <etiqueta> IF ELSEIF ELSE FOR WHILE DO IN READ WRITE PRINT BREAK CONTINUE PASS EXCEPT TO DOWNTO
%token NL EOF_INS APAR OPAR ACLAU OCLAU
%left OR
%left AND
%nonassoc PEQUENO GRANDE PEQIG GRAIG IGUAL DIFFE
%left MENOS MAS
%left DIVISION_ENTERA DIVISION PRODUCTO MODULO
%right EXPONENTE
%right ASSIGNACIONS
%nonassoc IFX
%nonassoc ELSE

%%
programa : bloques;
bloques : bloque bloques
        | bloque
        ;
bloque : if_sentencia
       | while_sentencia
       | for_sentencia
       | do_sentencia
       | instruccion
       | NL
       ;
if_sentencia : IF expresion ACLAU bloques OCLAU %prec IFX
             | IF expresion ACLAU bloques OCLAU else_sentencia
             ;
else_sentencia : ELSE expresion ACLAU bloques OCLAU
             | ELSEIF expresion ACLAU bloques OCLAU else_sentencia
             ;
while_sentencia: WHILE expresion ACLAU bloques OCLAU
               ;
for_sentencia: FOR APAR assignacion EOF_INS expresion EOF_INS assignacion OPAR ACLAU bloques OCLAU
             ;
do_sentencia: DO ACLAU bloques OCLAU WHILE expresion EOF_INS
            ;
instruccion : expresion EOF_INS;
expresion: expresion OR expresion
         | booleano;
booleano: booleano AND booleano
         | comparacion;
comparacion: comparacion PEQUENO comparacion
         | comparacion GRANDE comparacion
         | comparacion PEQIG comparacion
         | comparacion GRAIG comparacion
         | comparacion IGUAL comparacion
         | comparacion DIFFE comparacion
         | expresionArit
         ;
expresionArit: expresionArit MAS expresionArit
         | expresionArit MENOS expresionArit
         | termino;
termino: termino PRODUCTO termino
         | termino DIVISION termino
         | termino DIVISION_ENTERA termino
         | termino MODULO termino
         | potencia
         ;
potencia: potencia EXPONENTE potencia
         | factor
         ;
factor: ENTERO {printd("INT\n");}
         | FLOTANTE {printd("FLOAT\n");}
         | BOOLEANO {printd("BOOL\n");}
         | CADENA {printd("STRING\n");}
         | APAR expresion OPAR
         | assignacion
         ;
assignacion: variable ASSIGNACIONS expresion {printd("ASSIGNACION");} | variable;
// a=b=c;
variable: IDENTIFICADOR {printd("VARIABLE\n");};
%%
int
yyerror (char const *s)
{
    printf ("%s\n", s);
}
void main(int argc, char *argv[])
{
    extern FILE *yyin;
    ++argv; --argc;
    yyin = fopen( argv[0], "r" );
    yyparse();
}

Errors:

conflictos: 14 desplazamiento(s)/reducción(ones)

I reviewed the output and there are productions that produce the error but nose as solve them.

estado 21

   19 expresion: booleano .
   20 booleano: booleano . AND booleano

    AND  desplazar e ir al estado 38

    AND       [reduce usando la regla 19 (expresion)]
    $default  reduce usando la regla 19 (expresion)


estado 22

   21 booleano: comparacion .
   22 comparacion: comparacion . PEQUENO comparacion
   23            | comparacion . GRANDE comparacion
   24            | comparacion . PEQIG comparacion
   25            | comparacion . GRAIG comparacion
   26            | comparacion . IGUAL comparacion
   27            | comparacion . DIFFE comparacion

    DIFFE    desplazar e ir al estado 39
    IGUAL    desplazar e ir al estado 40
    GRAIG    desplazar e ir al estado 41
    PEQIG    desplazar e ir al estado 42
    GRANDE   desplazar e ir al estado 43
    PEQUENO  desplazar e ir al estado 44

    DIFFE     [reduce usando la regla 21 (booleano)]
    IGUAL     [reduce usando la regla 21 (booleano)]
    GRAIG     [reduce usando la regla 21 (booleano)]
    PEQIG     [reduce usando la regla 21 (booleano)]
    GRANDE    [reduce usando la regla 21 (booleano)]
    PEQUENO   [reduce usando la regla 21 (booleano)]
    $default  reduce usando la regla 21 (booleano)


estado 23

   28 comparacion: expresionArit .
   29 expresionArit: expresionArit . MAS expresionArit
   30              | expresionArit . MENOS expresionArit

    MAS    desplazar e ir al estado 45
    MENOS  desplazar e ir al estado 46

    MAS       [reduce usando la regla 28 (comparacion)]
    MENOS     [reduce usando la regla 28 (comparacion)]
    $default  reduce usando la regla 28 (comparacion)


estado 24

   31 expresionArit: termino .
   32 termino: termino . PRODUCTO termino
   33        | termino . DIVISION termino
   34        | termino . DIVISION_ENTERA termino
   35        | termino . MODULO termino

    MODULO           desplazar e ir al estado 47
    PRODUCTO         desplazar e ir al estado 48
    DIVISION         desplazar e ir al estado 49
    DIVISION_ENTERA  desplazar e ir al estado 50

    MODULO           [reduce usando la regla 31 (expresionArit)]
    PRODUCTO         [reduce usando la regla 31 (expresionArit)]
    DIVISION         [reduce usando la regla 31 (expresionArit)]
    DIVISION_ENTERA  [reduce usando la regla 31 (expresionArit)]
    $default         reduce usando la regla 31 (expresionArit)


estado 25

   36 termino: potencia .
   37 potencia: potencia . EXPONENTE potencia

    EXPONENTE  desplazar e ir al estado 51

    EXPONENTE  [reduce usando la regla 36 (termino)]
    $default   reduce usando la regla 36 (termino)
2
ccompiler-constructionbisonlex

2 Answers

1
votes

Expression syntax

There are two common styles of writing grammars for arithmetic expressions:

1. With precedence declarations.

In this case, we specify the precedence of each operator, starting with the lowest precedence (usually + and −). The higher the precedence, the more tightly the operator binds to its operands. For example, in 3+4*5, the * takes precedence over the +, since the expression is parsed as 3+(4*5).)

In this case, there is only one "expression" non-terminal, and we write all the rules with that single non-terminal:

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

%%

expression: expression "||" expression
          | expression "&&" expression
          | expression "<=" expression
          | expression '+' expression
          | expression '-' expression
  /* etcetera */
          | NUMBER
          | IDENTIFIER
          | '(' expression ')'

2. Explicit (no precedence declarations)

In this style, we write out the rules so that the expressions are unambiguous. In this case, we need a separate non-terminal for each precedence level, but we have no need for precedence declarations. Note that the non-terminals in each production explicitly include only the operators which bind more tightly, in context. In particular, associativity is also encoded, depending on whether the same operator to the left binds more tightly, or the operator to the right binds more tightly:

 expr : expr0

 expr0: expr0 '+' expr1  /* Left associative */
      | expr0 '-' expr1
      | expr1            /* There is always a unit rule */
 expr1: expr1 '*' expr2
      | expr1 '/' expr2
      | expr1 '%' expr2
      | expr2
  /* ... */
 expr3: expr4 "**" expr3 /* Right associative */
      | expr4
 expr4: expr5 "<=" expr5 /* Non-associative */
      | expr5 "==" expr5
      | expr5 "!=" expr5
      | expr5 ">=" expr5
      | expr5 '<'  expr5
      | expr5 '>'  expr5
      | expr5
 expr5: expr5 "&&" expr6
      | expr6
 expr6: expr6 "||" expr7
      | expr7
 expr7: '-' expr7   /* Prefix operator */
      | expr8
 expr8: expr8 '[' expr ']' /* Postfix operator */
      | term
 term : NUMBER | IDENTIFIER | '(' expr ')'

So you can choose either of the above, but you need to choose one or the other. What you have is an uncomfortable mixture, and it confuses both bison and human readers.

If statements

Here, the problem is much simpler. Your grammar allows if statements to be optionally extended with either else or elseif, but your precedence declaration only includes else.

0
votes

When writing an expression grammar, you should either use precedence levels on tokens and have all the rules in expression, or use multiple rules to denote the precedence. You can't really mix-and-match and do it partly one way and partly the other. Here you are trying to use %left/%right to set left/right assocation, and multiple rules to set precedence. You need to decide on one or the other.

To use just precedence declarations, replace all the non-terminals booleano, comparicion, etc with expression everywhere. Then delete the redundant expression: expression rules as these are what cause the conflicts.

To use rules for precedence, change the rules that have the same non-terminal both before and after the operator to use the next-level-down non-terminal on one side to set left or right associativity:

expresion: expresion OR booleano  /* left associative */

comparacion: expresionArit PEQUENO expresionArit   /* non-associative */

potencia: factor EXPONENTE potencia    /* right associative */