Брайан Керниган - UNIX — универсальная среда программирования Страница 73

$ cat code.c

#include "hoc.h"

#include "y.tab.h"

#include <stdio.h>

#define NSTACK 256

static Datum stack[NSTACK]; /* the stack */

static Datum *stackp; /* next free spot on stack */

#define NPROG 2000

Inst prog[NPROG]; /* the machine */

Inst *progp; /* next free spot for code generation */

Inst *pc; /* program counter during execution */

Inst *progbase = prog; /* start of current subprogram */

int returning; /* 1 if return stmt seen */

typedef struct Frame { /* proc/func call stack frame */

 Symbol *sp;  /* symbol table entry */

 Inst *retpc; /* where to resume after return */

 Datum *argn; /* n-th argument on stack */

 int nargs;   /* number of arguments */

} Frame;

#define NFRAME 100 Frame frame[NFRAME];

Frame *fp; /* frame pointer */

initcode() {

 progp = progbase;

 stackp = stack;

 fp = frame;

 returning = 0;

}

...

$

Поскольку теперь в таблице имен хранятся указатели на функции и процедуры, а также на строки для печати, необходимо расширить определение типа объединения в файле hoc.h:

$ cat hoc.h

typedef struct Symbol { /* symbol table entry */

 char *name;

 short type;

 union {

  double val;      /* VAR */

  double (*ptr)(); /* BLTIN */

  int (*defn)();   /* FUNCTION, PROCEDURE */

  char *str;       /* STRING */

 } u;

 struct Symbol *next; /* to link to another */

} Symbol;

$

В процессе трансляции функция define заносит запись о функции в таблицу имен, сохраняет указатель на нее и изменяет в случае успешной компиляции адрес следующего после созданных команд свободного слова:

define(sp) /* put func/proc in symbol table */

 Symbol *sp;

{

 sp->u.defn = (Inst)progbase; /* start of code */

 progbase = progp; /* next code starts here */

}

Когда в процессе выполнения вызывается функция или процедура, все аргументы уже вычислены и помещены в стек (первый аргумент находится на наибольшем уровне). Код операции вызова (call) сопровождается указателем на таблицу имен и числом аргументов. Сохраняется образ стека, в котором содержится вся существенная информация о программе: запись в таблице имен, место возврата после вызова, место хранения аргументов в стеке выражений, а также число аргументов, сопровождающих вызов. Образ стека создается функцией call, которая затем выполняет тело программы.

call() /* call a function */

{

 Symbol *sp = (Symbol*)pc[0]; /* symbol table entry */

 /* for function */

 if (fp++ >= &frame[NFRAME-1])

  execerror(sp->name, "call nested too deeply");

 fp->sp = sp;

 fp->nargs = (int)pc[1];

 fp->retpc = pc + 2;

 fp->argn = stackp - 1; /* last argument */

 execute(sp->u.defn);

 returning = 0;

}

Создаваемая структура показана на рис. 8.2.

Рис. 8.2: Структуры данных для вызова процедуры

В конце концов произойдет возврат из вызываемой программы при выполнении procret или funcret:

funcret() /* return from a function */

{

 Datum d;

 if (fp->sp->type == PROCEDURE)

  execerror(fp->sp->name, "(proc) returns value");

 d = pop(); /* preserve function return value */

 ret();

 push(d);

}

procret() /* return from a procedure */

