	Навигация
	Обратная связь Последние публикации

	Вход для пользователей
	Имя пользователя: * Пароль: * Запросить новый пароль

	Кто на сайте
	Сейчас на сайте 0 пользователей и 6 гостей.

Bison 1.35 - 4. Файлы грамматики Bison

[Содержание] [Назад] [Пред] [Вверх] [След] [Вперед]

4. Файлы грамматики Bison

Bison принимает на вход спецификацию контекстно-свободной грамматики и создаёт функцию на языке C, которая распознаёт правильные предложения этой грамматики.

Имя входного файла грамматики Bison по соглашению заканчивается на `.y'. См. раздел 10. Вызов Bison.

4.1 Структура грамматики Bison

Файл грамматики Bison содержит четыре основные секции, показанные здесь с соответствующими разделителями.

%{
Объявления C
%}

Объявления Bison

%%
Правила грамматики
%%

Дополнительный код на C

Комментарии, заключённые в `/* ... */', могут появляться в любой секции.

4.1.1 Секция объявлений C

Секция объявлений C содержит макроопределения и объявления функций и переменных, используемых в действиях правил грамматики. Они копируются в начало файла анализатора так, чтобы они предшествовали определению yyparse. Вы можете использовать `#include' для получения объявлений из файлов заголовков. Если вам не нужны какие-либо объявления C, вы можете опустить ограничивающие эту секцию `%{' и `%}'.

4.1.2 Секция объявлений Bison

Секция объявлений Bison содержит объявления, определяющие терминальные и нетерминальные символы, задающие приоритет и т.д. В некоторых простых грамматиках вам могут быть не нужны никакие объявления. См. раздел 4.7 Объявления Bison.

4.1.3 Секция правил грамматики

Секция правил грамматики содержит одно или более правил грамматики Bison и ничего более. См. раздел 4.3 Синтаксис правил грамматики.

Должно быть по меньшей мере одно правило грамматики, и первый ограничитель `%%' (предшествующий правилам грамматики) не может быть опущен, даже если это первая строка файла.

4.1.4 Секция дополнительного кода на C

Секция дополнительного кода на C в точности копируется в конец файла анализатора, точно так же, как секция объявлений C в начало. Это наиболее удобное место, чтобы поместить что-либо, что вы хотите иметь в файле анализатора, но что не нужно помещать перед определением yyparse. Например, сюда часто помещаются определения yylex и yyerror. См. раздел 5. Интерфейс анализатора на C.

Если последняя секция пуста, вы можете опустить `%%', отделяющее её от правил грамматики.

Сам анализатор Bison содержит множество статических переменных с именами, начинающимися с `yy', и макросов с именами, начинающимися с `YY'. Не использовать такие имена, за исключением описанных в этом руководстве, в секции дополнительного кода C файла грамматики -- хорошая идея.

4.2 Символы, терминальные и нетерминальные

Символы в грамматиках Bison представялют грамматическую классификацию языка.

Терминальный символ (также известный как тип лексемы) представляет класс синтаксически эквивалентных лексем. Вы используете такой символ в правилах грамматики, чтобы обозначить, что допустима лексема этого класса. В анализаторе Bison символ представляется числовым кодом, и функция yylex возвращает код типа лексемы чтобы показать, лексема какого вида прочитана. Вам не нужно знать, каково значение кода, для его обозначения можно использовать сам символ.

Нетерминальный символ обозначает класс синтаксически эквивалентных групп. Имя символа используется при написании правил грамматики. По соглашению оно должно быть записано в нижнем регистре.

Имена символов могут содержать буквы, цифры (но не начинаться с цифры), знаки подчёркивания и точки. Точки имеют значение только в нетерминалах.

Есть три способа записи терминальных символов в грамматике:

Именованный тип лексемы записывается идентификатором, как идентификаторы C. По соглашению он должен быть записан в верхнем регистре. Каждое такое имя должно быть определено в объявлении Bison, например, %token. См. раздел 4.7.1 Имена типов лексем.
Тип однолитерной лексемы (лексема-однолитерная константа) записывается в грамматике с использованием того же синтаксиса, что используется в C для литерных констант: например, '+' -- это тип однолитерной лексемы. Тип однолитерной лексемы не надо объявлять, если только вам не нужно задать тип его семантического значения (см. раздел 4.5.1 Типы данных семантических значений), ассоциативность или приоритет (см. раздел 6.3 Приоритет операций). По соглашению тип однолитерной лексемы используется только для представления лексемы, состоящей из этой конкретной литеры. Так, тип лексемы '+' используется для представления литеры `+' в качестве лексемы. Ничто не обязывает вас придерживаться этого соглашения, но если вы не будете этого делать, ваша программа будет путать других читателей. В Bison также могут быть использованы все обычные escape-последовательности, использующиеся в литерных константах C, но вы не должны использовать нулевой символ в качестве однолитерной константы, поскольку его код ASCII -- ноль -- это код, возвращаемый yylex при обнаружении конца файла. (см. раздел 5.2.1 Соглашения о вызове yylex).
Строковый литерал (строковая лексема) записывается как строковая константа C: например, строковым литералом является "<=". Строковый литерал не надо объявлять, если только вам не нужно задать тип его семантического значения (см. раздел 4.5.1 Типы данных семантических значений), ассоциативность или приоритет (см. раздел 6.3 Приоритет операций). Вы можете связать строковую лексему с символическим именем (псевдонимом), используя объявление %token (см. раздел 4.7.1 Имена типов лексем). Если вы не сделали этого, лексический анализатор должен отыскать номер строковой лексемы в таблице yytname (см. раздел 5.2.1 Соглашения о вызове yylex). ВНИМАНИЕ: В Yacc строковые лексемы не работают. По соглашению строковые лексемы используются только для представления лексемы, состоящей из этой конкретной строки. Так, тип лексемы "<=" используется для представления строки `<=' в качестве лексемы. Bison не обязывает вас придерживаться этого соглашения, но если вы не будете этого делать, люди, читающие вашу программу, запутаются. В Bison также могут быть использованы все escape-последовательности, использующиеся в строковых константах C. Строковая лексема должна содержать две или более литеры, для лексем из одной литеры используйте однолитерные лексемы (см. выше).

Выбранный вами способ записи терминального символа не влияет на его грамматический смысл. Оно зависит только от того, где он встречается в правилах, и когда функция анализатора его возвращает.

Значение, возвращаемое yylex, -- всегда один из терминальных символов (или 0 в случае конца входного текста). Каким бы способом вы не записывали тип лексемы в правилах грамматики, в определениия yylex он должен быть описан тем же образом. Числовой код типа однолитерной лексемы -- это просто код ASCII этой литеры, и таким образом yylex может для получения необходимого кода использовать ту же литерную константу. Каждый именованный тип лексемы в файле анализатора становится макросом C, и yylex может для обозначения кода использовать то же имя (именно поэтому точки в терминальных символах не имеют значения). См. раздел 5.2.1 Соглашения о вызове yylex.

Если yylex определяется в отдельном файле, вам необходимо сделать доступными ей макроопределения типов лексем. Используйте параметр `-d' при запуске Bison, и эти макроопределения будут записаны в отдельный файл заголовка `имя.tab.h', который вы можете включать в другие нуждающиеся в нём файлы исходного кода. См. раздел 10. Вызов Bison.

Символ error -- это терминальный символ, зарезервированный для восстановления после ошибок. Вы не должны использовать его для каких-то других целей. В частности, yylex никогда не должна возвращать это значение.

4.3 Синтаксис правил грамматики

Правило грамматики Bison имеет следующий общий вид:

результат: компоненты...
        ;

где результат -- это описываемый правилом нетерминальный символ, а компоненты -- различные терминальные и нетерминальные символы, объединяемые этим правилом (см. раздел 4.2 Символы, терминальные и нетерминальные).

Например:

exp:      exp '+' exp
        ;

говорит о том, что две группы типа exp и лексема `+' между ними могут быть объединены в более крупную группу типа exp.

Пробельные литеры в правилах только разделяют символы. Вы можете по своему усмотрению вставлять дополнительные промежутки.

Между компонентами могут быть разбросаны действия, определяющие семантику правила. Действие выглядит так:

{операторы C}

Обычно в правиле только одно действие, и оно следует после всех компонентов. См. раздел 4.5.3 Действия.

Для одного результата можно написать несколько правил, отдельно или же соединённых литерой вертикальной черты `|' как здесь:

результат:    компоненты первого правила...
        | компоненты второго правила...
        ...
        ;

В любом случае правила рассматриваются как различные, даже если они таким образом объединены.

Есть в правиле нет компонентов, это означает, что результат может соответствовать пустой строке. Например, вот как определяется последовательность нуля или более групп exp, разделённых запятыми:

expseq:   /* пусто */
        | expseq1
        ;

expseq1:  exp
        | expseq1 ',' exp
        ;

Традиционно в каждом правиле, не содержащем компонентов, пишется комментарий `/* пусто */'.

4.4 Рекурсивные правила

Правило называется рекурсивным, если нетерминал его результата появляется также в его правой части. Почти все грамматики Bison должны использовать рекурсию, потому что это единственный способ определить последовательность из произвольного числа элементов. Рассмотрим рекурсивное определение последовательности одного или более выражений, разделённых запятыми:

expseq1:  exp
        | expseq1 ',' exp
        ;

Поскольку рекурсивный символ expseq1 -- самый левый в правой части, мы называем это левой рекурсией. И наоборот, вот та же конструкция, определённая с использованием правой рекурсии:

expseq1:  exp
        | exp ',' expseq1
        ;

Последовательность любого вида может быть определена с использованием как левой, так и правой рекурсии, но вам следует всегда использовать леворекурсивные правила, потому что они могут разобрать последовательность из любого числа элементов, используя ограниченое стековое пространство. Размер используемого праворекурсивными правилами стека Bison пропорционален числу элементов последовательности, поскольку все эти элементы должны быть помещены в стек перед тем, как правило будет применено в первый раз. См. раздел 6. Алгоритм анализатора Bison, по поводу дальнейшего объяснения этого факта.

Косвенная или взаимная рекурсия возникает, когда результат правила не появляется непосредственно в правой части, но встречается в правилах для других нетерминалов, появляющихся в его правой части.

Например:

expr:     primary
        | primary '+' primary
        ;

primary:  constant
        | '(' expr ')'
        ;

определяет два взаимнорекурсивных правила, поскольку каждое из них ссылается на другое.

4.5 Определение семантики языка

Правила грамматики языка определяют только его синтаксис. Семантика определяется семантическими значениями, сопоставленными различным лексемам и группам, и правилами, выполняющимися при распознавании различных групп.

Например, калькулятор производит правильные вычисления, потому что с каждым выражением сопоставлено числовое значение. Он правильно складывает, потому что действие для группы `x + y' складывает числа, сопоставленные с x и y.

4.5.1 Типы данных семантических значений

В простой программе может быть достаточно использование одного и того же типа данных для семантических значений всех языковых конструкций. Это верно для примеров постфиксного и инфиксного калькулятора (см. раздел 3.1 Калькулятор обратной польской нотации).

По умолчанию Bison использует для всех семантических значений тип int. Чтобы задать другой тип, определите макрос YYSTYPE, как здесь:

#define YYSTYPE double

Это макроопределение должно находиться в секции объявлений C файла грамматики (см. раздел 4.1 Структура грамматики Bison).

4.5.2 Несколько типов значений

В большинстве программ вам будут нужны разные типы данных для разных видов лексем и групп. Например, числовой константе может быть нужен тип int или long, строковой -- тип char *, а идентификатору -- указатель на элемент таблицы символов.

Чтобы в анализаторе можно было использовать несколько типов семантических значений, Bison требует сделать две вещи:

Задать весь набор возможных типов данных в объявлении Bison %union (см. раздел 4.7.3 Набор типов значений).
Выбрать для каждого символа (терминального или нетерминального), для которого используются семантическое значение, один из этих типов. Для лексем это делается в объявлении Bison %token (см. раздел 4.7.1 Имена типов лексем), а для групп -- в объявлении Bison %type (см. раздел 4.7.4 Нетерминальные символы).

4.5.3 Действия

Действие сопровождает синтаксическое правило и содержит код на C, который должен выполняться при каждом распознавании текста, соответствующего этому правилу. Задачей большинства действий является вычисление семантического значения группы, собираемой правилом, исходя из семантических значений, сопоставленных лексемам или меньшим группам.

Действие состоит из операторов C, окружённых фигурными скобками, как составной оператор C. Оно может быть помещено в любой точке правила, и выполняется в этой точке. Большинство правил имеют только одно действие в конце правила, после всех компонентов. Действия внутри правила непросты, и используются только в специальных целях (см. раздел 4.5.5 Действия внутри правил).

Код на C действия может ссылаться на семантические значения компонентов, связываемых правилом с помощью конструкции $n, обозначающей значение n-го компонента. Семантическое значение собираемой группы -- $$ (Bison, копируя действия в файл анализатора, превращает обе эти конструкции в ссылки на элементы массива).

Вот типичный пример:

exp:    ...
        | exp '+' exp
            { $$ = $1 + $3; }

Это правило собирает exp из двух меньших групп exp, соединённых лексемой `знак плюс'. В действии $1 и $3 ссылаются на семантические значения двух групп-компонентов exp, являющихся первым и третьим символами в правой части правила. Сумма сохраняется в $$, становясь тем самым семантическим значением выражения сложения, только что распознанного правилом. Если бы с лексемой `+' было сопоставлено полезное семантическое значение, на него можно было бы ссылаться как на $2.

Если вы не задаёте действие для правила, Bison применяет действие по умолчанию: $$ = $1. То есть значение первого символа правила становится значением всего правила. Конечно, действие по умолчанию допустимо только если эти два типа данных соответствуют друг другу. Для пустого правила нет осмысленного действия по умолчанию, каждое пустое правило должно иметь явное действие, за исключением случая, когда его значение никогда не будет использоваться.

$n c нулевым или отрицательным n допустима для ссылки на лексемы и группы, находящиеся в стеке перед соответствующими текущему правилу лексемами и группами. Это очень рискованный приём, и чтобы надёжно пользоваться им, вы должны быть уверены, что знаете контекст применения правила. Вот случай, в котором вы можете безопасно использовать его:

foo:      expr bar '+' expr  { ... }
        | expr bar '-' expr  { ... }
        ;

bar:      /* пусто */
 */
        { previous_expr = $0; }
        ;

Пока bar используется только так, как здесь показано, $0 всегда будет ссылаться на expr, предшествующий bar в определении foo.

4.5.4 Типы данных значений в действиях

Если вы выбрали единственный тип данных семантических значений, конструкции $$ и $n всегда имеют этот тип.

Если вы используете %union для задания множества типов данных, вы должны определить выбор из этих типов для каждого терминального или нетерминального символа, который может иметь семантическое значение. Тогда каждый раз, когда вы используете $$ или $n, тип данных определяется тем, на какой символ в правиле они ссылаются. В этом примере,

exp:    ...
        | exp '+' exp
            { $$ = $1 + $3; }

$1 и $3 ссылаются на экземпляры exp, поэтому все они имеют тип данных, объявленный для нетерминального символа exp. Если бы использовался $2, то он имел бы тип данных, объявленный для терминального символа '+', каким бы он ни был.

Вместо этого вы можете указывать тип данных, когда вы ссылаетесь на значение, вставляя `<тип>' после `$' в начале ссылки. Например, если вы определите типы так:

%union {
  int itype;
  double dtype;
}

вы можете написать $<itype>1 чтобы сослаться на первый компонент правила как на целое, или $<dtype>1 -- чтобы сослаться как на вещественное число с двойной точностью.

4.5.5 Действия внутри правил

Время от времени полезно помещать действия внутрь правила. Эти действия записываются точно так же, как обычные действия в конце правил, но выполняются до того, как анализатор распознает следующие компоненты.

Действие внутри правила может с помощью $n ссылаться на компоненты, предшествующие ему, но не на последующие, поскольку выполняется до их разбора.

Действие внутри правила само по себе считается одним из компонентов правила. Это имеет значение, если позднее в том же правиле присутствует ещё одно действие (и, обычно, ещё одно в конце правила): вы должны при вычислении n в конструкции $n учитывать действия вместе с правилами.

Действие внутри правила также имеет семантическое значение. Действие может установить его значение присваиванием $$, а последующие действия в правиле могут ссылаться на него, используя $n. Поскольку для именования действия нет символа, нет способа объявить заранее тип данных его значения, поэтому вы должны использовать конструкцию `$<...>n' для задания типа данных каждый раз, когда вы ссылаетесь на это значение.

Установить значение всего правила действием внутри правила невозможно, поскольку присваивание $$ не будет этого делать. Единственный способ задать значение всего правила -- использовать обычное действие в конце правила.

Приведём пример гипотетического компилятора, обрабатывающего оператор let, имеющий вид: `let (переменная) оператор' и позволяющий создать переменную переменная только на время выполнения оператора. Для разбора этой конструкции мы должны поместить переменную в таблицу символов на время разбора оператора, а после этого удалить её. Вот, как это делается:

stmt:   LET '(' var ')'
                { $<context>$ = push_context ();
                  declare_variable ($3); }
        stmt    { $$ = $6;
                  pop_context ($<context>5); }

Как только распознано `let (переменная)', выполняется первое действие. Оно сохраняет копию текущего семантического контекста (список доступных переменных) в качестве своего семантического значения, используя вариант типа данных context. Потом оно вызывает declare_variable, чтобы добавить в этот список новую переменную. Когда работа первого действия завершена, может быть разобран вложенный оператор stmt. Имейте в виду, что действие внутри правила -- это пятый компонент, поэтому `stmt' -- шестой.

После разбора вложенного оператора его семантическое значение становится значением всего оператора let. Потом для восстановления прошлого списка переменных используется семантическое значение предыдущего действия. Это удалит из списка временную let-переменную, и она не будет существовать во время разбора остальной части программы.

Применение действий до того, как правило полностью распознано, часто приводит к конфликтам, поскольку анализатор должен принять определённый вариант разбора чтобы обработать действие. Например, следующие два правила без внутреннего действия могут сушествовать совместно в работающем анализаторе, потому что анализатор может сдвинуть лексему открывающей фигурной скобки и посмотреть, что следует за ней, перед принятием решения, есть там объявление или нет.

compound: '{' declarations statements '}'
        | '{' statements '}'
        ;

Но если мы добавим внутреннее действие, как показано ниже, правила перестанут работать:

compound: { prepare_for_local_variables (); }
          '{' declarations statements '}'
        | '{' statements '}'
        ;

Теперь анализатор вынужден решать, запускать или нет внутреннее действие, когда он прочитал ещё только открывающую скобку. Другими словами, он должен принять решение об использовании того или иного правила, не имея информации, достаточной для того, чтобы сделать это правильно (лексема открывающей фигурной скобки в этот момент -- это то, что называется лексемой, увиденной впереди, поскольку анализатор всё ещё решает, что с ней делать. См. раздел 6.1 Предпросмотренные лексемы.).

Вы можете думать, что можно решить проблему, расположив в обоих правилах одинаковые действия, как здесь:

compound: { prepare_for_local_variables (); }
          '{' declarations statements '}'
        | { prepare_for_local_variables (); }
          '{' statements '}'
        ;

Но это не поможет, потому что Bison не осознает, что эти два действия идентичны (Bison никогда не пытается понимать код на C в действиях).

Если грамматика такова, что определение можно отличить от оператора по первой лексеме (что верно для C), то одним из работающих решений будет поместить действие после открывающей скобки, как здесь:

compound: '{' { prepare_for_local_variables (); }
          declarations statements '}'
        | '{' statements '}'
        ;

Теперь первая лексема следующего определения или оператора, которая в любом случае должна сообщить Bison, какое правило использовать, действительно может это сделать.

Другое решение -- вынести действие в отдельный нетерминальный символ, служащий подпрограммой:

subroutine: /* пусто */
          { prepare_for_local_variables (); }
        ;

compound: subroutine
          '{' declarations statements '}'
        | subroutine
          '{' statements '}'
        ;

Теперь Bison может выполнить действие в правиле для subroutine, не принимая решения, какое из правил для compound использовать в конце концов. Имейте в виду, что действие теперь находится в конце правила. Любые действия внутри правил могут быть таким образом превращены в действия в конце правил, и именно это Bison на самом деле делает для реализации действий внутри правил.

4.6 Отслеживание положений

Хотя правил грамматики и семантических действий и достаточно, чтобы написать полностью функциональный анализатор, может быть полезно обрабатывать некоторую дополнительную информацию, особенно положение символов.

Способ обработки положений определяется указанием типа данных и действия, которые должны выполняться при разборе правил.

4.6.1 Тип данных положений

Определение типа данных для положений гораздо проще, чем для семантических значений, поскольку все лексемы и группы всегда используют один и тот же тип.

Тип положений задаётся определением макроса YYLTYPE. Если YYLTYPE не определён, Bison по умолчанию использует структуру из четырёх членов:

struct
{
  int first_line;
  int first_column;
  int last_line;
  int last_column;
}

4.6.2 Действия и положения

Действия полезны не только для определения семантики языка, но и для описания поведения анализатора, касающегося положений.

Наиболее очевидный способ получения положения синтаксической группы очень похож на способ вычисления семантических значений. Для получения доступа в конкретном правиле к связываемым элементам может использоваться несколько конструкций. Положение n-го компонента правой части правила обозначается @n, а положение группы левой части -- @$.

Вот простой пример, использующий для положений тип данных по умолчанию:

exp:    ...
        | exp '/' exp
            {
              @$.first_column = @1.first_column;
              @$.first_line = @1.first_line;
              @$.last_column = @3.last_column;
              @$.last_line = @3.last_line;
              if ($3)
                $$ = $1 / $3;
              else
                {
                  $$ = 1;
                  printf("Деление на ноль, l%d,c%d-l%d,c%d",
                         @3.first_line, @3.first_column,
                         @3.last_line, @3.last_column);
                }
            }

Как и для семантических значений, есть действие по умолчанию для положений, выполняемое при каждом разборе правила. Оно устанавливает начало @$ на начало первого символа, а конец -- на конец последнего символа.

При использовании действия по умолчанию отслеживание положений может быть полностью автоматическим. Вышеприведённый пример можно переписать так:

exp:    ...
        | exp '/' exp
            {
              if ($3)
                $$ = $1 / $3;
              else
                {
                  $$ = 1;
                  printf("Деление на ноль, l%d,c%d-l%d,c%d",
                         @3.first_line, @3.first_column,
                         @3.last_line, @3.last_column);
                }
            }

4.6.3 Действие по умолчанию для положений

На самом деле действия -- не лучшее место для вычисления положений. Поскольку положения гораздо более общи, чем семантические значения, в анализаторе есть место, где можно переопределить действие по умолчанию для каждого правила. Макрос YYLLOC_DEFAULT вызывается при каждом разборе правила, перед запуском связанного с ним действия.

В большинстве случаев этого макроса, в общем, достаточно, чтобы избавиться от специального кода в семантических действиях.

Макрос YYLLOC_DEFAULT принимает три параметра. Первый -- положение группы (результат вычисления). Второй -- массив, содержащий положения всех элементов правой части связываемого правила. Последний -- размер правой части правила.

По умолчанию он определён следующим образом:

#define YYLLOC_DEFAULT(Current, Rhs, N)         \
  Current.last_line   = Rhs[N].last_line;       \
  Current.last_column = Rhs[N].last_column;

При определении YYLLOC_DEFAULT вы должны считать, что:

У аргументов нет побочных действий. Однако, YYLLOC_DEFAULT может изменять только первый из них (результат).
Перед выполнением YYLLOC_DEFAULT анализатор устанавливает @$ равным @1.
Для обеспечения последовательности с реализацией семантических действий, правильные индексы массива -- от 1 до n.

4.7 Объявления Bison

Секция объявлений Bison грамматики Bison определяет символы, используемые при формулировке грамматики и типы данных семантических значений. См. раздел 4.2 Символы, терминальные и нетерминальные.

Все имена типов лексем (но не однолитерные лексемы, такие как '+' и '*') должны быть объявлены. Нетерминальные символы должны быть объявлены, если вам нужно задать используемый тип данных семантического значения (см. раздел 4.5.2 Несколько типов значений).

По умолчанию первое правило файла также задаёт начальный символ. Если вы хотите, чтобы начальным символом был какой-то другой, вы должны объявить его явно (см. раздел 2.1 Языки и контекстно-свободные грамматики).

4.7.1 Имена типов лексем

Основной способ объявления имени типа лексемы (терминального символа) следующий:

%token имя

В анализаторе Bison превратит это в директиву #define, так что функция yylex (если она присутствует в файле) сможет использовать имя имя для обозначения кода этого типа лексемы.

Если вы хотите задать ассоциативность и приоритет, вместо %token вы можете использовать %left, %right или %nonassoc. См. раздел 4.7.2 Приоритет операций.

Вы можете явно задать числовой код типа лексемы, добавив целочисленное значение непосредственно после имени лексемы:

%token NUM 300

Тем не менее, в общем случае лучше позволить Bison определить числовые коды для всех типов лексем самому. Bison автоматически выберет коды, не конфликтующие друг с другом и с литерами ASCII.

В случае, если тип значения -- объединение, вы дожны включить в %token или другие объявления лексем тип данных, заключённый в угловые скобки (см. раздел 4.5.2 Несколько типов значений).

Например:

%union {              /* определение набора типов */
  double val;
  symrec *tptr;
}
%token <val> NUM      /* определение лексемы NUM и её типа */

Вы можете связать строковую лексему с именем типа лексемы, записав строку в конце объявления %token, объявляющего это имя. Например:

%token arrow "=>"

Например, грамматика языка C может задавать такие имена и соответствующие строковые лексемы:

%token  <operator>  OR      "||"
%token  <operator>  LE 134  "<="
%left  OR  "<="

После того, как вы сопоставили друг с другом строку и тип лексемы, они становятся взаимозаменяемы в дальнейших объявлениях или правилах грамматики. Функция yylex может использовать имя лексемы или строку для получения числового кода типа лексемы (см. раздел 5.2.1 Соглашения о вызове yylex).

4.7.2 Приоритет операций

Для одновременного объявления лексемы и задания её приоритета и ассоциативности используйте объявления %left, %right или %nonassoc. Они называются объявлениями приоритета. См. раздел 6.3 Приоритет операций, для общей информации о приоритете операций.

Синтаксис объявления приоритета тот же, что и %token: или

%left символы...

или

%left <тип> символы...

В самом деле, любое из этих определений служит тем же целям, что и %token. Но кроме того, они задают ассоциативность и относительный приоритет всех символов:

Ассоциативность операции op определяет разбор повторяющихся операторов: будут ли при разборе `x op y op z' вначале сгруппированы x и y, или же y и z. %left задаёт левую ассоциативность (вначале группируются x и y), а %right -- правую (наоборот, y и z). %nonassoc задаёт неассоциативную операцию, т.е. `x op y op z' рассматривается как синтаксическая ошибка.
Приоритет операции определяет, как она соотносится с другими операциями. Все лексемы, объявленные в одном объявлении приоритета, имеют одинаковый приоритет, и разбираются вместе в соответствии с их ассоциативностью. При объединении двух лексем, объявленных в разных объявлениях приоритета, объявленная позднее имеет более высокий приоритет и группируется раньше.

4.7.3 Набор типов значений

Объявление %union задаёт весь набор возможных типов данных семантических значений. За ключевым словом %union следуют фигурные скобки, содержимое которых имеет тот же вид, что и содержимое структуры union C.

Например:

%union {
  double val;
  symrec *tptr;
}

Это объявление говорит о том, что есть два альтернативных типа: double и symrec *. Им даны имена val и tptr, эти имена используются в объявлениях %token и %type для указать одного из этих типов для терминального или нетерминального символа (см. раздел 4.7.4 Нетерминальные символы).

Имейте в виду, что, в отличие от объявления union в C, вы не ставите точку с запятой после закрывающей фигурной скобки.

4.7.4 Нетерминальные символы

Если вы используете %union для задания множества типов значений, вы должны объявить тип значения каждого нетерминального символа, семантическое значение которого используется. Это делает объявление %type:

%type <тип> нетерминал...

Здесь нетерминал -- имя нетерминального символа, а тип -- имя, данное в %union желаемой альтернативе (см. раздел 4.7.3 Набор типов значений). Вы можете задать в одном объявлении %type любое количество нетерминальных символов, если у них одинаковый тип значения. Для разделения между собой имён символов используйте пробелы.

Вы можете также объявить тип значения терминального символа. Для этого используйте ту же конструкцию <тип> в объявлении терминального символа. Все варианты объявления лексемы допускают наличие <тип>.

4.7.5 Подавление сообщений о конфликтах

В норме Bison сообщает, если в грамматике есть какие-либо конфликты (см. раздел 6.2 Конфликты сдвиг/свёртка), но большинство реальных грамматик содержат безвредные конфликты сдвиг/свёртка, разрешаемые предсказуемым образом, и которые сложно исключить. Желательно подавить сообщения об этих конфликтах, пока их число не изменяется. Вы можете сделать это объявлением %expect.

Это объявление выглядит так:

%expect n

Здесь n -- десятичное целое число. Это объявление говорит, что не нужно выдавать предупреждений, если грамматика содержит n конфликтов сдвиг/свёртка и не содержит конфликтов свёртка/свёртка. Если конфликтов меньше или больше, или если есть конфликты свёртка/свёртка, вместо обычного предупреждения выдаётся сообщение об ошибке.

В общем случае использование %expect включает следующие этапы:

Скомпилируйте вашу грамматику без %expect. Используйте параметр `-v' чтобы получить подробный список конфликтов и мест их возникновения. Bison также выведет число конфликтов.
Проверьте каждый из конфликтов, чтобы удостовериться в том, что решение Bison по умолчанию -- это то, чего вы на самом деле хотите. Если нет, перепишите грамматику и вернитесь к началу.
Добавьте объявление %expect, взяв число n равным выведенному Bison.

Теперь Bison перестанет раздражать вас сообщениями о проверенных вами конфликтах, но вновь начнёт выдавать сообщения, если изменения в грамматике повлекут появление новых конфликтов.

4.7.6 Начальный символ

По умолчанию Bison полагает начальным символом грамматики первый нетерминал, заданный в секции определения грамматики. Программист может переопределить его объявлением %start, как здесь:

%start символ

4.7.7 Чистый (повторно входимый) анализатор

Повторно входимая программа -- это программа, которая не меняется в процессе выполнения. Другими словами, она полностью состоит из чистого кода (кода только для чтения). Повторная входимость важна всегда, когда возможно асинхронное выполнение, например, не повторно входимая программа может быть ненадёжной при вызове её из обработчика сигнала. В системах с несколькими потоками управления, не повторно входимая программа может быть вызвана только внутри критического участка.

В норме Bison генерирует не повторно входимый анализатор. Это подходит в большинстве случаев, и даёт совместимость с YACC (стандартные интерфейсы YACC не повторно входимы по своей природе, потому что они используют для взаимодействия с yylex статически выделяемые переменные, включая yylval и yylloc).

В качестве альтернативы вы можете создать чистый, повторно входимый анализатор. Объявление Bison %pure_parser говорит, что вы хотите получить повторно входимый анализатор. Оно выглядит так:

%pure_parser

В результате переменные взаимодействия yylval и yylloc становятся локальными переменными yyparse и используются другие соглашения о вызове функции лексического анализатора yylex. См. раздел 5.2.4 Соглашения о вызове для чистых анализаторов, для прояснения деталей. Переменная yynerrs также становится локальной переменной yyparse (см. раздел 5.3 Функция сообщения об ошибках yyerror). Соглашения о вызове самой функции yyparse не изменяются.

Будет ли анализатор чистым, никак не влияет на правила грамматики. Вы можете создать как чистый, так и не повторно входимый анализатор из любой правильной грамматики.

4.7.8 Обзор объявлений Bison

Здесь приведено краткое изложение используемых при определении грамматики объявлений:

%union: объявляет набор типов данных, которые могут иметь семантические значения (см. раздел 4.7.3 Набор типов значений).
%token: Объявляет терминальный символ (имя типа лексемы) без указание приоритета или ассоциативности (см. раздел 4.7.1 Имена типов лексем).
%right: Объявляет терминальный символ (имя типа лексемы), являющийся знаком правоассоциативной операции (см. раздел 4.7.2 Приоритет операций).
%left: Объявляет терминальный символ (имя типа лексемы), являющийся знаком левоассоциативной операции (см. раздел 4.7.2 Приоритет операций).
%nonassoc: Объявляет терминальный символ (имя типа лексемы), являющийся знаком неассоциативной операции (использование его там, где требуется ассоциативность, является синтаксической ошибкой) (см. раздел 4.7.2 Приоритет операций).
%type: Объявляет тип семантического значения нетерминального символа (см. раздел 4.7.4 Нетерминальные символы).
%start: Задаёт начальный символ грамматики (см. раздел 4.7.6 Начальный символ).
%expect: Объявляет ожидаемое число конфликтов сдвиг/свёртка (см. раздел 4.7.5 Подавление сообщений о конфликтах).

Для изменения поведения bison используйте следующие директивы:

%debug

В файле анализатора определяет макрос YYDEBUG как 1, если он ещё не определён, так что компилируются возможности отладки. См. раздел 9. Отладка вашего анализатора.

%defines

Создаёт дополнительный выходной файл, содержащий макроопределения имён типов лексем, определённых в грамматике, и типа семантического значения YYSTYPE, а также несколько объявлений внешних (extern) переменных. Если выходной файл анализатора называется `имя.c', то этот файл будет называться `имя.h'. Этот выходной файл необходим, если вы хотите поместить определение yylex в отдельный файл исходного кода, потому что функция yylex должна иметь возможность обращаться к кодам типов лексем и переменной yylval. См. раздел 5.2.2 Семантические значения лексем.

%file-prefix="префикс"

Задаёт префикс имён всех выходных файлов Bison. Имена выбираются таким образом, как если бы входной файл назывался `префикс.y'.

%locations

Создаёт код с обработкой положений (см. раздел 5.4 Специальные возможности, используемые в действиях). Этот режим включается всегда, когда грамматика использует специальные лексемы `@n', но если ваша грамматика их не использует, `%locations' позволит обеспечить более аккуратный вывод сообщений об ошибках разбора.

%name-prefix="префикс"

Переименовывает используемые анализатором внешние символы так, что они начинаются с префикс вместо `yy'. Точный список переименовываемых символов: yyparse, yylex, yyerror, yynerrs, yylval, yychar и yydebug. Например, если вы используете `%name-prefix="c_"', их имена примут вид: c_parse, c_lex и т.д. См. раздел 4.8 Несколько анализаторов в одной программе.

%no-parser

Не включает никакого кода на C в файл анализатора, только создаёт таблицы. Файл анализатора будет содержать только директивы #define и объявления статических переменных. Этот параметр также указывает Bison записать в файл `имя_файла.act' код на C действий грамматики, окружённых фигурными скобками, пригодный для оператора switch.

%no-lines

Не создаёт никаких команд препроцессора #line в файле анализатора. Обычно Bison записывает эти команды в файл анализатора так, что компилятор C и отладчики будут связывать ошибки и объектный код с вашим исходным файлом (файлом грамматики). Эта директива заставит их связывать ошибки с файлом анализатора, рассматривая его как независимый исходный файл.

%output="имя_файла"

Задаёт имя_файла для файла анализатора.

%pure-parser

Запрашивает чистую (повторно входимую) программу анализатора (см. раздел 4.7.7 Чистый (повторно входимый) анализатор).

%token_table

Создать массив имён лексем в файле анализатора. Имя массива -- yytname, yytname[i] -- имя лексемы с внутренним кодом Bison i. Первые три элемента yytname всегда "$", "error и "$illegal", после них идут символы, определённые в файле грамматики. Для однолитерных и строковых лексем имя в таблице включает одинарные или двойные кавычки: например, "'+'" -- однолитерная константа, а "\"<=\"" -- строковая лексема. Все литеры строковой лексемы точно в том же виде содержатся в строке, находящейся в таблице, даже двойные кавычки не экранируются. Например, Если лексема состоит из трёх литер `*"*', её строка в yytname содержит `"*"*"'. (На C это будет записываться "\"*\"*\""). Когда вы задаёте %token_table, Bison также создаёт макроопределения YYNTOKENS, YYNNTS, YYNRULES, и YYNSTATES:

