Category : Files from Magazines
Archive   : DDJ0589.ZIP
Filename : SMLTER.ASC

_C Programming Column_
by Al Stevens

[LISTING ONE]


/* ---------------- interp.h -------------------- */
#define TOKBUFSIZE 4096 /* token buffer size */
#define MAXSYMBOLS 100 /* maximum symbols in table */
#define MAXSTRINGS 50 /* maximum strings in arrays */
#define MAXPARAMS 10 /* maximum parameters in calls */
/* ----------- error codes ----------------- */
enum errs {EARLYEOF,UNRECOGNIZED,DUPL_DECLARE,TABLEOVERFLOW,
OMERR,UNDECLARED,SYNTAX,BRACERR,PARENERR,MISSING,
NOTFUNC,BREAKERR,OUTOFPLACE,TOOMANYSTRINGS,BUFFULL,
DIVIDEERR};
/* ------- intrinsic function table -------- */
typedef struct {
char *fname;
int (*fn)(int *);
} INTRINSIC;
/* -------- symbol table ------------ */
typedef struct {
char *symbol; /* points to symbol name */
char *location; /* points to function code (NULL if int) */
char **tblloc; /* points to table array (NULL if func) */
int ival; /* value of integer */
} SYMBOL;
/* ------- function prototypes -------- */
void loadsource(void);
int function(char *, SYMBOL *);
#define interpret() function("main\0();", symtop);
/* ------ functions provided by the shell -------- */
int getsource(void);
void ungetsource(int);
void sierror(enum errs, char *, int);
/* -------- the compiled (interpretable) S source -------- */
extern SYMBOL globals[];
extern char *tokenbf;
extern char *strings[];
extern SYMBOL *symtop;


[LISTING TWO]

