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

Керниган Брайан Уилсон
Шрифт:

 ;

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;