コンパイラ実践一の加算スタックコンピュータ
4175 ワード
次は簡単な小型加算スタック計算機です
#include <stdio.h>
#include <stdlib.h>
///////////////////////////////////////////////
// Data structures for the Sum language.
enum Exp_Kind_t {EXP_INT, EXP_SUM};
struct Exp_t
{
enum Exp_Kind_t kind;
};
struct Exp_Int
{
enum Exp_Kind_t kind;
int i;
};
struct Exp_Sum
{
enum Exp_Kind_t kind;
struct Exp_t *left;
struct Exp_t *right;
};
// "constructors"
struct Exp_t *Exp_Int_new (int i)
{
struct Exp_Int *p = (Exp_Int *)malloc (sizeof(Exp_Int));
p->kind = EXP_INT;
p->i = i;
return (struct Exp_t *)p;
}
struct Exp_t *Exp_Sum_new (struct Exp_t *left, struct Exp_t *right)
{
struct Exp_Sum *p = (Exp_Sum *) malloc (sizeof(Exp_Sum));
p->kind = EXP_SUM;
p->left = left;
p->right = right;
return (struct Exp_t *)p;
}
// "printer"
void Exp_print (struct Exp_t *exp)
{
switch (exp->kind){
case EXP_INT:{
struct Exp_Int *p = (struct Exp_Int *)exp;
printf ("%d", p->i);
break;
}
case EXP_SUM:{
struct Exp_Sum *p = (struct Exp_Sum *)exp;
Exp_print (p->left);
printf ("+");
Exp_print (p->right);
break;
}
default:
break;
}
}
//////////////////////////////////////////////
// Data structures for the Stack language.
enum Stack_Kind_t {STACK_ADD, STACK_PUSH};
struct Stack_t
{
enum Stack_Kind_t kind;
};
struct Stack_Add
{
enum Stack_Kind_t kind;
};
struct Stack_Push
{
enum Stack_Kind_t kind;
int i;
};
// "constructors"
struct Stack_t *Stack_Add_new ()
{
struct Stack_Add *p = (Stack_Add *)malloc (sizeof(Stack_Add));
p->kind = STACK_ADD;
return (struct Stack_t *)p;
}
struct Stack_t *Stack_Push_new (int i)
{
struct Stack_Push *p = (Stack_Push *)malloc (sizeof(Stack_Push));
p->kind = STACK_PUSH;
p->i = i;
return (struct Stack_t *)p;
}
/// instruction list
struct List_t
{
struct Stack_t *instr;
struct List_t *next;
};
struct List_t *List_new (struct Stack_t *instr, struct List_t *next)
{
struct List_t *p = (List_t *)malloc (sizeof (List_t));
p->instr = instr;
p->next = next;
return p;
}
// "printer"
void List_reverse_print (struct List_t *list)
{
if(list == NULL)
return ;
List_reverse_print(list->next) ;
if(list->instr->kind == STACK_PUSH)
{
printf("PUSH %d
",((Stack_Push *)(list->instr))->i) ;
}
else
{
puts("ADD") ;
}
}
//////////////////////////////////////////////////
// a compiler from Sum to Stack
struct List_t *all = 0;
void emit (struct Stack_t *instr)
{
all = List_new (instr, all);
}
void compile (struct Exp_t *exp)
{
switch (exp->kind){
case EXP_INT:{
struct Exp_Int *p = (struct Exp_Int *)exp;
emit (Stack_Push_new (p->i));
break;
}
case EXP_SUM:{
// TODO();
Exp_Sum * t = (Exp_Sum *)exp ;
compile(t->left) ;
compile(t->right) ;
emit(Stack_Add_new()) ;
break;
}
default:
break;
}
}
//////////////////////////////////////////////////
// program entry
int main()
{
printf("Compile starting
");
// build an expression tree:
// +
// / \
// + 4
// / \
// 2 3
struct Exp_t *exp = Exp_Sum_new (Exp_Sum_new(Exp_Int_new (2)
, Exp_Int_new (3))
, Exp_Int_new (4)); //Exp_Sum_new(Exp_Int_new(4),NULL) ;
// print out this tree:
printf ("the expression is:
");
Exp_Sum *p = (Exp_Sum *) exp ;
if(p->left == NULL)
{
printf("%d
",((Exp_Int *)(p->right))->i) ;
printf("PUSH %d
",((Exp_Int *)(p->right))->i) ;
}
else if(p->right == NULL)
{
printf("%d
",((Exp_Int *)(p->left))->i) ;
printf("PUSH %d
",((Exp_Int *)(p->left))->i) ;
}
else
{
Exp_print (exp);
// compile this tree to Stack machine instructions
puts("") ;
compile (exp);
// print out the generated Stack instructons:
List_reverse_print (all);
}
printf("
Compile finished
");
return 0;
}