/* file: “tinyc.c” */

/* Copyright (C) 2001 by Marc Feeley, All Rights Reserved. */

#include

#include

#include

/*

* This is a compiler for the Tiny-C language. Tiny-C is a

* considerably stripped down version of C and it is meant as a

* pedagogical tool for learning about compilers. The integer global

* variables “a” to “z” are predefined and initialized to zero, and it

* is not possible to declare new variables. The compiler reads the

* program from standard input and prints out the value of the

* variables that are not zero. The grammar of Tiny-C in EBNF is:

*

*

*

* “if”

* “while”

* “do”

* “{” {

*

* “;”

*

*

*

*

*

*

*

* Here are a few invocations of the compiler:

*

* % echo “a=b=c=2<3;" | ./a.out
* a = 1
* b = 1
* c = 1
* % echo "{ i=1; while (i<100) i=i+i; }" | ./a.out
* i = 128
* % echo "{ i=125; j=100; while (i-j) if (i

node *paren_expr(); /* forward declaration */

node *term() /*

{ node *x;

if (sym == ID) { x=new_node(VAR); x->val=id_name[0]-‘a’; next_sym(); }

else if (sym == INT) { x=new_node(CST); x->val=int_val; next_sym(); }

else x = paren_expr();

return x;

}

node *sum() /*

{ node *t, *x = term();

while (sym == PLUS || sym == MINUS)

{ t=x; x=new_node(sym==PLUS?ADD:SUB); next_sym(); x->o1=t; x->o2=term(); }

return x;

}

node *test() /*

{ node *t, *x = sum();

if (sym == LESS)

{ t=x; x=new_node(LT); next_sym(); x->o1=t; x->o2=sum(); }

return x;

}

node *expr() /*

{ node *t, *x;

if (sym != ID) return test();

x = test();

if (x->kind == VAR && sym == EQUAL)

{ t=x; x=new_node(SET); next_sym(); x->o1=t; x->o2=expr(); }

return x;

}

node *paren_expr() /*

{ node *x;

if (sym == LPAR) next_sym(); else syntax_error();

x = expr();

if (sym == RPAR) next_sym(); else syntax_error();

return x;

}

node *statement()

{ node *t, *x;

if (sym == IF_SYM) /* “if”

{ x = new_node(IF1);

next_sym();

x->o1 = paren_expr();

x->o2 = statement();

if (sym == ELSE_SYM) /* … “else”

{ x->kind = IF2;

next_sym();

x->o3 = statement();

}

}

else if (sym == WHILE_SYM) /* “while”

{ x = new_node(WHILE);

next_sym();

x->o1 = paren_expr();

x->o2 = statement();

}

else if (sym == DO_SYM) /* “do”

{ x = new_node(DO);

next_sym();

x->o1 = statement();

if (sym == WHILE_SYM) next_sym(); else syntax_error();

x->o2 = paren_expr();

if (sym == SEMI) next_sym(); else syntax_error();

}

else if (sym == SEMI) /* “;” */

{ x = new_node(EMPTY); next_sym(); }

else if (sym == LBRA) /* “{” {

{ x = new_node(EMPTY);

next_sym();

while (sym != RBRA)

{ t=x; x=new_node(SEQ); x->o1=t; x->o2=statement(); }

next_sym();

}

else /*

{ x = new_node(EXPR);

x->o1 = expr();

if (sym == SEMI) next_sym(); else syntax_error();

}

return x;

}

node *program() /*

{ node *x = new_node(PROG);

next_sym(); x->o1 = statement(); if (sym != EOI) syntax_error();

return x;

}

/*—————————————————————————*/

/* Code generator. */

enum { IFETCH, ISTORE, IPUSH, IPOP, IADD, ISUB, ILT, JZ, JNZ, JMP, HALT };

typedef char code;

code object[1000], *here = object;

void g(code c) { *here++ = c; } /* missing overflow check */

code *hole() { return here++; }

void fix(code *src, code *dst) { *src = dst-src; } /* missing overflow check */

void c(node *x)

{ code *p1, *p2;

switch (x->kind)

{ case VAR : g(IFETCH); g(x->val); break;

case CST : g(IPUSH); g(x->val); break;

case ADD : c(x->o1); c(x->o2); g(IADD); break;

case SUB : c(x->o1); c(x->o2); g(ISUB); break;

case LT : c(x->o1); c(x->o2); g(ILT); break;

case SET : c(x->o2); g(ISTORE); g(x->o1->val); break;

case IF1 : c(x->o1); g(JZ); p1=hole(); c(x->o2); fix(p1,here); break;

case IF2 : c(x->o1); g(JZ); p1=hole(); c(x->o2); g(JMP); p2=hole();

fix(p1,here); c(x->o3); fix(p2,here); break;

case WHILE: p1=here; c(x->o1); g(JZ); p2=hole(); c(x->o2);

g(JMP); fix(hole(),p1); fix(p2,here); break;

case DO : p1=here; c(x->o1); c(x->o2); g(JNZ); fix(hole(),p1); break;

case EMPTY: break;

case SEQ : c(x->o1); c(x->o2); break;

case EXPR : c(x->o1); g(IPOP); break;

case PROG : c(x->o1); g(HALT); break;

}

}

/*—————————————————————————*/

/* Virtual machine. */

int globals[26];

void run()

{ int stack[1000], *sp = stack;

code *pc = object;

again: switch (*pc++)

{ case IFETCH: *sp++ = globals[*pc++]; goto again;

case ISTORE: globals[*pc++] = sp[-1]; goto again;

case IPUSH : *sp++ = *pc++; goto again;

case IPOP : –sp; goto again;

case IADD : sp[-2] = sp[-2] + sp[-1]; –sp; goto again;

case ISUB : sp[-2] = sp[-2] – sp[-1]; –sp; goto again;

case ILT : sp[-2] = sp[-2] < sp[-1]; --sp; goto again;
case JMP : pc += *pc; goto again;
case JZ : if (*--sp == 0) pc += *pc; else pc++; goto again;
case JNZ : if (*--sp != 0) pc += *pc; else pc++; goto again;
}
}
/*---------------------------------------------------------------------------*/
/* Main program. */
int main()
{ int i;
c(program());
for (i=0; i<26; i++)
globals[i] = 0;
run();
for (i=0; i<26; i++)
if (globals[i] != 0)
printf("%c = %dn", 'a'+i, globals[i]);
return 0;
}