Реферат: Проектирование трансляторов
вается, а во время разбора возможно переполнение внутреннего сте-
ка анализатора.
Рекурсивные правила необходимы при задании последовательнос-
тей и списков. Следующие примеры иллюстрируют универсальный спо-
соб описания этих конструкций:
последовательность: элемент
| последовательность элемент;
список: элемент | список ',' элемент;
Заметим, что в каждом из этих случаев первое правило (не со-
держащее рекурсии) будет применено только для первого элемента, а
второе (рекурсивное) - для всех последующих. Нетерминальные сим-
волы, связанные с последовательностями или списками разнородных
элементов, могут описываться произвольным числом рекурсивных и
нерекурсивных правил. Например, группа правил
идентификатор: буква |
'$' |
идентификатор буква |
идентификатор цифра |
идентификатор '_' ;
описывает идентификатор как последовательность букв, цифр и
символов "_", начинающуюся с буквы или символа "$". Следует обра-
тить внимание на то, что рекурсивные правила не имеют смысла, ес-
ли для определяемого ими нетерминала не задано ни одного правила
без рекурсии. Для обеспечения возможности задания пустых списков
или последовательностей в качестве нерекурсивного правила ис-
пользуется пустое:
последовательность : | последовательность элемент ;
Сочетание пустых и рекурсивных правил является удобным спо-
собом представления грамматик и ведет к большей их общности, од-
нако,некорректное использование пустых правил может вызывать кон-
фликтные ситуации (раздел 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 <stdio.h>
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}
и в точке, где вставлено действие, при разборе осуществляет-
ся свертка по пустому правилу, сопровождающаяся выполнением ука-
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40
