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

8.1 Этап 1: калькулятор с четырьмя действиями

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

Исходный текст 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%.8gn", $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 <stdio.h>
#include <ctype.h>
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 %dn", 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
$

Ранее мы утверждали, что, работая с yacc, легко менять язык. В качестве примера добавим к hoc1 унарный минус, чтобы выражения типа

-3-4

вычислялись, а не отвергались как синтаксические ошибки. Всего две строки нужно дополнительно включить в hoc.y. Добавляется новая лексема UNARYMINUS в ту часть грамматики, где задаются приоритеты, чтобы унарный минус имел наивысший приоритет:

%left '+' '-'
%left '*' '/'
%left UNARYMINUS /* новая лексема */

Грамматика увеличивается на одно правило для expr:

expr: NUMBER ($$= $1;}
 | '-' expr %prec UNARYMINUS {$$=- $2} /* новое */

Определение %prec "говорит", что символ унарного минуса (т.е. знак "-" перед выражением) имеет тот же приоритет, что и UNARYMINUS (наивысший); действие заключается в изменении знака. Приоритет минуса между двумя выражениями устанавливается по умолчанию.

Обидно, что приходится вводить две команды для компиляции 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 уже "знает", как преобразовать входной файл для yacchoc.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 понимает, что это не нужно
$

Оглавление книги