семам или нетерминальным символам. YACC считает именами нетерми-
налов все имена, не объявленные в секции деклараций именами лек-
сем. Все нетерминалы должны быть определены, т.е. имя каждого из
них должно появиться в левой части хотя бы одного правила. Допус-
тимо задание нескольких правил, определяющих один нетерминальный
символ, т.е. правил с одинаковой левой частью. Такие правила оп-
ределяют конструкции, идентичные на некотором уровне.
Правила с общей левой частью можно задавать в сокращенной
записи, без повторения левой части, используя для разделения
альтернативных определений символ "|".
При необходимости с любым правилом можно связать действие -
набор операторов языка Си, которые будут выполняться при каждом
распознавании конструкции во входном тексте. Действие не являет-
ся обязательным элементом правил.
Действие заключается в фигурные скобки и помещается вслед за
правой частью правила, т.е. правило с действием имеет вид:
<имя нетерминального символа>: определение {действие};
Точка с запятой после правила с действием может опускаться.
При использовании сокращенной записи правил с общей левой частью
следует иметь в виду, что действие может относиться только к от-
дельному правилу, а не к их совокупности. Следующий пример иллюс-
трирует задание действий в случае правил с общей левой частью.
На операторы, входящие в действия, не накладывается никаких
ограничений. В частности, в действиях могут содержаться вызовы
любых функций. Отдельные операторы могут быть помечены, к ним
возможен переход из других действий.
Существует возможность задания действий, которые будут вы-
полняться по мере распознавания отдельных фрагментов правила.
Действие в этом случае помещается после одного из элементов пра-
вой части так, чтобы положение действия соотвествовало моменту
разбора, в который данному действию будет передано управление.
Для того, чтобы действия имели реальный смысл, они, как пра-
вило, должны использовать некоторые общие переменные,
т.е. переменные, доступные во всех действиях и сохраняющие свои
значения по окончании очередного действия. Такие переменные опи-
сываются в начале секции правил, все описание ограничивается с
двух сторон строками
%{
и %}
Здесь же могут находиться произвольные операторы Си, рас-
сматриваемые как общие действия для всех правил.
Укажем еще на два вида объектов, использующихся в действиях.
Это, во-первых, глобальные переменные, которые описываются в сек-
ции деклараций , и, во-вторых, специальные переменные (псевдопе-
ременные),облегчающие взаимосвязь между действиями и связь их с
лексическим анализатором.Структура входной информации описывает-
ся в наборе правил иерархически, т.е. каждое правило соответ-
ствует определенному уровню структурного разбиения. Однако, пос-
ледовательность задания правил может не отражать этой иерархии и
быть вполне произвольной. Единственно необходимой для YACC яв-
ляется информация о том, какой из нетерминалов задает вершину ие-
рархии, т.е. соотвествует конструкциям, определяющим входной
текст в целом. Этот нетерминал принято называть НАЧАЛЬНЫМ
СИМВОЛОМ. Приведение входного текста к начальному символу являет-
ся целью грамматического анализатора. По умолчанию YACC считает
начальным символом тот нетерминал, имя которого стоит в левой
части первого из правил. Однако, если определять начальный сим-
вол в первом правиле пользователю неудобно, он может явно задать
имя начального символа в секции деклараций.
Существует два специфических вида правил, на которые полез-
но обратить внимание. Во-первых, это пустое правило вида
<имя нетерминального символа>: ;
определяющее пустую последовательность символов. Сочетание
пустого правила с другими правилами, определяющими тот же нетер-
минальный символ, является одним из способов указать на необяза-
тельность вхождения соответствующей конструкции. Например, сово-
купность правил
целое_число:знак целое_без_знака; знак: | '+'|'-';
определяет возможность задания целых чисел со знаком и без
него. Другой способ описать эту возможность состоит в задании
следующей группы правил:
целое_число:знак целое_без_знака | целое_без_знака ; знак:
'+'|'-';
С пустым правилом может быть обычным образом связано дей-
ствие:
ИМЯ: {тело_действия} ;
Во-вторых, правила часто описывают некоторую конструкцию ре-
курсивно, т.е. правая часть может рекурсивно включать определяе-
мый нетерминальный символ. Различают леворекурсивные правила вида:
<имя нетерминала>:<имя нетерминала> <многократно повто-
ряемый фрагмент>;
и праворекурсивные вида
<имя нетерминала>: <многократно повторяемый фрагмент>
<имя нетерминала>;
YACC допускает оба вида рекурсивных правил, однако, при ис-
пользовании правил с правой рекурсией об'ем анализатора увеличи-
вается, а во время разбора возможно переполнение внутреннего сте-
ка анализатора.
Рекурсивные правила необходимы при задании последовательнос-
тей и списков. Следующие примеры иллюстрируют универсальный спо-
соб описания этих конструкций:
последовательность: элемент
| последовательность элемент;
список: элемент | список ',' элемент;
Заметим, что в каждом из этих случаев первое правило (не со-
держащее рекурсии) будет применено только для первого элемента, а
второе (рекурсивное) - для всех последующих. Нетерминальные сим-
волы, связанные с последовательностями или списками разнородных
элементов, могут описываться произвольным числом рекурсивных и
нерекурсивных правил. Например, группа правил
идентификатор: буква |
'$' |
идентификатор буква |
идентификатор цифра |
идентификатор '_' ;
описывает идентификатор как последовательность букв, цифр и
символов "_", начинающуюся с буквы или символа "$". Следует обра-
тить внимание на то, что рекурсивные правила не имеют смысла, ес-
ли для определяемого ими нетерминала не задано ни одного правила
без рекурсии. Для обеспечения возможности задания пустых списков
или последовательностей в качестве нерекурсивного правила ис-
пользуется пустое:
последовательность : | последовательность элемент ;
Сочетание пустых и рекурсивных правил является удобным спо-
собом представления грамматик и ведет к большей их общности, од-
нако,некорректное использование пустых правил может вызывать кон-
фликтные ситуации (раздел 5) из-за неоднозначности выбора нетер-
минала, соответствующего пустой последовательности.
Секция деклараций состоит из последовательности строк двух
видов: строк-директив и строк исходного текста.
Строки исходного текста без изменений копируются в выходной
файл y.tab.c и могут содержать операторы препроцессора и описа-
ние внешних об'ектов. Область действия переменных, описанных в
секции деклараций, распространяется на весь спецификационный
файл, т.е. они доступны как в операторах действий, так и в проце-
дурах, находящихся в секции программ.
Строки-директивы начинаются символом "%" (этот символ в YACC
играет роль своего рода esc-символа). Две специальные директивы
%{ и %} ограничивают с двух сторон группы строк исходного текста.
Остальные директивы служат для задания дополнительной информации
о грамматике.
ДЕКЛАРАЦИЯ ИМЕН ЛЕКСЕМ
%token <список имен лексем>
Пользователь при описании грамматики решает, какие конструк-
ции целесообразнее непосредственно выделять из входного текста на
этапе лексического анализа, и на уровне этих конструкций (лексем)
задает грамматические правила. Все виды лексем, кроме литералов,
обозначаются некоторыми именами и под этими именами фигурируют в
секции правил. Благодаря декларации имен лексем в директиве
%token YACC отличает имена лексем от имен нетерминальных симво-
лов. Однако, декларация ни в коей мере не обеспечивает распозна-
вания лексем, и пользователю рекомендуется считать для себя ди-
рективу %token напоминанием о необходимости построения лексичес-
кого анализатора и руководствоваться этой директивой при его на-
писании.
Заметим, что ключевые слова описываемого входного языка час-
то бывает удобно считать лексемами. Имена лексем могут совпадать
с этими ключевыми словами, недопустимым является лишь совпадение
имен лексем с зарезервированными словами языка Си.
ДЕКЛАРАЦИЯ ПРИОРИТЕТОВ И АССОЦИАТИВНОСТИ ЛЕКСЕМ
%left <список лексем>
%right <список лексем>
%nonassos <список лексем>
Лексемы в данных директивах задаются литералами или именами.
В последнем случае декларация приоритета заменяет также деклара-
цию имени лексемы, хотя в целях обеспечения наглядности описания
является желательным присутствие в списке директивы %token всего
набора имен лексем.
Использование лексемы само по себе не требует задания ее
приоритета или ассоциативности.
При вызове YACC с флагом -d последовательность операторов
#define помещается также в информационный файл y.tab.h.
Переопределив при необходимости ряд номеров типов лек-
сем,пользователь должен проверить уникальность номеров у всех ис-
пользуемых лексем.
ДЕКЛАРАЦИЯ ИМЕНИ НАЧАЛЬНОГО СИМВОЛА
%start <имя начального символа>
Директива отменяет действующий по умолчанию выбор в качес-
тве начального символа нетериминала, определяемого первым грамма-
тическим правилом.
Секция программ-процедуры, которые должны быть включены в
генерируемую программу грамматического анализа. Любая из опреде-
ляемых пользователем программных компонент может находиться в