входного текста, генерация фрагмента об'ектного кода, отметка в
справочной таблице или форматирование вершины в дереве разбора)
генерируемая с помощью 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. Правая часть правила -
определение - представляет собой упорядоченную последова-
тельность элементов (нетерминальных символов и лексем), состав-
ляющих описываемую конструкцию. При грамматическом разборе такая
последовательность в результате применения правила заменяется не-
терминальным символом, имя которого указано в левой части. нетер-
минальные символы в определении задаются именами, а лексемы -
именами или литералами. Запись имен и литералов совпадает с за-
писью идентификаторов и символьных констант, принятой в Си.
По виду правила нельзя заключить, относятся эти имена к лек-