46023 (665330), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

ределяют конструкции, идентичные на некотором уровне.

Правила с общей левой частью можно задавать в сокращенной

записи, без повторения левой части, используя для разделения

альтернативных определений символ "|".

При необходимости с любым правилом можно связать действие -

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

распознавании конструкции во входном тексте. Действие не являет-

ся обязательным элементом правил.

Действие заключается в фигурные скобки и помещается вслед за

правой частью правила, т.е. правило с действием имеет вид:

: определение {действие};

Точка с запятой после правила с действием может опускаться.

При использовании сокращенной записи правил с общей левой частью

следует иметь в виду, что действие может относиться только к от-

дельному правилу, а не к их совокупности. Следующий пример иллюс-

трирует задание действий в случае правил с общей левой частью.

На операторы, входящие в действия, не накладывается никаких

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

любых функций. Отдельные операторы могут быть помечены, к ним

возможен переход из других действий.

Существует возможность задания действий, которые будут вы-

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

Действие в этом случае помещается после одного из элементов пра-

вой части так, чтобы положение действия соотвествовало моменту

разбора, в который данному действию будет передано управление.

Для того, чтобы действия имели реальный смысл, они, как пра-

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

т.е. переменные, доступные во всех действиях и сохраняющие свои

значения по окончании очередного действия. Такие переменные опи-

сываются в начале секции правил, все описание ограничивается с

двух сторон строками

%{

и %}

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

сматриваемые как общие действия для всех правил.

Укажем еще на два вида объектов, использующихся в действиях.

Это, во-первых, глобальные переменные, которые описываются в сек-

