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

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

Наглядно представить разбор вам поможет рис. 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

преобразуется в оператор

#defin

e в выходном файле

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 строк текста).