Проектирование трансляторов
}
}
ЛЕКЦИЯ 10
КРАТКИЕ СВЕДЕНИЯ О ГЕНЕРАТОРЕ СИНТАКСИЧЕСКИХ
АНАЛИЗАТОРОВ YACC
Значительная часть создаваемых программ, рассчитанных на оп-
ределенную структуру входной информации, явно или неявно вклю-
чает в себя некоторую процедуру синтаксического анализа. В зада-
чах, где пользователю при задании входной информации предостав-
ляется относительная свобода (в отношении сочетания и последова-
тельности структурных элементов), синтаксический анализ достаточ-
но сложен. При решении подобных задач существенную поддержку мо-
гут оказать сервисные программы, осуществляющие построение син-
таксических (грамматических) анализаторов на основе заданных све-
дений о синтаксической структуре входной информации. YACC отно-
сится к числу этих сервисных программ - генераторов грамматичес-
ких анализаторов.
Поскольку обширной областью, где наиболее явно видна необхо-
димость (нетривиального) грамматического анализа, а следова-
тельно и его автоматизации, является область создания транслято-
ров (в частности, компиляторов), программы, подобные YACC, полу-
чили еще название компиляторов (или генераторов) компиляторов.
Заметим, что понятие транслятора может относиться не только
к языкам программирования, но и к командным языкам, входным язы-
кам любых диалоговых систем, языкам управления технологическими
процессами и т.п.
Пользователь YACC должен описать структуру своей входной ин-
формации (ГРАММАТИКУ) как набор ПРАВИЛ в виде, близком к Бэкусо-
во-Науровской форме (БНФ). Каждое правило описывает грамматичес-
кую конструкцию, называемую НЕТЕРМИНАЛЬНЫМ СИМВО- ЛОМ, и сопос-
тавляет ей имя. С точки зрения грамматического разбора правила
рассматриваются как правила вывода (подстановки). Грамматические
правила описываются в терминах некоторых исходных конструкций,
которые называются лексическими единицами, или ЛЕКСЕМАМИ. Имеет-
ся возможность задавать лексемы непосредственно (литерально) или
употреблять в грамматических правилах имя лексемы. Как правило,
имена сопоставляются лексемам, соответствующим классам об'ектов,
конкретное значение которых не существенно для целей грамматичес-
кого анализа. (Иногда в литературе с понятием лексемы совпадает
понятие терминального символа; однако, ряд авторов называет тер-
минальными символами отдельные символы стандартного набора). При-
мерами имен лексем могут служить "ИДЕНТИФИ- КАТОР" и "ЧИСЛО", а
введение таких лексем позволяет обобщить конкретные способы запи-
си идентификаторов и чисел. В некоторых случаях имена лексем слу-
жат для придания правилам большей выразительности.
Лексемы должны распознаваться программой лексического анали-
за, определяемой пользователем. Пользователь же предварительно
выбирает конструкции,которые более удобно и эффективно распозна-
вать непосредственно, и в соответствии с этим об'являет имена
лексем. Пользовательская программа лексического анализа -
ЛЕКСИЧЕСКИЙ АНАЛИЗАТОР - осуществляет чтение реальной входной ин-
формации и передает грамматическому анализатору распознанные лек-
семы.
Как уже отмечалось, YACC обеспечивает автоматическое пос-
троение лишь процедуры грамматического анализа. Однако, действия
по обработке входной информации обычно должны выполняться по ме-
ре распознавания на входе тех или иных допустимых грамматических
конструкций. Поэтому наряду с заданием грамматики входных тек-
стов YACC предусматривает воможность описания для отдельных кон-
струкций семантических про-
цедур (ДЕЙСТВИЙ) с тем, чтобы они были включены в программу грам-
матического разбора. В зависимости от характера пользовательских
семантических процедур (интерпретация распознанного фрагмента
входного текста, генерация фрагмента об'ектного кода, отметка в
справочной таблице или форматирование вершины в дереве разбора)
генерируемая с помощью YACC программа будет обеспечивать кроме
анализа тот или иной вид обработки входного текста, в частности,
его компиляцию или интерпретацию.
Итак, пользователь YACC подготавливает общее описание
(СПЕЦИФИКАЦИИ) обработки входного потока, включающее правила,
описывающие входные конструкции, кодовую часть, к которой должно
быть организовано обращение при обнаружении этих конструкций, и
программу ввода базовых элементов потока (лексический
анализатор). Kомпилятор компиляторов обеспечивает создание под-
программы (грамматического анализатора), реализующей процедуру
обработки входного потока в соответствии с заданными специфика-
циями.
К компонентам компилятора компиляторов относятся выполняе-
мый файл yacc, библиотека стандартных программ /lib/liby.a, Файл
/usr/lib/yaccpar. Заключительная фаза построения компилятора тре-
бует применения компилятора языка Си.
ПРИНЦИПЫ РАБОТЫ YACC
Грамматические анализаторы, создаваемые с помощью YACC, реа-
лизуют так называемый LALR(1)-разбор, являющийся модификацией од-
ного из основных методов разбора "снизу вверх" - LR(k)-разбора
(буквы L(eft) и R(ight) в обоих сокращениях означают соответ-
ственно чтение входных символов слева направо и использование
правостороннего вывода. Индекс в скобках показывает число предва-
рительно просматриваемых лексических единиц).
Любой разбор по принципу "снизу вверх" (или восходящий раз-
бор) состоит в попытке приведения всей совокупности входных дан-
ных (входной цепочки) к так называемому "начальному символу грам-
матики" путем последовательного применения правил вывода.
В каждый момент грамматического разбора анализатор находит-
ся в некотором СОСТОЯНИИ, определяемом предысторией разбора, и в
зависимости от очередной лексемы предпринимает то или иное дей-
ствие для перехода к новому состоянию. Различают два типа дей-
ствий: "СДВИГ", т.е. чтение следующей входной лексемы, и
"СВЕРТКУ", т.е. применение одного из правил подстановки для заме-
щения нетерминалом последовательности символов, соответствующей
правой части правила. Работа YACC по генерации процедуры грамма-
тического анализа заключается в построении таблиц, которые для
каждого из состояний определяют тип действий анализатора и номер
следующего состояния в соответствии с каждой из входных лексем.
Любой метод разбора требует грамматик с определенными свой-
ствами. В этом смысле YACC предполагает контекстносвободные грам-
матики со свойствами LALR(1). LALR(1)- грамматики, являясь под-
множеством LR(1)-грамматик, допускают при построении таблиц раз-
бора сокращение общего числа состояний за счет об'единения иден-
тичных состояний, различающихся только набором символов-следова-
телей (символов, которые могут следовать после применения одного
из правил вывода, если разбор по этому правилу проходил через
данное состояние). Другие грамматики являются неоднозначными для
принятого в 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 допускает оба вида рекурсивных правил, однако, при ис-
пользовании правил с правой рекурсией об'ем анализатора увеличи-
вается, а во время разбора возможно переполнение внутреннего сте-
ка анализатора.
Рекурсивные правила необходимы при задании последовательнос-
тей и списков. Следующие примеры иллюстрируют универсальный спо-
соб описания этих конструкций:
последовательность: элемент
| последовательность элемент;
список: элемент | список ',' элемент;
Заметим, что в каждом из этих случаев первое правило (не со-
держащее рекурсии) будет применено только для первого элемента, а
второе (рекурсивное) - для всех последующих. Нетерминальные сим-
волы, связанные с последовательностями или списками разнородных
элементов, могут описываться произвольным числом рекурсивных и
нерекурсивных правил. Например, группа правил
идентификатор: буква |
'$' |
идентификатор буква |
идентификатор цифра |
идентификатор '_' ;
описывает идентификатор как последовательность букв, цифр и
символов "_", начинающуюся с буквы или символа "$". Следует обра-
тить внимание на то, что рекурсивные правила не имеют смысла, ес-
ли для определяемого ими нетерминала не задано ни одного правила
без рекурсии. Для обеспечения возможности задания пустых списков
или последовательностей в качестве нерекурсивного правила ис-
пользуется пустое:
последовательность : | последовательность элемент ;
Сочетание пустых и рекурсивных правил является удобным спо-
собом представления грамматик и ведет к большей их общности,