- •1. Принципы работы yacc
- •2. Входные и выходные файлы, структура грамматического ана-
- •3. Процедура построения грамматического анализатора
- •4. Задание входной информации yacc
- •4.1. Структура спецификационного файла
- •4.2. Секция правил
- •4.3. Секция деклараций
- •5. Декларация имен лексем
- •6. Декларация приоритетов и ассоциативности лексем
- •7. Декларация имени начального символа
- •7.1. Секция программ
- •Val. Если функция yylex находится в отдельном файле, то эта
- •7.2. Действия с использованием псевдопеременных
- •8. Конфликты грамматического разбора
- •If '(' условие ')' оператор else
- •9. Структура информационного входного файла y.Output
- •10. Обработка ошибок при грамматическом разборе
- •11. Диагностика ошибок
- •0, Считаются восьмеричными, все остальные - десятичными.
- •Int base, regs[26]; /* в действиях */
- •1. Принципы работы yacc .............................. 3
Генератор программ синтаксического анализа yacc
Производственно-внедренческий кооператив
"И Н Т Е Р Ф Е Й С"
Диалоговая Единая Мобильная
Операционная Система
Демос/P 2.1
Генератор программ синтаксического анализа yacc
Москва
1988
Аннотация
Значительная часть создаваемых программ, рассчитанных
на определенную структуру входной информации, явно или
неявно включает в себя некоторую процедуру синтаксического
анализа. В задачах, где пользователю при задании входной
информации предоставляется относительная свобода (в отноше-
нии сочетания и последовательности структурных элементов),
синтаксический анализ достаточно сложен. При решении подоб-
ных задач существенную поддержку могут оказать сервисные
программы, осуществляющие построение синтаксических (грамма-
тических) анализаторов на основе заданных сведений о синтак-
сической структуре входной информации. yacc относится к
числу этих сервисных программ - генераторов синтаксических
анализаторов.
Поскольку обширной областью, где наиболее явно видна
необходимость (нетривиального) грамматического анализа, а
следовательно и его автоматизации, является область создания
трансляторов (в частности, компиляторов), программы, подоб-
ные yacc, получили еще название компиляторов (или генерато-
ров) компиляторов.
Заметим, что понятие транслятора может относиться не
только к языкам программирования, но и к командным языкам,
входным языкам любых диалоговых систем, языкам управления
технологическими процессами и т.п.
Пользователь yacc должен описать структуру своей вход-
ной информации (грамматику) как набор правил в виде, близком
к Бэкусово-Науровской форме (БНФ). Каждое правило описывает
грамматическую конструкцию, называемую нетерминальным симво-
лом, и сопоставляет ей имя. С точки зрения грамматического
разбора правила рассматриваются как правила вывода (подста-
новки). Грамматические правила описываются в терминах неко-
торых исходных конструкций, которые называются лексическими
единицами, или лексемами. Имеется возможность задавать лек-
семы непосредственно (литерально) или употреблять в грамма-
тических правилах имя лексемы. Как правило, имена сопостав-
ляются лексемам, соответствующим классам объектов, конкрет-
ное значение которых не существенно для целей грамматичес-
кого анализа. (Иногда в литературе с понятием лексемы совпа-
дает понятие терминального символа; однако, ряд авторов
называет терминальными символами отдельные символы стандарт-
ного набора). Примерами имен лексем могут служить идентифи-
катор и число, а введение таких лBексем позволяет обобщить
конкретные способы записи идентификаторов и чисел. В некото-
рых случаях имена лексем служат для придания правилам боль-
шей выразительности.
Лексемы должны распознаваться программой лексического
анализа, определяемой пользователем. Пользователь же предва-
рительно выбирает конструкции,которые более удобно и
эффективно распознавать непосредственно, и в соответствии с
этим объявляет имена лексем. Пользовательская программа лек-
сического анализа - лексический анализатор - осуществляет
чтение реальной входной информации и передает синтаксичес-
кому анализатору распознанные лексемы.
Как уже отмечалось, yacc обеспечивает автоматическое
построение лишь процедуры грамматического анализа. Однако,
действия по обработке входной информации обычно должны
выполняться по мере распознавания на входе тех или иных
допустимых грамматических конструкций. Поэтому наряду с
заданием грамматики входных текстов yacc предусматривает
воможность описания для отдельных конструкций семантических
процедур (действий) с тем, чтобы они были включены в прог-
рамму грамматического разбора. В зависимости от характера
пользовательских семантических процедур (интерпретация рас-
познанного фрагмента входного текста, генерация фрагмента
объектного кода, отметка в справочной таблице или форматиро-
вание вершины в дереве разбора) генерируемая с помощью yacc
программа будет обеспечивать кроме анализа тот или иной вид
обработки входного текста, в частности, его компиляцию или
интерпретацию.
Итак, пользователь yacc подготавливает общее описание
(спецификации) обработки входного потока, включающее пра-
вила, описывающие входные конструкции, кодовую часть, к
которой должно быть организовано обращение при обнаружении
этих конструкций, и программу ввода базовых элементов потока
(лексический анализатор). Kомпилятор компиляторов обеспечи-
вает создание подпрограммы (синтаксического анализатора),
реализующей процедуру обработки входного потока в соответст-
вии с заданными спецификациями.
yacc написан на языке Си и работает под управлением
системы ДЕМОС.
К компонентам компилятора компиляторов относятся выпол-
няемый файл yacc, библиотека стандартных программ
/lib/liby.a, Файл /usr/lib/yaccpar. Заключительная фаза
построения компилятора требует применения компилятора языка
Си.
1. Принципы работы yacc
Грамматические анализаторы, создаваемые с помощью yacc,
реализуют так называемый LALR(1)-разбор, являющийся модифи-
кацией одного из основных методов разбора "снизу вверх" -
LR(k)-разбора (буквы L(eft) и R(ight) в обоих сокращениях
означают соответственно чтение входных символов слева нап-
раво и использование правостороннего вывода. Индекс в скоб-
ках показывает число предварительно просматриваемых лекси-
ческих единиц).
- 3 -
Любой разбор по принципу "снизу вверх" (или восходящий
разбор) состоит в попытке приведения всей совокупности вход-
ных данных (входной цепочки) к так называемому "начальному
символу грамматики" (это понятие будет объяснено в разделе
4.1) путем последовательного применения правил вывода.
В каждый момент грамматического разбора анализатор
находится в некотором состоянии, определяемом предысторией
разбора, и в зависимости от очередной лексемы предпринимает
то или иное действие для перехода к новому состоянию. Разли-
чают два типа действий: сдвиг, т.е. чтение следующей входной
лексемы, и свертку, т.е. применение одного из правил подс-
тановки для замещения нетерминалом последовательности симво-
лов, соответствующей правой части правила. Работа yacc по
генерации процедуры грамматического анализа заключается в
построении таблиц, которые для каждого из состояний опреде-
ляют тип действий анализатора и номер следующего состояния в
соответствии с каждой из входных лексем.
Любой метод разбора требует грамматик с определенными
свойствами. В этом смысле yacc предполагает контекстно-
свободные грамматики со свойствами LALR(1). LALR(1)-
грамматики, являясь подмножеством LR(1)-грамматик, допускают
при построении таблиц разбора сокращение общего числа состо-
яний за счет объединения идентичных состояний, различающихся
только набором символов-следователей (символов, которые
могут следовать после применения одного из правил вывода,
если разбор по этому правилу проходил через данное состоя-
ние). Другие грамматики являются неоднозначными для приня-
того в yacc метода разбора и вызовут конфликты (раздел 5).
Однако, если язык, описываемый данной грамматикой, в прин-
ципе допускает задание грамматики, однозначной для данного
метода разбора, то yacc позволяет без перестройки грамматики
построить грамматический анализатор, разрешающий конфликты
на основе механизма приоритетов (раздел 5).
2. Входные и выходные файлы, структура грамматического ана-
лизатора
Входная информация для yacc задается в спецификационном
файле, структура которого рассматривается в разделе 4.
На выходе компилятора компиляторов в результате обра-
ботки спецификаций создается файл y.tab.c с исходным текстом
Си-процедур, составляющих грамматический анализатор. Основ-
ной в файле y.tab.c является процедура yyparse, реализующая
алгоритм грамматического разбора. При формировании ее yacc
использует файл /usr/lib/yaccpar, содержащий неизменяемую
часть анализатора. Кроме yyparse, в файл y.tab.c yacc вклю-
чает построенные им таблицы разбора, описания и программные
фрагменты пользовательских спецификаций.
- 4 -
Процедура 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
содержащий описание состояний анализатора и сообщения о
конфликтах (раздел 6)
y.tab.h
содержащий описание лексем (раздел 4.3).
Для генерации этих файлов требуется задание соответст-
вующих флагов при вызове yacc.