YYNTOKENS: Самый большой номер лексемы плюс один.
YYNNTS: Число нетерминальных символов.
YYNRULES: Число правил грамматики.
YYNSTATES: Число состояний анализатора (см. раздел 6.5 Состояния анализатора).

%verbose

Создаёт дополнительный выходной файл, содержащий подробные описания состояний анализатора, и какие действия в этом состоянии выполняются при пред-просмотре каждого типа лексем. Этот файл также описывает все конфликты, как разрешаемые приоритетом операций, так и не разрешаемые. Имя файла получается заменой `.tab.c' или `.c' в имени выходного файла анализатора на `.output'. Поэтому, если входной файл называется `foo.y', файл анализатора по умолчанию будет называться `foo.tab.c'. Вследствие этого, подробный выходной файл будет называться `foo.output'.

%yacc

%fixed-output-files

Как будто был задан параметр --yacc, т.е. имитирует Yacc, включая его соглашения об именах. См. раздел 10.1 Параметры Bison.

4.8 Несколько анализаторов в одной программе

Большая часть программ, использующих Bison, разбирает только один язык, и поэтому содержит только один анализатор Bison. Но что делать, если вы хотите одной программой анализировать более одного языка? Тогда вам нужно разрешить конфликты имён между различными определениями yyparse, yylval и т.д.

Простой способ сделать это -- использовать параметр `-p префикс' (см. раздел 10. Вызов Bison). Тогда имена интерфейсных функций и переменных анализатора Bison будут начинаться с префикс, а не с yy. Это можно использовать, чтобы дать всем анализаторам различные не конфликтующие имена.

Точный список переименуемых символов: yyparse, yylex, yyerror, yynerrs, yylval, yychar и yydebug. Например, если вы используете `-p c', эти имена превратятся в cparse, clex и т.д.

Никакие другие переменные и макросы, связанные с Bison, не переименуются. Они не глобальны, и если одни и те же имена будут использоваться в разных анализаторах, конфликта не возникнет. Например, макрос YYSTYPE не будет переименован, но различное его определение в разных анализаторах не вызовет проблем (см. раздел 4.5.1 Типы данных семантических значений).

Параметр `-p' добавляет макроопределения в начало выходного файла анализатора, определяя yyparse как префиксparse и т.д. Это фактически подставляет во всём файле анализатора одно имя вместо другого.

[Содержание] [Назад] [Пред] [Вверх] [След] [Вперед]


	Тут могла бы быть ваша реклама!

Навигация

Вход для пользователей

Кто на сайте

Bison 1.35 - 4. Файлы грамматики Bison