Lex & Yacc : efficiently building source tree...

[cman]

 I'm just now finishing the back end of  a small translator ( not for object code , but for source code shells - I thought I would try something easy first  :bg ). I'm looking at some of the code and trying to "clean it up". For a certain source pattern definition I built a linked list of source tree structs , adding each item to the end of the list as it is parsed, as for the generic function pattern definition:

Code Select Expand


directFuncDef:
postFixID textAtom '(' fscList ')' ';' { $$ = makeDirFunctionDef ( $1 , $2 , 0 , $4 , 0) ; }
| postFixID textAtom'<' textAtomList '>' '(' fscList ')' ';' { $$ = makeDirFunctionDef ( $1 , $2 , $4 , $7 , 0 ); }
| printOption postFixID  textAtom'(' fscList ')' ';' { $$ = makeDirFunctionDef ( $2 , $3 , 0 , $5 , $1 ) ; }
| printOption postFixID  textAtom'<' textAtomList '>' '(' fscList ')' ';' { $$ = makeDirFunctionDef ( $2 , $3 , $5 , $8 , $1 ); }
  ;





Anyway , I insert each item at the end of the list using  a loop:

Code Select Expand


parameterList:
           parameter { $$ = $1; }
          | parameterList ',' parameter { $$ = makeAtomPostList ( $1 , $3 ); }



with "makeAtomPostList":

Code Select Expand



sourceNode * makeAtomPostList ( sourceNode * l , sourceNode * r )
{


sourceNode * t = l; //set pointer to the front of the list

while ( t -> next ) //find end of list
t = t -> next;
t -> next = r; //attach the new item

return l;

}





The only other way I think this could be done is to stick the head of the list somewhere and pass the address of the last item through the function ( but where? and how many wheres?? ) :

Code Select Expand



sourceNode * makeAtomPostList ( sourceNode * l , sourceNode * r )
{

//headOfList global

if ( headOfList == 0 ) //list is empty
                {
                     l -> next = r;
                     headOfList = l;
                     return r;
                }
               else
               {
                   l -> next = r;
                   return r;
               }
}





Any suggestions? Hope to start something that can translate to object code when this is done ( been doing the research for this ( I'm to  Parsing in the Dragon Book  :'( ( I got sidetracked with work and my interest in the study of algorithms  :bg ) ). Thanks! :bg

[tenkey]

One way to store the end of a list...

Make the "head pointer" a node instead of just a pointer. Make head.next your list pointer, and make your other field a pointer to the last node.

[cman]

I think I see what your saying. I could add a pointer to the source tree node as well so that insertions to the rear of the list will be constant time . Something like:

Code Select Expand


#include <iostream.h>

struct sourceNode //example source tree node
{
int data; //example data
sourceNode * next; // pointer to next node
sourceNode * rear; //points to rear of list
};

void main()
{

int i = 0;

sourceNode * temp;
sourceNode * list = NULL;

while ( i < 10 )
{
temp = new sourceNode;
if ( ! list ) //enter first node
{
list = temp;
list -> rear = temp;
temp -> data = i;
temp -> next = 0;
}
else //constant time rear insertion!
{
temp -> data = i;
temp -> next = 0;
temp -> rear = 0;
list -> rear -> next = temp;
list -> rear = temp;

}
i ++;
}


sourceNode * s = list;
cout << endl;
while ( s )
{
cout << " " <<  s -> data;
s = s -> next;
}

cout << endl;

}




Thanks for the tips! :U