5.6 Intermediate Representation Output for miniC

Though it is possible to include actions in the yacc grammar of a language to either directly execute a program written in that language (as is done in hoc6) or directly generate a target code, we have taken the option of generating Intermediate Representation (IR) (Chapter 8) in anticipation of discussion of various optimization methods.

Any reasonable IR can be obtained by including proper action terms in the yacc grammar. Here we illustrate a small part of the final grammar with action terms for generating two kinds of IR – reverse polish notation (RPN) and 4-tuple notation. The full grammar with IR generating actions is given in Chapters 8 and 12. Here, we show IR for arithmetic expressions expr and assignment statement asgn.

The following miniC program, test1.miniC was used as an example:

int : a,b,c,d 
a = 3 
b = 5
c = 7
d = a * (b + c)
end

The RPN output was:

AST: 3 
AST: a =
AST: 5
AST: b =
AST: 7 
AST: c =
AST: a
AST: b
AST: c
AST: +
AST: *
AST: d =

The 4-tuple (matrix) output was:

MAT1:  LD	3	T1	––
MAT2:  =	T1	 a	––
MAT3:  LD	5	T2	––
MAT4:  =	T2	 b	––
MAT5:  LD	7	T3	––
MAT6:  =	T3	 c	––
MAT7:  LD	a	T4	––
MAT8:  LD	b	T5	––
MAT9:  LD	c	T6	––
MAT10: ADD	T5	T6	T7
MAT11: MUL	T4	T7	T8
MAT12: =	T8	 d	––

The corresponding action terms in the yacc grammar are:

asgn: VAR ‘=’ expr {printf(″AST: %s =
″, name($1));
      printf(″MAT%d: = T%d %s ––
″, ++mcount,tcount,name($1));tpush(tcount);} 
    | IVAR ‘=‘ expr { printf(″AST: %s =
″, name($1));
      printf(″MAT%d: = T%d %s ––
″, ++mcount,tcount,name($1));tpush(tcount);}

expr: INT {$$ = $1; printf(″AST: %s
″, name($1));
           printf(″MAT%d: LD %s T%d ––
″, ++mcount,name($1),
                                      ++tcount);tpush(tcount);} 
    | NUMBER {$$ = $1; printf(″AST: %s
″, name($1));
           printf(″MAT%d: LD %s T%d ––
″, ++mcount,name($1),
                                      ++tcount);tpush(tcount);}
    | VAR {$$ = $1; printf(″AST: %s
″, name($1));
           printf(″MAT%d: LD %s T%d ––
″, ++mcount,name($1),
                                      ++tcount);tpush(tcount);} 
    | IVAR {$$ = $1; printf(″AST: %s
″, name($1);
            printf(″MAT%d: LD %s T%d ––
″, ++mcount,name($1),
                                      ++tcount);tpush(tcount);} 
    | expr ‘+’ expr { printf(″AST: +
″); $$ = $3;
                   printf(″MAT%d: ADD T%d T%d T%d
″, ++mcount, tpop(), tpop(),
                                              ++tcount);tpush(tcount);} 
    | expr ‘–’ expr { printf(″AST: –
″); $$ = $3;
                  printf(″MAT%d: SUB T%d T%d T%d
″, ++mcount, tpop(), tpop(),
                                             ++tcount) ;tpush(tcount);} 
    | expr ‘*’ expr { printf(″AST: *
″); $$ = $3;
                  printf(″MAT%d: MUL T%d T%d T%d
″, ++mcount, tpop(), tpop(),
                                             ++tcount); tpush(tcount);} 
    | expr ‘/’ expr { printf(″AST: /
″); $$ = $3;
                  printf(″MAT%d: DIV T%d T%d T%d
″, ++mcount, tpop(), tpop(),
                                             ++tcount); tpush(tcount);}

Note that we have inserted the action terms for both RPN and 4-tuples at the same places in the grammar, though the nature of these two IRs is quite different.