UNIX — страница 85 из 115

$ cat hoc.y
%{
#include "hoc.h"
#define code2(c1,c2) code(c1); code(c2)
#define code3(c1,c2,c3) code(c1); code(c2); code(c3)
%}
%union {
 Symbol *sym; /* symbol table pointer */
 Inst *inst;  /* machine instruction */
}
%token  NUMBER VAR BLTIN UNDEF
%right '='
%left '+'
%left '*' '/'
%left UNARYMINUS
%right '^' /* exponentiation */
%%
list: /* nothing */ | list '\n'
 | list asgn '\n' { code2(pop, STOP); return 1; }
 | list expr '\n' { code2(print, STOP); return 1; }
 | list error '\n' { yyerrok; }
 ;
asgn: VAR '=' expr { code3(varpush, (Inst)$1, assign); }
 ;
expr: NUMBER { code2(constpush, (Inst)$1); }
 | VAR { code3(varpush, (Inst)$1, eval); }
 | asgn
 | BLTIN '(' expr ')' { code2(bltin, (Inst)$1->u.ptr); }
 | '(' expr ')'
 | expr '+' expr { code(add); }
 | expr '-' expr { code(sub); }
 | expr '*' expr { code(mul); }
 | expr '/' expr { code(div); }
 | expr '^' expr { code(power); }
 | '-' expr %prec UNARYMINUS { code (negate); }
 ;
%%
/* end of grammar */
...

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

Мы несколько изменили процедуру main. Теперь происходит возврат из анализатора после выполнения каждого оператора или выражения, и порожденный код выполняется. При обнаружении файла yyparse возвращает нуль.

main(argc, argv) /* hoc4 */
 char *argv[];
{
 int fpecatch();

 progname = argv[0];
 init();
 setjmp(begin);
 signal(SIGFPE, fpecatch);
 for (initcode(); yyparse(); initcode())
  execute(prog);
 return 0;
}

Лексический анализатор отличается мало в основном тем, что числа следует сохранять, а не использовать немедленно. Для этого достаточно занести их в таблицу имен вместе с переменными. Ниже приведена измененная часть yylex:

yylex() /* hoc4 */
 ...
 if (с == '.' || isdigit(c)) {
  /* number */
  double d;
  ungetc(c, stdin);
  scanf("%lf", &d);
  yylval.sym = install("", NUMBER, d);
  return NUMBER;
 }
 ...

Каждый элемент стека интерпретатора является вещественным значением или указателем на запись в таблице имен; тип данных стека объединение всех элементов. Сама машина реализуется как массив указателей на процедуры, выполняющие операции типа mul, или на данные в таблице имен. Файл макроопределений hoc.h увеличивается, поскольку он должен включить эти структуры данных и описания функций для интерпретатора, чтобы они были доступны программе в целом. (Кстати, мы предпочли поместить всю информацию в один файл, а не в два, хотя для больших программ ее целесообразно разделить на несколько файлов с тем, чтобы включать каждый из них только там, где он действительно нужен.)

$ cat hoc.h
typedef struct Symbol { /* symbol table entry */
 char *name;
 short type; /* VAR, BLTIN, UNDEF */
 union {
  double val; /* if VAR */
  double (*ptr)(); /* if BLTIN */
 } u;
 struct Symbol *next; /* to link to another */
} Symbol;
Symbol *install(), *lookup();

typedef union Datum { /* interpreter stack type */
 double val;
 Symbol *sym;
} Datum;
extern Datum pop();

typedef int (*Inst)(); /* machine instruction */
#define STOP (Inst) 0

extern Inst prog[];
extern eval(), add(), sub(), mul(), div(), negate(), power();
extern assign(), bltin(), varpush(), constpush(), print();
$

Процедуры, выполняющие машинные команды и управляющие стеком, хранятся в файле с именем code.c. Поскольку содержимое файла составляет около 150 строк, мы покажем его по частям:

$ cat code.c
#include "hoc.h"
#include "y.tab.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 */

initcode() /* initialize for code generation */
{
 stackp = stack;
 progp = prog;
}
...

Управление стеком осуществляется путем обращений к двум процедурам push и pop:

push(d) /* push d onto stack */
 Datum d;
{
 if (stackp >= &stack[NSTACK])
  execerror("stack overflow", (char*)0);
 *stackp++ = d;
}

Datum pop() /* pop and return top elem from stack */
{
 if (stackp <= stack)
  execerror("stack underflow", (char*)0);
 return *--stackp;
}

Машинные команды создаются в процессе разбора при обращении к функции code, которая просто вносит команду на первое свободное место массива prog. Она возвращает адрес команды (который не используется в hoc4):

Inst *code(f) /* install one instruction or operand */
 Inst f;
{
 Inst *oprogp = progp;
 if (progp >= &prog[NPROG])
  execerror("program too big", (char*)0);
 *progp++ = f;
 return oprogp;
}

Выполнение машинной команды фантастически тривиально, а как мала процедура, которая "выполняет" машинные команды, когда уже определены все программы!