Страница:
Производственно-внедренческий кооператив
"И Н Т Е Р Ф Е Й С"
Диалоговая Единая Мобильная
Операционная Система
Демос/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.
3. Процедура построения грамматического анализатора
Построение грамматического анализатора осуществляется в
два этапа. На первом этапе файл спецификаций входного языка
обрабатывается компилятором компиляторов yacc, для чего
задается командная строка
yacc [-vd] yfile
Здесь yfile - имя файла спецификаций, а флаги имеют следую-
щий смысл:
v - сформировать в файле y.output подробное описание грам-
матического анализатора;
- 5 -
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. Этот флаг полезно считать обязательным.
4. Задание входной информации yacc
4.1. Структура спецификационного файла
Пользовательские спецификации, задающие правила органи-
зации входной информации и алгоритм ее обработки, объединя-
ются в спецификационный файл следующей структуры:
%%
%%
Ядром спецификационного файла и единственной его обяза-
тельной частью является секция правил. При отсутсивии секции
программ может быть опущена вторая группа "%%"; следова-
тельно, минимальная допустимая конфигурация входного файла
имеет вид:
%%
Пробелы, знаки табуляции и перевода строки игнориру-
ются, недопустимо лишь появление их в именах. Комментарий,
ограниченный символами "/*" в начале и "*/" в конце, может
находиться между любыми двумя разделителями в любой секции
входного файла.
- 6 -
Секция правил состоит из одного или нескольких грамма-
тических правил. Эти правила должны определять все допусти-
мые входные конструкции и связанные с определенными конст-
рукциями действия по обработке входного потока.
Назначение секции деклараций состоит в основном в зада-
нии информации о лексемах.
Секция программ представляет собой некоторый набор про-
цедур на языке Си, которые должны включаться в текст прог-
раммы грамматического разбора. Например, это могут быть
процедура лексического анализа yylex и пользовательские про-
цедуры, вызываемые в действиях.
4.2. Секция правил
В данной секции с помощью набора грамматических правил
должны быть определены все конструкции, из которых впос-
ледствии будут строиться входные тексты. Не подлежат опреде-
лению в секции правил лишь конструкЦии, выбранные пользова-
телем в качестве лексем, считающиеся для грамматического
анализа исходными единицами. Правила задаются в форме, близ-
кой БНФ.
Правило, определяющее синтаксический вид конструкции,
задается таким образом:
<имя_нетерминального_символа>: определение;
Здесь ":" и ";" - специальные символы yacc. Правая часть
правила - определение - представляет собой упорядоченную
последовательность элементов (нетерминальных символов и лек-
сем), составляющих описываемую конструкцию. При грамматичес-
ком разборе такая последовательность в результате применения
правила заменяется нетерминальным символом, имя которого
указано в левой части. нетерминальные символы в определении
задаются именами, а лексемы - именами или литералами. Запись
имен и литералов совпадает с записью идентификаторов и сим-
вольных констант, принятой в Си.
Правило:
P_Head: P_name '(' P_list ')';
определяет нетерминал P_Head как последовательность 4-х эле-
ментов: два элемента заданы литерально, два других - име-
нами. По виду правила нельзя заключить, относятся эти имена
к лексемам или нетерминальным символам. yacc считает именами
нетерминалов все имена, не объявленные в секции деклараций
именами лексем (разд.4.3). Все нетерминалы должны быть
- 7 -
определены, т.е. имя каждого из них должно появиться в левой
части хотя бы одного правила. Допустимо задание нескольких
правил, определяющих один нетерминальный символ, т.е. правил
с одинаковой левой частью. Такие правила определяют конст-
рукции, идентичные на некотором уровне. Ниже приводятся три
правила, определяющие виды операторов в некотором языке:
statement : assign_stat ;
statement : if_then_stat;
statement : goto_stat;
Правила с общей левой частью можно задавать в сокращен-
ной записи, без повторения левой части, используя для разде-
ления альтернативных определений символ "|". Предыдущие пра-
вила можно переписать в виде:
statement : assign_stat |
if_then_stat |
goto_stat;
При необходимости с любым правилом можно связать дейст-
вие - набор операторов языка Си, которые будут выполняться
при каждом распознавании конструкции во входном тексте.
Действие не является обязательным элементом правил.
Действие заключается в фигурные скобки и помещается
вслед за правой частью правила, т.е. правило с действием
имеет вид:
<имя_нетерминального_символа>:
определение {действие};
Точка с запятой после правила с действием может опускаться.
При использовании сокращенной записи правил с общей
левой частью следует иметь в виду, что действие может отно-
ситься только к отдельному правилу, а не к их совокупности.
Следующий пример иллюстрирует задание действий в случае пра-
вил с общей левой частью.
statement: assign_stat
|
if_then_stat {printf("if_оператор\n");}
|
goto_stat {kgoto++;
printf("goto_оператор\n");}
- 8 -
На операторы, входящие в действия, не накладывается
никаких ограничений. В частности, в действиях могут содер-
жаться вызовы любых функций. Отдельные операторы могут быть
помечены, к ним возможен переход из других действий.
Существует возможность задания действий, которые будут
выполняться по мере распознавания отдельных фрагментов пра-
вила. Действие в этом случае помещается после одного из эле-
ментов правой части так, чтобы положение действия соотвест-
вовало моменту разбора, в который данному действию будет
передано управление.
Например, в правиле
if_then_stat: if'(' expression ')' {действие1}
then statement ';' {действие 2}
действия заданы с таким расчетом, чтобы при разборе строки
вида
if (a>b) then x=a;
действие 1 выполнялось при нахождении правой круглой скобки,
а действие 2 - по окончании разбора.
Для того, чтобы действия имели реальный смысл, они, как
правило, должны использовать некоторые общие переменные,
т.е. переменные, доступные во всех действиях и сохраняющие
свои значения по окончании очередного действия. Такие пере-
менные описываются в начале секции правил, все описание
ограничивается с двух сторон строками
%{
и
%}
Здесь же могут находиться произвольные операторы Си, расс-
матриваемые как общие действия для всех правил.
Дополним приведенный выше фрагмент спецификаций для
statement с тем, чтобы осуществлялся подсчет и вывод на
печать операторов goto
- 9 -
%{
int kgoto;
%}
prog: DECLS {kgoto=0;}
stats {printf("%d\n",kgoto);}
stats: statement
| stats statement;
statement:assign_stat
...
|
if_then_stat
...
|
goto_stat {kgoto++;
... }
Укажем еще на два вида объектов, использующихся в
действиях. Это, во-первых, глобальные переменные, которые
описываются в секции деклараций (разд.4.3), и, во-вторых,
специальные переменные (псевдопеременные),облегчающие взаи-
мосвязь между действиями и связь их с лексическим анализато-
ром. Работе с псевдопеременными посвящен раздел 4.5. Струк-
тура входной информации описывается в наборе правил иерархи-
чески, т.е. каждое правило соответствует определенному
уровню структурного разбиения. Однако, последовательность
задания правил может не отражать этой иерархии и быть вполне
произвольной. Единственно необходимой для yacc является
информация о том, какой из нетерминалов задает вершину
иерархии, т.е. соотвествует конструкциям, определяющим вход-
ной текст в целом. Этот нетерминал принято называть началь-
ным символом. Приведение входного текста к начальному сим-
волу является целью грамматического анализатора. По умолча-
нию yacc считает начальным символом тот нетерминал, имя
которого стоит в левой части первого из правил. Однако, если
определять начальный символ в первом правиле пользователю
неудобно, он может явно задать имя начального символа в сек-
ции деклараций.
Существует два специфических вида правил, на которые
полезно обратить внимание. Во-первых, это пустое правило
вида
<имя_нетерминального_символа>: ;
определяющее пустую последовательность символов. Сочетание
пустого правила с другими правилами, определяющими тот же
нетерминальный символ, является одним из способов указать на
необязательность вхождения соответствующей конструкции.
Например, совокупность правил
- 10 -
_число:знак целое_без_знака;
определяет возможность задания целых чисел со знаком и без
него. Другой способ описать эту возможность состоит в зада-
нии следующей группы правил:
целое_число:знак целое_без_знака |
целое_без_знака ;
знак: '+'|'-';
С пустым правилом может быть обычным образом связано
действие:
ИМЯ: {тело_действия} ;
Во-вторых, правила часто описывают некоторую конструкцию
рекурсивно, т.е. правая часть может рекурсивно включать
определяемый нетерминальный символ. Различают леворекурсив-
ные правила вида:
<имя_нетерминала>:<имя_нетерминала>
<многократно_повторяемый_фрагмент>;
и праворекурсивные вида
<имя_нетерминала>:
<многократно_повторяемый_фрагмент>
<имя_нетерминала>;
yacc допускает оба вида рекурсивных правил, однако при
использовании правил с правой рекурсией объем анализатора
увеличивается, а во время разбора возможно переполнение
внутреннего стека анализатора.
Рекурсивные правила необходимы при задании последова-
тельностей и списков. Следующие примеры иллюстрируют уни-
версальный способ описания этих конструкций:
последовательность: элемент
| последовательность элемент;
список: элемент|список ',' элемент;
- 11 -
Заметим, что в каждом из этих случаев первое правило (не
содержащее рекурсии) будет применено только для первого эле-
мента, а второе (рекурсивное) - для всех последующих. Нетер-
минальные символы, связанные с последовательностями или
списками разнородных элементов, могут описываться произволь-
ным числом рекурсивных и нерекурсивных правил. Например,
группа правил
идентификатор: буква |
'$' |
идентификатор буква|
идентификатор цифра|
идентификатор '_' ;
описывает идентификатор как последовательность букв, цифр и
символов "_", начинающуюся с буквы или символа "$". Следует
обратить внимание на то, что рекурсивные правила не имеют
смысла, если для определяемого ими нетерминала не задано ни
одного правила без рекурсии. Для обеспечения возможности
задания пустых списков или последовательностей в качестве
нерекурсивного правила используется пустое:
последовательность :
| последовательность элемент ;
Сочетание пустых и рекурсивных правил является удобным
способом представления грамматик и ведет к большей их общ-
ности, однако,некорректное использование пустых правил может
вызывать конфликтные ситуации (раздел 5) из-за неоднознач-
ности выбора нетерминала, соответствующего пустой последова-
тельности.
4.3. Секция деклараций
Секция деклараций состоит из последовательности строк
двух видов: строк-директив и строк исходного текста.
Строки исходного текста без изменений копируются в
выходной файл y.tab.c и могут содержать операторы препроцес-
сора и описание внешних объектов. Область действия перемен-
ных, описанных в секции деклараций, распространяется на весь
спецификационный файл, т.е. они доступны как в операторах
действий, так и в процедурах, находящихся в секции программ.
Строки-директивы начинаются символом "%" (этот символ в
yacc играет роль своего рода esc-символа). Две специальные
директивы
- 12 -
%{
и
%}
ограничивают с двух сторон группы строк исходного текста.
Остальные директивы служат для задания дополнительной инфор-
мации о грамматике.
5. Декларация имен лексем
%token <список_имен_лексем>
Пользователь при описании грамматики решает, какие
конструкции целесообразнее непосредственно выделять из вход-
ного текста на этапе лексического анализа, и на уровне этих
конструкций (лексем) задает грамматические правила. Все виды
лексем, кроме литералов, обозначаются некоторыми именами и
под этими именами фигурируют в секции правил. Благодаря дек-
ларации имен лексем в директиве %token yacc отличает имена
лексем от имен нетерминальных символов. Однако, декларация
ни в коей мере не обеспечивает распознавания лексем, и поль-
зователю рекомендуется считать для себя директиву %token
напоминанием о необходимости построения лексического анали-
затора (разд.4.4) и руководствоваться этой директивой при
его написании. Пример декларации имен лексем:
%token IDENT CONST ЗНАК IF THEN GOTO
Заметим, что ключевые слова описываемого входного языка
часто бывает удобно считать лексемами. Имена лексем могут
совпадать с этими ключевыми словами, недопустимым является
лишь совпадение имен лексем с зарезервированными словами
языка Си. В примере во избежание недоразумений для имен лек-
сем использованы прописные буквы.
6. Декларация приоритетов и ассоциативности лексем
%left <список_лексем>
%right <список_лексем>
%nonassoc <список_лексем>
Лексемы в данных директивах задаются литералами или
именами. В последнем случае декларация приоритета заменяет
также декларацию имени лексемы, хотя в целях обеспечения
наглядности описания является желательным присутствие в
- 13 -
списке директивы %token всего набора имен лексем.
Содержательный смысл декларации приоритетов и ассоциа-
тивности выясняется в разделе 5 в связи с вопросом о разре-
"И Н Т Е Р Ф Е Й С"
Диалоговая Единая Мобильная
Операционная Система
Демос/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.
3. Процедура построения грамматического анализатора
Построение грамматического анализатора осуществляется в
два этапа. На первом этапе файл спецификаций входного языка
обрабатывается компилятором компиляторов yacc, для чего
задается командная строка
yacc [-vd] yfile
Здесь yfile - имя файла спецификаций, а флаги имеют следую-
щий смысл:
v - сформировать в файле y.output подробное описание грам-
матического анализатора;
- 5 -
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. Этот флаг полезно считать обязательным.
4. Задание входной информации yacc
4.1. Структура спецификационного файла
Пользовательские спецификации, задающие правила органи-
зации входной информации и алгоритм ее обработки, объединя-
ются в спецификационный файл следующей структуры:
%%
%%
Ядром спецификационного файла и единственной его обяза-
тельной частью является секция правил. При отсутсивии секции
программ может быть опущена вторая группа "%%"; следова-
тельно, минимальная допустимая конфигурация входного файла
имеет вид:
%%
Пробелы, знаки табуляции и перевода строки игнориру-
ются, недопустимо лишь появление их в именах. Комментарий,
ограниченный символами "/*" в начале и "*/" в конце, может
находиться между любыми двумя разделителями в любой секции
входного файла.
- 6 -
Секция правил состоит из одного или нескольких грамма-
тических правил. Эти правила должны определять все допусти-
мые входные конструкции и связанные с определенными конст-
рукциями действия по обработке входного потока.
Назначение секции деклараций состоит в основном в зада-
нии информации о лексемах.
Секция программ представляет собой некоторый набор про-
цедур на языке Си, которые должны включаться в текст прог-
раммы грамматического разбора. Например, это могут быть
процедура лексического анализа yylex и пользовательские про-
цедуры, вызываемые в действиях.
4.2. Секция правил
В данной секции с помощью набора грамматических правил
должны быть определены все конструкции, из которых впос-
ледствии будут строиться входные тексты. Не подлежат опреде-
лению в секции правил лишь конструкЦии, выбранные пользова-
телем в качестве лексем, считающиеся для грамматического
анализа исходными единицами. Правила задаются в форме, близ-
кой БНФ.
Правило, определяющее синтаксический вид конструкции,
задается таким образом:
<имя_нетерминального_символа>: определение;
Здесь ":" и ";" - специальные символы yacc. Правая часть
правила - определение - представляет собой упорядоченную
последовательность элементов (нетерминальных символов и лек-
сем), составляющих описываемую конструкцию. При грамматичес-
ком разборе такая последовательность в результате применения
правила заменяется нетерминальным символом, имя которого
указано в левой части. нетерминальные символы в определении
задаются именами, а лексемы - именами или литералами. Запись
имен и литералов совпадает с записью идентификаторов и сим-
вольных констант, принятой в Си.
Правило:
P_Head: P_name '(' P_list ')';
определяет нетерминал P_Head как последовательность 4-х эле-
ментов: два элемента заданы литерально, два других - име-
нами. По виду правила нельзя заключить, относятся эти имена
к лексемам или нетерминальным символам. yacc считает именами
нетерминалов все имена, не объявленные в секции деклараций
именами лексем (разд.4.3). Все нетерминалы должны быть
- 7 -
определены, т.е. имя каждого из них должно появиться в левой
части хотя бы одного правила. Допустимо задание нескольких
правил, определяющих один нетерминальный символ, т.е. правил
с одинаковой левой частью. Такие правила определяют конст-
рукции, идентичные на некотором уровне. Ниже приводятся три
правила, определяющие виды операторов в некотором языке:
statement : assign_stat ;
statement : if_then_stat;
statement : goto_stat;
Правила с общей левой частью можно задавать в сокращен-
ной записи, без повторения левой части, используя для разде-
ления альтернативных определений символ "|". Предыдущие пра-
вила можно переписать в виде:
statement : assign_stat |
if_then_stat |
goto_stat;
При необходимости с любым правилом можно связать дейст-
вие - набор операторов языка Си, которые будут выполняться
при каждом распознавании конструкции во входном тексте.
Действие не является обязательным элементом правил.
Действие заключается в фигурные скобки и помещается
вслед за правой частью правила, т.е. правило с действием
имеет вид:
<имя_нетерминального_символа>:
определение {действие};
Точка с запятой после правила с действием может опускаться.
При использовании сокращенной записи правил с общей
левой частью следует иметь в виду, что действие может отно-
ситься только к отдельному правилу, а не к их совокупности.
Следующий пример иллюстрирует задание действий в случае пра-
вил с общей левой частью.
statement: assign_stat
|
if_then_stat {printf("if_оператор\n");}
|
goto_stat {kgoto++;
printf("goto_оператор\n");}
- 8 -
На операторы, входящие в действия, не накладывается
никаких ограничений. В частности, в действиях могут содер-
жаться вызовы любых функций. Отдельные операторы могут быть
помечены, к ним возможен переход из других действий.
Существует возможность задания действий, которые будут
выполняться по мере распознавания отдельных фрагментов пра-
вила. Действие в этом случае помещается после одного из эле-
ментов правой части так, чтобы положение действия соотвест-
вовало моменту разбора, в который данному действию будет
передано управление.
Например, в правиле
if_then_stat: if'(' expression ')' {действие1}
then statement ';' {действие 2}
действия заданы с таким расчетом, чтобы при разборе строки
вида
if (a>b) then x=a;
действие 1 выполнялось при нахождении правой круглой скобки,
а действие 2 - по окончании разбора.
Для того, чтобы действия имели реальный смысл, они, как
правило, должны использовать некоторые общие переменные,
т.е. переменные, доступные во всех действиях и сохраняющие
свои значения по окончании очередного действия. Такие пере-
менные описываются в начале секции правил, все описание
ограничивается с двух сторон строками
%{
и
%}
Здесь же могут находиться произвольные операторы Си, расс-
матриваемые как общие действия для всех правил.
Дополним приведенный выше фрагмент спецификаций для
statement с тем, чтобы осуществлялся подсчет и вывод на
печать операторов goto
- 9 -
%{
int kgoto;
%}
prog: DECLS {kgoto=0;}
stats {printf("%d\n",kgoto);}
stats: statement
| stats statement;
statement:assign_stat
...
|
if_then_stat
...
|
goto_stat {kgoto++;
... }
Укажем еще на два вида объектов, использующихся в
действиях. Это, во-первых, глобальные переменные, которые
описываются в секции деклараций (разд.4.3), и, во-вторых,
специальные переменные (псевдопеременные),облегчающие взаи-
мосвязь между действиями и связь их с лексическим анализато-
ром. Работе с псевдопеременными посвящен раздел 4.5. Струк-
тура входной информации описывается в наборе правил иерархи-
чески, т.е. каждое правило соответствует определенному
уровню структурного разбиения. Однако, последовательность
задания правил может не отражать этой иерархии и быть вполне
произвольной. Единственно необходимой для yacc является
информация о том, какой из нетерминалов задает вершину
иерархии, т.е. соотвествует конструкциям, определяющим вход-
ной текст в целом. Этот нетерминал принято называть началь-
ным символом. Приведение входного текста к начальному сим-
волу является целью грамматического анализатора. По умолча-
нию yacc считает начальным символом тот нетерминал, имя
которого стоит в левой части первого из правил. Однако, если
определять начальный символ в первом правиле пользователю
неудобно, он может явно задать имя начального символа в сек-
ции деклараций.
Существует два специфических вида правил, на которые
полезно обратить внимание. Во-первых, это пустое правило
вида
<имя_нетерминального_символа>: ;
определяющее пустую последовательность символов. Сочетание
пустого правила с другими правилами, определяющими тот же
нетерминальный символ, является одним из способов указать на
необязательность вхождения соответствующей конструкции.
Например, совокупность правил
- 10 -
_число:знак целое_без_знака;
определяет возможность задания целых чисел со знаком и без
него. Другой способ описать эту возможность состоит в зада-
нии следующей группы правил:
целое_число:знак целое_без_знака |
целое_без_знака ;
знак: '+'|'-';
С пустым правилом может быть обычным образом связано
действие:
ИМЯ: {тело_действия} ;
Во-вторых, правила часто описывают некоторую конструкцию
рекурсивно, т.е. правая часть может рекурсивно включать
определяемый нетерминальный символ. Различают леворекурсив-
ные правила вида:
<имя_нетерминала>:<имя_нетерминала>
<многократно_повторяемый_фрагмент>;
и праворекурсивные вида
<имя_нетерминала>:
<многократно_повторяемый_фрагмент>
<имя_нетерминала>;
yacc допускает оба вида рекурсивных правил, однако при
использовании правил с правой рекурсией объем анализатора
увеличивается, а во время разбора возможно переполнение
внутреннего стека анализатора.
Рекурсивные правила необходимы при задании последова-
тельностей и списков. Следующие примеры иллюстрируют уни-
версальный способ описания этих конструкций:
последовательность: элемент
| последовательность элемент;
список: элемент|список ',' элемент;
- 11 -
Заметим, что в каждом из этих случаев первое правило (не
содержащее рекурсии) будет применено только для первого эле-
мента, а второе (рекурсивное) - для всех последующих. Нетер-
минальные символы, связанные с последовательностями или
списками разнородных элементов, могут описываться произволь-
ным числом рекурсивных и нерекурсивных правил. Например,
группа правил
идентификатор: буква |
'$' |
идентификатор буква|
идентификатор цифра|
идентификатор '_' ;
описывает идентификатор как последовательность букв, цифр и
символов "_", начинающуюся с буквы или символа "$". Следует
обратить внимание на то, что рекурсивные правила не имеют
смысла, если для определяемого ими нетерминала не задано ни
одного правила без рекурсии. Для обеспечения возможности
задания пустых списков или последовательностей в качестве
нерекурсивного правила используется пустое:
последовательность :
| последовательность элемент ;
Сочетание пустых и рекурсивных правил является удобным
способом представления грамматик и ведет к большей их общ-
ности, однако,некорректное использование пустых правил может
вызывать конфликтные ситуации (раздел 5) из-за неоднознач-
ности выбора нетерминала, соответствующего пустой последова-
тельности.
4.3. Секция деклараций
Секция деклараций состоит из последовательности строк
двух видов: строк-директив и строк исходного текста.
Строки исходного текста без изменений копируются в
выходной файл y.tab.c и могут содержать операторы препроцес-
сора и описание внешних объектов. Область действия перемен-
ных, описанных в секции деклараций, распространяется на весь
спецификационный файл, т.е. они доступны как в операторах
действий, так и в процедурах, находящихся в секции программ.
Строки-директивы начинаются символом "%" (этот символ в
yacc играет роль своего рода esc-символа). Две специальные
директивы
- 12 -
%{
и
%}
ограничивают с двух сторон группы строк исходного текста.
Остальные директивы служат для задания дополнительной инфор-
мации о грамматике.
5. Декларация имен лексем
%token <список_имен_лексем>
Пользователь при описании грамматики решает, какие
конструкции целесообразнее непосредственно выделять из вход-
ного текста на этапе лексического анализа, и на уровне этих
конструкций (лексем) задает грамматические правила. Все виды
лексем, кроме литералов, обозначаются некоторыми именами и
под этими именами фигурируют в секции правил. Благодаря дек-
ларации имен лексем в директиве %token yacc отличает имена
лексем от имен нетерминальных символов. Однако, декларация
ни в коей мере не обеспечивает распознавания лексем, и поль-
зователю рекомендуется считать для себя директиву %token
напоминанием о необходимости построения лексического анали-
затора (разд.4.4) и руководствоваться этой директивой при
его написании. Пример декларации имен лексем:
%token IDENT CONST ЗНАК IF THEN GOTO
Заметим, что ключевые слова описываемого входного языка
часто бывает удобно считать лексемами. Имена лексем могут
совпадать с этими ключевыми словами, недопустимым является
лишь совпадение имен лексем с зарезервированными словами
языка Си. В примере во избежание недоразумений для имен лек-
сем использованы прописные буквы.
6. Декларация приоритетов и ассоциативности лексем
%left <список_лексем>
%right <список_лексем>
%nonassoc <список_лексем>
Лексемы в данных директивах задаются литералами или
именами. В последнем случае декларация приоритета заменяет
также декларацию имени лексемы, хотя в целях обеспечения
наглядности описания является желательным присутствие в
- 13 -
списке директивы %token всего набора имен лексем.
Содержательный смысл декларации приоритетов и ассоциа-
тивности выясняется в разделе 5 в связи с вопросом о разре-