Search code examples
parsingyacclex

Yacc shift/reduce that I cannot identify

So I am having this .y file on which I am trying to parse and evaluate a function with it's parameters, but a have one shift/reduce conflict that I cannot identify:

.y

%{
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include "types.h"
#define YYDEBUG 0
/* prototypes */
nodeType *opr(int oper, int nops, ...);
nodeType *id(int i);
nodeType *con(int value);
void freeNode(nodeType *p);
void yyerror(char *s);

nodeType *RadEc;
int sym[26]; /* symbol table */

%}

%union {
  int iValue;      /* integer value */
  char sIndex;     /* symbol table index */
  nodeType *nPtr;  /* node pointer */
};

%token <iValue> INTEGER 
%token <sIndex> VARIABLE
%token WHILE IF PRINT SUBRAD ENDSUB THEN DO ENDIF RAD
%nonassoc IFX
%nonassoc ELSE

%left GE LE EQ NE '>' '<'
%left '+' '-'
%left '*' '/'
%nonassoc UMINUS

%type <nPtr> statement expr stmt_list
%type <iValue> expresie
%start      program

%%

program   : declaratii cod         { exit(0); }
          ;

declaratii: SUBRAD stmt_list ENDSUB   { RadEc=$2; }
          | /* NULL */
          ;

statement : '\n'                    { $$ = opr(';', 2, NULL, NULL); }
          | expr '\n'                   { $$ = $1; }
          | PRINT expr '\n'             { $$ = opr(PRINT, 1, $2); }
          | VARIABLE '=' expr '\n'          { $$ = opr('=', 2, id($1), $3); }
          | DO stmt_list WHILE expr         { $$ = opr(WHILE, 2, $4, $2); }
          | IF expr THEN stmt_list ENDIF %prec IFX  { $$ = opr(IF, 2, $2, $4); }
          | IF expr THEN stmt_list ELSE stmt_list ENDIF { $$ = opr(IF, 3, $2, $4, $6); }
          ;

stmt_list : statement
          | stmt_list statement   { $$ = opr(';', 2, $1, $2); }
          ;

expr      : INTEGER               { $$ = con($1); }
          | VARIABLE              { $$ = id($1); }
          | '-' expr %prec UMINUS { $$ = opr(UMINUS, 1, $2); }
          | expr '+' expr         { $$ = opr('+', 2, $1, $3); }
          | expr '-' expr         { $$ = opr('-', 2, $1, $3); }
          | expr '*' expr         { $$ = opr('*', 2, $1, $3); }
          | expr '/' expr         { $$ = opr('/', 2, $1, $3); }
          | expr '<' expr         { $$ = opr('<', 2, $1, $3); }
          | expr '>' expr         { $$ = opr('>', 2, $1, $3); }
          | expr GE expr          { $$ = opr(GE, 2, $1, $3); }
          | expr LE expr          { $$ = opr(LE, 2, $1, $3); }
          | expr NE expr          { $$ = opr(NE, 2, $1, $3); }
          | expr EQ expr          { $$ = opr(EQ, 2, $1, $3); }
          | '(' expr ')'          { $$ = $2; }
          ;


cod   : '.'          {exit(0);}
      | instruc '\n' cod
      ;


instruc   : '\n'
      | PRINT expresie              {printf("%d\n",$2);}
      | VARIABLE '=' expresie           {sym[$1]=$3;}
      | RAD'('expresie','expresie','expresie')'     {sym[0]=$3; sym[1]=$5; sym[2]=$7; ex(RadEc);}
      ;


expresie  : INTEGER         { $$ = $1; }
          | VARIABLE            { $$ = sym[$1]; }
          | '-' expresie %prec UMINUS   { $$ = -$2; }
          | expresie '+' expresie   { $$ = $1+$3; }
          | expresie '-' expresie   { $$ = $1-$3; }
          | expresie '*' expresie   { $$ = $1*$3; }
          | expresie '/' expresie   { $$ = $1/$3; }
          | expresie '<' expresie   { $$ = $1<$3; }
          | expresie '>' expresie   { $$ = $1>$3; }
          | expresie GE expresie    { $$ = $1>=$3; }
          | expresie LE expresie    { $$ = $1<=$3; }
          | expresie NE expresie    { $$ = $1!=$3; }
          | expresie EQ expresie    { $$ = $1==$3; }
          | '(' expresie ')'        { $$ = $2; }
          ;

