Первоначально системе UNIX предназначалась роль среды для разработки программ. В настоящей главе мы обсудим некоторые применяемые с этой целью программные средства на примере солидной программы — интерпретатора языка программирования, сравнимого по мощности с Бейсиком. Мы выбрали реализацию языка, потому что возникающие здесь проблемы характерны для больших программ. Более того, многие программы полезно рассматривать как языковые процессоры, преобразующие входной поток определенной структуры в последовательность действий и выходной поток, т. е. мы хотим продемонстрировать вам программные средства разработки языков.
В частности, вашему вниманию предлагаются следующие программы:
• yacc — генератор синтаксических анализаторов; программа, которая по описанию грамматики языка порождает анализатор;
• make — программа, определяющая процесс компиляции сложных программ и управляющая им;
• lex — программа, аналогичная yacc, но создающая лексические анализаторы.
Мы покажем вам приемы разработки программ в несколько этапов — от простого к сложному. Ниже описаны шесть этапов реализации языка, каждый из которых поучителен уже сам по себе. Эти этапы отражают реальный процесс написания программы:
1. Создание калькулятора с четырьмя действиями: +, -, *, / (и со скобками). Калькулятор выполняет операции над числами с плавающей точкой, каждая строка состоит из одного выражения; полученное значение печатается сразу.
2. Добавление переменных с именами от а до z. В этой версии есть также унарный минус и некоторые средства защиты от ошибок.
3. Добавление переменных с именами произвольной длины, встроенных функций для sin, exp и т.п., полезных констант типа π (обозначается как PI) и операции возведения в степень.
4. Внесение внутренних изменений: оператор вычисляется не непосредственно, а порождает код, который впоследствии интерпретируется. Новые возможности не добавляются, но подготавливается переход к п. 5.
5. Добавление структур управления: if-else и while — группирование операторов с помощью и и операции отношений типа >, <= и т.п.
6. Добавление рекурсивных процедур и функций с параметрами, а также операторов для ввода-вывода строк и чисел.
Окончательная версия языка описана в гл. 9 как пример программных средств подготовки документации системы UNIX. В приложении 2 приводится справочное руководство по калькулятору.
Эта глава довольно объемная, поскольку в ней детально рассматривается, как правильно написать нетривиальную программу. Предполагается, что вы знаете язык Си и имеете под рукой экземпляр справочного руководства по системе UNIX (том 2), поскольку просто невозможно объяснить все нюансы. Будьте готовы к тому, что вам придется прочитать главу несколько раз. Окончательная версия полностью представлена в приложении 3. Заметим, кстати, что мы долго спорили из-за имени языка, но так и не придумали подходящее. Остановились на hoc, что означает "калькулятор высокого уровня" (high level calculator).
Его версии соответственно называются hoc1, hoc2 и т.д.
8.1 Этап 1: калькулятор с четырьмя действиями
Прежде всего рассмотрим реализацию hoc1 — программы с такими же возможностями, как и простейший карманный калькулятор, но гораздо менее удобной для переноса. Она выполняет четыре операции: +, -, *, / и, имеет скобки с произвольной глубиной вложенности, чем обладают лишь немногие калькуляторы. Если вы введете выражение и символ RETURN, результат будет напечатан в следующей строке:
$ hoc1
4*3*2
24
(1+2)*(3+4)
21
1/2
0.5
355/113
3.1415929
-3 - 4
hoc1 : syntax error near line 4 No unary minus yet
$
Грамматика
С появлением формы Бэкуса-Наура, предложенной для Алгола, языки стали описываться с помощью формальной грамматики. Абстрактное описание грамматики hoc1 простое и краткое:
список: выраж \n
список выраж \n
выраж: NUMBER
выраж + выраж
выраж - выраж
выраж * выраж
выраж / выраж
( выраж )
Здесь список — последовательность выражений, каждое из которых завершается символом перевода строки, а выражение — число или пара выражений, объединенных операцией, либо выражение в скобках.
Приведенное описание не полное, так как в нем не определены естественный приоритет и ассоциативность операций, а также не заданы значения конструкциям языка. Хотя список специфицируется через выраж, а оно в свою очередь через NUMBER, само NUMBER нигде не определено, Поэтому чтобы перейти от упрощенного описания к работающей программе, необходимо внести ясность в эти вопросы.
Программа yacc
Генератор синтаксических анализаторов yacc преобразует компилятор грамматических правил языка, подобных приведенным выше, в анализатор, который разбирает операторы языка. Yacc обладает возможностью приписывать значения компонентам грамматики таким образом, что в процессе разбора значение может быть "вычислено" . Используется yacc поэтапно,
На первом этапе записывается грамматика языка, но более точно, чем было показано ранее, т.е. определяется синтаксис. На этом этапе назначение yacc — предупреждение появления ошибок и двусмысленностей в грамматике.
На втором этапе каждое правило (правило вывода грамматики) сопровождается описанием действия на тот случай, когда найден экземпляр грамматической конструкции в разбираемой программе. Часть действия записывается на Си, причем должны выполняться определенные соглашения о связи между грамматикой и текстом. Здесь определяется семантика языка.
Третий этап — создание лексического анализатора, который должен читать разбираемый входной поток и разбивать его для анализатора на осмысленные единицы. Примером лексической единицы длиной в несколько символов может служить NUMBER; операции из одного символа, такие, как + и *, также являются лексическими единицами. По традиции лексические единицы называют лексемами.
На следующем этапе разрабатывается управляющая процедура, которая вызывает анализатор, созданный yacc.
Программа yacc преобразует грамматику и семантические процедуры в функцию разбора с именем yyparse и записывает ее в виде файла с текстом на Си. Если yacc не находит ошибок, то анализатор, лексический анализатор и управляющую процедуру можно откомпилировать, возможно, связать с другими программами на Си и выполнить.
Действие yacc сводится к многократному обращению к лексическому анализатору за лексемами, распознаванию грамматических (синтаксических) конструкций во входном потоке и выполнению семантических процедур по мере распознавания грамматических правил. Вызывать лексический анализатор нужно по имени yylex, так как именно эту функцию инициирует анализатор yyparse всякий раз, когда ему нужна следующая лексема. (Все имена, используемые yacc, начинаются с y.)
Чтобы быть более точными, укажем, что входной поток для yacc должен иметь такой вид:
%{
Операторы Си типа #include, описания и т. д.
Эта часть необязательна.
%}
yacc-описания: лексемы, грамматические переменные,
информация о приоритетах и ассоциативности
%%
грамматические правила и действия
%%
еще операторы Си (необязательно):
main() {
...; yyparse(); ...
}
yylex() {
...
}
...
Этот поток поступает на вход yacc, а результат записывается в файл y.tab.c, имеющий следующую структуру:
Операторы на Си между %{ и %}, если есть
Операторы на Си из части после второй комбинации %%, если есть:
main() {
...; yyparse(); ...
}
yylex() {
...
}
...
yyparse() {
анализатор, который вызывает yylex()
}
Такой подход типичен для системы UNIX: yacc выдает текст на Си, а не оттранслированный файл (.o), что является наиболее гибким решением, так как созданный текст, переносим и легко поддается любому другому преобразованию (если появится хорошая идея).
Генератор yacc сам по себе представляется мощным программным средством. Его изучение потребует от вас, конечно, некоторых усилий, но все ваши "затраты" многократно окупятся. Анализаторы, создаваемые yacc, — небольшие, эффективные и корректные (хотя за семантические преобразования отвечаете вы). Кроме того, многие неприятные проблемы, связанные с процессом разбора, решаются автоматически. Программы языковых распознавателей достаточно легко создавать и, что, возможно, еще более важно, изменять по мере совершенствования определения языка.
Использование программ на этапе 1
Исходный текст hoc1 состоит из грамматических правил с описанием действий лексической процедуры yylex и функции main, хранимых в одном файле hoc.y. (Имена файлов, содержащих текст для yacc, традиционно оканчиваются на .y, но это соглашение в отличие от соглашения о сс и .c не поддерживает сам yacc.) Грамматика составляет первую половину файла hoc.y:
$ cat hoc.y
%{
#define YYSTYPE double /* data type of yacc stack */
%}
%token NUMBER
%left '+' /* left associative, same precedence */
%left '*' '/' /* left assoc., higher precedence */
%%
list: /* nothing */
| list '\n'
| list expr '\n' { printf("\t%.8g\n", $2); }
;
expr: NUMBER { $$ = $1; }
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr { $$ = $1 / $3; }
| '(' expr ')' { $$ = $2; }
;
%%
/* end of grammar */
...
Вы видите, как много информации заключено в этих нескольких строках. Поскольку мы не можем вам здесь все объяснить, в частности, как работает синтаксический анализатор, обратитесь к справочному руководству по yacc.
Альтернативные правила разделены символом '|'. С каждым грамматическим правилом может быть связано определенное действие, которое выполняется, когда экземпляр этого правила распознается во входном потоке. Действие описывается последовательностью операторов Си, заключенной в фигурные скобки. Внутри последовательности $n (т.е. $1, $2 и т.д.) определяет значение, вырабатываемое n-м компонентом правила, а $$ значение, вырабатываемое всеми компонентами правила в целом. Так, в правиле
expr: NUMBER { $$ = $1; }
$1 — значение, вырабатываемое при распознавании NUMBER, и оно же является результирующим значением expr. В данном случае присваивание $$ = $1 может быть опущено, так как $$ всегда принимает значение $1 (если не устанавливается явно каким либо иным образом). В следующей строке с правилом
expr: expr '+' expr { $$ = $1 + $3; }
результирующее значение expr является суммой двух компонентов, тоже expr. Отметим, что $2 соответствует '+' т.е. каждый компонент пронумерован.
Строкой выше выражение, за которым следует символ перевода строки ('\n'), распознается как список, и печатается его значение. Если за такой конструкцией следует конец входного потока, процесс разбора завершается правильно. Список может быть пустой строкой; так учитываются пустые входные строки.
Формат входного потока для yacc — произвольный. Наш формат рекомендуется как стандартный.
В этой реализации процесс распознавания или разбора входного потока приводит к немедленному вычислению выражения. В более сложных решениях (включая hoc4 и его последующие версии) процесс разбора порождает код для дальнейшего выполнения.
Наглядно представить разбор вам поможет рис. 8.1, где изображено дерево разбора. Кроме того, вы должны знать, как вычисляются значения и как они распространяются от листьев к корню дерева.
Рис. 8.1: Дерево разбора для 2 + 3*4
Реально значения не полностью разобранных правил хранятся в стеке и через стек передаются от одного правила к следующему. Обычно данные в стеке имеют целый тип, но поскольку мы в своей работе используем числа с плавающей точкой, необходимо переопределить значение по умолчанию. Определение
#define YYSTYPE double
устанавливает двойную точность для типа данных стека.
Теперь перейдем к описанию синтаксических классов, распознаваемых лексическим анализатором, если только они не являются литералами, состоящими из одного символа вида '+' и '-'. Описание %token специфицирует одни или несколько таких объектов. При необходимости можно задать левую или правую ассоциативность, используя %left или %right вместо %token.
(Левая ассоциативность означает, что a-b-с будет разбираться как (а - b) - с, а не а - (b - с).) Приоритет устанавливается порядком появления операции: лексемы из одного определения имеют один и тот же приоритет, а лексемы, специфицированные позднее, — более высокий. Таким образом, в грамматике может быть неоднозначность (т.е. для некоторых входных потоков существует несколько способов разбора), но дополнительная информация в определениях разрешает эту неоднозначность.
Вторую половину файла hoc.y составляют процедуры:
/* Продолжение hoc.y */
#include
#include
char *progname; /* for error messages */
int lineno = 1;
main(argc, argv) /* hoc1 */
char *argv[];
{
progname = argv[0];
yyparse();
}
Функция main обращается к yyparse для разбора входного потока. Переход в цикле от одного выражения к другому происходит в рамках грамматики с помощью последовательности правил вывода для списка. Приемлемо также обращаться в цикле к yyparse из функции main, если действия для списка предполагают печать значения и немедленный возврат.
Функция yyparse в свою очередь многократно обращается за лексемами из входного потока к функции yylex. Наша функция yylex проста: в ее задачи входят пропуск пробелов и символов табуляции, преобразование цифровых строк в числовое значение и подсчет входных строк для вывода сообщений об ошибках. Поскольку грамматика допускает только +, -, *, /, (, ) и \n, при появлении любого другого символа yyparse выдает сообщение об ошибке. Получение 0 означает для yyparse "конец файла".
/* Продолжение hoc.y */
yylex() /* hoc1 */
{
int с;
while ((c=getchar()) == ' ' || с == '\t')
;
if (c == EOF)
return 0;
if (c == '.' || isdigit(c)) {
/* number */
ungetc(c, stdin);
scanf("%lf", &yylval);
return NUMBER;
}
if (c == '\n')
lineno++;
return с;
}
Переменная yylval используется для связи между синтаксическим и лексическим анализаторами; она определена в yyparse и имеет тот же тип, что стек yacc. Функция yylex возвращает тип лексемы, равно как и ее функциональное значение, и приравнивает yylval значению лексемы (если оно есть). Например, число с плавающей точкой имеет тип NUMBER и значение, скажем, 12.34. Для некоторых лексем, прежде всего состоящих из одного символа, таких, как '+' или '\n', в грамматике используется только тип. В этом случае yylval не нужно определять.
Определение %token NUMBER из входного файла для yacc преобразуется в оператор #define в выходном файле y.tab.c, поэтому NUMBER можно использовать в качестве константы в любом месте Си программы. Yacc выбирает такие значения, которые не будут смешиваться с символами ASCII.
При наличии синтаксической ошибки yyparse обращается к yyerror со строкой, содержащей загадочное сообщение: "syntax error" ("синтаксическая ошибка"). Предполагается, что функцию yyerror предоставляет пользователь: в нашей функции строка просто передается другой функции — warning, которая выдает некоторую дополнительную информацию. В последующих версиях hoc функция warning будет применяться непосредственно.
yyerror(s) /* called for yacc syntax error */
char *s;
{
warning(s, (char*)0);
}
warning(s, t) /* print warning message */
char *s, *t;
{
fprintf(stderr, "%s: %s", progname, s);
if (t)
fprintf(stderr, " %s", t);
fprintf(stderr, " near line %d\n", lineno);
}
Этим завершаются процедуры файла hoc.y. Трансляция программы для yacc происходит в два этапа:
$ yacc hoc.y Выходной поток попадает в y.tab.c
$ сс y.tab.c -о hoc1 Выполняемая программа попадает в hoc1
$ hoc1
2/3
0.66666667
-3-4
hoc1: syntax error near line 1
$
Упражнение 8.1
Исследуйте структуру файла y.tab.c (для hoc1 это составляет около 300 строк текста).
Внесение изменений — унарный минус
Ранее мы утверждали, что, работая с yacc, легко менять язык. В качестве примера добавим к hoc1 унарный минус, чтобы выражения типа
-3-4
вычислялись, а не отвергались как синтаксические ошибки. Всего две строки нужно дополнительно включить в hoc.y. Добавляется новая лексема UNARYMINUS в ту часть грамматики, где задаются приоритеты, чтобы унарный минус имел наивысший приоритет:
%left '+' '-'
%left '*' '/'
%left UNARYMINUS /* новая лексема */
Грамматика увеличивается на одно правило для expr:
expr: NUMBER ($$= $1;}
| '-' expr %prec UNARYMINUS {$$=- $2} /* новое */
Определение %prec "говорит", что символ унарного минуса (т.е. знак "-" перед выражением) имеет тот же приоритет, что и UNARYMINUS (наивысший); действие заключается в изменении знака. Приоритет минуса между двумя выражениями устанавливается по умолчанию.
Упражнение 8.2
Добавьте операции % (взятие остатка) и унарный плюс к hoc1 . Рекомендация: обратитесь к справочному руководству по frexp(3) .
Некоторые замечания относительно make
Обидно, что приходится вводить две команды для компиляции hoc1. Хотя, конечно, нетрудно составить командный файл для такого задания, но есть лучший способ, который позднее можно распространить на тот случай, когда программа состоит из нескольких исходных файлов. Программа make читает описания взаимозависимости компонентов программы и позволяет создать ее действующую версию. Она проверяет время последней модификации каждого компонента, выясняет минимальный объем перекомпиляции, которую необходимо выполнить для получения новой действующей версии, и затем запускает процесс. Программа make разбирается в запутанных многошаговых процессах, в частности в yacc, поэтому ей можно давать задания, не уточняя отдельные шаги.
Особенно полезно обращаться к make, когда создаваемая программа настолько велика, что "располагается" в нескольких исходных файлах. Однако она удобна и для таких малых программ, как hoc1. Ниже приведены описания команд для make, рассчитанные на hoc1, которые make предполагает найти в файле с именем makefile.
$ cat makefile
hoc1: hoc.o
cc hoc.o -o hoc1
$
Здесь сообщается, что hoc1 зависит от hoc.o и что hoc1 создается из hoc.o с помощью команды сс, которая запускает компилятор Си, помещая выходной поток в файл hoc1. Программа make уже "знает", как преобразовать входной файл для yacc hoc.y в выходной файл hoc.o:
$ make Проделаем первый раз получение hoc1 с помощью make
yacc hoc.y
сс -с y.tab.c
rm y.tab.c
mv y.tab.o hoc.о
сс hoc.о -о hoc1
$ make Попробуем еще раз
'hoc1' is up to date make понимает, что это не нужно
$
8.2 Этап 2: переменные и восстановление после ошибки
Следующий шаг переход от hoc1 к hoc2, который сводится к расширению памяти (в памяти хранится 26 переменных с именами от а до z). Это довольно несложный и весьма полезный промежуточный этап. Мы также введем здесь процесс обработки ошибок. Если вы проверите hoc1, то убедитесь, что реакцией на синтаксические ошибки являются вывод сообщения и прекращение работы. Поведение же hoc1 в случае арифметических ошибок типа деления на нуль достойно всяческого порицания:
$ hoc1
1/0
Floating exception - core dump
$
Для реализации новых возможностей требуются лишь небольшие изменения: приблизительно 35 строк текста. Лексический анализатор yylex должен распознавать буквы как переменные, а грамматика содержать правила вывода вида
expr: VAR
| VAR '=' expr
Выражение может содержать операцию присваивания; разрешены также многократные присваивания типа
x = y = z = 0
Простейший способ хранения значений переменных создать массив из 26 элементов; однобуквенную переменную можно использовать в качестве индекса массива. Однако если анализатору предстоит обрабатывать и имена переменных, и значения в одном стеке, необходимо сообщить yacc, что элемент стека является объединением double и int, а не просто элементом типа double. Это делается с помощью описания %union. Описания #define или typedef подходят для определения стека из базовых типов как double, но для типов объединения требуется описание %union, поскольку yacc осуществляет контроль типов в выражениях вида $$ = $2.
Ниже приведена часть определения грамматики hoc.y для программы hoc2:
$ cat hoc.y
%{
double mem[26]; /* memory for variables 'a'..'z' */
%}
%union { /* stack type */
double val; /* actual value */
int index; /* index into mem[] */
}
%token
%token
%type
%right '='
%left '+'
%left '*' '/'
%left UNARYMINUS
%%
list: /* nothing */
| list '\n'
| list expr '\n' { printf ("\t%.8g\n", $2); }
| list error '\n' { yyerrok; }
;
expr: NUMBER
| VAR { $$ = mem[$1]; }
| VAR '=' expr { $$ = mem[$1] = $3; }
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr {
if ($3 == 0.0)
execerror("division by zero", "");
$$ = $1 / $3;
}
| '(' expr ')' { $$ = $2; }
| '-' expr %prec UNARYMINUS { $$ = -$2; }
;
%%
/* end of grammar */
...
Из описания %union следует, что элементы стека содержат или число с двойной точностью (обычный случай), или целое, являющееся индексом в массиве mem. В описании %token дополнительно указывается тип значения. В описании %type есть сведения о том, что выраж является элементом объединения
Обработка ошибок происходит в несколько этапов. Прежде всего производится проверка на нулевой делитель: если делитель равен нулю, вызывается процедура обработки ошибок execerror. Второй этап заключается в перехвате сигнала "переполнение вещественного" ("floating point exception"), который возникает при переполнении вещественного числа. Сигнал устанавливается в функции main. Последний шаг восстановления после ошибки заключается в добавлении к грамматике правила вывода для ошибки. В грамматике yacc слово error зарезервировано; оно дает возможность анализатору осознать синтаксическую ошибку и восстановиться после нее. Если произойдет ошибка, yacc в конце концов использует это правило, распознает ошибку как грамматически "правильную" конструкцию и, таким образом, восстановится. Действие yyerrok заключается в установке признака в анализаторе, который позволяет вернуться ему назад в состояние осмысленного разбора. Восстановление после ошибки сложная проблема для всех анализаторов. Мы показали вам здесь лишь самые элементарные приемы и только обозначили возможности yacc.
В грамматике hoс2 произошли незначительные изменения. Ниже приведена функция main, дополненная обращением к setjmp. Оно позволяет запомнить то нормальное состояние, которое будет использовано при восстановлении после ошибки. В функции execerror происходит соответствующее обращение к longjmp. (Описание setjmp и longjmp см. в разд. 7.5.)
...
#include
#include
char *progname;
int lineno = 1;
#include
#include
jmp_buf begin;
main(argc, argv) /* hoc2 */
char *argv[];
{
int fpecatch();
progname = argv[0];
setjmp(begin);
signal(SIGFPE, fpecatch);
yyparse();
}
execerror(s, t) /* recover from run-time error */
char *s, *t;
{
warning(s, t);
longjmp(begin, 0);
}
fpecatch() /* catch floating point exceptions */
{
execerror("floating point exception", (char*)0);
}
В целях отладки мы сочли удобным, чтобы функция execerror вызывала abort (см. справочное руководство по abort(3)), что приведет к распечатке содержимого памяти, которую затем смогут использовать программы adb и sdb. Когда разработка программы полностью завершится, обращение к abort будет заменено на longjmp.
В программе hoc2 лексический анализатор несколько иной. В нем учтено различие строчных и прописных букв, а поскольку теперь yyval является объединением, нужно выбрать подходящий элемент перед выходом из yylex. Ниже показаны измененные фрагменты:
yylex() /* hoc2 */
{
...
if (с == '.' || isdigit(c)) { /* number */
ungetc(c, stdin);
scanf("%lf", &yylval.val);
return NUMBER;
}
if (islower(c)) {
yylval.index = с - 'a'; /* ASCII only */
return VAR;
}
...
Еще раз отметим, что тип лексемы (т.е. NUMBER) не совпадает с ее значением (например, 3.1416).
Продемонстрируем новые возможности hoc2 переменные и способность восстановления после ошибки:
$ hoc2
x = 355
355
y = 113
113
p = x/z z не определено, а значит, равно 0
hoc2: division by zero near line 4 Восстановление после ошибки
x/y
3.1415929
1е30 * 1е30 Переполнение
hoc2: floating point exception near line 5
...
В самом деле, для PDP-11 требуются вполне конкретные меры, чтобы обнаружить переполнение вещественного, но на большинстве других машин hoc2 действует так, как показано выше.
Упражнение 8.3
Обеспечьте возможность запоминания последнего вычисленного значения, чтобы его не приходилось вводить снова для последовательности связанных вычислений. Одним из решений может быть использование какой-либо переменной, например 'p' , в качестве "предыдущего" (previous) значения.
Упражнение 8.4
Измените программу hoc так, чтобы можно было использовать символ ';' как разделитель выражений наравне с символом перевода строки.
8.3 Этап 3: переменные с произвольными именами; встроенные функции
В версию hoc3 добавлено несколько новых средств, из-за чего увеличился текст программы. Основное нововведение возможность обращения к встроенным функциям:
sin cos atan exp log log10 sqrt int abs
Введена также дополнительно операция возведения в степень '^' (право ассоциативная с наивысшим приоритетом).
Поскольку лексический анализатор должен справляться с встроенными именами длиной более чем в один символ, не так уж много усилий придется приложить, чтобы допустить переменные с именами произвольной длины. Для хранения информации об этих переменных нужна довольно сложная таблица имен, но если мы ее создаем, то можно заранее задать в ней вместе с именами значения некоторых полезных констант:
| PI | 3.14159265358979323846 | Число π |
| E | 2.71828182845904523536 | Основание натурального логарифма |
| GAMMA | 0.57721566490153286060 | Константа Эйлера-Маскерони |
| DEG | 57.2957795130823208768 | Отношение градуса к радиану |
| PHI | 1.61803398874989484820 | Золотое сечение |
В результате получим полезный калькулятор:
$ hoc3
1.5^2.3
2.5410306
exp(2*3*log(1.5))
2.5410306
sin(PI/2)
1
atan(1)*DEG
45
Несколько улучшилась и работа распознавателя. В hoc2 присваивание x = expr не только вызывало присваивание, но и приводило к печати значения, поскольку все выражения печатаются:
$ hoc2
x=2*3.14159
6.28318 В случае присваивания переменной значение печатается
В программе hoc3 проводится различие между присваиваниями и выражениями; значения печатаются только для выражений:
$ hoc3
x=2*3.14159 Присваивание: значение не печатается
x Выражение:
6.28318 Значение печатается
Получившаяся в результате всех этих изменений программа настолько велика (около 250 строк текста), что для простоты редактирования и ускорения компиляции лучше разбить ее на отдельные файлы. Итак, теперь мы имеем пять файлов вместо одного:
| hoc.y | грамматика, main , yylex (как и прежде); |
| hoc.h | глобальные структуры данных для включения в другие файлы; |
| symbol.c | функции, работающие с таблицей имен: lookup , install ; |
| unit.c | встроенные функции и константы; init ; |
| math.c | функции для вызова стандартных математических функций: Sqrt , Log и т.д. |
Необходимо более детально познакомиться с работой Си программы, состоящей из нескольких файлов, и программы make, чтобы переложить на нее часть своих обязанностей.
Вернемся снова к программе make и рассмотрим вначале структуру таблицы имен. Поименованный объект имеет имя, тип (VAR или BLTIN) и значение. Так, объект типа VAR имеет значение double; если объект является встроенным, то его значением служит указатель на функцию, возвращающую double. Данная информация используется в hoc.y, symbol.c и init.c. Ее можно размножить в трех экземплярах, но тогда легко ошибиться или забыть исправить один из экземпляров при внесении изменений. Вместо этого мы поместили общую информацию в файл макроопределений hoc.h, который можно включить при необходимости в любой файл. (Окончание .h традиционно, но не контролируется никакими программами.) В файл makefile также добавлены сведения о зависимости исходных файлов от hoc.h, чтобы при изменении 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();
$
Тип UNDEF обозначает VAR, которой пока не присвоили значения. Объекты связаны в список с помощью элемента next в записи Symbol. Сам список является локальным для symbol.c, доступ к нему возможен только посредством функций lookup и install. Это позволяет в случае необходимости легко менять структуру таблицы имен (что мы уже сделали однажды). Функция lookup отыскивает в списке заданное имя и возвращает указатель на Symbol, если имя найдено, и 0 в противном случае. Таблица имен рассчитана на линейный поиск, что вполне допустимо для диалогового калькулятора, поскольку поиск имен выполняется не во время его работы, а в процессе разбора. Функция install вносит переменную и связанные с ней тип и значение в начало списка. Функция emalloc обращается к стандартной функции размещения malloc (см. справочное руководство по malloc(3)) и проверяет результат. Указанные три функции составляют содержимое файла symbol.c. Файл y.tab.h создается при выполнении команды yacc -d; он содержит операторы #define, порождаемые yacc для лексем NUMBER, VAR, BLTIN и т.д.
$ cat symbol.c
#include "hoc.h"
#include "y.tab.h"
static Symbol *symlist = 0; /* symbol table: linked list */
Symbol *lookup(s) /* find s in symbol table */
char *s;
{
Symbol *sp;
for (sp = symlist; sp != (Symbol*)0; sp = sp->next)
if (strcmp(sp->name, s) == 0)
return sp;
return 0; /* 0 ==> not found */
}
Symbol *install(s, t, d) /* install s in symbol table */
char *s;
int t;
double d;
{
Symbol *sp;
char *emalloc();
sp = (Symbol*)emalloc(sizeof(Symbol));
sp->name = emalloc(strlen(s)+1); /* +1 for '\0' */
strcpy(sp->name, s);
sp->type = t;
sp->u.val = d;
sp->next = symlist; /* put at front of list */
symlist = sp;
return sp;
}
char *emalloc(n) /* check return from malloc */
unsigned n;
{
char *p, *malloc();
p = malloc(n);
if (p == 0)
execerror("out of memory", (char*)0);
return p;
}
$
Файл init.c содержит определения констант (PI и т.п.) и указатели на встроенные функции; они заносятся в таблицу имен функцией init, находящейся в main.
$ cat init.c
#include "hoc.h"
#include "y.tab.h"
#include
extern double Log(), Log10(), Exp(), Sqrt(), integer();
static struct { /* Constants */
char *name;
double cval;
} consts[] = {
"PI", 3.14159265358979323846,
"E", 2.71828182845904523536,
"GAMMA", 0.57721566490153286060, /* Euler */
"DEG", 57.29577951308232087680, /* deg/radian */
"PHI", 1.61803398874989484820, /* golden ratio */
0, 0
};
static struct { /* Built-ins */
char *name;
double (*func)();
} builtins[] = {
"sin", sin,
"cos", cos,
"atan", atan,
"log", Log, /* checks argument */
"log10", Log10, /* checks argument */
"exp", Exp, /* checks argument */
"sqrt", Sqrt, /* checks argument */
"int", integer,
"abs", fabs,
0, 0
};
init() /* install constants and built-ins in table */
{
int i;
Symbol *s;
for (i = 0; consts[i].name; i++)
install(consts[i].name, VAR, consts[i].cval);
for (i = 0; builtins[i].name; i++) {
s = install(builtins[i].name, BLTIN, 0.0);
s->u.ptr = builtins[i].func;
}
}
Данные хранятся в таблицах, а не вводятся в текст программы, чтобы легче было их читать и изменять. Таблицы определены как статические, что обеспечивает их доступность только в данном файле. Мы вскоре вернемся к обсуждению стандартных математических функций типа Log и Sqrt.
Построив такой базис, можно перейти к изменениям в грамматике, которые осуществляются на его основе.
$ cat hoc.y
%{
#include "hoc.h"
extern double Pow();
%}
%union {
double val; /* actual value */
Symbol *sym; /* symbol table pointer */
}
%token
%token
%type
%right '='
%left '+'
%left '*' '/'
%left UNARYMINUS
%right '^' /* exponentiation */
%%
list: /* nothing */
| list '\n'
| list asgn '\n'
| list expr '\n' { printf("\t%.8g\n", $2); }
| list error '\n' { yyerrok; }
;
asgn: VAR '=' expr { $$=$1->u.val=$3; $1->type = VAR; }
;
expr: NUMBER
| VAR {
if ($1->type == UNDEF)
execerror("undefined variable", $1->name);
$$ = $1->u.val;
}
| asgn
| BLTIN '(' expr ')' { $$ = (*($1->u.ptr))($3); }
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr {
if ($3 == 0.0)
execerror("division by zero", ""); $$ = $1 / $3;
}
| expr '^' expr { $$ = Pow($1, $3); }
| '(' expr ')' { $$ = $2; }
| '-' expr %prec UNARYMINUS { $$ = -$2; }
;
%%
/* end of grammar */
...
Теперь в грамматике присутствует asgn для присваивания, подобно expr для выражения. Входная строка, состоящая только из
VAR = expr
является присваиванием, и, следовательно, ни одно из значений не печатается. Заметьте, кстати, как мы легко добавили к грамматике операцию возведения в степень, являющуюся правоассоциативной.
Для стека yacc используется другое определение %union: вместо представления переменной как индекса в массиве из 26 элементов введен указатель на объект типа Symbol. Файл макроопределений hoc.h содержит определение этого типа.
Лексический анализатор распознает имена переменных, находит их в таблице имен и определяет, относятся ли они к переменным (VAR) или к встроенным функциям (BLTIN). Функция yylex возвращает один из указанных типов. Заметим, что определенные пользователем переменные и предопределенные переменные типа PI относятся к VAR.
Одно из свойств переменной состоит в том, что ей может быть присвоено либо не присвоено значение, поэтому обращение к не определенной переменной должно диагностироваться программой yyparse как ошибка. Возможность проверки переменной (определена она или нет) должна быть предусмотрена в грамматике, а не в лексическом анализаторе. Когда VAR распознается на лексическом уровне, контекст пока еще не известен, но нам не нужны сообщения о том, что x не определен, хотя контекст и вполне допустимый, как, например, x в присваивании типа x = 1.
Ниже приводится измененная часть функции yylex:
yylex() /* hoc3 */
{
...
if (isalpha(c)) {
Symbol *s;
char sbuf[100], *p = sbuf;
do {
*p++ = c;
} while ((c=getchar()) != EOF && isalnum(c));
ungetc(c, stdin);
*p = '\0';
if ((s=lookup(sbuf)) == 0)
s = install(sbuf, UNDEF, 0.0);
yylval.sym = s;
return s->type == UNDEF ? VAR : s->type;
}
...
В функции main добавлена еще одна строка, в которой вызывается процедура инициации init для занесения в таблицу имен встроенных и предопределенных имен типа PI:
main(argc, argv) /* hoc3 */
char *argv[];
{
int fpecatch();
progname = argv[0];
init();
setjmp(begin);
signal(SIGFPE, fpecatch);
yyparse();
}
Теперь остался только файл math.с. Для некоторых стандартных математических функций требуется обработка ошибок для диагностики и восстановления, например, стандартная функция по умолчанию возвращает 0, если аргумент отрицателен. Функции из файла math.с используют контроль ошибок, описанный в разд. 2 справочного руководства по UNIX (см. гл. 7). Это более надежный и переносимый вариант, чем введение своих проверок, так как, вероятно, конкретные ограничения функций полнее учитываются в "официальной" программе. Файл макроопределений
$ cat math.с
#include
#include
extern int errno;
double errcheck();
double Log(x)
double x;
{
return errcheck(log(x), "log");
}
double Log10(x)
double x;
{
return errcheck(log10(x), "log10");
}
double Sqrt(x)
double x;
{
return errcheck(sqrt(x), "sqrt");
}
double Exp(x)
double x;
{
return errcheck(exp(x), "exp");
}
double Pow(x, y)
double x, y;
{
return errcheck(pow(x,y), "exponentiation");
}
double integer(x)
double x;
{
return (double)(long)x;
}
double errcheck(d, s) /* check result of library call */
double d;
char *s;
{
if (errno == EDOM) {
errno = 0;
execerror(s, "argument out of domain");
} else if (errno == ERANGE) {
errno = 0;
execerror(s, "result out of range");
}
return d;
}
Любопытная, хотя грамматически неясная, диагностики появится при запуске yacc с новой грамматикой:
$ yacc hoc.y
conflicts: 1 shift/reduce
$
Сообщение shift/reduce означает, что грамматика hoc3 неоднозначна: единственная входная строка
x=1
может быть разобрана двумя способами.
Анализатор может решить, что присв сводится к выраж, а затем к список, как показано в левом дереве разбора, или что нужно применить заключающий символ \n сразу (shift — перенос) и преобразовать все в список, не используя промежуточных выводов, как в правом дереве разбора. Встретив неоднозначность, yacc выбирает перенос, так как это почти всегда правильное решение для реальных грамматик. Вы должны понимать такие сообщения, чтобы быть уверенным, что yacc сделал правильный выбор. Запуск yacc с флагом -v порождает обширный файл с именем y.output, который поможет вам найти причины конфликтов.
Упражнение 8.5
В данной версии hoc3 допустимо присваивание:
PI=3
Хорошо ли это? Как бы вы изменили hoc3 , чтобы запретить присваивание "констант"?
Упражнение: 8.6
Добавьте к грамматике встроенную функцию atan2(x, y) для вычисления величины угла, тангенс которого равен x/y . Добавьте встроенную функцию rand() , вырабатывающую случайные вещественные числа, равномерно распределенные на интервале [0,1). Как бы вам пришлось изменить грамматику, чтобы разрешить встроенные функции с разным числом аргументов?
Упражнение 8.7
Как ввести дополнительное средство для выполнения команд прямо в hoc , подобно операции ! в программах UNIX?
Упражнение 8.8
Переработайте текст math.c так, чтобы можно было использовать таблицу, а не предложенное выше множество идентичных функций.
Еще одно замечание относительно make
Поскольку теперь программа hoc3 размещается не в одном, а в пяти файлах, makefile становится более сложным:
$ cat makefile
YFLAGS = -d # force creation of y.tab.h
OBJS = hoc.o init.o math.o symbol.o # abbreviation
hoc3: $(OBJS)
cc $(OBJS) -lm -o hoc3
hoc.o: hoc.h
init.o symbol.o: hoc.h y.tab.h
pr:
@pr hoc.y hoc.h init.c math.c symbol.c makefile
clean:
rm -f $(OBJS) y.tab.[ch]
$
Строка YFLAGS = -d добавляет флаг -d в командную строку запуска yacc, создаваемую make. Этот флаг предписывает yacc создать файл y.tab.h, содержащий операторы #define. Строка OBJS = ... вводит сокращение для записи конструкции, используемой последовательно несколько раз. Синтаксис здесь не такой, как для переменных интерпретатора, скобки обязательны. Флаг -lm указывает, что математические функции нужно искать в библиотеке libm.a.
Теперь программа hoc3 образуется из четырех файлов .о, причем некоторые из них в свою очередь зависят от файлов .h. "Зная" эти зависимости, make может рассчитать, какая требуется перетрансляция в случае изменения любого из указанных файлов. Если вы хотите выяснить действия make, не запуская процесс, то попробуйте ввести команду
$ make -n
С другой стороны, если необходимо установить временную согласованность файлов, с помощью флага -t (touch исправить) вы можете как бы модифицировать файлы, не производя перетрансляции.
Обратите внимание на то, что мы ввели не только множество зависимостей между исходными файлами, но и несколько полезных процедур, сконцентрировав их в одном файле. По умолчанию программа make выполняет первое действие, указанное в файле makefile. Однако если на первом месте окажется элемент, помечающий правило зависимости, такой, как symbol.o или pr, то выполняться будет он. Считается, что в случае "пустой" зависимости элемент всегда берется не из последней версии, поэтому при запросе он обязательно должен изменяться. Итак,
$ make pr | lpr
инициирует распечатку зависимостей файлов на принтере. (Появление символа @ в "@pr" подавляет эхо выполняемой команды, запущенной с помощью make.) Команда же
make clean
удаляет выходные файлы yacc, а также файлы .o.
Такой механизм пустых зависимостей в файле makefile часто оказывается более предпочтительным по сравнению с командным файлом как средство для концентрации в одном файле всех связанных операций. Область применения команды make не ограничивается только разработкой программ, она позволяет сгруппировать в единый набор все операции, имеющие временные зависимости.
Несколько замечаний относительно lex
Программа lex порождает лексические анализаторы аналогично тому, как yacc генерирует программы грамматического разбора: вы создаете описание лексических правил вашего языка с помощью регулярных выражений и фрагментов Си программ, которые будут выполняться при обнаружении строки, соответствующей шаблону. Программа lex строит по этой информации распознаватель. Программы lex и yacc взаимодействуют таким же образом, как и описанные выше лексические анализаторы. Мы не собираемся здесь детально рассматривать lex; наша цель — заинтересовать вас, а подробности вы найдете в справочном руководстве по UNIX (том 2B).
Вначале приведем lex-программу из файла lex.l, которая заменяет применявшуюся до сих пор функцию 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 … для переменной 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
%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%.8g\n", 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. Попытайтесь реализовать его в качестве упражнения.
И снова о make
По мере увеличения исходного текста программы 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 остался тем же.
Упражнение 8.10
Сделайте размеры стека и массива prog динамическими, чтобы для hoc4 всегда хватало объема памяти, если только ее можно получить, обращаясь к функции malloc .
Упражнение 8.11
Измените hoc4 так, чтобы использовать в функции execute вместо вызова функций переключатель по виду операции + . Каково соотношение версий по размеру исходного текста и по времени выполнения? Как приблизительно их сопоставить по сложности развития и поддержания?
8.5 Этап 5: структуры управления и операции отношений
Версия hoc5 оправдывает все затраты, связанные с созданием интерпретатора. В нее допустимо включать операторы if-else и while, аналогичные операторам языка Си, группировать операторы с помощью { и } и использовать оператор print. Она содержит полный набор операций отношений (>, >=, и т.д.), а также операций AND, OR, && и ||. (Две последние операции не гарантируют вычисления слева направо, хотя такой подход принят в Си; вычисляются оба условия, даже если в этом нет необходимости.)
Грамматику hoc5 дополняют лексемы, нетерминальные символы и правила для if, while, фигурных скобок и операций отношений. Поэтому она получилась несколько больше, но не намного сложнее предыдущих версий (возможно, за исключением правил для if и while):
$ 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
%type
%right '='
%left OR
%left AND
%left GT GE LT LE EQ NE
%left '+'
%left '*' '/'
%left UNARYMINUS NOT
%right '^'
%%
list: /* nothing */
| list '\n'
| list asgn '\n' { code2(pop, STOP); return 1; }
| list stmt '\n' { code(STOP); return 1; }
| list expr '\n' { code2(print, STOP); return 1; }
| list error '\n' { yyerrok; }
;
asgn: VAR '=' expr { $$=$3; code3(varpush, (Inst)$1, assign); }
;
stmt: expr { code(pop); }
| PRINT expr { code(prexpr); $$ = $2; }
| while cond stmt end {
($1)[1] = (Inst)$3; /* body of loop */
($1)[2] = (Inst)$4; } /* end, if cond fails */
| if cond stmt end { /* else-less if */
($1)[1] = (Inst)$3; /* thenpart */
($1)[3] = (Inst)$4; } /* end, if cond fails */
| if cond stmt end ELSE stmt end { /* if with else */
($1)[1] = (Inst)$3; /* thenpart */
($1)[2] = (Inst)$6; /* elsepart */
($1)[3] = (Inst)$7; } /* end, if cond fails */
| '{' stmtlist '}' { $$ = $2; }
;
cond: '(' expr ')' { code(STOP); $$ = $2; }
;
while: WHILE { $$ = code3(whilecode, STOP, STOP); }
;
if: IF { $$=code(ifcode); code3(STOP, STOP, STOP); }
;
end: /* nothing */ { code(STOP); $$ = progp; }
;
stmtlist: /* nothing */ { $$ = progp; }
| stmtlist '\n'
| stmtlist stmt
;
expr: NUMBER { $$ = code2(constpush, (Inst)$1); }
| VAR { $$ = code3(varpush, (Inst)$1, eval); }
| asgn
| BLTIN '(' expr ')'
{ $$ = $3; code2(bltin, (Inst)$1->u.ptr); }
| '(' expr ')' { $$ = $2; }
| expr '+' expr { code(add); }
| expr '-' expr { code(sub); }
| expr '*' expr { code(mul); }
| expr '/' expr { code(div); }
| expr '^' expr { code (power); }
| '-' expr %prec UNARYMINUS { $$ = $2; code(negate); }
| expr GT expr { code(gt); }
| expr GE expr { code(ge); }
| expr LT expr { code(lt); }
| expr LE expr { code(le); }
| expr EQ expr { code(eq); }
| expr NE expr { code(ne); }
| expr AND expr { code(and); }
| expr OR expr { code(or); }
| NOT expr { $$ = $2; code(not); }
%%
/* end of grammar */
В грамматике есть пять случаев неоднозначности типа сдвиг/свертка, подобных упомянутой в грамматике для hoc3.
Обратите внимание на то, что команды STOP, завершающие последовательность операторов, теперь порождаются в нескольких местах. Как и прежде, progp здесь представляет собой адрес очередной создаваемой команды. При выполнении все команды STOP служат для завершения цикла в функции execute. Правило для понятия все по сути является подпрограммой, вызываемой из нескольких мест, именно оно порождает команду STOP и возвращает адрес следующей за ней команды.
Команды, создаваемые для операторов if и while, требуют особого рассмотрения. Когда встречается ключевое слово while, порождается операция whilecode, и адрес этой команды возвращается в качестве значения правила
пока: WHILE
Но в то же самое время резервируются два следующих машинных слова, которые будут определены ниже. Далее создаются команды для выражения, которое образует условие в операторе while. Значение, возвращаемое правилом cond, является адресом начала команд для условия. После распознавания всего оператора while в два зарезервированных слова, вводимых за командой whilecode, заносится адрес начала тела цикла и адрес оператора, следующего за циклом. (Команда по этому адресу будет создана позднее.)
| пока усл опер все {
($1)[1] = (Inst) $3 /* тело цикла */
($1)[2] = (Inst) $4 /* все, если условие неверно */
}
Здесь $1 обозначает адрес команды whilecode, таким образом, ($1)[1] и ($1)[2] обозначают два следующих слова.
Рисунок, приведенный ниже, может прояснить ситуацию:
С оператором if дело обстоит аналогично, но резервируются три слова: для частей then и else, а также для оператора, следующего за if. Мы вскоре рассмотрим этот случай.
Лексический анализ теперь несколько удлиняется в основном из-за необходимости распознавания дополнительных операций:
yylex() /* hoc5 */
{
...
switch (с) {
case '>': return follow('=', GE, GT);
case '<': return follow('=', LE, LT);
case '=': return follow('=', EQ, '=');
case '!': return follow('=', NE, NOT);
case '|': return follow('|', OR, '|');
case '&': return follow('&', AND, '&');
case '\n': lineno++; return '\n';
default: return c;
}
}
Функция follow "смотрит" на один символ вперед и возвращает символ назад во входной поток с помощью ungetc, если он оказался не тем, который требовался:
follow(expect, ifyes, ifno) /* look ahead for >=, etc. */
{
int с = getchar();
if (c == expect)
return ifyes;
ungetc(c, stdin);
return ifno;
}
В файле hoc.h стало больше описаний функций, например всех отношений, но в общем его структура такая же, как и в hoc4. Ниже приведено несколько последних строк грамматики:
$ cat hoc.h
...
typedef int (*Inst)(); /* machine instruction */
#define STOP (Inst)0
extern Inst prog[], *progp, *code();
extern eval(), add(), sub(), mul(), div(), negate(), power();
extern assign(), bltin(), varpush(), constpush(), print();
extern prexpr();
extern gt(), lt(), eq(), ge(), le(), ne(), and(), or(), not();
extern ifcode(), whilecode();
$
Большая часть файла code.c также не изменилась, хотя, очевидно, здесь появилось много новых процедур для обработки операций отношений. Типичным примером может служить функция le ("less than equal to" меньше или равно).
le() {
Datum d1, d2;
d2 = pop();
d1 = pop();
d1.val = (double)(d1.val <= d2.val);
push(d1);
}
He совсем тривиальными являются функции whilecode и ifcode. Чтобы понять их, необходимо уяснить, что функция execute последовательно обрабатывает команды до тех пор, пока не будет найдена команда STOP, после чего происходит возврат из execute. Процесс разбора построен таким образом, что команда STOP завершает каждую последовательность команд, которую нужно обработать за одно обращение к execute. Тело цикла while, а также условие и фрагменты оператора if после then и else обрабатываются с помощью рекурсивных обращений к execute, возврат из которых по завершении обработки осуществляется в функцию execute на один уровень вложенности выше. Управление этими рекурсивными обращениями обеспечивается в whilecode и ifcode. Последние и предназначены для обработки соответствующих операторов.
whilecode() {
Datum d;
Inst *savepc = pc; /* loop body */
execute(savepc+2); /* condition */
d = pop();
while (d.val) {
execute(*((Inst **)(savepc))); /* body */
execute(savepc+2);
d = pop();
}
pc = *((Inst **)(savepc+1)); /* next statement */
}
Как уже отмечалось ранее, после операции whilecode размещается указатель на тело цикла, затем указатель на следующий оператор, а за ним команды условия. Когда вызывается whilecode, значение указателя pc уже увеличено, так что он содержит указатель на тело цикла. Таким образом, pc+1 настроен на следующий оператор, а pc+2 на команды условия.
Функция ifcode аналогична предыдущей: при входе в нее pc ссылается на фрагмент посте then, pc+1 на фрагмент посте else, pc+2 на следующий оператор, а pc+3 на условие.
ifcode()
{
Datum d;
Inst *savepc = pc; /* then part */
execute(savepc+3); /* condition */
d = pop();
if (d.val)
execute(*((Inst **)(savepc)));
else if (*((Inst **)(savepc+1))) /* else part? */
execute(*((Inst **)(savepc+1)));
pc = *((Inst**)(savepc+2)); /* next stmt */
}
Программа в файле init.c также немного увеличится за счет введения в нее таблицы ключевых слов, хранимых в таблице имен вместе с остальной информацией:
$ cat init.с
...
static struct { /* Keywords */
char *name;
int kval;
} keywords [] = {
"if", IF,
"else", ELSE,
"while", WHILE,
"print", PRINT,
0, 0,
};
...
Для занесения в таблицу имен ключевых слов нужно организовать еще один цикл в функции init:
...
for (i = 0; keywords[i].name; i++)
install(keywords[i].name, keywords[i].kval, 0.0);
...
Изменения в функциях, управляющих таблицей имен, не требуются; в файле code.c есть функция prexpr, которая вызывается при выполнении оператора вида print выраж.
prexpr() /* print numeric value */
{
Datum d;
d = pop();
printf ('"%.8g\n", d.val);
}
Это не та функция печати, которая автоматически вызывается для вывода окончательного результата вычислений. Здесь выбирается число из стека и добавляется символ перевода строки к выходному потоку.
Теперь hoc5 представляет собой вполне полезный калькулятор, хотя для серьезного программирования необходимы дополнительные средства. В приведенных ниже упражнениях предлагаются возможные решения.
Упражнение 8.12
Добавьте для отладки к hoc5 средство печати создаваемых машинных команд в понятной форме.
Упражнение 8.13
Введите в свою программу операции присваивания из языка Си вида += , *= и т.п., а также операции инкремента и декремента ++ и -- . Измените операции && и || так, чтобы обеспечить вычисление слева направо и условное вычисление, как в Си программах.
Упражнение 8.14
Введите в hoc5 оператор for , как в Си-программах. Добавьте операторы break и continue .
Упражнение 8.15
Как бы вы изменили грамматику или лексический анализатор hoc5 (или и то, и другое), чтобы сделать программу более "терпимой" к использованию символов перевода строки? Каким образом можно ввести символ в качестве синонима символа перевода строки? Как ввести в язык примечания? Какой синтаксис, по вашему мнению, нужно использовать?
Упражнение 8.16
Добавьте к hoc5 средства обработки прерываний, чтобы некорректные вычисления можно было остановить без потери значений уже вычисленных переменных.
Упражнение 8.17
Неудобно создавать программный файл, запускать его на выполнение, а затем редактировать с целью внесения небольших изменений. Как бы вы изменили hoc5 , чтобы создать команду редактирования, которая автоматически вызывала бы редактор с уже считанной копией вашей hoc -программы? Подсказка : изучите текст функции.
8.6 Этап 6: функции и процедуры; ввод-вывод
На последнем из описываемых здесь этапе развития программа значительно разрастается: в нее добавляются процедуры и функции, средства печати строк символов наряду с числами и чтения чисел из стандартного входного потока. Кроме того, в язык hoc6 вводятся аргументы имен файлов, включая имя "-", обозначающее стандартный входной поток. Все эти изменения увеличивают программу на 235 строк, доводя ее общий размер до 810 строк. В результате hoc преобразуется из калькулятора в интерпретатор языка программирования. Полностью программа приводится в приложении 3.
В грамматике вызовы функции определяются как выражения, а вызовы процедур как операторы. И то, и другое детально поясняется в приложении 2, где дается еще несколько примеров. Так, определение и использование процедуры печати всех чисел Фибоначчи, меньших заданного параметра, происходят следующим образом:
$ cat fib
proc fib() {
a = 0
b = 1
while (b < $1) {
print b
с = b
b = a+b
a = с
}
print "\n"
}
$ hoc6 fib -
fib(1000)
1 1 2 3 5 8 13 21 34.55 89 144 233 377 610 987
...
Здесь также показано использование файлов: имя файла "-" задает стандартный входной поток.
Ниже приведена функция "факториал":
$ cat fac
func fac() {
if ($1 <= 0) return 1 else return $1 * fac($1-1)
}
$ hoc6 fac -
fac(0)
1
fac(7)
5040
fac(10)
3628800
...
Внутри процедуры или функции к параметрам можно обращаться с помощью $1 и т.д., как в командных файлах, но, кроме того, допустимо присваивание параметрам. Функции и процедуры рекурсивны, но в качестве локальных переменных можно использовать только параметры; остальные переменные являются глобальными, т.е. доступными во всей программе.
В языке hoc функции и процедуры различаются, что дает возможность проверки, ценной для освобождения стека. (Ведь так легко забыть выполнить возврат или записать липшее выражение и получить несбалансированный стек!)
Требуется значительное число изменений для преобразования грамматики при переходе от hoc5 к hoc6, но все они локальные. Нужны новые лексемы и нетерминальные символы, а в описание %union необходимо ввести новый элемент для хранения числа аргументов:
$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 */
int narg; /* number of arguments */
}
%token
%token
%token
%type
%type
%type
%type
%right '='
%left OR
%left AND
%left GT GE LT LE EQ NE
%left '+'
%left '*' '/'
%left UNARYMINUS NOT
%right '^'
%%
list: /* nothing */
| list '\n'
| list defn '\n'
| list asgn '\n' { code2(pop, STOP); return 1; }
| list stmt '\n' { code(STOP); return 1; }
| list expr '\n' { code2(print, STOP); return 1; }
| list error '\n' { yyerrok; }
;
asgn: VAR '=' expr { code3(varpush,(Inst)$1,assign); $$=$3; }
| ARG '=' expr
{ defnonly("$"); code2(argassign,(Inst)$1); $$=$3;}
;
stmt: expr { code(pop); }
| RETURN { defnonly("return"); code(procret); }
| RETURN expr
{ defnonly("return"); $$=$2; code(funcret); }
| PROCEDURE begin '(' arglist ')'
{ $$ = $2; code3(call, (Inst)$1, (Inst)$4); }
| PRINT prlist { $$ = $2; }
| while cond stmt end {
($1)[1] = (Inst)$3; /* body of loop */
($1)[2] = (Inst)$4;
} /* end, if cond fails */
| if cond stmt end { /* else-less if */
($1)[1] = (Inst)$3; /* thenpart */
($1)[3] = (Inst)$4;
} /* end, if cond fails */
| if cond stmt end ELSE stmt end { /* if with else */
($1)[1] = (Inst)$3; /* thenpart */
($1)[2] = (Inst)$6; /* elsepart */
($1)[3] = (Inst)$7;
} /* end, if cond fails */
| '{' stmtlist '}' { $$ = $2; }
;
cond: '(' expr ')' { code(STOP); $$ = $2; }
;
while: WHILE { $$ = code3(whilecode,STOP,STOP); }
;
if: IF { $$ = code(ifcode); code3(STOP, STOP, STOP); }
;
begin: /* nothing */ { $$ = progp; }
;
end: /* nothing */ { code(STOP); $$ = progp; }
;
stmtlist: /* nothing */ { $$ = progp; }
| stmtlist '\n'
| stmtlist stmt
;
expr: NUMBER { $$ = code2(constpush, (Inst)$1); }
| VAR { $$ = code3(varpush, (Inst)$1, eval); }
| ARG { defnonly("$"); $$ = code2(arg, (Inst)$1); }
| asgn
| FUNCTION begin '(' arglist ')'
{ $$ = $2; code3(call,(Inst)$1,(Inst)$4); }
| READ '(' VAR ')' { $$ = code2(varread, (Inst)$3); }
| BLTIN '(' expr ')' { $$=$3; code2(bltin, (Inst)$1->u.ptr); }
| '(' expr ')' { $$ = $2; }
| expr '+' expr { code(add); }
| expr '-' expr { code(sub); }
| expr '*' expr { code(mul); }
| expr '/' expr { code(div); }
| expr '^' expr { code (power); }
| '-' expr %prec UNARYMINUS { $$=$2; code(negate); }
| expr GT expr { code(gt); }
| expr GE expr { code(ge); }
| expr LT expr { code(lt); }
| expr LE expr { code(le); }
| expr EQ expr { code(eq); }
| expr NE expr { code(ne); }
| expr AND expr { code(and); }
| expr OR expr { code(or); }
| NOT expr { $$ = $2; code(not); }
;
prlist: expr { code(prexpr); }
| STRING { $$ = code2(prstr, (Inst)$1); }
| prlist ',' expr { code(prexpr); }
| prlist ',' STRING { code2(prstr, (Inst)$3); }
;
defn: FUNC procname { $2->type=FUNCTION; indef=1; }
'(' ')' stmt { code(procret); define($2); indef=0; }
| PROC procname { $2->type=PROCEDURE; indef=1; }
'(' ')' stmt { code(procret); define($2); indef=0; }
;
procname: VAR
| FUNCTION
| PROCEDURE
;
arglist: /* nothing */ { $$ = 0; }
| expr { $$ = 1; }
| arglist expr { $$ = $1 + 1; }
;
%%
/* end of grammar */
...
С помощью правила для аргсписок (список аргументов) подсчитывается число аргументов. На первый взгляд может показаться, что нужно каким-то образом собирать аргументы, но это не так, поскольку каждое выражение (выраж) из списка аргументов вырабатывает значение в стеке как раз там, где оно необходимо.
Правило для опред вводит новое свойство языка yacc: встроенное действие. Оказывается, можно поместить действие посредине правила, так, чтобы оно выполнялось в процессе распознавания последнего. Мы воспользовались этой возможностью, чтобы запомнить, что сейчас распознается: определение функции или процедуры. (В качестве альтернативного решения можно было бы ввести новый символ типа begin, который распознавался бы в соответствующее время.) Функция defnonly печатает предупреждающее сообщение, если вопреки синтаксису какая-либо конструкция окажется вне определения функции или процедуры. Обычно вам предоставляется выбор: обнаруживать ошибку синтаксически или семантически. Перед нами уже стояла такая задача ранее, при диагностике неопределенных переменных. Функция defnonly хорошо иллюстрирует ситуацию, когда семантическая проверка легче синтаксической.
defnonly(s) /* warn if illegal definition */
char *s;
{
if (!indef)
execerror(s, "used outside definition");
}
Переменная indef определена в hoc.y и принимает значения в действиях для опред.
К лексическому анализатору добавлены средства проверки аргументов: символ $, за которым следует чисто для строки в кавычках. Последовательности в строках, начинающиеся с обратной дробной черты, например \n, обрабатываются функцией backslash:
yylex() /* hoc6 */
...
if (c == '$') { /* argument? */
int n = 0;
while (isdigit(c=getc(fin)))
n = 10 * n + c — '0';
ungetc(с, fin);
if (n == 0)
execerror("strange $...", (char*)0);
yylval.narg = n;
return ARG;
}
if (c == '"') { /* quoted string */
char sbuf [100], *p, *emalloc();
for (p = sbuf; (c=getc(fin)) != '"'; p++) {
if (с == '\n' || c == EOF)
execerror("missing quote", "");
if (p >= sbuf + sizeof (sbuf) - 1) {
*p = '\0';
execerror("string too long", sbuf);
}
*p = backslash(c);
}
*p = 0;
yylval.sym = (Symbol*)emalloc(strlen(sbuf)+1);
strcpy(yylval.sym, sbuf);
return STRING;
}
...
backslash(c) /* get next char with \'s interpreted */
int c;
{
char *index(); /* 'strchr()' in some systems */
static char transtab[] = "b\bf\fn\nr\rt\t";
if (c != '\\')
return c;
c = getc(fin);
if (islower(c) && index(transtab, c))
return index(transtab, с)[1];
return c;
}
Лексический анализатор является примером конечного автомата независимо от того, написан ли он на Си или получен с помощью порождающей программы типа lex. Наша первоначальная версия Си программы стала весьма сложной, и поэтому для всех программ, больших ее по объему, лучше использовать lex, чтобы максимально упростить внесение изменений.
Остальные изменения сосредоточены главным образом в файле code.c, хотя несколько имен функций добавляется к файлу hoc.h. Машина остается той же, но с дополнительным стеком для хранения последовательности вложенных вызовов функций и процедур (проще ввести второй стек, чем загружать больший объем информации в существующий). Начало файла code.c выглядит так:
$ cat code.c
#include "hoc.h"
#include "y.tab.h"
#include
#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 */
Inst *progbase = prog; /* start of current subprogram */
int returning; /* 1 if return stmt seen */
typedef struct Frame { /* proc/func call stack frame */
Symbol *sp; /* symbol table entry */
Inst *retpc; /* where to resume after return */
Datum *argn; /* n-th argument on stack */
int nargs; /* number of arguments */
} Frame;
#define NFRAME 100 Frame frame[NFRAME];
Frame *fp; /* frame pointer */
initcode() {
progp = progbase;
stackp = stack;
fp = frame;
returning = 0;
}
...
$
Поскольку теперь в таблице имен хранятся указатели на функции и процедуры, а также на строки для печати, необходимо расширить определение типа объединения в файле hoc.h:
$ cat hoc.h
typedef struct Symbol { /* symbol table entry */
char *name;
short type;
union {
double val; /* VAR */
double (*ptr)(); /* BLTIN */
int (*defn)(); /* FUNCTION, PROCEDURE */
char *str; /* STRING */
} u;
struct Symbol *next; /* to link to another */
} Symbol;
$
В процессе трансляции функция define заносит запись о функции в таблицу имен, сохраняет указатель на нее и изменяет в случае успешной компиляции адрес следующего после созданных команд свободного слова:
define(sp) /* put func/proc in symbol table */
Symbol *sp;
{
sp->u.defn = (Inst)progbase; /* start of code */
progbase = progp; /* next code starts here */
}
Когда в процессе выполнения вызывается функция или процедура, все аргументы уже вычислены и помещены в стек (первый аргумент находится на наибольшем уровне). Код операции вызова (call) сопровождается указателем на таблицу имен и числом аргументов. Сохраняется образ стека, в котором содержится вся существенная информация о программе: запись в таблице имен, место возврата после вызова, место хранения аргументов в стеке выражений, а также число аргументов, сопровождающих вызов. Образ стека создается функцией call, которая затем выполняет тело программы.
call() /* call a function */
{
Symbol *sp = (Symbol*)pc[0]; /* symbol table entry */
/* for function */
if (fp++ >= &frame[NFRAME-1])
execerror(sp->name, "call nested too deeply");
fp->sp = sp;
fp->nargs = (int)pc[1];
fp->retpc = pc + 2;
fp->argn = stackp - 1; /* last argument */
execute(sp->u.defn);
returning = 0;
}
Создаваемая структура показана на рис. 8.2.
Рис. 8.2: Структуры данных для вызова процедуры
В конце концов произойдет возврат из вызываемой программы при выполнении procret или funcret:
funcret() /* return from a function */
{
Datum d;
if (fp->sp->type == PROCEDURE)
execerror(fp->sp->name, "(proc) returns value");
d = pop(); /* preserve function return value */
ret();
push(d);
}
procret() /* return from a procedure */
{
if (fp->sp->type == FUNCTION)
execerror(fp->sp->name(func) returns no value");
ret();
}
Функция ret удаляет аргументы из стека, сохраняет указатель на образ стека fp и устанавливает счетчик команд:
ret() /* common return from func or proc */
{
int i;
for (i = 0; i < fp->nargs; i++)
pop(); /* pop arguments */
pc = (Inst*)fp->retpc;
--fp;
returning = 1;
}
Некоторые программы интерпретатора нуждаются в небольших поправках для учета ситуаций, когда происходит возврат во вложенных операторах. Решение не элегантно, но верно и состоит во введении признака с именем returning, который принимает значение 1 при обнаружении оператора return. Выполнение, организуемое функциями ifcode, whilecode, execute, завершается раньше, если установлен признак returning; в функции call он обнуляется.
ifcode() {
Datum d;
Inst *savepc = pc; /* then part */
execute(savepc+3); /* condition */
d = pop();
if (d.val)
execute(*((Inst**)(savepc)));
else if (*((Inst**)(savepc+1))) /* else part? */
execute(*((Inst**)(savepc+1)));
if (!returning)
pc = *((Inst**)(savepc+2)); /* next stmt */
}
whilecode() {
Datum d;
Inst *savepc = pc;
execute(savepc+2); /* condition */
d = pop();
while (d.val) {
execute(*((Inst**)(savepc))); /* body */
if (returning)
break;
execute(savepc+2); /* condition */
d = pop();
}
if (!returning)
pc = *((Inst**)(savepc+1)); /* next stmt */
}
execute(p)
Inst *p;
{
for (pc = p; *pc != STOP && !returning; )
(*((++pc)[-1]))();
}
Аргументы выбираются для получения значения или присваивания с помощью функции getarg, которая следит за сбалансированностью стека:
double *getarg() /* return pointer to argument */
{
int nargs = (int)*pc++;
if (nargs > fp->nargs)
execerror(fp->sp->name, "not enough arguments");
return &fp->argn[nargs - fp->nargs].val;
}
arg() /* push argument onto stack */
{
Datum d;
d.val = *getarg();
push(d);
}
argassign() /* store top of stack in argument */
{
Datum d;
d = pop();
push(d); /* leave value on stack */
*getarg() = d.val;
}
Функции prstr и prexpr печатают строки и числа:
prstr() /* print string value */
{
printf("%s", (char*)*pc++);
}
prexpr() /* print numeric value */
{
Datum d;
d = pop();
printf("%.8g d.val);
}
Функция varread читает переменные. Она возвращает 0 при обнаружении конца файла и 1 — в противном случае, а также устанавливает значение указанной переменной:
varread() /* read into variable */
{
Datum d;
extern FILE *fin;
Symbol *var = (Symbol*)*pc++;
Again:
switch (fscanf(fin, "%lf", &var->u.val)) {
case EOF:
if (moreinput())
goto Again;
d.val = var->u.val = 0.0;
break;
case 0:
execerror("non-number read into", var->name);
break;
default:
d.val = 1.0;
break;
}
var->type = VAR;
push(d);
}
Обнаружив конец файла для текущего входного потока, функция varread обратится к moreinput, которая откроет следующий файл, заданный в качестве аргумента (если он есть). В функции moreinput обработка входной информации имеет некоторые нюансы, здесь не рассматриваемые; речь о них идет в приложении 3.
Итак, мы завершили разработку программы hoc. Для сравнения приведем число непустых строк в каждой версии:
hoc1 59
hoc2 94
hoc3 248 (для версии с lex 229)
hoc4 396
hoc5 574
hoc6 809
Конечно, эти значения были вычислены программным способом: $
sed '/$/d' `pick *.[chyl]` | wc -l
Безусловно, развитие языка может быть продолжено, и вам предоставляется такая возможность в приведенных ниже упражнениях.
Упражнение 8.18
Измените hoc6 так, чтобы можно было использовать поименованные формальные параметры в подпрограммах вместо $1 и т.д.
Упражнение 8.19
Сейчас все переменные глобальны, за исключением параметров. Уже есть большая часть механизма для введения локальных переменных, хранимых в стеке. Одно из решений заключается во введении описания auto , которое резервирует место в стеке для перечисленных переменных; не перечисленные переменные считаются глобальными. Кроме того, придется расширить таблицу имен так, чтобы поиск в ней осуществлялся вначале для локальных, а затем для глобальных переменных. Как это связано с поименованными аргументами?
Упражнение 8.20
Как бы вы ввели массивы в язык hoc ? Как следует передавать их функциям и процедурам? Как возвращать их?
Упражнение 8.21
Обобщите работу со строками так, чтобы переменные могли хранить строки, а не только числа. Какие операции потребуются для этого? Самая трудная часть управление памятью добейтесь динамичного хранения строк: память должна освобождаться, когда строки перестают быть нужными. В качестве промежуточного шага добавьте более развитые форматы печати, например, обеспечьте возможность использования некоторых форм стандартной Си функции printf .
8.7 Оценка времени выполнения
Мы сравнивали hoc с другими программами-калькуляторами UNIX, чтобы приблизительно оценить, насколько хорошо он работает. К таблице, представленной ниже (табл. 8.1), можно, конечно, отнестись скептически, но она показывает "разумность" нашей реализации. Все приведенные в ней величины даны в секундах. Работа велась на PDP-11/70. Было выполнено два теста. Первый, вычисление функции Аккерманна ack(3,3), — хороший тест для отработки механизма вызова функций. Здесь происходят 2432 вызова, причем некоторые из них достаточно глубоко вложены.
func ack() {
if ($1 == 0) return ($2+1)
if($2 == 0) return (ack($1 - 1, 1))
return (ack($1 - 1, ack($1, $2 - 1)))
}
ack(3,3)
Второй тест — стократное вычисление чисел Фибоначчи со значениями, меньшими 1000. В этом случае выполнялись в основном арифметические операции с периодическим вызовом функций:
proc fib() {
a = 0
b = 1
while (b < $1) {
с = b
b = a+b
a = c
}
}
i = 1
while (i < 100) {
fib(1000)
i = i + 1
}
Тест выполнялся на четырех языках: hoc, bc(1), bas (древний диалект Бейсика, который существует только на PDP-11) и Си (использовался тип PDP-11 для всех переменных) .
Числа, приведенные в табл. 8.1, являются суммой пользовательского и системного времени процессора и вычислены с помощью функции time.
| Программа | (3,3) | 100*fib(1000) |
| hoc | 5.5 | 5.0 |
| bas | 1.3 | 0.7 |
| bc | 39.7 | 14.9 |
| c | <0.1 | 0.1 |
Таблица 8.1: Время работы на PDP-11/70 (в секундах)
Можно также приспособить Си программу для определения количества времени, используемого каждой функцией. Программу нужно перетранслировать в режиме профилирования, введя флаг -p в каждой единице трансляции Си и при режиме загрузки. Если изменить файл makefile для чтения:
hoc6: $(OBJS)
сс $(CFLAGS) $(OBJS) -lm -о hoc6
чтобы команда сс задействовала переменную CFLAGS, а затем задать
$ make clean; make CFLAGS=-p
то результирующая программа будет выполняться с профилированием. После выполнения программы остается файл mon.out, который интерпретируется программой профилировщиком prof.
Для иллюстрации изложенного мы протестировали hoc6 на приведенной выше программе Фибоначчи:
$ hoc6
$ prof hoc6 | sed 15q Анализ
name %time cumsec #call ms/call
_pop 15.6 0.85 32182 0.03
_push 14.3 1.63 32182 0.02
mcount 11.3 2.25
csv 10.1 2.80
cret 8.8 3.28
_assign 8.2 3.73 5050 0.09
_eval 8.2 4.18 8218 0.05
_execute 6.0 4.51 3567 0.09
_varpush 5.9 4.83 13268 0.02
_lt 2.7 4.98 1783 0.08
_constpu 2.0 5.09 497 0.22
_add 1.7 5.18 1683 0.05
_getarg 1.5 5.26 1683 0.05
_yyparse 0.6 5.30 3 11.11
$
Результаты, полученные с помощью профилировщика, также подвержены случайным вариациям, как и те, что получены с помощью функции time, поэтому их следует считать лишь указанием настоящих значений, а не принимать за абсолютную истину. Тем не менее при необходимости приведенные значения могут помочь повысить быстродействие программы hoc. Приблизительно третья часть времени тратится на запись и чтение из стека. Накладные расходы еще более возрастут, если мы будем учитывать время выполнения функций связи csv и cret между программами Си (функция mcount представляет собой часть программы с профилированием, полученную с помощью команды ее -р.). Замена вызовов функций на макрообращения даст заметную разницу во времени выполнения.
Для проверки этого предположения мы изменили code.c, заменив вызовы push и pop на макрокоманды, управляющие стеком:
#define push(d) *stackp++ = (d)
#define popm() *--stackp = pop() /* функция все-таки нужна */
(Функция pop все-таки нужна в качестве кода операции нашей машины, поэтому нельзя заменить все обращения к ней.) Новая версия выполняется на 35% быстрее; время в табл. 8.1 сокращается от 5.5 до 3.7 с и от 5.0 до 3.1 с.
Упражнение 8.22
В макрокомандах push и popm не предусмотрен контроль ошибок. Прокомментируйте разумность такого решения. Как бы вы обеспечили контроль ошибок, производимый в версии с функциями, не снижая быстродействия макрокоманд?
8.8 Заключение
Ознакомившись с материалом этой главы, мы можем сделать важные выводы. Во-первых, средства для развития языков очень нужны, так как позволяют сконцентрировать внимание на интересной работе проектировании языка (с ним легко экспериментировать). Грамматика является организующей структурой при реализации: программы привязываются к грамматике и вызываются в подходящий момент в процессе разбора.
Во-вторых, и это уже философский аспект, ценна сама постановка задачи речь идет о разработке языка, а не просто о написании программы. Построение программы как языкового процессора обеспечивает регулярность синтаксиса (т.е. взаимодействие с пользователем), делает более структурированной реализацию. Кроме того, мы получаем гарантию, что новые средства будут хорошо согласовываться с уже реализованными. Под "языками", конечно, следует понимать не только традиционные языки программирования, но и уже упоминавшиеся выше в примерах языки eqn и pick, а также yacc, lex, и make.
Рассмотрены здесь и вопросы использования программных средств. В частности, показана роль программы make, которая предотвращает целый класс ошибок (например, вы забыли перетранслировать какую-то подпрограмму). Она позволяет избавиться от лишней работы и предоставляет удобный способ сгруппировать в одном файле большое число связанных и, возможно, зависимых операций.
С помощью файлов макроопределений вы можете координировать описания данных, доступных более чем в одном файле. Проводя централизацию информации, они исключают ошибки, вызванные несогласованностью применяемых версий, особенно если действуют совместно с программой make. Весьма важно разбить данные и подпрограммы на файлы таким образом, чтобы они не были видимы, если в этом нет необходимости.
Хотелось бы отметить, что из-за ограниченного объема книги мы мало внимания уделили тем средствам UNIX, которые применяются при разработке семейства программ hoc. Каждая версия программы находится в отдельном каталоге, для идентичных файлов используются связи; постоянно вызываются команды ls и du, чтобы следить за тем, какие файлы где находятся. На многие вопросы ответы дают сами программы. Например, на вопрос: "Где описана данная переменная?" отвечает программа grep. "Как мы внесли изменения в данную версию?" отвечает idiff. "Насколько велик файл?" отвечает wc. Пора делать копию файла обратитесь к команде cp. Нужно скопировать только те файлы, которые изменились со времени последнего копирования? Вам поможет в этом деле программа make.
Такой общий подход типичен для повседневной разработки программ в системе UNIX: множество небольших программных средств, каждое в отдельности или их различные сочетания, позволяет автоматизировать работу, которую иначе пришлось бы выполнять вручную.
Историческая и библиографическая справка
Программа yacc создана С. Джонсоном. Класс языков, для которых yacc может создавать программу разбора, называется LALR-(1): разбор здесь ведется слева направо и входной поток просматривается не более чем на одну лексему вперед. Понятие раздельных описаний для задания приоритетов и разрешения неоднозначностей в грамматике появилось вместе с yacc . Этот вопрос рассматривается в статье А. В. Ахо, С. К. Джонсона и Д. Д. Ульмана "Deterministic parsing of ambiguous grammars" (CACM, August, 1975). Там же приведены новые алгоритмы и структуры данных для создания и хранения таблиц разбора.
Основы теории, на базе которой построены yacc и другие программы анализаторы, излагаются в книге А. В. Ахо и Д. Д. Ульмана "Principles of Compiler Design" (Addison Wesley, 1977). Сама программа yacc описана в справочном руководстве по UNIX (том 2B). В этом разделе также представлен калькулятор, сравнимый с hoc2 : для вас такое сравнение может оказаться полезным.
Программа lex первоначально было написана М. Леском. Теория lex освещена в книге Ахо и Ульмана, а сам язык lex описан в справочном руководстве по UNIX.
Программы yacc и в меньшей степени lex использовались для реализации многих языковых процессоров, включая переносимый компилятор Си, процессоры на Паскале, Фортране 77, Ратфоре, awk , be , egn и pick .
Программа make создана С. Фельдманом и описана в статье "MAKE a program for maintaining computer programs" (Software-Practice & Experience, April, 1979).
В книге Д. Бентли "Writing Efficient Programs" (Prentice-Hall, 1982) обсуждается техника ускорения выполнения программ. Акцент в ней делается на создание подходящего алгоритма, а также на улучшение кода, если в этом есть необходимость.