Bison 1.35 - 3. Примеры
[Содержание] [Назад] [Пред] [Вверх] [След] [Вперед]3. Примеры
Сейчас мы приведём и объясним три простые программы, написанные с использованием Bison: калькулятор обратной польской нотации, калькулятор алгебраической (инфиксной) нотации, и многофункциональный калькулятор. Все три протестированы под BSD Unix 4.3, каждая из них даёт пригодный для использования, хотя и ограниченный, интерактивный настольный калькулятор.
Эти примеры просты, но грамматики Bison для реальных языков программирования пишутся таким же образом.
3.1 Калькулятор обратной польской нотации
Первый пример -- это простой калькулятор с двойной точностью для выражений в обратной польской нотации (использующий постфиксные операции). Этот пример является хорошей отправной точкой, поскольку приоритеты операций не используются. Обработка приоритетов будет показана во втором примере.
Исходный код этого калькулятора называется `rpcalc.y'. По соглашению для входных файлов Bison используется расширение `.y'.
3.1.1 Объявления для rpcalc
Это объявления C и Bison для калькулятора обратной польской нотации. Как и в C, комментарии помещаются между `/*...*/'.
/* Калькулятор обратной польской нотации. */
%{
#define YYSTYPE double
#include <math.h>
%}
%token NUM
%% /* Далее следуют правила грамматики и действия */
Секция объявлений C (см. раздел 4.1.1 Секция объявлений C содержит две директивы препроцессора.
Директива #define определяет макрос YYSTYPE. Это задаёт тип
данных C для семантических значений как лексем, так и групп (см. раздел 4.5.1 Типы данных семантических значений). Анализатор Bison будет
использовать любой тип, заданный YYSTYPE, а если вы не определили его
-- тип по умолчанию int. Поскольку мы указали double, с каждой
лексемой и каждым выражением будет ассоциировано вещественное число.
Директива #include используется для объявления функции возведения
в степень pow.
Из второй секции, объявлений Bison, Bison получает информацию о типах лексем
(см. раздел 4.1.2 Секция объявлений Bison). Здесь должен быть
объявлен любой терминальный символ, не являющийся однолитерной константой
(они, как правило, не нуждаются в объявлении). В этом примере все
арифметические операции обозначаются однолитерными константами, поэтому
нужно объявить только терминальный символ NUM, тип лексемы для числовых
констант.
3.1.2 Правила грамматики для rpcalc
Это правила грамматики для калькулятора обратной польской нотации.
input: /* пусто */
| input line
;
line: '\n'
| exp '\n' { printf ("\t%.10g\n", $1); }
;
exp: NUM { $$ = $1; }
| exp exp '+' { $$ = $1 + $2; }
| exp exp '-' { $$ = $1 - $2; }
| exp exp '*' { $$ = $1 * $2; }
| exp exp '/' { $$ = $1 / $2; }
/* возведение в степень */
| exp exp '^' { $$ = pow ($1, $2); }
/* унарный минус */
| exp 'n' { $$ = -$1; }
;
%%
Здесь определены группы "языка" rpcalc: выражение (названное exp),
строка ввода (line), и законченный входной текст (input). У
каждого из этих нетерминальных символов имеется несколько альтернативных
правил, объединённых знаком `|', читающимся "или". В последующих
разделах объясняется, что означают эти правила.
Семантика языка определяется действиями, предпринимаемыми при распознавании группы. Действия -- это код на C, находящийся между фигурными скобками. См. раздел 4.5.3 Действия.
Вы должны писать эти действия на C, однако Bison предоставляет способ
передачи семантических значений между правилами. В каждом действии
псевдопеременная $$ обозначает семантическое значение группы,
которую собирает это правило. Присвоение $$ значения -- основная
работа большинства действий. На семантические значения компонентов правила
можно ссылаться как на $1, $2 и т.д.
3.1.2.1 Объяснение input
Рассмотрим определение input:
input: /* пусто */
| input line
;
Это определение читается следующим образом: "Законченный входной текст
представляет собой пустую строку либо законченный входной текст, за
которым следует входная строка". Обратите внимание, что "законченный
входной текст" определяется в терминах самого себя. Это определение
называется леворекурсивным, поскольку input всегда является
самым левым символом последовательности. См. раздел 4.4 Рекурсивные правила.
Первая альтернатива пуста, поскольку между двоеточием и первым знаком
`|' нет символов. Это означает, что input может соответствовать
пустой входной строке (без лексем). Мы пишем так правило, потому что допустимо
нажатие клавиш Ctrl-d сразу после запуска калькулятора. По соглашению
пустая альтернатива ставится первой и в ней пишется комментарий
`/* пусто */'.
Второе альтернативное правило (input line) описывает любой
нетривиальный входной текст. Оно означет "После прочтения любого количества
строк, прочитать ещё одну, если это возможно". Левая рекурсия заставляет
это правило выполняться в цикле. Поскольку первая альтернатива соответствует
пустому входному тексту, цикл будет выполняться ноль или более раз.
Функция анализатора yyparse продолжает обработку входного текста
до тех пор, пока не будет обнаружена грамматическая ошибка или лексические
анализатор не скажет, что входных лексем больше нет -- мы условимся, что
это произойдёт по достижении конца файла.
3.1.2.2 Объяснение line
Теперь рассмотрим определение line:
line: '\n'
| exp '\n' { printf ("\t%.10g\n", $1); }
;
Первая альтернатива -- это лексема литеры новой строки, это означает,
что rpcalc принимает пустую строку (и игнорирует её, поскольку там нет
никакого правила). Вторая альтернатива -- это выражение, за которым следует
литера новой строки. Именно эта альтернатива несёт основную пользу rpcalc.
Семантическое значение группы exp -- это значение $1, потому
что искомое exp -- первый символ альтернативы. Действие выводит это
значение, которое является результатом вычислений, заданных пользователем.
Это действие необычно, потому что оно не присваивает значения $$.
Вследствие этого семантическое значение line не инициализируется
(значение будет непредсказуемым). Было бы ошибкой в программе, если бы
это значение когда-либо использовалось, но мы не пользуемся им -- после того,
как rpcalc вывел значение введённой пользователем входной строки, оно больше
не нужно.
3.1.2.3 Объяснение expr
Группа exp имеет несколько правил, по одному на каждый вид выражений.
Первое правило обрабатывает наиболее простым выражениям -- отдельным числам.
Второе обрабатывает выражение сложения, которые выглядит как два выражения,
за которыми следует знак `плюс'. Третье обрабатывает вычитание и т.д.
exp: NUM
| exp exp '+' { $$ = $1 + $2; }
| exp exp '-' { $$ = $1 - $2; }
...
;
Мы используем `|' чтобы объединить все правила для exp, но мы
могли бы с тем же успехом написать их отдельно:
exp: NUM ;
exp: exp exp '+' { $$ = $1 + $2; } ;
exp: exp exp '-' { $$ = $1 - $2; } ;
...
У большей части правил есть действия, вычисляющие значение выражения из
значений его частей. Например, в правиле для сложения $1 относится
к первому компоненту exp, а $2 -- ко второму. Третий компонент,
'+' не имеет осмысленного ассоциированного семантического значения,
но если бы он имел его, на него можно было ссылаться как на $3. Когда
yyparse, используя это правило, распознаёт выражение-сумму, сумма
значений двух подвыражений даст значение всего выражения. См. раздел 4.5.3 Действия.
Вы не обязаны приписывать действие каждому правилу. Когда у правила нет
действия, по умолчанию Bison копирует значение $1 в $$.
Именно это происходит в первом правиле (используюшем NUM).
Показанный здесь способ форматирования -- рекомендуемое соглашение, но Bison не требует этого. Вы можете добавлять или изменять промежутки по своему усмотрению. Например, такая запись:
exp : NUM | exp exp '+' {$$ = $1 + $2; } | ...
означает то же, что и:
exp: NUM
| exp exp '+' { $$ = $1 + $2; }
| ...
Однако последняя намного более наглядна.
3.1.3 Лексический анализатор rpcalc
Задачей лексического анализатора является низкоуровневый разбор --
преобразование литер или последовательностей литер входного текста в
лексемы. Анализатор Bison получает эти лексемы, вызывая лексический
анализатор. См. раздел 5.2 Функция лексического анализатора yylex.
Для работы калькулятора обратной польской нотации нужен весьма простой
лексический анализатор. Он пропускает пробелы и знаки табуляции, читает
числа как значения типа double и возвращает их как лексемы типа
NUM. Любые другие литеры, не являющиеся частью числа, считаются
отдельными лексемами. Имейте в виду, что код лексемы для таких однолитерных
лексем -- это сама литера.
Возвращаемое значение функции лексического анализатора -- это числовой код,
представляющий тип лексемы. Текст, используемый в правилах Bison для
обозначения типа лексемы, также является выражением C для числового кода
этого типа. Это может работать двумя способами. Если тип лексемы является
литерой, её числовым кодом будет ASCII-код этой литеры, вы можете использовать
в лексическом анализаторе в качестве числа ту же литеру. Если тип лексемы --
идентификатор, этот идентификатор Bison определяет как макрос C,
определением которого будет подходящее число. В этом примере, поэтому,
NUM становится макросом, используемым yylex.
Семантическое значение лексемы (если оно у неё есть) сохраняется в глобальной
переменной yylval, где её и ищет анализатор Bison (тип данных
yylval -- YYSTYPE, определяемый в начале грамматики;
см. раздел 3.1.1 Объявления для rpcalc).
Нулевой код типа лексемы возвращается, если обнаружен конец файла (Bison считает указателем конца входного файла любые неположительные значения).
Ниже приведён код лексического анализатора:
/* Лексический анализатор возвращает вещественное число
с двойной точностью в стеке и лексему NUM, или прочитанную
литеру ASCII, если это не число. Все пробелы и знаки
табуляции пропускаются, в случае конца файла возвращается 0. */
#include <ctype.h>
int
yylex (void)
{
int c;
/* пропустить промежутки */
while ((c = getchar ()) == ' ' || c == '\t')
;
/* обработка чисел */
if (c == '.' || isdigit (c))
{
ungetc (c, stdin);
scanf ("%lf", &yylval);
return NUM;
}
/* вернуть конец файла */
if (c == EOF)
return 0;
/* вернуть одну литеру */
return c;
}
3.1.4 Управляющая функция
В соответствии c духом этого примера управляющая функция сведена к явному
минимуму. Единственное требование -- она должна вызывать yyparse
чтобы запустить процесс разбора.
int
main (void)
{
return yyparse ();
}
3.1.5 Подпрограмма сообщения об ошибках
Когда yyparse обнаруживает синтаксическую ошибку, она вызывает
функцию сообщения об ошибках yyerror для вывода сообщения об
ошибке (обычно, но не всегда, "ошибка разбора"). Предоставить эту
функцию должен программист (см. раздел 5. Интерфейс анализатора на C),
поэтому приведём используемое нами определение:
#include <stdio.h>
void
yyerror (const char *s) /* вызывается yyparse в случае ошибки */
{
printf ("%s\n", s);
}
После возврата из функции yyerror анализатор Bison може произвести
восстановление после ошибки и продолжить разбор, если грамматика содержит
подходящее правило ошибки (см. раздел 7. Восстановление после ошибок). В противном
случае yyparse вернёт ненулевое значение. В этом примере мы не писали
никаких правил ошибки, поэтому любой неправильный входной текст приведёт
к завершению работы калькулятора. Это поведение неудачно для настоящего
калькулятора, но вполне подходит для первого примера.
3.1.6 Запуск Bison для создания анализатора
Перед запуском Bison для создания анализатора нам нужно решить, хранить
весь исходный код в одном или нескольких файлах. Для такого простого примера
проще всего будет поместить всё в один файл. Определение yylex,
yyerror и main находятся в конце файла, в секции
"дополнительного кода на C" (см. раздел 2.8 Обзор схемы грамматики Bison).
В больших проектах, скорее всего, у вас будет несколько файлов с исходным
кодом, и вы будет использовать make для их перекомпиляции.
Если весь исходный код находится в одном файле, используйте следующую команду для преобразования его в файл анализатора:
bison имя_файла.y
В этом примере файл называется `rpcalc.y' ("Reverse Polish CALCulator"
-- калькулятор обратной польской нотации). Bison создаёт файл
`имя_файла.tab.c', убирая `.y' из названия исходного файла.
Выходной файл Bison содержит исходный код yyparse. Дополнительные
функции (yylex, yyerror и main) в точности копируются
из входного файла в выходной.
3.1.7 Компиляция файла анализатора
Так нужно компилировать и запускать файл анализатора:
# Перечислить файлы в текущем каталоге.
$ ls
rpcalc.tab.c rpcalc.y
# Компиляция анализатора Bison.
# `-lm' указывает компилятору искать pow в
# математической библиотеке.
$ cc rpcalc.tab.c -lm -o rpcalc
# Снова перечислить файлы.
$ ls
rpcalc rpcalc.tab.c rpcalc.y
Файл `rpcalc' теперь содержит исполняемый код. Вот пример сеанса
работы с rpcalc.
$ rpcalc
4 9 +
13
3 7 + 3 4 5 *+-
-13
3 7 + 3 4 5 * + - n Обратите внимание на унарный минус
`n'
13
5 6 / 4 n +
-3.166666667
3 4 ^ Возведение в степень
81
^D Признак конца файла
$
3.2 Калькулятор инфиксной нотации: calc
Теперь мы модифицируем rpcalc для обработки инфиксных, а не постфиксных операций. Инфиксная нотация предполагает принцип приоритета операций и необходимость обработки скобок произвольной глубины вложенности. Вот код Bison файла `calc.y' -- инфиксного настольного калькулятора.
/* Калькулятор для выражени в инфиксной нотации -- calc */
%{
#define YYSTYPE double
#include <math.h>
%}
/* Объявления BISON */
%token NUM
%left '-' '+'
%left '*' '/'
%left NEG /* обращение -- унарный минус */
%right '^' /* возведение в степень */
/* Далее следует грамматика */
%%
input: /* пустая строка */
| input line
;
line: '\n'
| exp '\n' { printf ("\t%.10g\n", $1); }
;
exp: NUM { $$ = $1; }
| exp '+' exp { $$ = $1 + $3; }
| exp '-' exp { $$ = $1 - $3; }
| exp '*' exp { $$ = $1 * $3; }
| exp '/' exp { $$ = $1 / $3; }
| '-' exp %prec NEG { $$ = -$2; }
| exp '^' exp { $$ = pow ($1, $3); }
| '(' exp ')' { $$ = $2; }
;
%%
Функции yylex, yyerror и main могут быь теми же,
что и раньше.
В этом коде показаны две новые важные возможности.
Во второй секции (объявления Bison) %left объявляет типы лексем
и говорит, что они обозначают левоассоциативные операции. Объявления
%left и %right (правая ассоциативность) используются вместо
%token, использующегося для объявления имени типа лексемы без
ассоциативности (эти лексемы являются однолитерными константами, которые
обычно не требуют объявления. Мы объявляем их здесь для указания
ассоциативности).
Приоритет операций определяется порядком строк с объявлениями -- чем больше
номер строки (чем ниже она на странице или на экране), тем выше приоритет.
Отсюда, возведение в степень имеет наивысший приоритет, далее идут унарный
минус (NEG), `*' и `/' и т.д. См. раздел 6.3 Приоритет операций.
Другая новая возможность -- %prec в секции грамматики для операции
унарного минуса. %prec просто указывает Bison, что правило
`| '-' exp' имеет тот же приоритет, что и NEG -- в данном случае
следующий за наивысшим. См. раздел 6.4 Контекстно-зависимый приоритет.
Вот пример работы с `calc.y':
$ calc 4 + 4.5 - (34/(8*3+-3)) 6.880952381 -56 + 2 -54 3 ^ 2 9
3.3 Простое восстановление после ошибок
До сих пор это руководство не касалось вопроса восстановления после
ошибок -- как продолжить разбор после того, как анализатор обнаружил
синтаксическую ошибку. Всё, что мы предпринимали -- это выдача сообщения
об ошибке функцией yyerror. Вспомним, что по умолчанию после вызова
yyerror yyparse завершает работу. Это значит, что неправильный
ввод приведёт к завершению работы калькулятора. Сейчас мы покажем, как
исправить этот недостаток.
Язык Bison содержит зарезервированное слово error, которое можно
включить в правило грамматики. В следующем примере оно добавлено к одной
из альтернатив line:
line: '\n'
| exp '\n' { printf ("\t%.10g\n", $1); }
| error '\n' { yyerrok; }
;
Это добавление к грамматике допускает простое восстановление после
ошибок в случае ошибки разбора. Если читается выражение, которое не может
быть вычислено, третьим правилом для line будет распознана ошибка, и
разбор продолжится (однако функция yyerror по-прежнему используется
для вывода сообщения). Действие выполняет оператор yyerrok,
автоматически определяемый Bison макрос. Он означает, что восстановление после
ошибки завершено (см. раздел 7. Восстановление после ошибок). Обратите внимания на
различие между yyerrok и yyerror -- ни то, ни другое не
опечатка.
Этот вид восстановления после ошибок работает с синтаксическими ошибками.
Есть другие виды ошибок, например, деление на ноль, вызывающее сигнал
исключения, обычно являющегося фатальным. Настоящая программа калькулятора
должна обрабатывать этот сигнал и использовать longjmp для возврата
в функцию main и продолжения разбора входных строк. Ей следует также
отбросить остаток текущей строки входа. Мы не будем далее обсуждать этот
вопрос, потому что он не характерен для программ Bison.
3.4 Калькулятор с отслеживаием положений: ltcalc
Этот пример расширяет калькулятор инфиксной нотации отслеживанием положений. Это свойство будет использоваться для улучшения сообщений об ошибках. Для большей ясности этот пример -- простой целочисленный калькулятор, поскольку большая часть изменений, необходимых для использования положений, будет сделана в лексическом анализаторе.
3.4.1 Объявления ltcalc
Объявления C и Bison для калькулятора с отслеживанием положение те же самые, что и для калькулятора инфиксной нотации.
/* Калькулятор с отслеживанием положений. */
%{
#define YYSTYPE int
#include <math.h>
%}
/* Объявления Bison. */
%token NUM
%left '-' '+'
%left '*' '/'
%left NEG
%right '^'
%% /* Далее следует грамматика */
Заметьте, что специальных объявлений для работы с положениями нет. Определять
тип данных для сохранения положений не нужно, мы будем использовать тип,
заданный по умолчанию (см. раздел 4.6.1 Тип данных положений),
являющийся структурой с четырьмя следующими целочисленными полями:
first_line, first_column, last_line и last_column.
3.4.2 Правила грамматики ltcalc
Обрабатываются положения или нет, не влияет на синтаксис вашего языка. Поэтому правила грамматики языка в этом примере будут очень похожи на правила в предыдущем примере, мы только модифицируем их для работы с новой информацией.
В этом примере мы будем использовать положения для сообщения о делении на ноль, и определения места неправильных выражений и подвыражений.
input : /* пусто */
| input line
;
line : '\n'
| exp '\n' { printf ("%d\n", $1); }
;
exp : NUM { $$ = $1; }
| exp '+' exp { $$ = $1 + $3; }
| exp '-' exp { $$ = $1 - $3; }
| exp '*' exp { $$ = $1 * $3; }
| exp '/' exp
{
if ($3)
$$ = $1 / $3;
else
{
$$ = 1;
fprintf (stderr, "%d.%d-%d.%d: деление на ноль",
@3.first_line, @3.first_column,
@3.last_line, @3.last_column);
}
}
| '-' exp %preс NEG { $$ = -$2; }
| exp '^' exp { $$ = pow ($1, $3); }
| '(' exp ')' { $$ = $2; }
Этот код показывает, как получать значения положений изнутри семантических
действий, используя псевдопеременные @n для компонентов правила
и @$ -- для групп.
Нам не нужно присваивать значение @$, создаваемый анализатор делает
это автоматически. По умолчанию перед выполнением кода на C для каждого
действия @$ правила с n компонентами сопоставляется интервал
от начала @1 до конца @n. Это поведение может быть
переопределено (см. раздел 4.6.3 Действие по умолчанию для положений), а для очень специфических правил @$ может
вычисляться вручную.
3.4.3 Лексический анализатор ltcalc.
До сих пор для отслеживания положений мы полагались на значения Bison по умолчанию. Следующим шагом мы перепишем лексический анализатор и сделаем его способным передавать в анализатор положения лексем, как он уже делает это с их семантическими значениями.
Для этой цели мы должны принимать в расчёт каждую литеру входного текста, чтобы избежать того, что вычисленные положения будут неверными.
int
yylex (void)
{
int c;
/* пропустить промежутки */
while ((c = getchar ()) == ' ' || c == '\t')
++yylloc.last_column;
/* шаг */
yylloc.first_line = yylloc.last_line;
yylloc.first_column = yylloc.last_column;
/* обработка чисел */
if (isdigit (c))
{
yylval = c - '0';
++yylloc.last_column;
while (isdigit (c = getchar ()))
{
++yylloc.last_column;
yylval = yylval * 10 + c - '0';
}
ungetc (c, stdin);
return NUM;
}
/* вернуть конец файла */
if (c == EOF)
return 0;
/* вернуть однц литеру и обновить положение */
if (c == '\n')
{
++yylloc.last_line;
yylloc.last_column = 0;
}
else
++yylloc.last_column;
return c;
}
В основном, лексический анализатор делает то же, что и раньше: пропускает
пробелы и знаки табуляции и читает числа или однолитерные лексемы.
Дополнительно он обновляет yylloc, глобальную переменную (типа
YYLTYPE), содержащую положение лексемы.
Теперь, каждый раз, когда функция возвращет лексему, в распоряжении
анализатора находятся как её номер, так и семантическое значение и положение
в тексте. Последнее необходимое изменение -- инициализация yylloc,
например, в управляющей функции.
int
main (void)
{
yylloc.first_line = yylloc.last_line = 1;
yylloc.first_column = yylloc.last_column = 0;
return yyparse ();
}
Помните, что вычисление положений не касается синтаксиса. Каждая литера должна быть ассоциирована с обновлением информации о положении, независимо от того, находится ли она в правильном входном тексте, в комментариях, в строковой константе и т.д.
3.5 Многофункциональный калькулятор: mfcalc
Теперь, когда мы уже обсудили основы Bison, пришло время перейти к более
сложной задаче. Приведённые выше калькуляторы поддерживали только пять
функций: `+', `-', `*', `/' и `^'. Было бы приятно
иметь калькулятор, предоставляющий другие математические функции, такие как
sin, cos и т.д.
Добавить новые операции в инфиксный калькулятор, до тех пор, пока они
обозначаются односимвольными константами, несложно. Лексический анализатор
yylex возвращает все нечисловые литеры как лексемы, так что для
добавления операции достаточно введения нового правила грамматики. Но мы
хотим иметь нечто более гибкое, встроенные функции, синтаксис которых
выглядит так:
имя_функции (аргумент)
В то же время, мы добавим в калькулятор память, допуская создание именованных переменных, сохранение в них значений и последующее использование. Вот пример сеанса работы многофункционального калькулятора:
$ mfcalc pi = 3.141592653589 3.1415926536 sin(pi) 0.0000000000 alpha = beta1 = 2.3 2.3000000000 alpha 2.3000000000 ln(alpha) 0.8329091229 exp(ln(beta1)) 2.3000000000 $
Обратите внимание, что допускаются множественное присваивание и вложенные вызовы функций.
3.5.1 Объявления mfcalc
Вот объявления C и Bison для многофункционального калькулятора.
%{
#include <math.h> /* Математические функции: cos(), sin() и т.д. */
#include "calc.h" /* Содержит определение `symrec' */
%}
%union {
double val; /* Чтобы возвращать числа. */
symrec *tptr; /* Чтобы возвращать указатели таблицы символов */
}
%token <val> NUM /* Простое число двойной точности */
%token <tptr> VAR FNCT /* Переменная и функция */
%type <val> exp
%right '='
%left '-' '+'
%left '*' '/'
%left NEG /* Обращение -- унарный минус */
%right '^' /* Возведение в степень */
/* Далее следует грамматика */
%%
Вышеприведённая грамматика вводит только две новые возможности языка Bison. Эти возможности позволяют семантическим значениям иметь различные типы данных (см. раздел 4.5.2 Несколько типов значений).
Объявление %union задаёт весь список возможных типов, это употребляется
вместо определения YYSTYPE. Допустимые типы теперь: вещественные числа
двойной точности (для exp и NUM) и указатели на элементы
таблицы символов. См. раздел 4.7.3 Набор типов значений.
Поскольку значения теперь могут иметь различные типы, необходимо ассоциировать
тип с каждым символом грамматики, семантическое значение которого используется.
Эти символы: NUM, VAR, FNCT и exp. Их объявления
дополнены информацией об их типах данных (помещённой в угловых скобках).
Конструкция Bison %type используется для объявления нетерминальных
символов, так же как %token используется для объявления типов лексем.
Ранее мы не использовали %type, потому что нетерминальные символы обычно
неявно объявляются правилами, определяющими их. Но exp должно быть
объявлено явно чтобы можно было задать тип его значения. См. раздел 4.7.4 Нетерминальные символы.
3.5.2 Правила грамматики mfcalc
Вот правила грамматики многофункционального калькутора. Большая их часть
напрямую скопирована из calc. Введено три новых правила, использующие
VAR и FNCT.
input: /* пусто */
| input line
;
line:
'\n'
| exp '\n' { printf ("\t%.10g\n", $1); }
| error '\n' { yyerrok; }
;
exp: NUM { $$ = $1; }
| VAR { $$ = $1->value.var; }
| VAR '=' exp { $$ = $3; $1->value.var = $3; }
| FNCT '(' exp ')' { $$ = (*($1->value.fnctptr))($3); }
| exp '+' exp { $$ = $1 + $3; }
| exp '-' exp { $$ = $1 - $3; }
| exp '*' exp { $$ = $1 * $3; }
| exp '/' exp { $$ = $1 / $3; }
| '-' exp %prec NEG { $$ = -$2; }
| exp '^' exp { $$ = pow ($1, $3); }
| '(' exp ')' { $$ = $2; }
;
/* End of grammar */
%%
3.5.3 Таблица символов mfcalc
Многофункциональному калькулятору требуется таблица символов для отслеживания имён и значений переменных и функций. Это не влияет на правила грамматики (за исключением действий) или объявления Bison, но требует введения некоторых дополнительных функций на C.
Сама таблица символов состоит из связанного списка записей. Её определение, находящееся в заголовке `calc.h', приведено далее. Оно позволяет размещать в таблице как функции, так и переменные.
/* Тип функций. */
typedef double (*func_t) (double);
/* Тип данных для связей в цепочке символов. */
struct symrec
{
char *name; /* имя символа */
int type; /* тип символа: либо VAR, либо FNCT */
union
{
double var; /* значение VAR */
func_t fnctptr; /* значение FNCT */
} value;
struct symrec *next; /* поле связи */
};
typedef struct symrec symrec;
/* Таблица символов: цепочка `struct symrec'. */
extern symrec *sym_table;
symrec *putsym (const char *, func_t);
symrec *getsym (const char *);
Новая версия main включает вызов init_table, функции,
инициализирующей таблицу символов. Вот текст этих двух функций
#include <stdio.h>
int
main (void)
{
init_table ();
return yyparse ();
}
void
yyerror (const char *s) /* Вызывается yyparse в случае ошибки */
{
printf ("%s\n", s);
}
struct init
{
char *fname;
double (*fnct)(double);
};
struct init arith_fncts[] =
{
"sin", sin,
"cos", cos,
"atan", atan,
"ln", log,
"exp", exp,
"sqrt", sqrt,
0, 0
};
/* Таблица символов: цепочка `struct symrec'. */
symrec *sym_table = (symrec *) 0;
/* Поместить арифметические функции в таблицу. */
void
init_table (void)
{
int i;
symrec *ptr;
for (i = 0; arith_fncts[i].fname != 0; i++)
{
ptr = putsym (arith_fncts[i].fname, FNCT);
ptr->value.fnctptr = arith_fncts[i].fnct;
}
}
Вы можете добавить к калькулятору дополнительные функции, просто редактируя список инициализации и включая необходимые файлы заголовков.
Две важные функции позволяют просматривать символы в таблице и вводить новые.
Функции putsym передаётся имя и тип (VAR или FNCT)
заносимого объекта. Объект включается в начало списка, и возвращается
указатель на объект. Функции getsym передаётся имя искомого символа.
Если он найден, возвращается указатель на него, иначе же ноль.
symrec *
putsym (char *sym_name, int sym_type)
{
symrec *ptr;
ptr = (symrec *) malloc (sizeof (symrec));
ptr->name = (char *) malloc (strlen (sym_name) + 1);
strcpy (ptr->name,sym_name);
ptr->type = sym_type;
ptr->value.var = 0; /* set value to 0 even if fctn. */
ptr->next = (struct symrec *)sym_table;
sym_table = ptr;
return ptr;
}
symrec *
getsym (const char *sym_name)
{
symrec *ptr;
for (ptr = sym_table; ptr != (symrec *) 0;
ptr = (symrec *)ptr->next)
if (strcmp (ptr->name,sym_name) == 0)
return ptr;
return 0;
}
Функция yylex теперь должна распознавать переменные, числовые значения
и односимвольные арифметические операции. Строки алфавитноцифровых литер,
начинающиеся не с цифры, распознаются или как переменные, или как функции, в
зависимости от того, что говорится о них в таблице символов.
Строка передаётся функции getsym для поиска в таблице символов. Если
имя встречается в таблице, в yyparse возвращаются указатель на его
положение и его тип (VAR или FNCT). Если в таблице его ещё нет,
оно заносится как VAR, используя putsym. Опять же, указатель и
тип (который должен быть VAR) возвращаются в yyparse.
Для обработки числовых значений и арифметических операций изменения в
yylex не нужны.
#include <ctype.h>
int
yylex (void)
{
int c;
/* Игнорировать промежутки, получить первый непробельный символ. */
while ((c = getchar ()) == ' ' || c == '\t');
if (c == EOF)
return 0;
/* С литеры начинается число => разобрать число. */
if (c == '.' || isdigit (c))
{
ungetc (c, stdin);
scanf ("%lf", &yylval.val);
return NUM;
}
/* С литеры начинается идентификатор => читать имя. */
if (isalpha (c))
{
symrec *s;
static char *symbuf = 0;
static int length = 0;
int i;
/* Первоначально сделать буфер достаточно большим
для имени символа из 40 литер. */
if (length == 0)
length = 40, symbuf = (char *)malloc (length + 1);
i = 0;
do
{
/* Если буфер полон, расширить его. */
if (i == length)
{
length *= 2;
symbuf = (char *)realloc (symbuf, length + 1);
}
/* Добавить эту литеру в буфер. */
symbuf[i++] = c;
/* Получить следующую литеру. */
c = getchar ();
}
while (c != EOF && isalnum (c));
ungetc (c, stdin);
symbuf[i] = '\0';
s = getsym (symbuf);
if (s == 0)
s = putsym (symbuf, VAR);
yylval.tptr = s;
return s->type;
}
/* Любая другая литера сама по себе является лексемой. */
return c;
}
Эта программа одновременно и достаточно мощна, и гибка. Вы можете легко
добавлять новые функции и также несложно модифицировать код для введения
предопределённых переменных, таких как pi и e.
3.6 Упражнения
- Добавьте несколько новых функций из `math.h' в список инициализации.
-
Добавьте ещё один массив, содержащий константы и их значения. Потом
модифицируйте
init_tableчтобы внести эти константы в таблицу символов. Проще всего будет придать константам типVAR. - Заставьте программу выводить сообщение об ошибке, если пользователь ссылается на неинициализированную переменную каким-либо образом, кроме присвоения ей значения.
[Содержание] [Назад] [Пред] [Вверх] [След] [Вперед]