%%

nodeType *con(int value) 
{ 
  nodeType *p; 

  /* allocate node */ 
  if ((p = malloc(sizeof(conNodeType))) == NULL) 
    yyerror("out of memory"); 
  /* copy information */ 
  p->type = typeCon; 
  p->con.value = value; 
  return p; 
} 

nodeType *id(int i) 
{ 
  nodeType *p; 
  /* allocate node */ 
  if ((p = malloc(sizeof(idNodeType))) == NULL) 
    yyerror("out of memory"); 
  /* copy information */ 
  p->type = typeId; 
  p->id.i = i; 
  return p; 
} 

nodeType *opr(int oper, int nops, ...) 
{ 
  va_list ap; 
  nodeType *p; 
  size_t size; 
  int i; 

  /* allocate node */ 
  size = sizeof(oprNodeType) + (nops - 1) * sizeof(nodeType*); 
  if ((p = malloc(size)) == NULL) 
    yyerror("out of memory"); 
  /* copy information */
  p->type = typeOpr; 
  p->opr.oper = oper; 
  p->opr.nops = nops; 
  va_start(ap, nops); 
  for (i = 0; i < nops; i++) 
    p->opr.op[i] = va_arg(ap, nodeType*); 
  va_end(ap); 

  return p; 
}

void freeNode(nodeType *p) 
{ 
  int i; 

  if (!p) 
    return; 
  if (p->type == typeOpr) { 
    for (i = 0; i < p->opr.nops; i++) 
      freeNode(p->opr.op[i]); 
  } 
  free (p); 
} 

int ex(nodeType *p) 
{ 
  if (!p) 
    return 0; 

  switch(p->type) 
    { 
    case typeCon: return p->con.value; 
    case typeId: return sym[p->id.i]; 
    case typeOpr: switch(p->opr.oper) 
                    { 
            case WHILE: while(ex(p->opr.op[0])) 
                           ex(p->opr.op[1]); 
                        return 0; 
            case IF: if (ex(p->opr.op[0])) 
                        ex(p->opr.op[1]); 
                     else if (p->opr.nops > 2) 
                         ex(p->opr.op[2]); 
                     return 0; 
            case PRINT: printf("%d\n", ex(p->opr.op[0])); 
                        return 0; 
            case ';': ex(p->opr.op[0]); 
                      return ex(p->opr.op[1]); 
            case '=': return sym[p->opr.op[0]->id.i] = ex(p->opr.op[1]); 
            case UMINUS: return -ex(p->opr.op[0]); 
            case '+': return ex(p->opr.op[0]) + ex(p->opr.op[1]); 
            case '-': return ex(p->opr.op[0]) - ex(p->opr.op[1]); 
            case '*': return ex(p->opr.op[0]) * ex(p->opr.op[1]); 
            case '/': return ex(p->opr.op[0]) / ex(p->opr.op[1]); 
            case '<': return ex(p->opr.op[0]) < ex(p->opr.op[1]); 
            case '>': return ex(p->opr.op[0]) > ex(p->opr.op[1]); 
            case GE: return ex(p->opr.op[0]) >= ex(p->opr.op[1]); 
            case LE: return ex(p->opr.op[0]) <= ex(p->opr.op[1]); 
            case NE: return ex(p->opr.op[0]) != ex(p->opr.op[1]); 
            case EQ: return ex(p->opr.op[0]) == ex(p->opr.op[1]); 
            } 
    } 
}

void yyerror(char *s) 
{ 
  fprintf(stdout, "%s\n", s); 
} 

int main(void) 
{
#if YYDEBUG
  yydebug = 1;
#endif
  yyparse();
  return 0; 
}

I tried different ways to see were am I losing something, but I am pretty new at this and still cannot figure it out very well the conflicts.

Any help much appreciated.

Solution

  • Your grammar allows statements to be expressions and it allows two statements to appear in sequence without any separator.

    Now, both of the following are expressions:

    a
-1

    Suppose they appear like that in a statement list. How is that different from this single expression?

    a - 1

    Ambiguity always shows up as a parsing conflict.

    By the way, delimited if statements (with an endif marker) cannot exhibit the dangling else ambiguity. The endif bracket makes the parse unambiguous. So all of the precedence apparatus copied from a different grammar is totally redundant here.