wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> CS: VARIABLE RENAMER
        
(Message started by: Aaron on Aug 9^th, 2002, 2:30pm)

Title: CS: VARIABLE RENAMER
Post by Aaron on Aug 9^th, 2002, 2:30pm

question:
You are writing a parser that reads a C program and translates all the variable names into new names of the form "VAR######", where ###### is an integer incremented for each unique variable name. Discuss what is needed for the case where the C program already contains a variable of the form "VAR######".

I must not understand the question correctly, since I don't see a difficulty here. the VAR#### originally in the c program will be transformed as well thus no longer there to cause a conflict...

eg.

this program:

void myProg () {
int a, b c;
int VAR01001001 = a + b + c;
printf("%d\n", VAR01001001);
}

will become:

void myProg () {
int VAR001, VAR002, VAR003;
int VAR004 = VAR001 + VAR002 + VAR003;
printf("%d\n", VAR004);
}

the transformation lookup is 1 to 1:

a => VAR001
b => VAR002
c => VAR003
VAR01001001 => VAR004

... or is this problem a lot more complex then I thought?

Title: Re: CS: VARIABLE RENAMER
Post by -D- on Aug 9^th, 2002, 4:36pm

Yes. what if the VAR#### in the original program is say: VAR0001 and it's the 5th variable. By the time you get to the 5th variable and start to rename it, you've already renamed all the first ones VAR0001 and now you have to figure out which of the VAR0001's in the program are the 5th variable and which are the 1st.

One solution is a pre-mangler pass through the file that tacks a "_temp" or similar to all variables of the form VAR#### so that they maintain their uniqueness.
-D-

Title: Re: CS: VARIABLE RENAMER
Post by -D- on Aug 9^th, 2002, 4:40pm

I need to ammend one part. My point was assuming you do a pass for each variable, obviously that's not necessarily ideal.

If you instead took a pass through the file for all variable declarations, put them in a lookup table paired with their new names and then went through the file and replaced all variables as soon as they were encountered you would not have this problem.

Basically the "trick" to the problem (if asked as an interview question for example) is ensuring you state either of these points to show that you considered it a possibility or discounted it as a problem.
-D-

Title: Re: CS: VARIABLE RENAMER
Post by Ankur on Jun 9^th, 2005, 6:00am

I guess i dont understand the issue:

if in the c prog there is something like this

int a, a001;

u convert it into

int a001, a001002;

so how do u map back:

strip the last 3 digits out of the var.

what is the problem?

Title: Re: CS: VARIABLE RENAMER
Post by River Phoenix on Jun 10^th, 2005, 10:07am

when you have
int b;
int a001;

they should be translated to
int a001;
int a002;

Title: Re: CS: VARIABLE RENAMER
Post by Grimbal on Jun 10^th, 2005, 3:48pm

It is like the problem of translating all A's in a text by B and all B's by A. If you first replace all A's by B's and then all B's by A's you are in trouble. But if you do on e pass exchanging all A's and B's, it works. And it is faster.

For the renaming of variables, just parse the whole source as a compiler would do and whenever an identifier is found, if it is the first time, generate and store a name, if not, get the generated name.