Более сложный пример
В этом пункте рассматривается пример грамматики, в которой используются некоторые специфические свойства yacc'а. Калькулятор из предыдущего пункта реконструируется, чтобы обеспечить действия над вещественными числами и над интервалами таких чисел. Калькулятор понимает вещественные константы, арифметические операции +, -, *, /, унарный -, переменные от a до z. Кроме того, он воспринимает интервалы вида
(X, Y)
где X не превосходит Y. Можно использовать 26 переменных типа интервал с именами от A до Z. Калькулятор работает аналогично тому, который был описан в пункте Простой пример; присваивания не возвращают значений и ничего не выводят, остальные выражения выводят результат (вещественный или интервальный).
В данном примере используется ряд интересных особенностей yacc'а и языка C. Интервал представляется структурой, состоящей из левой и правой границ, значения которых имеют тип double. При помощи конструкции typedef этому структурному типу дается имя INTERVAL. В стек значений yacc'а могут быть занесены также значения целого и вещественного типов (целые числа используются в качестве индекса в массиве, содержащем значения переменных). Отметим, что организация вычислений в целом сильно зависит от возможности присваивать структуры и объединения в языке C. Многие действия вызывают функции, возвращающие значения структурного типа.
Стоит отметить использование макроса YYERROR для обработки ошибочных ситуаций, когда делается попытка деления на интервал, содержащий 0, или употребляется интервал, левая граница которого больше правой. Механизм нейтрализации ошибок используется для того, чтобы отбросить остаток некорректной строки.
Кроме смешивания типов в стеке значений данная грамматика демонстрирует любопытный способ отслеживания типа (скалярного или интервального) промежуточных выражений. Отметим, что скаляр может быть автоматически преобразован в интервал, если контекст требует значения интервального типа. Это приводит к большому числу конфликтов, которые обнаруживает в грамматике yacc: 18 конфликтов свертка-перенос и 26 свертка-свертка. Проблему можно рассмотреть на примере двух входных строк
2.5 + (3.5 - 4.)
и
2.5 + (3.5, 4.)
Во втором примере константа 2.5 должна использоваться в интервальнозначном выражении, однако данный факт не известен до тех пор, пока не прочитана запятая. К этому времени константа 2.5 обработана и алгоритм разбора не может уже передумать и вернуться назад. В более общем случае может оказаться необходимым просмотреть вперед неограниченное число лексем, чтобы сообразить, преобразовывать ли скаляр в интервал. Эту проблему обходят, вводя два правила для каждой бинарной интервальнозначной операции: одну на случай, когда левый операнд является скаляром, другую - когда левый операнд является интервалом. Во втором случае правый операнд должен быть интервалом, поэтому преобразование будет выполняться автоматически. Несмотря на эту увертку, остается еще много случаев, в которых преобразование может либо выполняться либо нет, что приводит к конфликтам. Чтобы их разрешить, в начало файла спецификаций помещен список правил, задающих скаляры; такой способ разрешения конфликтов ведет к тому, что скалярные выражения остаются скалярными до тех пор, пока их не заставят стать интервальными.
Демонстрируемый способ обработки множественных типов весьма поучителен и ... непрактичен. Если имеется много типов выражений, а не два, как в данном примере, число правил возрастает лавинообразно, а число конфликтов - еще быстрее. Поэтому в более привычных языках программирования лучше считать информацию о типе частью значения, а не частью грамматики.
В заключение - несколько слов о лексическом анализе вещественных констант. Чтобы преобразовать текст в число двойной точности, используется процедура atof() из стандартной C-библиотеки. Если лексический анализатор обнаруживает ошибку, он возвращает лексему, которая не допускается грамматикой, провоцируя тем самым синтаксическую ошибку и, как следствие, ее нейтрализацию.
%{
#include <stdio.h> #include <ctype.h>
typedef struct interval { double lo, hi; } INTERVAL;
INTERVAL vmul (), vdiv ();
double atof ();
double dreg [26]; INTERVAL vreg [26];
%}
%start lines
%union { int ival; double dval; INTERVAL vval; }
%token <ival> DREG VREG /* индексы в массивах dreg, vreg */
%token <dval> CONST /* константа с плавающей точкой */
%type <dval> dexp /* выражение */
%type <vval> vexp /* интервальное выражение */
/* информация о приоритетах операций */
%left '+' '-' %left '*' '/' %left UMINUS /* наивысший приоритет у унарного минуса */
%% /* начало секции правил */
lines : /* пусто */ | lines line ; line : dexp '\n' { printf ("%15.8f\n", $1); } | vexp '\n' { printf ("(%15.8f, %15.8f)\n", $1.lo, $1.hi); } | DREG '=' dexp '\n' { dreg [$1] = $3; } | VREG '=' vexp '\n' { vreg [$1] = $3; } | error '\n' { yyerrok; } ;
dexp : CONST | DREG { $$ = dreg [$1]; } | dexp '+' dexp { $$ = $1 + $3; } | dexp '-' dexp { $$ = $1 - $3; } | dexp '*' dexp { $$ = $1 * $3; } | dexp '/' dexp { $$ = $1 / $3; } | '-' dexp %prec UMINUS { $$ = -$2; } | '(' dexp ')' { $$ = $2; } ;
vexp : dexp { $$.hi = $$.lo = $1; } | '(' dexp ',' dexp ')' { $$.lo = $2; $$.hi = $4; if ($$.lo > $$.hi) { printf ("нижняя граница больше верхней\n"); YYERROR; } }
| VREG { $$ = vreg[$1]; } | vexp '+' vexp { $$.hi = $1.hi + $3.hi; $$.lo = $1.lo + $3.lo; } | dexp '+' vexp { $$.hi = $1 + $3.hi; $$.lo = $1 + $3.lo; } | vexp '-' vexp { $$.hi = $1.hi - $3.hi; $$.lo = $1.lo - $3.lo; } | dexp '-' vexp { $$.hi = $1 - $3.hi; $$.lo = $1 - $3.lo; }
| vexp '*' vexp { $$ = vmul ($1.lo, $1.hi, $3); } | dexp '*' vexp { $$ = vmul ($1, $1, $3); } | vexp '/' vexp { if (dcheck ($3)) YYERROR; $$ = vdiv ($1.lo, $1.hi, $3); } | dexp '/' vexp { if (dcheck ($3)) YYERROR; $$ = vdiv ($1, $1, $3); } | '-' vexp %prec UMINUS { $$.hi = -$2.lo; $$.lo = -$2.hi; } | '(' vexp ')' { $$ = $2; } ;
%% /* начало секции подпрограмм */
#define BSZ 50 /* размер буфера для числа с плав. точкой */
/* лексический анализ */
int yylex () { register int c;
/* пропустить пробелы */ while ((c = getchar ()) == ' ') ; if (isupper (c)) { yylval.ival = c - 'A'; return (VREG); } if (islower (c)) { yylval.ival = c - 'a'; return (DREG); }
/* проглотить цифры, точки, экспоненты */
if (isdigit (c) c == '.') { char buf [BSZ + 1], *cp = buf; int dot = 0, exp = 0;
for (; (cp - buf) < BSZ; ++cp, c = getchar ()) { *cp = c; if (isdigit (c)) continue; if (c == '.') { if (dot++ exp) return ('.'); /* приводит к синт. ошибке */ continue; } if (c == 'e') { if (exp++) return ('e'); /* приводит к синт. ошибке */ continue; } /* конец числа */ break; } *cp = ' '; if (cp - buf >= BSZ) (void) printf ("константа слишком длинная\n"); else /* возврат последнего прочитанного символа */ ungetc (c, stdin); yylval.dval = atof (buf); return (CONST); } return (c); }
INTERVAL hilo (a, b, c, d) double a, b, c, d; { /* вычисляет минимальный интервал, содержащий a, b, c и d */
/* используется процедурами, вычисляющими * и / */ INTERVAL v;
if (a > b) { v.hi = a; v.lo = b; } else { v.hi = b; v.lo = a; }
if (c > d) { if (c > v.hi) v.hi = c; if (d < v.lo) v.lo = d; } else { if (d > v.hi) v.hi = d; if (c < v.lo) v.lo = c; } return (v); }
INTERVAL vmul (a, b, v) double a, b; INTERVAL v; { return (hilo (a*v.hi, a*v.lo, b*v.hi, b*v.lo)); }
dcheck (v) INTERVAL v; { if (v.hi >= 0. && v.lo <= 0.) { (void) printf ("интервал-делитель содержит 0.\n"); return (1); } return (0); }
INTERVAL vdiv (a, b, v) double a, b; INTERVAL v; { return (hilo (a / v.hi, a / v.lo, b / v.hi, b / v.lo)); }
