Translating a while statement from c to assembly using yacc

Question

I'm trying to write a yacc source file for a program that will convert a simple while statement from C language (let's say ANSI 89) to assembly at&t. The following is my grammar, the central part of yacc file.

%%
while_statement     :   'w' 'h' 'i' 'l' 'e' '(' control_statement ')' '{'  block '}'
{printing of the assembly code;}
control_statement   :   expression '>' expression   { $$ = strcat(write exp jg back,) ;}
        |   expression '<' expression   { $$ = strcat(write exp jl back,) ;}
        |   expression '==' expression  { $$ = strcat(write exp je back,) ;}
        |   expression '<=' expression  { $$ = strcat(write exp jle back,) ;}
        |   expression '>=' expression  { $$ = strcat(write exp jge back,) ;}
        |   expression '!=' expression  { $$ = strcat(write exp jne back,) ;}
        |   expression { $$ = $1;}

block           :   expression ';'
        |   block expression ';'

expression      :       expression '+' expression   { $$ = $1 + $3;}
        |       expression '-' expression   { $$ = $1 - $3;}
        |       expression '*' expression   { $$ = $1 * $3;}
        |       expression '/' expression   { if($3 == 0)
                                yyerror("divide by zero");
                              else
                                $$ = $1 / $3;}
        |       '-' expression          { $$ = -$2;}
        |       '(' expression ')'      { $$ = $2;}
        |   string '=' expression       { create new variable called string with expression value }
        |       number              { $$ = $1;}

string          :   letter {$$ = $1;}
        |   string letter {strcat($$, ??;}

letter          :   A {strcat($$, 'A');}
        .........

number          :   digit       { $$ = $$ + $1;}
        |       number digit    { $$ = ($1 * 10) + $2;}

digit   : '0' {$$ = 0;}
| '1' {$$ = 1;} 
| '2' {$$ = 2;}
| '3' {$$ = 3;}
| '4' {$$ = 4;}
| '5' {$$ = 5;}
| '6' {$$ = 6;}
| '7' {$$ = 7;}
| '8' {$$ = 8;}
| '9' {$$ = 9;}     
%%

My question is: wich kind of function I'm supposed to use to concatenate the values for the final string? Or which kind of data types, struct, union, etc. I should use? Thanks in advance for the answers.

Answer 1

Well, for a while loop, what you want is something like:

start-label:
code to evaluate condition
conditional branch if-false to end-label
code for the body of the loop
unconditional branch to start-label
end-label:

So in your pseudo code, that would look something like:

while_statement: WHILE '(' condition ')' '{' block '}'
    { $$ = concatenate("start-label:", $3, "jfalse end-label", $6, "jmp start-label", "end-label:"); }

where concatenate is whatever you're using to build strings out of a bunch of other strings.

That's assuming you're building up your assembly code by concatenating strings together (which is what its seems like you're trying to do from your pseudo-code.) Also, if you want to allow for more than a single loop, you'll need to create unique labels to use for each, rather than using fixed strings.

Answer 2

Hmm.
As far as I understand your grammer, you are at the very beginning of using yacc. For that, it is not bad, so I give you just some hints whow to proceed...
a. You are aware, that currently all your expressions can only be constant, because you are evaluating them at compile-time, e.g. you write in the plus-case {$$ = $1 + $3}, and this expression is evaluated while yacc is running. If you want this to be evaluated at runtime, you need to emit the correct assembler instrutions like {emit ("add", allocReg(), $1, $3);} where this to-be-written function emit could at the beginning just expect register names in $1 and $3.
b. Then if you would change the action in the number-case to load the number into a register (for which you need to do some housekeeping), that is, the action for a number would be

{reg=allocReg();
 emit ("mov", reg, $$);
}

(of course you need to free all allocated Registers when they are no longer used, e.g. after they have been used in an add-operation as summands).
c. Before you can do your jump on conditions, you need so emit some compare instructions. to compare, e.g. cmp $1, $3
d. When using yacc, you transport data 'upwards' by assigning them to $$, and use $1...$n produced by other rules. This data can have different types, depending on the rules. So your idea of using a union for that is a way to do that (all goes somewhere in your grammar-file):

typedef union {
  int                number;
  char               singleChar;
  VarName            *var;
  ...
} dataVariant;
#undef YYSTYPE
#define YYSTYPE dataVariant

with this you can write in your grammar something like $$.number=$1.number. There is also a %union-construct inside yacc which is more comfortable, you can read something about it there: Lex and YACC primer