/* ----------- interp.c ----------- */
#include
#include
#include
#include
#include
#include
#include "interp.h"
#define TRUE 1
#define FALSE 0
/* --------- the compiled (interpretable) S source ---------- */
SYMBOL globals[MAXSYMBOLS]; /* function/variable symbol table */
char *tokenbf = NULL; /* compiled token buffer */
char *strings[MAXSTRINGS]; /* char *[] string arrays */
SYMBOL *symtop; /* top of symbol table */
/* ---------- the external intrinsic functions ----------- */
extern INTRINSIC *infs; /* initialized by the SI shell */
/* ------ function macros ------------ */
#define bypass() tptr+=strlen(tptr)+1
#define isletter(c) (isalpha(c)||isdigit(c)||c =='_')
#define iswhite(c) (c==' '||c=='\t')
/* ---- function prototypes ----- */
static void linker(void);
static int gettoken(void);
static int getok(void);
static int iskeyword(void);
static int isident(void);
static int istoken(void);
static int getword(void);
static int getcx(void);
static void compound_statement(SYMBOL *);
static void statement(SYMBOL *);
static void statements(SYMBOL *);
static void skip_statements(SYMBOL *);
static void addsymbol(SYMBOL *, char *, char *, char **);
static SYMBOL *findsymbol(SYMBOL *, char *, SYMBOL *);
static SYMBOL *ifsymbol(SYMBOL *, char *, SYMBOL *);
static void freesymbols(SYMBOL *);
static void error(enum errs, char *);
static int iftoken(int);
static void skippair(int, int);
static void needtoken(int);
static int iftoken(int);
static int nexttoken(void);
static int expression(SYMBOL *);
static int escseq(void);
/* --------------- tokens ------------------ */
#define AUTOINC 'P'
#define AUTODEC 'D'
#define EQUALTO 'E'
#define NOTEQUAL 'N'
#define GE 'G'
#define LE 'L'
#define IF 'f'
#define ELSE 'e'
#define WHILE 'w'
#define FOR 'F'
#define CHAR 'c'
#define INT 'i'
#define STRING 's'
#define COMMENT1 '/'
#define COMMENT2 '*'
#define POINTER '*'
#define PLUS '+'
#define MINUS '-'
#define MULTIPLY '*'
#define DIVIDE '/'
#define EQUAL '='
#define LESS '<'
#define GREATER '>'
#define NOT '!'
#define LPAREN '('
#define RPAREN ')'
#define LBRACE '{'
#define RBRACE '}'
#define LBRACKET '['
#define RBRACKET ']'
#define COMMA ','
#define AND '&'
#define ADDRESS '@'
#define OR '|'
#define QUOTES '"'
#define QUOTE '\''
#define UNDERSCORE '_'
#define SEMICOLON ';'
#define IDENT 'I'
#define CONSTANT 'C'
#define LINENO 127
#define RETURN 'r'
#define BREAK 'b'
/* -------- table of key words and their tokens --------- */
static struct keywords {
char *kw;
int kwtoken;
} kwds[] = {
"\n", LINENO,
"for", FOR,
"while", WHILE,
"if", IF,
"else", ELSE,
"int", INT,
"char", CHAR,
"return",RETURN,
"break", BREAK,
NULL, 0
};
/* ------------ table of direct translate tokens -------- */
static int tokens[] = {
COMMA,LBRACE,RBRACE,LPAREN,RPAREN,EQUAL,NOT,POINTER,
LESS,GREATER,AND,OR,QUOTES,SEMICOLON,LBRACKET,RBRACKET,
MULTIPLY,DIVIDE,PLUS,MINUS,EOF,LINENO,0
};
/* --------------------- local data ----------------------- */
static char word[81]; /* word space for source parsing */
static int linenumber; /* current source file line number */
static int frtn; /* return value from a function */
static char *tptr; /* running token pointer */
static int stptr; /* running string allocation offset */
static int breaking, returning, skipping;
static SYMBOL *endglobals;
/* ----------- lexical scan and call linker ------------ */
void loadsource(void)
{
int tok = 0;
if (tokenbf == NULL)
if ((tokenbf = malloc(TOKBUFSIZE+81)) == NULL)
error(OMERR, "");
symtop = symtop ? symtop : globals;
freesymbols(globals);
memset(tokenbf, '\0', TOKBUFSIZE+81);
linenumber = 1;
tptr = tokenbf;
while (tok != EOF) {
if (tptr >= tokenbf + TOKBUFSIZE)
error(BUFFULL, "");
*tptr++ = tok = gettoken();
switch (tok) {
case LINENO:
sprintf(tptr, "%03d", linenumber);
tptr += 3;
break;
case CONSTANT:
case IDENT:
case STRING:
strcpy(tptr, word);
bypass();
break;
default:
break;
}
}
linker(); /* link the external variables and functions */
}
/* -- convert a script program to tokens for interpreter,
return the next token -------- */
static int gettoken(void)
{
int tok = getword();
if (tok == 0)
if ((tok = iskeyword()) == 0)
if ((tok = istoken()) == 0)
tok = isident();
if (tok == 0)
error(UNRECOGNIZED, word);
return tok;
}
/* ----- test to see if current word is a token ----- */
static int istoken(void)
{
int *t = tokens, t2;
while (*t && word[1] == '\0')
if (*word == *t++) {
switch (*word) {
case EOF:
break;
case AND:
if ((t2 = getcx()) != AND) {
*word = ADDRESS;
ungetsource(t2);
}
break;
case OR:
if (getcx() != OR)
error(MISSING, word);
break;
case PLUS:
case MINUS:
if ((t2 = getcx()) == *word)
*word = *word==PLUS ? AUTOINC : AUTODEC;
else
ungetsource(t2);
break;
default:
if ((t2 = getcx()) == EQUAL) {
switch (*word) {
case EQUAL: return EQUALTO;
case NOT: return NOTEQUAL;
case LESS: return LE;
case GREATER: return GE;
default: break;
}
}
ungetsource(t2);
break;
}
return *word;
}
return 0;
}
/* -------- test word for a keyword --------- */
static int iskeyword()
{
struct keywords *k = kwds;
while (k->kw)
if (strcmp(k->kw, word) == 0)
return k->kwtoken;
else
k++;
return 0;
}
/* ------ test for an ident -------- */
static int isident()
{
char *wd = word;
int n = 0;
if (isalpha(*wd) || *wd == UNDERSCORE)
return IDENT;
if (strlen(wd) <= 6) {
if (strncmp(wd, "0x", 2) == 0) {
wd += 2; /* 0x.... hex constant */
while (*wd) {
n = (n*16)+(isdigit(*wd) ? *wd-'0' :
tolower(*wd) - 'a' + 10);
wd++;
}
sprintf(word,"%d", n); /* converted hex constant */
}
else /* test for decimal constant */
while (*wd)
if (!isdigit(*wd++))
return 0;
return CONSTANT;
}
return 0;
}
/* -------- get the next word from the input stream ------- */
static int getword(void)
{
char *wd = word;
int c = ' ', tok = 0;
while (iswhite(c)) /* bypass white space */
c = getok();
if (c == QUOTE) {
tok = CONSTANT; /* quoted constant ('x') */
if ((c = getcx()) == '\\') /* escape sequence (\n) */
c = escseq();
sprintf(word, "%d", c); /* build the constant value */
wd += strlen(word);
if (getcx() != QUOTE) /* needs the other quote */
error(MISSING,"'");
}
else if (c == QUOTES) {
tok = STRING; /* quoted string "abc" */
while ((c = getcx()) != QUOTES)
*wd++ = c == '\\' ? escseq() : c;
}
else {
*wd++ = c; /* 1st char of word */
while (isletter(c)) { /* build an ident */
c = getok();
if (isletter(c))
*wd++ = c;
else
ungetsource(c);
}
}
*wd = '\0'; /* null terminate the word or token */
return tok;
}
/* ---- escape sequence in literal constant or string ---- */
static int escseq()
{
int c = getcx();
return (c == 'n' ? '\n' :
c == 't' ? '\t' :
c == 'f' ? '\f' :
c == 'a' ? '\a' :
c == 'b' ? '\b' :
c == 'r' ? '\r' :
c == '0' ? '\0' : c);
}
/* ------- get a character from the input stream -------- */
static int getok(void)
{
int c, c1;
while ((c = getsource()) == COMMENT1) {
if ((c1 = getcx()) != COMMENT2) { /* comment */
ungetsource(c1);
break;
}
while (TRUE) { /* found comment begin token pair */
while ((c1 = getcx()) != COMMENT2)
;
if ((c1 = getcx()) == COMMENT1)
break; /* found comment end token pair */
}
}
if (c == '\n') /* count source line numbers */
linenumber++;
return c;
}
/* ------- read a character from input, error if EOF ------ */
static int getcx(void)
{
int c;
if ((c = getsource()) == EOF)
error(EARLYEOF, "");
return c;
}
/* --------- build the global symbol table --------- */
static void linker(void)
{
int tok = 0;
char *svtptr;
INTRINSIC *ff = infs;
tptr = tokenbf;
/* --- add intrinsic functions to the symbol table --- */
while (ff->fname) {
addsymbol(globals,ff->fname,ff->fname,NULL);
ff++;
}
while (tok != EOF) {
switch (tok = nexttoken()) {
case CHAR:
svtptr = tptr;
if (iftoken(POINTER)) {
needtoken(IDENT);
bypass();
if (iftoken(LBRACKET)) {
tptr = svtptr;
nexttoken();
nexttoken();
addsymbol(globals,tptr,NULL,
strings+stptr);
bypass();
needtoken(LBRACKET);
needtoken(RBRACKET);
needtoken(EQUAL);
needtoken(LBRACE);
while (TRUE) {
if (!iftoken(STRING))
break;
if (stptr == MAXSTRINGS)
error(TOOMANYSTRINGS, "");
strings[stptr++] = tptr;
bypass();
if (!iftoken(COMMA))
break;
}
strings[stptr++] = NULL;
needtoken(RBRACE);
needtoken(SEMICOLON);
break;
}
}
tptr = svtptr;
case INT:
while (TRUE) {
if (iftoken(POINTER))
;
needtoken(IDENT);
addsymbol(globals,tptr,NULL,NULL);
bypass();
if (iftoken(EQUAL))
(symtop-1)->ival=expression(globals);
if (!iftoken(COMMA))
break;
}
needtoken(SEMICOLON);
break;
case IDENT:
addsymbol(globals, tptr, tptr, NULL);
bypass();
skippair(LPAREN, RPAREN);
skippair(LBRACE, RBRACE);
break;
case EOF:
break;
default:
error(OUTOFPLACE, (char *) &tok);
}
}
endglobals = symtop;
}
/* --------- a function is called ---------- */
int function(char *fnc, SYMBOL *sp)
{
int params[MAXPARAMS+1], p, i;
INTRINSIC *ff = infs;
char *savetptr = tptr;
frtn = 0;
tptr = fnc;
bypass();
needtoken(LPAREN);
for (p = 0; p < MAXPARAMS; ) { /* scan for parameters */
if (iftoken(RPAREN))
break;
params[p++]=expression(sp); /* build params */
if (!iftoken(COMMA)) { /* into parameter array */
needtoken(RPAREN);
break;
}
}
params[p] = 0;
while (ff->fname) { /* search the intrinsic table */
if (strcmp(fnc,ff->fname) == 0) {
frtn = (*ff->fn)(params); /* call intrinsic func */
tptr = savetptr;
return frtn;
}
ff++;
}
if ((tptr=findsymbol(globals,fnc,endglobals)->location)
== NULL)
error(NOTFUNC,fnc); /* function not declared */
bypass();
needtoken(LPAREN);
sp = symtop;
for (i = 0; i < p; i++) { /* params into local sym tbl */
needtoken(IDENT);
addsymbol(sp,tptr,NULL,NULL);
(symtop-1)->ival = params[i];
bypass();
if (i < p-1)
needtoken(COMMA);
}
needtoken(RPAREN);
compound_statement(sp); /* execute the function */
freesymbols(sp); /* release the local symbols */
tptr = savetptr;
breaking = returning = FALSE;
return frtn; /* the function's return value */
}
/* ------- execute one statement or a {} block -------- */
static void statements(SYMBOL *sp)
{
if (iftoken(LBRACE)) {
--tptr;
compound_statement(sp);
}
else
statement(sp);
}
/* -------- execute a {} statement block ----------- */
static void compound_statement(SYMBOL *sp)
{
char *svtptr = tptr;
SYMBOL *spp = symtop;
needtoken(LBRACE);
while (iftoken(CHAR) || iftoken(INT)) {
while (TRUE) { /* local variables in block */
if (iftoken(POINTER))
; /* bypass pointer token(s) */
needtoken(IDENT);
addsymbol(spp,tptr,NULL,NULL);
bypass();
if (iftoken(EQUAL)) /* handle assignments */
(symtop-1)->ival=expression(sp);
if (!iftoken(COMMA))
break;
}
needtoken(SEMICOLON);
}
while (!iftoken(RBRACE) && !breaking && !returning)
statements(sp);
tptr = svtptr; /* point to the opening { brace */
freesymbols(spp); /* free the local symbols */
skippair(LBRACE, RBRACE); /* skip to end of block */
}
/* --------- execute a single statement ---------- */
static void statement(SYMBOL *sp)
{
char *svtptr, *fortest, *forloop, *forblock;
int rtn, tok = nexttoken();
switch (tok) {
case IF:
needtoken(LPAREN);
rtn = expression(sp); /* condition being tested */
needtoken(RPAREN);
if (rtn)
statements(sp); /* condition is true */
else
skip_statements(sp); /* condition is false */
while (iftoken(ELSE))
if (rtn) /* do the reverse for else */
skip_statements(sp);
else
statements(sp);
break;
case WHILE:
rtn = TRUE;
breaking = returning = FALSE;
svtptr = tptr;
while (rtn && !breaking && !returning) {
tptr = svtptr;
needtoken(LPAREN);
rtn = expression(sp); /* the condition tested */
needtoken(RPAREN);
if (rtn)
statements(sp); /* true */
else
skip_statements(sp); /* false */
}
breaking = returning = FALSE;
break;
case FOR:
svtptr = tptr; /* svptr -> 1st ( after for */
needtoken(LPAREN);
if (!iftoken(SEMICOLON)) {
expression(sp); /* initial expression */
needtoken(SEMICOLON);
}
fortest = tptr; /* fortest -> terminating test */
tptr = svtptr;
skippair(LPAREN,RPAREN);
forblock = tptr; /* forblock -> block to run */
tptr = fortest;
breaking = returning = FALSE;
while (TRUE) {
if (!iftoken(SEMICOLON)) {
if (!expression(sp)) /* terminating test */
break;
needtoken(SEMICOLON);
}
forloop = tptr;
tptr = forblock;
statements(sp); /* the loop statement(s) */
if (breaking || returning)
break;
tptr = forloop;
if (!iftoken(RPAREN)) {
expression(sp); /* the end of loop expr */
needtoken(RPAREN);
}
tptr = fortest;
}
tptr = forblock;
skip_statements(sp); /* skip past the block */
breaking = returning = FALSE;
break;
case RETURN:
if (!iftoken(SEMICOLON)) {
frtn = expression(sp);
needtoken(SEMICOLON);
}
returning = !skipping;
break;
case BREAK:
needtoken(SEMICOLON);
breaking = !skipping;
break;
case IDENT:
--tptr;
expression(sp);
needtoken(SEMICOLON);
break;
default:
error(OUTOFPLACE, (char *) &tok);
}
}
/* -------- bypass statement(s) ------------ */
static void skip_statements(SYMBOL *sp)
{
skipping++; /* semaphore that suppresses assignments, */
statements(sp); /* breaks,returns,++,--,function calls */
--skipping; /* turn off semaphore */
}
/* -------- recursive descent expression analyzer -------- */
static int primary(SYMBOL *sp)
{
int tok, rtn = 0;
SYMBOL *spr;
switch (tok = nexttoken()) {
case LPAREN:
rtn = expression(sp);
needtoken(RPAREN);
break;
case NOT:
rtn = !primary(sp);
break;
case CONSTANT:
rtn = atoi(tptr);
bypass();
break;
case POINTER:
rtn = *(int *)primary(sp) & 255;
break;
case ADDRESS:
case AUTOINC:
case AUTODEC:
needtoken(IDENT);
case IDENT:
if ((spr = ifsymbol(sp,tptr,symtop)) == NULL)
spr = findsymbol(globals,tptr,endglobals);
if (spr->location) {
/* ---- this is a function call ---- */
if (tok != IDENT)
error(OUTOFPLACE, (char *) &tok);
rtn = skipping ? 0 : function(tptr,sp);
bypass();
skippair(LPAREN,RPAREN);
break;
}
bypass();
if (spr->tblloc) {
/* ---- this is a table ---- */
rtn = (tok == ADDRESS ?
(int) (&spr->tblloc) :
(int) ( spr->tblloc) );
break;
}
if (!skipping && tok == AUTOINC)
++(spr->ival);
else if (!skipping && tok == AUTODEC)
--(spr->ival);
if (tok != ADDRESS && iftoken(EQUAL)) {
rtn = expression(sp);
spr->ival = skipping ? spr->ival : rtn;
}
rtn = tok == ADDRESS ? (int)&spr->ival : spr->ival;
if (tok != ADDRESS)
if (iftoken(AUTOINC) && !skipping)
(spr->ival)++;
else if (iftoken(AUTODEC) && !skipping)
(spr->ival)--;
break;
case STRING:
rtn = (int) tptr;
bypass();
break;
default:
error(OUTOFPLACE, (char *) &tok);
}
return rtn;
}
static int mult(SYMBOL *sp)
{
int drtn, rtn = primary(sp);
while (TRUE)
if (iftoken(MULTIPLY))
rtn = (rtn * primary(sp));
else if (iftoken(DIVIDE)) {
if ((drtn = primary(sp)) == 0)
error(DIVIDEERR, "");
rtn /= drtn;
}
else
break;
return rtn;
}
static int plus(SYMBOL *sp)
{
int rtn = mult(sp);
while (TRUE)
if (iftoken(PLUS))
rtn = (rtn + mult(sp));
else if (iftoken(MINUS))
rtn = (rtn - mult(sp));
else
break;
return rtn;
}
static int le(SYMBOL *sp)
{
int rtn = plus(sp);
while (TRUE)
if (iftoken(LE))
rtn = (rtn <= plus(sp));
else if (iftoken(GE))
rtn = (rtn >= plus(sp));
else if (iftoken(LESS))
rtn = (rtn < plus(sp));
else if (iftoken(GREATER))
rtn = (rtn > plus(sp));
else
break;
return rtn;
}
static int eq(SYMBOL *sp)
{
int rtn = le(sp);
while (TRUE)
if (iftoken(EQUALTO))
rtn = (rtn == le(sp));
else if (iftoken(NOTEQUAL))
rtn = (rtn != le(sp));
else
break;
return rtn;
}
static int and(SYMBOL *sp)
{
int rtn = eq(sp);
while (iftoken(AND))
rtn = (eq(sp) && rtn);
return rtn;
}
static int expression(SYMBOL *sp)
{
int rtn = and(sp);
while (iftoken(OR))
rtn = (and(sp) || rtn);
return rtn;
}
/* ----- skip the tokens between a matched pair ----- */
static void skippair(int ltok, int rtok)
{
int pairct = 0, tok;
if ((tok = nexttoken()) != ltok)
error(ltok == LBRACE ? BRACERR : PARENERR, "");
while (TRUE) {
if (tok == ltok)
pairct++;
if (tok == rtok)
if (--pairct == 0)
break;
if ((tok = nexttoken()) == EOF)
error(ltok == LBRACE ? BRACERR : PARENERR, "");
}
}
/* ----- a specified token is required next ----- */
static void needtoken(int tk)
{
if (nexttoken() != tk)
error(MISSING, (char *) &tk);
}
/* ----- test for a specifed token next in line ----- */
static int iftoken(int tk)
{
if (nexttoken() == tk)
return TRUE;
--tptr;
return FALSE;
}
/* ----- get the next token from the buffer ----- */
static int nexttoken(void)
{
while (*tptr == LINENO)
tptr += 4;
return *tptr++;
}
/* ------ add a symbol to the symbol table ------------ */
static void
addsymbol(SYMBOL *s,char *sym,char *floc,char **tloc)
{
if (ifsymbol(s,sym,symtop) != NULL)
error(DUPL_DECLARE, sym);
if (symtop == globals + MAXSYMBOLS)
error(TABLEOVERFLOW, "");
if ((symtop->symbol = malloc(strlen(sym) + 1)) == NULL)
error(OMERR, "");
strcpy(symtop->symbol, sym);
symtop->location = floc;
symtop->tblloc = tloc;
symtop->ival = 0;
symtop++;
}
/* --------- find a symbol on the symbol table --------- */
static SYMBOL *findsymbol(SYMBOL *s, char *sym, SYMBOL *ends)
{
if ((s = ifsymbol(s, sym, ends)) == NULL)
error(UNDECLARED, sym);
return s;
}
/* -------- test for a symbol on the symbol table ------ */
static SYMBOL *ifsymbol(SYMBOL *s, char *sym, SYMBOL *sp)
{
while (s < sp--)
if (strcmp(sym, sp->symbol) == 0)
return sp;
return NULL;
}
/* ------- free the symbols from a symbol table ------- */
static void freesymbols(SYMBOL *s)
{
while (s < symtop)
free((--symtop)->symbol);
}
/* -------- post an error to the shell ------- */
static void error(enum errs erno, char *s)
{
while (*tptr != LINENO && tptr > tokenbf)
--tptr;
sierror(erno, s, (*tptr == LINENO) ? atoi(tptr+1) : 1);
}


