46023 (Проектирование трансляторов), страница 11

правила описываются в терминах некоторых исходных конструкций,

которые называются лексическими единицами, или ЛЕКСЕМАМИ. Имеет-

ся возможность задавать лексемы непосредственно (литерально) или

употреблять в грамматических правилах имя лексемы. Как правило,

имена сопоставляются лексемам, соответствующим классам об'ектов,

конкретное значение которых не существенно для целей грамматичес-

кого анализа. (Иногда в литературе с понятием лексемы совпадает

понятие терминального символа; однако, ряд авторов называет тер-

минальными символами отдельные символы стандартного набора). При-

мерами имен лексем могут служить "ИДЕНТИФИ- КАТОР" и "ЧИСЛО", а

введение таких лексем позволяет обобщить конкретные способы запи-

си идентификаторов и чисел. В некоторых случаях имена лексем слу-

жат для придания правилам большей выразительности.

Лексемы должны распознаваться программой лексического анали-

за, определяемой пользователем. Пользователь же предварительно

выбирает конструкции,которые более удобно и эффективно распозна-

вать непосредственно, и в соответствии с этим об'являет имена

лексем. Пользовательская программа лексического анализа -

ЛЕКСИЧЕСКИЙ АНАЛИЗАТОР - осуществляет чтение реальной входной ин-

формации и передает грамматическому анализатору распознанные лек-

семы.

Как уже отмечалось, 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 считает именами нетерми-

налов все имена, не объявленные в секции деклараций именами лек-

сем. Все нетерминалы должны быть определены, т.е. имя каждого из

них должно появиться в левой части хотя бы одного правила. Допус-

тимо задание нескольких правил, определяющих один нетерминальный

символ, т.е. правил с одинаковой левой частью. Такие правила оп-