Реферат: Проектирование трансляторов
принятого в YACC метода разбора и вызовут конфликты.
Однако, если язык, описываемый данной грамматикой, в принци-
пе допускает задание грамматики, однозначной для данного метода
разбора, то YACC позволяет без перестройки грамматики построить
грамматический анализатор, разрешающий конфликты на основе меха-
низма приоритетов.
ВХОДНЫЕ И ВЫХОДНЫЕ ФАЙЛЫ, СТРУКТУРА
ГРАММАТИЧЕСКОГО АНАЛИЗАТОРА
Входная информация для YACC задается в СПЕЦИФИКАЦИОННОМ
ФАЙЛЕ. На выходе компилятора компиляторов в результате обработки
спецификаций создается файл y.tab.c с исходным текстом Сипроце-
дур, составляющих грамматический анализатор. Основной в файле
y.tab.c является процедура yyparse, реализующая алгоритм грамма-
тического разбора. При формировании ее YACC использует файл
/usr/lib/yaccpar, содержащий неизменяемую часть анализатора. Кро-
ме yyparse, в файл y.tab.c YACC включает построенные им таблицы
разбора, описания и программные фрагменты пользовательских специ-
фикаций.
Процедура yyparse представляет собой целочисленную функцию,
возвращающую значение 0 или 1. Значение 0 возвращается в случае
успешного разбора по достижении признака конца файла, значение 1-
в случае несоответствия входного текста заданным спецификациям.
Процедура yyparse содержит многократное обращение к процедуре
лексического анализа yylex, текст которой либо переносится в файл
y.tab.c из спецификационного файла, либо прикомпоновывается впос-
ледствии.
Для организации обращения к процедуре yyparse в библиотеке
YACC существует стандартная процедура main, не содержащая помимо
обращения к yyparse никаких действий. Пользователь может напи-
сать собственную процедуру main, включив в нее как начальные дей-
ствия, предваряющие вызов yyparse (установка нужных режимов, от-
крытие файлов, частичное заполнение таблиц), так и действия по
завершении разбора, которым должен предшествовать анализ возвра-
щаемого yyparse значения; действиями в случае успешного разбора
могут быть закрытие файлов, вывод результатов, вызов следующей
фазы транслятора, в частности, повторный вызов yyparse. Для заме-
ны стандартной процедуры пользовательской программой main она
должна быть описана в спецификационном файле или присоединена на
этапе вызова Си-компилятора для подготовки исполняемой программы.
Кроме выходного файла y.tab.c, YACC может дополнительно гене-
рировать следующие выходные файлы:
y.output содержащий описание состояний анализатора и сообще-
ния о конфликтах;
y.tab.h содержащий описание лексем.
Для генерации этих файлов требуется задание соответствующих
флагов при вызове YACC.
ПРОЦЕДУРА ПОСТРОЕНИЯ ГРАММАТИЧЕСКОГО АНАЛИЗАТОРА
Построение грамматического анализатора осуществляется в два
этапа. На первом этапе файл спецификаций входного языка обрабаты-
вается компилятором компиляторов YACC, для чего задается коман-
дная строка yacc [-vd] yfile. Здесь yfile - имя файла специфика-
ций, а флаги имеют следующий смысл: v - сформировать в файле
y.output подробное описание грамматического анализатора; d -
сформировать в файле y.tab.h описание лексем.
Текстовые файлы y.output и y.tab.h содержат справочную ин-
формацию для пользователя, и никак не используются на втором эта-
пе построения грамматического анализатора. Основной результат ра-
боты YACC - процедура yyparse и грамматические таблицы - поме-
щается в файл y.tab.c. На втором этапе построения грамматическо-
го анализатора для получения в файле a.out исполняемой программы
компилируется файл y.tab.c и присоединяются другие программные
компоненты:
cc y.tab.c [cfile...ofile...lfile...] -ly
где cfile, ofile,lfile - имена исходных, объектных и библио-
течных файлов, содержащих присоединяемые процедуры. В этот спи-
сок не включается имя стандартной библиотеки YACC /lib/liby.a, ее
подключение обеспечивается заданием флага ly. Этот флаг полезно
считать обязательным.
ЗАДАНИЕ ВХОДНОЙ ИНФОРМАЦИИ YACC
Структура спецификационного файла
Пользовательские спецификации, задающие правила организации
входной информации и алгоритм ее обработки, об'единяются в специ-
фикационный файл следующей структуры:
декларации
%%
правила
%%
программы
Ядром спецификационного файла и единственной его обяза-
тельной частью является секция правил. При отсутсивии секции
программ может быть опущена вторая группа "%%"; следовательно,
минимальная допустимая конфигурация входного файла имеет вид:
%%
правила
Пробелы, знаки табуляции и перевода строки игнорируются, не-
допустимо лишь появление их в именах. Комментарий, ограниченный
символами "/*" в начале и "*/" в конце, может находиться между
любыми двумя разделителями в любой секции входного файла.
СЕКЦИЯ ПРАВИЛ состоит из одного или нескольких грамматичес-
ких правил. Эти правила должны определять все допустимые входные
конструкции и связанные с определенными конструкциями действия по
обработке входного потока.
Назначение СЕКЦИИ ДЕКЛАРАЦИИ состоит в основном в задании
информации о лексемах.
СЕКЦИЯ ПРОГРАММ представляет собой некоторый набор процедур
на языке Си, которые должны включаться в текст программы грамма-
тического разбора. Например, это могут быть процедура лексическо-
го анализа yylex и пользовательские процедуры, вызываемые в дей-
ствиях.
СЕКЦИЯ ПРАВИЛ. В данной секции с помощью набора грамматичес-
ких правил должны быть определены все конструкции, из которых
впоследствии будут строиться входные тексты. Не подлежат опреде-
лению в секции правил лишь конструкЦии, выбранные пользователем в
качестве лексем, считающиеся для грамматического анализа исходны-
ми единицами. Правила задаются в форме, близкой БНФ.
Правило, определяющее синтаксический вид конструкции, за-
дается таким образом: <имя нетерминального символа>: определение;
здесь ':' и ';' специальные символы YACC. Правая часть правила -
определение - представляет собой упорядоченную последова-
тельность элементов (нетерминальных символов и лексем), состав-
ляющих описываемую конструкцию. При грамматическом разборе такая
последовательность в результате применения правила заменяется не-
терминальным символом, имя которого указано в левой части. нетер-
минальные символы в определении задаются именами, а лексемы -
именами или литералами. Запись имен и литералов совпадает с за-
писью идентификаторов и символьных констант, принятой в Си.
По виду правила нельзя заключить, относятся эти имена к лек-
семам или нетерминальным символам. YACC считает именами нетерми-
налов все имена, не объявленные в секции деклараций именами лек-
сем. Все нетерминалы должны быть определены, т.е. имя каждого из
них должно появиться в левой части хотя бы одного правила. Допус-
тимо задание нескольких правил, определяющих один нетерминальный
символ, т.е. правил с одинаковой левой частью. Такие правила оп-
ределяют конструкции, идентичные на некотором уровне.
Правила с общей левой частью можно задавать в сокращенной
записи, без повторения левой части, используя для разделения
альтернативных определений символ "|".
При необходимости с любым правилом можно связать действие -
набор операторов языка Си, которые будут выполняться при каждом
распознавании конструкции во входном тексте. Действие не являет-
ся обязательным элементом правил.
Действие заключается в фигурные скобки и помещается вслед за
правой частью правила, т.е. правило с действием имеет вид:
<имя нетерминального символа>: определение {действие};
Точка с запятой после правила с действием может опускаться.
При использовании сокращенной записи правил с общей левой частью
следует иметь в виду, что действие может относиться только к от-
дельному правилу, а не к их совокупности. Следующий пример иллюс-
трирует задание действий в случае правил с общей левой частью.
На операторы, входящие в действия, не накладывается никаких
ограничений. В частности, в действиях могут содержаться вызовы
любых функций. Отдельные операторы могут быть помечены, к ним
возможен переход из других действий.
Существует возможность задания действий, которые будут вы-
полняться по мере распознавания отдельных фрагментов правила.
Действие в этом случае помещается после одного из элементов пра-
вой части так, чтобы положение действия соотвествовало моменту
разбора, в который данному действию будет передано управление.
Для того, чтобы действия имели реальный смысл, они, как пра-
вило, должны использовать некоторые общие переменные,
т.е. переменные, доступные во всех действиях и сохраняющие свои
значения по окончании очередного действия. Такие переменные опи-
сываются в начале секции правил, все описание ограничивается с
двух сторон строками
%{
и %}
Здесь же могут находиться произвольные операторы Си, рас-
сматриваемые как общие действия для всех правил.
Укажем еще на два вида объектов, использующихся в действиях.
Это, во-первых, глобальные переменные, которые описываются в сек-
ции деклараций , и, во-вторых, специальные переменные (псевдопе-
ременные),облегчающие взаимосвязь между действиями и связь их с
лексическим анализатором.Структура входной информации описывает-
ся в наборе правил иерархически, т.е. каждое правило соответ-
ствует определенному уровню структурного разбиения. Однако, пос-
ледовательность задания правил может не отражать этой иерархии и
быть вполне произвольной. Единственно необходимой для YACC яв-
ляется информация о том, какой из нетерминалов задает вершину ие-
рархии, т.е. соотвествует конструкциям, определяющим входной
текст в целом. Этот нетерминал принято называть НАЧАЛЬНЫМ
СИМВОЛОМ. Приведение входного текста к начальному символу являет-
ся целью грамматического анализатора. По умолчанию YACC считает
начальным символом тот нетерминал, имя которого стоит в левой
части первого из правил. Однако, если определять начальный сим-
вол в первом правиле пользователю неудобно, он может явно задать
имя начального символа в секции деклараций.
Существует два специфических вида правил, на которые полез-
но обратить внимание. Во-первых, это пустое правило вида
<имя нетерминального символа>: ;
определяющее пустую последовательность символов. Сочетание
пустого правила с другими правилами, определяющими тот же нетер-
минальный символ, является одним из способов указать на необяза-
тельность вхождения соответствующей конструкции. Например, сово-
купность правил
целое_число:знак целое_без_знака; знак: | '+'|'-';
определяет возможность задания целых чисел со знаком и без
него. Другой способ описать эту возможность состоит в задании
следующей группы правил:
целое_число:знак целое_без_знака | целое_без_знака ; знак:
'+'|'-';
С пустым правилом может быть обычным образом связано дей-
ствие:
ИМЯ: {тело_действия} ;
Во-вторых, правила часто описывают некоторую конструкцию ре-
курсивно, т.е. правая часть может рекурсивно включать определяе-
мый нетерминальный символ. Различают леворекурсивные правила вида:
<имя нетерминала>:<имя нетерминала> <многократно повто-
ряемый фрагмент>;
и праворекурсивные вида
<имя нетерминала>: <многократно повторяемый фрагмент>
<имя нетерминала>;
YACC допускает оба вида рекурсивных правил, однако, при ис-
пользовании правил с правой рекурсией об'ем анализатора увеличи-
вается, а во время разбора возможно переполнение внутреннего сте-
ка анализатора.
Рекурсивные правила необходимы при задании последовательнос-
тей и списков. Следующие примеры иллюстрируют универсальный спо-
соб описания этих конструкций:
последовательность: элемент
| последовательность элемент;
список: элемент | список ',' элемент;
Заметим, что в каждом из этих случаев первое правило (не со-
держащее рекурсии) будет применено только для первого элемента, а
второе (рекурсивное) - для всех последующих. Нетерминальные сим-
волы, связанные с последовательностями или списками разнородных
элементов, могут описываться произвольным числом рекурсивных и
нерекурсивных правил. Например, группа правил
идентификатор: буква |
'$' |
идентификатор буква |
идентификатор цифра |
идентификатор '_' ;
описывает идентификатор как последовательность букв, цифр и
символов "_", начинающуюся с буквы или символа "$". Следует обра-
тить внимание на то, что рекурсивные правила не имеют смысла, ес-
ли для определяемого ими нетерминала не задано ни одного правила
без рекурсии. Для обеспечения возможности задания пустых списков
или последовательностей в качестве нерекурсивного правила ис-
пользуется пустое:
последовательность : | последовательность элемент ;
Сочетание пустых и рекурсивных правил является удобным спо-
собом представления грамматик и ведет к большей их общности, од-
нако,некорректное использование пустых правил может вызывать кон-
фликтные ситуации (раздел 5) из-за неоднозначности выбора нетер-
минала, соответствующего пустой последовательности.
Секция деклараций состоит из последовательности строк двух
видов: строк-директив и строк исходного текста.
Строки исходного текста без изменений копируются в выходной
файл y.tab.c и могут содержать операторы препроцессора и описа-
ние внешних об'ектов. Область действия переменных, описанных в
секции деклараций, распространяется на весь спецификационный
файл, т.е. они доступны как в операторах действий, так и в проце-
дурах, находящихся в секции программ.
Строки-директивы начинаются символом "%" (этот символ в YACC
играет роль своего рода esc-символа). Две специальные директивы
%{ и %} ограничивают с двух сторон группы строк исходного текста.
Остальные директивы служат для задания дополнительной информации
о грамматике.
ДЕКЛАРАЦИЯ ИМЕН ЛЕКСЕМ
%token <список имен лексем>
Пользователь при описании грамматики решает, какие конструк-
ции целесообразнее непосредственно выделять из входного текста на
этапе лексического анализа, и на уровне этих конструкций (лексем)
задает грамматические правила. Все виды лексем, кроме литералов,
обозначаются некоторыми именами и под этими именами фигурируют в
секции правил. Благодаря декларации имен лексем в директиве
%token YACC отличает имена лексем от имен нетерминальных симво-
лов. Однако, декларация ни в коей мере не обеспечивает распозна-
вания лексем, и пользователю рекомендуется считать для себя ди-
рективу %token напоминанием о необходимости построения лексичес-
кого анализатора и руководствоваться этой директивой при его на-
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23