{

 if (fp->sp->type == FUNCTION)

  execerror(fp->sp->name(func) returns no value");

 ret();

}

Функция ret удаляет аргументы из стека, сохраняет указатель на образ стека fp и устанавливает счетчик команд:

ret() /* common return from func or proc */

{

 int i;

 for (i = 0; i < fp->nargs; i++)

  pop(); /* pop arguments */

 pc = (Inst*)fp->retpc;

 --fp;

 returning = 1;

}

Некоторые программы интерпретатора нуждаются в небольших поправках для учета ситуаций, когда происходит возврат во вложенных операторах. Решение не элегантно, но верно и состоит во введении признака с именем returning, который принимает значение 1 при обнаружении оператора return. Выполнение, организуемое функциями ifcode, whilecode, execute, завершается раньше, если установлен признак returning; в функции call он обнуляется.

ifcode() {

 Datum d;

 Inst *savepc = pc; /* then part */

 execute(savepc+3); /* condition */

 d = pop();

 if (d.val)

  execute(*((Inst**)(savepc)));

 else if (*((Inst**)(savepc+1))) /* else part? */

  execute(*((Inst**)(savepc+1)));

 if (!returning)

  pc = *((Inst**)(savepc+2)); /* next stmt */

}

whilecode() {

 Datum d;

 Inst *savepc = pc;

 execute(savepc+2); /* condition */

 d = pop();

 while (d.val) {

  execute(*((Inst**)(savepc))); /* body */

  if (returning)

   break;

  execute(savepc+2); /* condition */

  d = pop();

 }

 if (!returning)

  pc = *((Inst**)(savepc+1)); /* next stmt */

}

execute(p)

 Inst *p;

{

 for (pc = p; *pc != STOP && !returning; )

  (*((++pc)[-1]))();

}

Аргументы выбираются для получения значения или присваивания с помощью функции getarg, которая следит за сбалансированностью стека:

double *getarg() /* return pointer to argument */

{

 int nargs = (int)*pc++;

 if (nargs > fp->nargs)

  execerror(fp->sp->name, "not enough arguments");

 return &fp->argn[nargs - fp->nargs].val;

}

arg() /* push argument onto stack */

{

 Datum d;

 d.val = *getarg();

 push(d);

}

argassign() /* store top of stack in argument */

{

 Datum d;

 d = pop();

 push(d); /* leave value on stack */

 *getarg() = d.val;

}

Функции prstr и prexpr печатают строки и числа:

prstr() /* print string value */

{

 printf("%s", (char*)*pc++);

}

prexpr() /* print numeric value */

{

 Datum d;

 d = pop();

 printf("%.8g d.val);

}

Функция varread читает переменные. Она возвращает 0 при обнаружении конца файла и 1 — в противном случае, а также устанавливает значение указанной переменной:

varread() /* read into variable */

{

 Datum d;

 extern FILE *fin;

 Symbol *var = (Symbol*)*pc++;

Again:

 switch (fscanf(fin, "%lf", &var->u.val)) {

 case EOF:

  if (moreinput())

   goto Again;

  d.val = var->u.val = 0.0;

  break;

 case 0:

  execerror("non-number read into", var->name);

  break;

 default:

  d.val = 1.0;

  break;

 }

 var->type = VAR;

 push(d);

}

Обнаружив конец файла для текущего входного потока, функция varread обратится к moreinput, которая откроет следующий файл, заданный в качестве аргумента (если он есть). В функции moreinput обработка входной информации имеет некоторые нюансы, здесь не рассматриваемые; речь о них идет в приложении 3.

Итак, мы завершили разработку программы hoc. Для сравнения приведем число непустых строк в каждой версии:

hoc1 59

hoc2 94

hoc3 248 (для версии с lex 229)

hoc4 396

hoc5 574

hoc6 809

Конечно, эти значения были вычислены программным способом: $

sed '/$/d' `pick *.[chyl]` | wc -l

Безусловно, развитие языка может быть продолжено, и вам предоставляется такая возможность в приведенных ниже упражнениях.

Измените hoc6 так, чтобы можно было использовать поименованные формальные параметры в подпрограммах вместо $1 и т.д.

Сейчас все переменные глобальны, за исключением параметров. Уже есть большая часть механизма для введения локальных переменных, хранимых в стеке. Одно из решений заключается во введении описания auto, которое резервирует место в стеке для перечисленных переменных; не перечисленные переменные считаются глобальными. Кроме того, придется расширить таблицу имен так, чтобы поиск в ней осуществлялся вначале для локальных, а затем для глобальных переменных. Как это связано с поименованными аргументами?

Как бы вы ввели массивы в язык hoc? Как следует передавать их функциям и процедурам? Как возвращать их?

Обобщите работу со строками так, чтобы переменные могли хранить строки, а не только числа. Какие операции потребуются для этого? Самая трудная часть управление памятью добейтесь динамичного хранения строк: память должна освобождаться, когда строки перестают быть нужными. В качестве промежуточного шага добавьте более развитые форматы печати, например, обеспечьте возможность использования некоторых форм стандартной Си функции printf.