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

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

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 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увеличивается, поскольку он должен включить эти структуры данных и описания функций для интерпретатора, чтобы они были доступны программе в целом. (Кстати, мы предпочли поместить всю информацию в один файл, а не в два, хотя для больших программ ее целесообразно разделить на несколько файлов с тем, чтобы включать каждый из них только там, где он действительно нужен.)