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

Керниган Брайан Уилсон

 sscanf(yytext, "%lf", &yylval.val);

 return NUMBER;

}

[a-zA-Z][a-zA-Z0-9]* {

 Symbol *s;

 if ((s=lookup(yytext)) == 0)

s = install(yytext, UNDEF, 0.0);

 yylval.sym = s;

 return s->type == UNDEF ? VAR : s->type;

}

\n { lineno++; return '\n'; }

/* everything else */

. { return yytext[0]; }

$

Каждое "правило" является регулярным выражением, как и те, что использовались

в

egrep

или

awk

, однако в отличие от них

lex

распознает комбинации в стиле Си типа

\t

и

\n

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

*

и

+

задают сколь угодно длинную строку. Если правило применимо к текущей части входного потока, то выполняется действие. Совпавшая с правилом входная строка доступна в

lex

– программе под именем

yytext

. Чтобы работать в

lex

, нужно изменить файл

makefile

: Программа

make

$ cat makefile

YFLAGS = -d

OBJS = hoc.o lex.o init.o math.o symbol.o

hoc3: $(OBJS)

cc $(OBJS) -lm -ll -o hoc3

hoc.o: hoc.h

lex.o init.o symbol.o: hoc.h y.tab.h

...

$

"знает", как получить из файла

.l

настоящий файл

.o

; все, что требуется от нас, дать ей сведения о зависимостях. (Нужно добавить библиотеку

lex -ll

к списку каталогов, в которых ведет поиск команда сс, поскольку распознаватель, создаваемый

lex

, нуждается в дополнительных функциях.) Эффект получается весьма ощутимым, причем совершенно автоматически:

$ make

yacc -d hoc.y

 conflicts: 1 shift/reduce

сс -с y.tab.c

rm y.tab.c

mv y.tab.o hoc.o

lex lex.l

сс -с lex.yy.c

rm lex.yy.c

mv lex.yy.o lex.o

сс -c init.c

сс -c math.c

сс -c symbol.c

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

$

Если один файл изменится, достаточно единственной команды

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

будет для вас хорошей практикой.

Упражнение 8.9

Сравните размеры двух версий

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