Reputation: 934
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)
Upvotes: 3
Views: 308
Reputation: 126448
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 */
Upvotes: 0
Reputation: 241911
There are two common styles of writing grammars for arithmetic expressions:
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 ')'
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.
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
.
Upvotes: 1