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

Формат входного потока для 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

$

Исследуйте структуру файла 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(наивысший); действие заключается в изменении знака. Приоритет минуса между двумя выражениями устанавливается по умолчанию.

Добавьте операции %(взятие остатка) и унарный плюс к hoc1. Рекомендация: обратитесь к справочному руководству по frexp(3).

Обидно, что приходится вводить две команды для компиляции hoc1. Хотя, конечно, нетрудно составить командный файл для такого задания, но есть лучший способ, который позднее можно распространить на тот случай, когда программа состоит из нескольких исходных файлов. Программа makeчитает описания взаимозависимости компонентов программы и позволяет создать ее действующую версию. Она проверяет время последней модификации каждого компонента, выясняет минимальный объем перекомпиляции, которую необходимо выполнить для получения новой действующей версии, и затем запускает процесс. Программа makeразбирается в запутанных многошаговых процессах, в частности в yacc, поэтому ей можно давать задания, не уточняя отдельные шаги.