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

yylex:

$ cat lex.l
%{
#include "hoc.h"
#include "y.tab.h"

extern int lineno;
%}
%%
[ \t] { ; } /* skip blanks and tabs */
[0-9]+\.?][0-9]*\.[0-9]+ {
 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         … для переменной xassign    Записать значение в переменную, убрать указательpop       Убрать верхний элемент из стекаSTOP      Конец последовательности команд

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

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

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