YACC grammar for WHILE loop and statements wouldn't work

Question

I am trying to generate intermediate code of the following grammar for while loop and general statements, but I keep encountering syntax error. Though earlier, the grammar for statements and expressions worked, but after adding the production for while loop this program doesn't work.

this is my lex.l file

%{
    #include "y.tab.h"
%}


NUMBER      [0-9]       
ALPHABET    [a-zA-Z]

%%

[\t];
{NUMBER}+   { strcpy(yylval.str, yytext); return ID; }
{ALPHABET}  { strcpy(yylval.str, yytext); return ID; }
"while"     { return WHILE; }
"do"        { return DO; }
"<"     { yylval.symbol=yytext[0]; return OP; }
">"     { yylval.symbol=yytext[0]; return OP; }
"!="        { yylval.symbol=yytext[0]; return OP; }
"=="        { yylval.symbol=yytext[0]; return OP; }
[\n];
.       { return yytext[0]; }

%%

And this is my yacc.y file

%{
    #include <stdio.h>
    #include <string.h>


    char result_gen();
    char quadruple_entry(char a[], char b, char c[]);
    char quadruple_entry_assign(char a[], char b, char c[]);
    char quadruple_entry_loop();
    char quadruple_entry_do();
    void three_address_code();

    int q_index = 0;
    char result[3] = {'t','0','\0'};
    char result2[3] = {'L','0','\0'};
    char temp[3];
    char temp2[3];

    struct QuadrupleStructure {
        char arg1[10];
        char op;
        char arg2[10];
        char rslt[3];
    }quadruple[25];

    
 
%}

%union {
    char str[10];
    char symbol;
}

%token WHILE DO
%token <str> ID
%token <symbol> OP
%type  <str> expr 

%right '='
%left '+' '-'
%left '/' '*'


%%
wstmt   :   WHILE { quadruple_entry_loop(); } stmt  DO { quadruple_entry_do(); }
    ;

stmt    :   ID '=' expr  { quadruple_entry_assign($1, '=', $3); }
    |   ID OP ID { quadruple_entry($1,$2,$3); }
    ;


expr    :   expr '+' expr { quadruple_entry($1, '+', $3); strcpy($$,temp); }

    |   expr '-' expr { quadruple_entry($1, '-', $3); strcpy($$,temp); }

    |   expr '/' expr { quadruple_entry($1, '/', $3); strcpy($$,temp); }

    |   expr '*' expr { quadruple_entry($1, '*', $3); strcpy($$,temp); }

    |   '(' expr ')'  { strcpy($$,$2); }

    |   ID        { strcpy($$,$1); }
    ;

%%




char result_gen() {
    strcpy(temp,result);
    result[1]++;
}


char quadruple_entry(char a[], char b, char c[]) {
    result_gen();

    strcpy(quadruple[q_index].arg1, a);
    quadruple[q_index].op = b;
    strcpy(quadruple[q_index].arg2, c);
    strcpy(quadruple[q_index].rslt, temp);

    q_index++;
}

char quadruple_entry_assign(char a[], char b, char c[]) {
    char tempLocal[3] = {' ',' ','\0'};
    strcpy(quadruple[q_index].arg1, a);
    quadruple[q_index].op = b;
    strcpy(quadruple[q_index].arg2, c);
    strcpy(quadruple[q_index].rslt, tempLocal);

    q_index++;
}

char quadruple_entry_loop() {
    char tempLocal[3];
    strcpy(tempLocal, result2);

    char tempLocal2[] = " if ";
    char tempLocal3 = ' ';
    char tempLocal4[] = " ";
    
    strcpy(quadruple[q_index].rslt, tempLocal);
    strcpy(quadruple[q_index].arg1, tempLocal4);
    quadruple[q_index].op = tempLocal3;
    strcpy(quadruple[q_index].arg2, tempLocal2);
 
    q_index++;  
}

char quadruple_entry_do() {
    char tempLocal[4];
    strcpy(tempLocal, result2);
    tempLocal[3] = ':';
    strcpy(quadruple[q_index].arg1,tempLocal);

    char tempLocal2[] = " ";
    char tempLocal3 = ' ';

    quadruple[q_index].op = tempLocal3;
    strcpy(quadruple[q_index].arg2, tempLocal2);

    q_index++;
    result2[1]++;
    
    char tempLocal4[4];
    strcpy(tempLocal4, result2);
    tempLocal4[3] = ':';
    strcpy(quadruple[q_index].arg1,tempLocal4);

    char tempLocal5[] = " ";
    char tempLocal6 = ' ';

    quadruple[q_index].op = tempLocal6;
    strcpy(quadruple[q_index].arg2, tempLocal5);

    q_index++;
    result2[1]++;
}
     

void three_address_code() {
    int i;
    for(i=0 ; i<q_index ; i++) 
    printf("\n%s := %s %c %s", quadruple[i].rslt, quadruple[i].arg1, quadruple[i].op, quadruple[i].arg2);
}

void yyerror(char *s){
    printf("Errror %s",s);
}

int yywrap() {
    return 1;
}

int main() {
    yyparse();
    three_address_code();
    return 0;
} 

Input:

i=2*5-10
while i<5 do 

Output:

Errror syntax error

If someone can figure out where the grammar is wrong, or if my code is wrong, it'd be very helpful.

Answer 1

In my opinion, your rule

wstmt   :   WHILE { quadruple_entry_loop(); } stmt  DO { quadruple_entry_do(); }
    ;

is wrong. As your stmt only considers assignment expressions, you should include a stmt in the expression for the syntax to be valid.

Your syntax rule for wstmt, without interspersed code is:

wstmt   : WHILE stmt DO ;

you should change it into:

wstmt   :   WHILE  expr  DO stmt ;

and the precise points to do the proper output of code should be:

wstmt: WHILE { 
        /* get a new label and place it at
         * this point, you'll need to jump
         * here, push the label name in a
         * stack */
    }
    expr { 
        /* include code here to evaluate
         * (probably you do it inside expr */
    }
    DO {
        /* get a new label but don't place it
         * yet, and push it's name in the
         * stack */
    }
    stmt {
        /* a jump to the first label you
         * pushed (the one that is already
         * placed), then emit code for the
         * second label (the one that is not
         * placed yet */
    };  

(and you should include possibilities to use the < and > and evaluating boolean operators in the expr syntax, also)

the stmt nonterminal forces what you put as while condition to be an assignment, and this is not what you have written as input.

In my humble opinion, you should implement this compiler in two phases.... first try to do full language parsing (as it is a separate, unrelated, and completely different problem), and once you have the parser making the right syntax tree (you can probe it trying to build the syntax tree proper, and printing it) and once you have it working... then you can intersperse the code generation code.

Answer 2

Your start symbol is wstmt, so the program accepts a single while statement as an input. If you need to accept a sequence of statements, you need a symbol that expands into a sequence of statements as your starting symbol.

In addition, your lexer doesn't swallow spaces, so any program that has spaces has an error.