Проектирование трансляторов

yylastch=yytext;

}

}

ЛЕКЦИЯ 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 допускает оба вида рекурсивных правил, однако, при ис-

пользовании правил с правой рекурсией об'ем анализатора увеличи-

вается, а во время разбора возможно переполнение внутреннего сте-

ка анализатора.


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

тей и списков. Следующие примеры иллюстрируют универсальный спо-

соб описания этих конструкций:


последовательность: элемент

| последовательность элемент;


список: элемент | список ',' элемент;


Заметим, что в каждом из этих случаев первое правило (не со-

держащее рекурсии) будет применено только для первого элемента, а

второе (рекурсивное) - для всех последующих. Нетерминальные сим-

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

элементов, могут описываться произвольным числом рекурсивных и

нерекурсивных правил. Например, группа правил


идентификатор: буква |

'$' |

идентификатор буква |

идентификатор цифра |

идентификатор '_' ;


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

символов "_", начинающуюся с буквы или символа "$". Следует обра-

тить внимание на то, что рекурсивные правила не имеют смысла, ес-

ли для определяемого ими нетерминала не задано ни одного правила

без рекурсии. Для обеспечения возможности задания пустых списков

или последовательностей в качестве нерекурсивного правила ис-

пользуется пустое:


последовательность : | последовательность элемент ;


Сочетание пустых и рекурсивных правил является удобным спо-

собом представления грамматик и ведет к большей их общности,

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: