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

$

Если один файл изменится, достаточно единственной команды make для получения действующей версии:

$ touch lex.l Смена времени модификации файла lex.l

$ make

lex lex.l

cc -с lex.yy.c

rm lex.yy.c

mv lex.yy.o lex.o

cc hoc.o lex.o init.o math.o symbol.o -ll -lm -o hoc3

$

Некоторое время мы дебатировали о том, следует ли считать обсуждение программы lex отступлением от нашей темы и поэтому показать ее кратко, а затем перейти к другим вопросам или рассматривать ее как основное средство для лексического анализа, когда язык становится слишком сложным. У нас были аргументы "за" и "против". Затруднения в работе с lex (помимо того, что пользователь должен изучить еще один язык) связаны с тем, что замедляется выполнение программы, а распознаватели оказываются более объемными и медленными, чем эквивалентные версии на языке Си. К тому же возникают трудности с механизмом ввода в некоторых особых случаях, таких, как восстановление после ошибки, а также с вводом из файла. Ни одна из перечисленных проблем не является существенной для hoc. К сожалению, из-за ограниченного объема книги мы вынуждены вернуться в последующих лексических анализаторах к Си. Однако создание версии с lex будет для вас хорошей практикой.

Сравните размеры двух версий hoc3. Подсказка: обратитесь к справочному руководству по size(1).

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); }