Книга: UNIX — универсальная среда программирования

8.4 Этап 4: компиляция на машину

8.4 Этап 4: компиляция на машину

Мы постепенно приближаемся к созданию hoc5 — интерпретатора языка со структурами управления. Программа hoc4 является промежуточным звеном: она имеет те же операции, что и hoc3, но реализуется на базе интерпретатора, как hoc5. Мы действительно написали такую программу hoc4 и в результате получили две программы с одинаковыми возможностями, что ценно для отладки. По мере разбора входного потока hoc4 порождает код, рассчитанный на простую машину, а не выдает сразу результат. При определении конца оператора будет выполнен код, порожденный для вычисления нужного результата (т.е. произойдет "интерпретация").

Под простой машиной здесь подразумевается стековая машина: когда появляется операнд, он заносится в стек, точнее, создаются команды, заносящие операнд в стек). Большинство операций над операндами выполняется в вершине стека. Например, при обработке присваивания

x=2*y

создаются следующие команды:

constpush Записать в стек: константа … константа2

2
varpush   Записать указатель на таблицу имен в стек

y         … для переменной у

eval      Вычислить: заменить указатель значением

mul       Перемножить два верхних элемента; результат заменяет их

varpush   Записать указатель на таблицу имен в стек

x         … для переменной x

assign    Записать значение в переменную, убрать указатель

pop       Убрать верхний элемент из стека

STOP      Конец последовательности команд

Когда выполняются команды, выражение вычисляется и результат записывается в x, как и указано в примечаниях. Последняя команда pop удаляет из стека верхний элемент, поскольку он больше не нужен.

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

Структура таблицы имен для hoc4 совпадает с таковой для hoc3: инициация проводится в init.c, и математические функции, находящиеся в math.c, одни и те же. Грамматика hoc4 идентична грамматике hoc3, но действия совершенно иные. Вообще, каждое действие порождает машинные команды и все необходимые для них аргументы. Например, в случае появления VAR в выражении создаются три команды: команда varpush, указатель на таблицу имен для переменной и команда eval, которая заменяет при вычислении указатель на таблицу имен соответствующим значением. Код для '*' содержит одну команду mul, поскольку операнды для нее уже находятся в стеке.

$ 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 <sym> 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;
}

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

execute(p) /* run the machine */
 Inst *p;
{
 for (pc = p; *pc != STOP; )
  (*(*pc++))();
}

В цикле выполняется функция, указываемая командой, на которую в свою очередь указывает счетчик команд pc. Значение pc увеличивается, что делает возможным выбор очередной команды. Команда с кодом операции STOP завершает цикл. Некоторые команды, например constpush и varpush, сами увеличивают pc, чтобы "перескочить" через любые аргументы, следующие за командой.

constpush() /* push constant onto stack */
{
 Datum d;
 d.val = ((Symbol*)*pc++)->u.val;
 push(d);
}
varpush() /* push variable onto stack */
{
 Datum d;
 d.sym = (Symbol*)(*pc++);
 push(d);
}

Оставшаяся часть описания машины проста. Так, арифметические операции в основном те же, и создаются они редактированием одного образца. Ниже показана операция add:

add() /* add top two elems on stack */
{
 Datum d1, d2;
 d2 = pop();
 d1 = pop();
 d1.val += d2.val;
 push(d1);
}

Другие процедуры также просты:

eval() /* evaluate variable on stack */
{
 Datum d;
 d = pop();
 if (d.sym->type == UNDEF)
 execerror("undefined variable", d.sym->name);
 d.val = d.sym->u.val;
 push(d);
}
assign() /* assign top value to next value */
{
 Datum d1, d2;
 d1 = pop();
 d2 = pop();
 if (d1.sym->type != VAR && d1.sym->type != UNDEF)
 execerror("assignment to non-variable", d1.sym->name);
 d1.sym->u.val = d2.val;
 d1.sym->type = VAR;
 push(d2);
}
print() /* pop top value from stack, print it */
{
 Datum d;
 d = pop();
 printf("t%.8gn", d.val);
}
bltin() /* evaluate built-in on top of stack */
{
 Datum d;
 d = pop();
 d.val = (*(double (*)())(*pc++))(d.val);
 push(d);
}

Самый сложный момент здесь операция приведения в функции, которая требует, чтобы *pc рассматривался как указатель на функцию, возвращающую double, и эта функция выполняется с d.val в качестве аргумента.

Диагностические сообщения от функций eval и assign никогда не появятся, если программа работает нормально. Мы оставили их на случай возникновения недоразумений из-за какой-нибудь ошибки программы. Потери за счет увеличения времени выполнения и размера кода даже не так важны, как обнаружение ошибки при внесении необдуманных изменений (что мы и наблюдали несколько раз).

Использование языка Си дает возможность работать с указателем на функцию, что позволяет писать компактные и эффективные программы.

Альтернативное решение состоит в том, чтобы сделать операторы константами и сгруппировать семантические функции в большой переключатель в функции execute. Попытайтесь реализовать его в качестве упражнения.

По мере увеличения исходного текста программы hoc возрастает необходимость механически отслеживать изменения и взаимозависимости. Неоценимую помощь здесь может оказать команда make: она автоматизирует процесс, который иначе пришлось бы выполнять вручную (и иногда с ошибками) или создавать для этого специальный командный файл.

Мы сделаем еще две модификации в файле makefile. Первая связана с тем, что хотя несколько файлов и зависят от констант, определенных в yacc программе файла y.tab.h, нет нужды их перетранслировать, если не изменились сами константы, а изменение в тексте Си программы из файла hoc.y не влияет на другие файлы. В новой версии makefile файлы .o зависят от нового файла x.tab.h, который изменяется только при замене содержимого файла y.tab.h. Вторая модификация основана на том, что правило для pr (печать исходных файлов) зависит лишь от самих исходных файлов, а именно, печатаются только измененные файлы.

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

Приведем makefile для hoc4:

YFLAGS = -d
OBJS = hoc.o code.o init.o math.o symbol.o
hoc4: $(OBJS)
      cc $(OBJS) -lm -o hoc4
hoc.o code.o init.o symbol.o: hoc.h
code.o init.o symbol.o: x.tab.h
x.tab.h: y.tab.h
      -cmp -s x.tab.h y.tab.h || cp y.tab.h x.tab.h
pr: hoc.y hoc.h code.c init.c math.c symbol.c
      @pr $?
      @touch pr
clean:
      rm -f $(OBJS) [xy].tab.[ch]

Символ '-' перед командой cmp дает указание make продолжать выполнение даже в случае неудачи cmp; это позволяет не останавливать работу и при несуществующем файле x.tab.h (флаг -s предписывает команде cmp не производить вывод, но установить код завершения). Комбинация $? раскрывается как список элементов из правила с устаревшей версией. К сожалению, форма записи в makefile слабо связана с обозначениями в интерпретаторе.

Проиллюстрируем изложенное выше на примере (в предположении, что все файлы последней версии):

$ touch hoc.y Изменим время для файла hoc.y

$ make
yacc -d hoc.y
 conflicts: 1 shift/reduce
сс -с y.tab.c
rm y.tab.c
mv y.tab.o hoc.o
cmp -s x.tab.h y.tab.h || cp y.tab.h x.tab.h
cc hoc.o code.o init.o math.o symbol.o -lm -o hoc4
$ make -n pr Печать измененных файлов

pr hoc.y
touch pr
$

Отметим, что, кроме hoc.y, файлы не перетранслировались, поскольку файл y.tab.h остался тем же.

Оглавление книги