ции деклараций , и, во-вторых, специальные переменные (псевдопе-

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

лексическим анализатором.Структура входной информации описывает-

ся в наборе правил иерархически, т.е. каждое правило соответ-

ствует определенному уровню структурного разбиения. Однако, пос-

ледовательность задания правил может не отражать этой иерархии и

быть вполне произвольной. Единственно необходимой для YACC яв-

ляется информация о том, какой из нетерминалов задает вершину ие-

рархии, т.е. соотвествует конструкциям, определяющим входной

текст в целом. Этот нетерминал принято называть НАЧАЛЬНЫМ

СИМВОЛОМ. Приведение входного текста к начальному символу являет-

ся целью грамматического анализатора. По умолчанию YACC считает

начальным символом тот нетерминал, имя которого стоит в левой

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

вол в первом правиле пользователю неудобно, он может явно задать

имя начального символа в секции деклараций.

Существует два специфических вида правил, на которые полез-

но обратить внимание. Во-первых, это пустое правило вида

: ;

определяющее пустую последовательность символов. Сочетание

пустого правила с другими правилами, определяющими тот же нетер-

минальный символ, является одним из способов указать на необяза-

тельность вхождения соответствующей конструкции. Например, сово-

купность правил

целое_число:знак целое_без_знака; знак: | '+'|'-';

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

него. Другой способ описать эту возможность состоит в задании

следующей группы правил:

целое_число:знак целое_без_знака | целое_без_знака ; знак:

'+'|'-';

С пустым правилом может быть обычным образом связано дей-

ствие:

ИМЯ: {тело_действия} ;

Во-вторых, правила часто описывают некоторую конструкцию ре-

курсивно, т.е. правая часть может рекурсивно включать определяе-

мый нетерминальный символ. Различают леворекурсивные правила вида:

: <многократно повто-

ряемый фрагмент>;

и праворекурсивные вида

:

;

YACC допускает оба вида рекурсивных правил, однако, при ис-

пользовании правил с правой рекурсией об'ем анализатора увеличи-

вается, а во время разбора возможно переполнение внутреннего сте-

ка анализатора.

Рекурсивные правила необходимы при задании последовательнос-

тей и списков. Следующие примеры иллюстрируют универсальный спо-

соб описания этих конструкций:

последовательность: элемент

| последовательность элемент;

список: элемент | список ',' элемент;

Заметим, что в каждом из этих случаев первое правило (не со-

держащее рекурсии) будет применено только для первого элемента, а

второе (рекурсивное) - для всех последующих. Нетерминальные сим-

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

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

нерекурсивных правил. Например, группа правил

идентификатор: буква |

'$' |

идентификатор буква |

идентификатор цифра |

идентификатор '_' ;

описывает идентификатор как последовательность букв, цифр и

символов "_", начинающуюся с буквы или символа "$". Следует обра-

тить внимание на то, что рекурсивные правила не имеют смысла, ес-

ли для определяемого ими нетерминала не задано ни одного правила

без рекурсии. Для обеспечения возможности задания пустых списков

или последовательностей в качестве нерекурсивного правила ис-

пользуется пустое:

последовательность : | последовательность элемент ;

Сочетание пустых и рекурсивных правил является удобным спо-

собом представления грамматик и ведет к большей их общности, од-

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

фликтные ситуации (раздел 5) из-за неоднозначности выбора нетер-

минала, соответствующего пустой последовательности.

Секция деклараций состоит из последовательности строк двух

видов: строк-директив и строк исходного текста.

Строки исходного текста без изменений копируются в выходной

файл y.tab.c и могут содержать операторы препроцессора и описа-

ние внешних об'ектов. Область действия переменных, описанных в

секции деклараций, распространяется на весь спецификационный

файл, т.е. они доступны как в операторах действий, так и в проце-

дурах, находящихся в секции программ.

Строки-директивы начинаются символом "%" (этот символ в YACC

играет роль своего рода esc-символа). Две специальные директивы

%{ и %} ограничивают с двух сторон группы строк исходного текста.

Остальные директивы служат для задания дополнительной информации

о грамматике.

ДЕКЛАРАЦИЯ ИМЕН ЛЕКСЕМ

%token

Пользователь при описании грамматики решает, какие конструк-

ции целесообразнее непосредственно выделять из входного текста на

этапе лексического анализа, и на уровне этих конструкций (лексем)

задает грамматические правила. Все виды лексем, кроме литералов,

обозначаются некоторыми именами и под этими именами фигурируют в

секции правил. Благодаря декларации имен лексем в директиве

%token YACC отличает имена лексем от имен нетерминальных симво-

лов. Однако, декларация ни в коей мере не обеспечивает распозна-

вания лексем, и пользователю рекомендуется считать для себя ди-

рективу %token напоминанием о необходимости построения лексичес-

кого анализатора и руководствоваться этой директивой при его на-

писании.

Заметим, что ключевые слова описываемого входного языка час-

то бывает удобно считать лексемами. Имена лексем могут совпадать

с этими ключевыми словами, недопустимым является лишь совпадение

имен лексем с зарезервированными словами языка Си.

ДЕКЛАРАЦИЯ ПРИОРИТЕТОВ И АССОЦИАТИВНОСТИ ЛЕКСЕМ

%left

%right

%nonassos

Лексемы в данных директивах задаются литералами или именами.

В последнем случае декларация приоритета заменяет также деклара-

цию имени лексемы, хотя в целях обеспечения наглядности описания

является желательным присутствие в списке директивы %token всего

набора имен лексем.

Использование лексемы само по себе не требует задания ее

приоритета или ассоциативности.

При вызове YACC с флагом -d последовательность операторов

#define помещается также в информационный файл y.tab.h.

Переопределив при необходимости ряд номеров типов лек-

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

пользуемых лексем.

ДЕКЛАРАЦИЯ ИМЕНИ НАЧАЛЬНОГО СИМВОЛА

%start

Директива отменяет действующий по умолчанию выбор в качес-

тве начального символа нетериминала, определяемого первым грамма-

тическим правилом.

Секция программ-процедуры, которые должны быть включены в

генерируемую программу грамматического анализа. Любая из опреде-

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

секции программ спецификационного файла, либо присоединяться на

этапе вызова Си-компилятора для трансляции файла y.tab.c и компо-

новки выходной программы. Перечислим процедуры, которые одним из

этих способов должны быть заданы:

- лексический анализатор - функция с именем yylex();

- все процедуры, вызовы которых содержатся в действиях, свя-

занных с грамматическими правилами;

- главная процедура main() при необходимости заменить ее

стандартный библиотечный вариант, который имеет вид:

main() { return (yyparse(); }

- процедура обработки ошибок yyerror() - также для замены

библиотечного варианта (его текст приводится ниже).

#include

yyerror(s)char *s; { fprintf(stderr, "%s0, s);}

Для обеспечения корректной работы грамматического анализато-

ра функция лексического анализа yylex должна быть согласована с

конкретной спецификацией грамматики и удовлетворять определенным

требованиям. Основная задача функции yylex состоит во вводе из

входного потока ряда очередных символов до выявления конструкции,

соответствующей одной из лексем, и возвращении номера типа этой

лексемы. Для нелитеральных лексем номером типа может служить

об'явленное в секции деклараций имя лексемы (с помощью механизма

#define YACC обеспечивает замену его нужным номером), в случае

литералов номером типа является числовое значение символа (если

оно не было переопределено). Алгоритм поиска должен заключаться в

попытке нахождения сначала более сложных (нелитеральных) лексем и

лишь при несовпадении ни с одной из них текущих элементов ввода

возвращать номер типа литеральной лексемы (любой однозначный сим-

вол, не начинающий ни одну из возможных лексем, сам образует лек-

сему).

Действия с использованием псевдопеременных.Для обеспечения

связи между действиями, а также между действиями и лексическим

анализатором создаваемые YACC грамматические анализаторы поддер-

живают специальный стек, в котором сохраняются значения лексем и

нетерминальных символов. Значение лексемы автоматически попадает

в стек после ее распознавания лексическим анализатором (напомним,

что им считается текущее значение переменной yylval). После каж-

дой свертки вычисляется значение нетерминала, заместившего свер-

нутую строку, и помещается в вершину стека; значения элементов

правой части примененного правила перед этим выталкиваются из

стека. Заметим, что таким образом к моменту свертки любого прави-

ла все значения нетериналов в правой части оказываются вычислен-

ными в результате сверток. Способ вычисления значения нетермина-

ла будет рассмотрен ниже.

Описанный механизм не требует вмешательства пользователя и

предоставляет ему следующие возможности:

- Использовать в действиях, осуществляемых после свертки по

правилу, значение любого элемента его правой части. Доступ к этим

значениям обеспечивается набором так называемых ПСЕВДОПЕРЕМЕННЫХ

с именами $1,$2,..., где $i соответствует значению i-го элемента;

элементы правой части правила нумеруются слева направо без разли-

чия лексем и нетерминальных символов;

- Формировать в действиях значение, образованного в ре-

зультате свертки нетерминала путем присвоения этого значения

псевдопеременной с именем $$. Eсли в действии не определяется

значение переменной $$ (а также если действие отсутствует), зна-

чением нетерминала после свертки по умолчанию становится значе-

ние первого элемента правой части, т.е. неявно выполняется прис-

ваивание.

Несколько иная ситуация в отношении использования псевдопе-

ременных имеет место для правил, содержащих действия внутри пра-

вой части. На самом деле YACC интерпретирует правило вида

A: B C {действие 1} D {действие 2} K

как

A: B C EMPTY1 D EMPTY2 K;

EMPTY1: {действие 1}

EMPTY2: {действие 2}

и в точке, где вставлено действие, при разборе осуществляет-

Характеристики

Список файлов реферата