[содержание] [назад] [пред] [вверх] [след] [вперед] 4. файлы грамматики bisonbison принимает на вход спецификацию контекстно-свободной грамматики и создаёт функцию на языке c, которая распознаёт правильные предложения этой грамматики. имя входного файла грамматики bison по соглашению заканчивается на `.y'. см. раздел 10. вызов bison. 4.1 структура грамматики bisonфайл грамматики bison содержит четыре основные секции, показанные здесь с соответствующими разделителями.
%{
объявления c
%}
объявления bison
%%
правила грамматики
%%
дополнительный код на c
комментарии, заключённые в `/* ... */', могут появляться в любой секции. 4.1.1 секция объявлений c
секция объявлений c содержит макроопределения и объявления функций и
переменных, используемых в действиях правил грамматики. они копируются в
начало файла анализатора так, чтобы они предшествовали определению
4.1.2 секция объявлений bisonсекция объявлений bison содержит объявления, определяющие терминальные и нетерминальные символы, задающие приоритет и т.д. в некоторых простых грамматиках вам могут быть не нужны никакие объявления. см. раздел 4.7 объявления bison. 4.1.3 секция правил грамматикисекция правил грамматики содержит одно или более правил грамматики bison и ничего более. см. раздел 4.3 синтаксис правил грамматики. должно быть по меньшей мере одно правило грамматики, и первый ограничитель `%%' (предшествующий правилам грамматики) не может быть опущен, даже если это первая строка файла. 4.1.4 секция дополнительного кода на c
секция дополнительного кода на c в точности копируется в конец
файла анализатора, точно так же, как секция объявлений c в начало.
это наиболее удобное место, чтобы поместить что-либо, что вы хотите иметь
в файле анализатора, но что не нужно помещать перед определением
если последняя секция пуста, вы можете опустить `%%', отделяющее её от правил грамматики. сам анализатор bison содержит множество статических переменных с именами, начинающимися с `yy', и макросов с именами, начинающимися с `yy'. не использовать такие имена, за исключением описанных в этом руководстве, в секции дополнительного кода c файла грамматики -- хорошая идея. 4.2 символы, терминальные и нетерминальныесимволы в грамматиках bison представялют грамматическую классификацию языка.
терминальный символ (также известный как тип лексемы) представляет
класс синтаксически эквивалентных лексем. вы используете такой символ в
правилах грамматики, чтобы обозначить, что допустима лексема этого класса.
в анализаторе bison символ представляется числовым кодом, и функция
нетерминальный символ обозначает класс синтаксически эквивалентных групп. имя символа используется при написании правил грамматики. по соглашению оно должно быть записано в нижнем регистре. имена символов могут содержать буквы, цифры (но не начинаться с цифры), знаки подчёркивания и точки. точки имеют значение только в нетерминалах. есть три способа записи терминальных символов в грамматике:
выбранный вами способ записи терминального символа не влияет на его грамматический смысл. оно зависит только от того, где он встречается в правилах, и когда функция анализатора его возвращает.
значение, возвращаемое
если
символ 4.3 синтаксис правил грамматикиправило грамматики bison имеет следующий общий вид:
результат: компоненты...
;
где результат -- это описываемый правилом нетерминальный символ, а компоненты -- различные терминальные и нетерминальные символы, объединяемые этим правилом (см. раздел 4.2 символы, терминальные и нетерминальные). например:
exp: exp '+' exp
;
говорит о том, что две группы типа пробельные литеры в правилах только разделяют символы. вы можете по своему усмотрению вставлять дополнительные промежутки. между компонентами могут быть разбросаны действия, определяющие семантику правила. действие выглядит так:
{операторы c}
обычно в правиле только одно действие, и оно следует после всех компонентов. см. раздел 4.5.3 действия. для одного результата можно написать несколько правил, отдельно или же соединённых литерой вертикальной черты `|' как здесь:
результат: компоненты первого правила...
| компоненты второго правила...
...
;
в любом случае правила рассматриваются как различные, даже если они таким образом объединены.
есть в правиле нет компонентов, это означает, что результат может
соответствовать пустой строке. например, вот как определяется
последовательность нуля или более групп
expseq: /* пусто */
| expseq1
;
expseq1: exp
| expseq1 ',' exp
;
традиционно в каждом правиле, не содержащем компонентов, пишется комментарий `/* пусто */'. 4.4 рекурсивные правилаправило называется рекурсивным, если нетерминал его результата появляется также в его правой части. почти все грамматики bison должны использовать рекурсию, потому что это единственный способ определить последовательность из произвольного числа элементов. рассмотрим рекурсивное определение последовательности одного или более выражений, разделённых запятыми:
expseq1: exp
| expseq1 ',' exp
;
поскольку рекурсивный символ
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 использует для всех семантических значений тип #define yystype double это макроопределение должно находиться в секции объявлений c файла грамматики (см. раздел 4.1 структура грамматики bison). 4.5.2 несколько типов значений
в большинстве программ вам будут нужны разные типы данных для разных видов
лексем и групп. например, числовой константе может быть нужен тип чтобы в анализаторе можно было использовать несколько типов семантических значений, bison требует сделать две вещи:
4.5.3 действиядействие сопровождает синтаксическое правило и содержит код на c, который должен выполняться при каждом распознавании текста, соответствующего этому правилу. задачей большинства действий является вычисление семантического значения группы, собираемой правилом, исходя из семантических значений, сопоставленных лексемам или меньшим группам. действие состоит из операторов c, окружённых фигурными скобками, как составной оператор c. оно может быть помещено в любой точке правила, и выполняется в этой точке. большинство правил имеют только одно действие в конце правила, после всех компонентов. действия внутри правила непросты, и используются только в специальных целях (см. раздел 4.5.5 действия внутри правил).
код на c действия может ссылаться на семантические значения компонентов,
связываемых правилом с помощью конструкции вот типичный пример:
exp: ...
| exp '+' exp
{ $$ = $1 + $3; }
это правило собирает
если вы не задаёте действие для правила, bison применяет действие по умолчанию:
foo: expr bar '+' expr { ... }
| expr bar '-' expr { ... }
;
bar: /* пусто */
*/
{ previous_expr = $0; }
;
пока 4.5.4 типы данных значений в действиях
если вы выбрали единственный тип данных семантических значений, конструкции
если вы используете
exp: ...
| exp '+' exp
{ $$ = $1 + $3; }
вместо этого вы можете указывать тип данных, когда вы ссылаетесь на значение, вставляя `<тип>' после `$' в начале ссылки. например, если вы определите типы так:
%union {
int itype;
double dtype;
}
вы можете написать 4.5.5 действия внутри правилвремя от времени полезно помещать действия внутрь правила. эти действия записываются точно так же, как обычные действия в конце правил, но выполняются до того, как анализатор распознает следующие компоненты.
действие внутри правила может с помощью
действие внутри правила само по себе считается одним из компонентов правила.
это имеет значение, если позднее в том же правиле присутствует ещё одно
действие (и, обычно, ещё одно в конце правила): вы должны при вычислении
n в конструкции
действие внутри правила также имеет семантическое значение. действие может
установить его значение присваиванием
установить значение всего правила действием внутри правила невозможно,
поскольку присваивание
приведём пример гипотетического компилятора, обрабатывающего оператор
stmt: let '(' var ')'
{ $<context>$ = push_context ();
declare_variable ($3); }
stmt { $$ = $6;
pop_context ($<context>5); }
как только распознано `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 может выполнить действие в правиле для 4.6 отслеживание положенийхотя правил грамматики и семантических действий и достаточно, чтобы написать полностью функциональный анализатор, может быть полезно обрабатывать некоторую дополнительную информацию, особенно положение символов. способ обработки положений определяется указанием типа данных и действия, которые должны выполняться при разборе правил. 4.6.1 тип данных положенийопределение типа данных для положений гораздо проще, чем для семантических значений, поскольку все лексемы и группы всегда используют один и тот же тип.
тип положений задаётся определением макроса
struct
{
int first_line;
int first_column;
int last_line;
int last_column;
}
4.6.2 действия и положениядействия полезны не только для определения семантики языка, но и для описания поведения анализатора, касающегося положений.
наиболее очевидный способ получения положения синтаксической группы очень
похож на способ вычисления семантических значений. для получения доступа в
конкретном правиле к связываемым элементам может использоваться несколько
конструкций. положение 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 действие по умолчанию для положений
на самом деле действия -- не лучшее место для вычисления положений. поскольку
положения гораздо более общи, чем семантические значения, в анализаторе есть
место, где можно переопределить действие по умолчанию для каждого правила.
макрос в большинстве случаев этого макроса, в общем, достаточно, чтобы избавиться от специального кода в семантических действиях.
макрос по умолчанию он определён следующим образом: #define yylloc_default(current, rhs, n) \ current.last_line = rhs[n].last_line; \ current.last_column = rhs[n].last_column;
при определении
4.7 объявления bisonсекция объявлений bison грамматики bison определяет символы, используемые при формулировке грамматики и типы данных семантических значений. см. раздел 4.2 символы, терминальные и нетерминальные.
все имена типов лексем (но не однолитерные лексемы, такие как по умолчанию первое правило файла также задаёт начальный символ. если вы хотите, чтобы начальным символом был какой-то другой, вы должны объявить его явно (см. раздел 2.1 языки и контекстно-свободные грамматики). 4.7.1 имена типов лексемосновной способ объявления имени типа лексемы (терминального символа) следующий: %token имя
в анализаторе bison превратит это в директиву
если вы хотите задать ассоциативность и приоритет, вместо вы можете явно задать числовой код типа лексемы, добавив целочисленное значение непосредственно после имени лексемы: %token num 300 тем не менее, в общем случае лучше позволить bison определить числовые коды для всех типов лексем самому. bison автоматически выберет коды, не конфликтующие друг с другом и с литерами ascii.
в случае, если тип значения -- объединение, вы дожны включить в например:
%union { /* определение набора типов */
double val;
symrec *tptr;
}
%token <val> num /* определение лексемы num и её типа */
вы можете связать строковую лексему с именем типа лексемы, записав строку
в конце объявления %token arrow "=>" например, грамматика языка c может задавать такие имена и соответствующие строковые лексемы: %token <operator> or "||" %token <operator> le 134 "<=" %left or "<="
после того, как вы сопоставили друг с другом строку и тип лексемы, они
становятся взаимозаменяемы в дальнейших объявлениях или правилах грамматики.
функция 4.7.2 приоритет операций
для одновременного объявления лексемы и задания её приоритета и ассоциативности
используйте объявления
синтаксис объявления приоритета тот же, что и %left символы... или %left <тип> символы...
в самом деле, любое из этих определений служит тем же целям, что и
4.7.3 набор типов значений
объявление например:
%union {
double val;
symrec *tptr;
}
это объявление говорит о том, что есть два альтернативных типа:
имейте в виду, что, в отличие от объявления 4.7.4 нетерминальные символы
если вы используете %type <тип> нетерминал...
здесь нетерминал -- имя нетерминального символа, а тип -- имя,
данное в
вы можете также объявить тип значения терминального символа. для этого
используйте ту же конструкцию 4.7.5 подавление сообщений о конфликтах
в норме bison сообщает, если в грамматике есть какие-либо конфликты
(см. раздел 6.2 конфликты сдвиг/свёртка), но большинство реальных
грамматик содержат безвредные конфликты сдвиг/свёртка, разрешаемые
предсказуемым образом, и которые сложно исключить. желательно подавить
сообщения об этих конфликтах, пока их число не изменяется. вы можете сделать
это объявлением это объявление выглядит так: %expect n здесь n -- десятичное целое число. это объявление говорит, что не нужно выдавать предупреждений, если грамматика содержит n конфликтов сдвиг/свёртка и не содержит конфликтов свёртка/свёртка. если конфликтов меньше или больше, или если есть конфликты свёртка/свёртка, вместо обычного предупреждения выдаётся сообщение об ошибке.
в общем случае использование
теперь bison перестанет раздражать вас сообщениями о проверенных вами конфликтах, но вновь начнёт выдавать сообщения, если изменения в грамматике повлекут появление новых конфликтов. 4.7.6 начальный символ
по умолчанию bison полагает начальным символом грамматики первый нетерминал,
заданный в секции определения грамматики. программист может переопределить
его объявлением %start символ 4.7.7 чистый (повторно входимый) анализаторповторно входимая программа -- это программа, которая не меняется в процессе выполнения. другими словами, она полностью состоит из чистого кода (кода только для чтения). повторная входимость важна всегда, когда возможно асинхронное выполнение, например, не повторно входимая программа может быть ненадёжной при вызове её из обработчика сигнала. в системах с несколькими потоками управления, не повторно входимая программа может быть вызвана только внутри критического участка.
в норме bison генерирует не повторно входимый анализатор. это подходит
в большинстве случаев, и даёт совместимость с yacc (стандартные интерфейсы
yacc не повторно входимы по своей природе, потому что они используют
для взаимодействия с
в качестве альтернативы вы можете создать чистый, повторно входимый анализатор.
объявление bison %pure_parser
в результате переменные взаимодействия будет ли анализатор чистым, никак не влияет на правила грамматики. вы можете создать как чистый, так и не повторно входимый анализатор из любой правильной грамматики. 4.7.8 обзор объявлений bisonздесь приведено краткое изложение используемых при определении грамматики объявлений:
для изменения поведения
4.8 несколько анализаторов в одной программе
большая часть программ, использующих bison, разбирает только один язык, и
поэтому содержит только один анализатор bison. но что делать, если вы хотите
одной программой анализировать более одного языка? тогда вам нужно разрешить
конфликты имён между различными определениями
простой способ сделать это -- использовать параметр `-p префикс'
(см. раздел 10. вызов bison). тогда имена интерфейсных функций и переменных
анализатора bison будут начинаться с префикс, а не с
точный список переименуемых символов:
никакие другие переменные и макросы, связанные с bison, не
переименуются. они не глобальны, и если одни и те же имена будут
использоваться в разных анализаторах, конфликта не возникнет. например,
макрос
параметр `-p' добавляет макроопределения в начало выходного файла
анализатора, определяя [содержание] [назад] [пред] [вверх] [след] [вперед] |