Реферат: Проектирование трансляторов
вается компилятором компиляторов 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 допускает оба вида рекурсивных правил, однако, при ис-
пользовании правил с правой рекурсией об'ем анализатора увеличи-
Страницы: 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
