Реферат: Проектирование трансляторов
димость (нетривиального) грамматического анализа, а следова-
тельно и его автоматизации, является область создания транслято-
ров (в частности, компиляторов), программы, подобные 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.
ПРОЦЕДУРА ПОСТРОЕНИЯ ГРАММАТИЧЕСКОГО АНАЛИЗАТОРА
Построение грамматического анализатора осуществляется в два
этапа. На первом этапе файл спецификаций входного языка обрабаты-
Страницы: 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