[LISTING THREE]

/* ---------- si.c -------------- */
#include
#include
#include
#include "interp.h"
/* ----------- intrinsic interpreter functions ---------- */
static int iprntf(int *p) /* printf */
{
printf((char*)p[0],p[1],p[2],p[3],p[4]);
return 0;
}
static int igtch(int *p) /* getchar */
{
return putch(getch());
}
static int iptch(int *c) /* putchar */
{
return putchar(*c);
}
INTRINSIC ffs[] = { "printf", iprntf,
"getchar", igtch,
"putchar", iptch,
NULL, NULL };
extern INTRINSIC *infs = ffs;
/* ---------- error messages ------------- */
char *erm[]={ "Unexpected end of file", "Unrecognized",
"Duplicate ident", "Symbol table full",
"Out of heap memory", "Undeclared ident",
"Syntax Error", "Unmatched {}",
"Unmatched ()", "Missing",
"Not a function", "Misplaced break",
"Out of place", "Too many strings",
"Token buffer overflow", "Divide by zero" };
static FILE *fp;
void main(int argc, char *argv[])
{
if (argc == 2)
if ((fp = fopen(argv[1], "r")) != NULL) {
loadsource();
fclose(fp);
interpret();
}
}
void sierror(enum errs erno, char *s, int line)
{
printf("\r\n%s %s on line %d\n",s,erm[erno],line);
exit(1);
}
int getsource(void) { return getc(fp); }
void ungetsource(int c) { ungetc(c, fp); }