Problem with right recursive rules with Bison

Question

I have implemented with bison the management of a multidimensional array this piece of code works, using the left recursive rules however. The manual indicates that it is preferable to use those on the right. link : Bison Recursive Rules

now, however, if I use the right rule, the array is not parsed correctly. the problem is that when I use the right rule, the internal array a[2,3] returns 4 dimensions instead of 2 and the other array x[,] have no dimension.

my question is : why this piece of code does not work with right recursive rule ?

incorrect recursive erroneous rule:

argList
    : expr              {stackNode [ kstack++ ] = $1 ;  }
    | argList ',' expr  {stackNode [ kstack++ ] = $3 ;  }

sample source:

xy[1, a[2,3] ] =  4  ;

grammar of bison:

argList
    : expr              {stackNode [ kstack++ ] = $1 ;  }
    | expr ',' argList  {stackNode [ kstack++ ] = $1 ;  }
;   

statement                                                
    : tPV
    | expr tPV  { $$=$1; } 
;

expr
    : tINTEGER                  { $$ = new_tINTEGER ( $1 ) ;    }
    | tID '[' argList ']'
    {   
        void** n=(void**) malloc ( sizeof(void**)*kstack ) ;    
        for(int j=0,  i=kstack-1    ;   i>=0    ;   i-- )   n[j++] = (void*) stackNode[i] ;
        $$ = new_tArrayArgList ( $1,kstack,n ) ;
        kstack=0;
    }   
    | expr tEQ      expr            { $$ = new_tBINOP ( tEQ,$1,$3) ;    /*  =   */} 

reference link:

How to build an Array with Bison/Yacc and a Recursive Rule

Left Recursive Rules in Context Free Grammar

Regards Claudio

Answer 1

The problem is that you use the global varaibles stackNode and kstack to track argument lists. This is not reentrant, so when you have nested argument lists, processing the inner list absorbs and corrupts the state of the outer list, resulting in garbage. This is independent of left- vs right- recursion, though the two cases will show different corruption.

The solution is to not use globals -- return the necessary values in $$:

argList
    : expr              { $$ = new_empty_deque();
                          push_back($$, $1);  }
    | expr ',' argList  { $$ = $3; push_front($$, $1); }
;   

alternately (and superior), use a left-recursive rule:

argList
    : expr              { $$ = new_empty_deque();
                          push_back($$, $1);  }
    | argList ',' expr  { $$ = $1; push_back($$, $3); }
;