Страница:
шении конфликтов грамматического разбора. Использование
лексемы само по себе не требует задания ее приоритета или
ассоциативности.
При первом появлении лексемы или литерала в секции дек-
лараций за каждым из них может следовать неотрицательное
целое число, рассматриваемое как номер типа лексемы. По
умолчанию номера типов всех лексеМ определяются yacc следую-
щим образом:
- для литерала номером типа лексемы считается числовое
значение данного литерального символа, рассматриваемого
как однобайтовое целое число;
- лексемы,обозначенные именами, в соответствии с очеред-
ностью их объявления получают последовательные номера,
начиная с 257;
- специальная лексема error, зарезервированная для обра-
ботки ошибок (раздел 7), получает номер типа 256.
Для каждого имени лексемы независимо от того, переопре-
делен ли ее номер пользователем, yacc генерирует в выходном
файле y.tab.c оператор макропрепроцессора
#define <имя_лексемы> <номер_типа>
В случае переопределения номера типа литеральной лек-
семы также формируется оператор #define, например, директива
%left 'z' 258
породит оператор
#define z 258
Заметим, что возможно переопределение номеров лишь для
буквенных литералов.
При вызове yacc с флагом -d последовательность операто-
ров #define помещается также в информационный файл y.tab.h.
Переопределив при необходимости ряд номеров типов
лексем,пользователь должен проверить уникальность номеров у
всех используемых лексем.
- 14 -
7. Декларация имени начального символа
%start <имя_начального_символа>
Директива отменяет действующий по умолчанию выбор в
качестве начального символа нетериминала, определяемого пер-
вым грамматическим правилом.
7.1. Секция программ
В секцию программ помещается описание пользовательских
процедур, которые должны быть включены в генерируемую прог-
рамму грамматического анализа. Любая из определяемых пользо-
вателем программных компонент может находиться в секции
программ спецификационного файла, либо присоединяться на
этапе вызова Си-компилятора для трансляции файла y.tab.c и
компоновки выходной программы. Перечислим процедуры, которые
одним из этих способов должны быть заданы:
- лексический анализатор - функция с именем yylex();
- все процедуры, вызовы которых содержатся в действиях,
связанных с грамматическими правилами;
- главная процедура main() при необходимости заменить ее
стандартный библиотечный вариант, который имеет вид
main() {return (yyparse();}
- процедура обработки ошибок yyerror() - также для замены
библиотечного варианта (его текст приводится ниже).
#include <stdio.h>
yyerror(s) char *s; {
fprintf(stderr, "%s\n", s);}
Для обеспечения корректной работы грамматического ана-
лизатора функция лексического анализа yylex должна быть сог-
ласована с конкретной спецификацией грамматики и удовлетво-
рять определенным требованиям. Основная задача функции yylex
состоит во вводе из входного потока ряда очередных символов
до выявления конструкции, соответствующей одной из лексем, и
возвращении номера типа этой лексемы. Для нелитеральных лек-
сем номером типа может служить объявленное в секции деклара-
ций имя лексемы (с помощью механизма #define yacc обеспечи-
вает замену его нужным номером), в случае литералов номером
типа является числовое значение символа (если оно не было
- 15 -
переопределено). Алгоритм поиска должен заключаться в
попытке нахождения сначала более сложных (нелитеральных)
лексем и лишь при несовпадении ни с одной из них текущих
элементов ввода возвращать номер типа литеральной лексемы
(любой однозначный символ, не начинающий ни одну из возмож-
ных лексем, сам образует лексему).
Приведем текст процедуры лексического анализа, распоз-
нающей идентификаторы и целые числа:
#include <stdio.h>
yylex() {char c;
while ((c=getc(stdin))==' '||c=='\n');
if(c>='0'&&c<='9'){
while((c=getc(stdin))>='0'&&c<='9');
ungetc(c,stdin));
return (CONST);}
if (c>='a'&&c<='z'){
while ((c=getc(stdin))>'a'&&c<='z'
||c>='0'&&c<='9');
ungetc(c,stdin); return (NAME);}
return (c); }
Сложность лексического анализатора зависит от того,
какие структурные единицы взяты за основу при описании грам-
матических правил. Детализовав грамматику до отдельных сим-
волов, можно обойтись простейшим лексическим анализатором,
осуществляющим только их ввод:
yylex() {return (getchar());}
Однако, в этом случае число правил растет, а граммати-
ческий разбор оказывается менее эффективным. Поэтому пользо-
ватель обычно должен найти некоторый компромисс при выборе
набора лексем.
В процедуре лексического анализа кроме выделения лексем
можно предусмотреть некоторую обработку лексем определенных
типов, в частности, запоминание конкретных значений лексем.
Кроме того, эти значения обычно требуется передать граммати-
ческому анализатору. С этой целью нужное значение должно
быть присвоено внешней переменной целого типа с именем yyl-
val. Если функция yylex находится в отдельном файле, то эта
переменная должна быть объявлена:
extern int yylval;
- 16 -
Уточним, что в дальнейшем значением лексемы мы будем
называть значение, присвоенное при ее распознавании перемен-
ной yylval; значение, возвращаемое функцией yylex, является
номером типа лексемы. Примером значения лексемы могут слуить
числовое значение цифры, вычисленное значение константы,
адрес идентификатора в таблице имен (построение таблицы имен
удобно осуществлять лексическим анализатором). Заметим,
что, хотя значение yylval устанавливается с целью использо-
вания его в действиях, непосредственное обращение к переМен-
ной yylval в действии не имеет смысла (поскольку в yylval
всегда находится значение последней выделенной лексемы).
Доступ в действиях к значениям лексем осуществляется с
помощью специального механизма, описанного в разделе 4.5.
7.2. Действия с использованием псевдопеременных
Для обеспечения связи между действиями, а также между
действиями и лексическим анализатором создаваемые yacc грам-
матические анализаторы поддерживают специальный стек, в
котором сохраняются значения лексем и нетерминальных симво-
лов. Значение лексемы автоматически попадает в стек после
ее распознавания лексическим анализатором (напомним, что им
считается текущее значение переменной yylval). После каждой
свертки вычисляется значение нетерминала, заместившего свер-
нутую строку, и помещается в вершину стека; значения элемен-
тов правой части примененного правила перед этим выталкива-
ются из стека. Заметим, что таким образом к моменту свертки
любого правила все значения нетерминалов в правой части ока-
зываются вычисленными в результате сверток. Способ вычисле-
ния значения нетерминала будет рассмотрен ниже.
Описанный механизм не требует вмешательства пользова-
теля и предоставляет ему следующие возможности:
- Использовать в действиях, осуществляемых после свертки
по правилу, значение любого элемента его правой части.
Доступ к этим значениям обеспечивается набором так
называемых псевдопеременных с именами $1,$2,..., где $i
соответствует значению i-го элемента; элементы правой
части правила нумеруются слева направо без различия
лексем и нетерминальных символов, например, в правиле
P_Head: P_name '(' P_list ')';
псевдопеременные $1,$2,$3,$4 относились бы соответст-
венно к P_name, '(', P_list, ')'.
- Формировать в действиях значение, образованного в
результате свертки нетерминала путем присвоения этого
значения псевдопеременной с именем $$. Так, в правиле
- 17 -
expr: expr '+' expr { $$=$1+$3; }
значением нового нетерминала expr станет сумма ранее
вычисленных значений двух других нетерминалов expr.
Eсли в действии не определяется значение переменной $$
(а также если действие отсутствует), значением нетерми-
нала после свертки по умолчанию становится значение
первого элемента правой части, т.е. неявно выполняется
присваивание
$$=$1;
Пример (вычисление значения целого числа)
%token DIGIT
%%
...
CONST: DIGIT
| CONST DIGIT {$$=$1*10+$2;}
...
%%
yylex()
{
char c;
if((c=getchar())>='0'&& c<='9') {
yylval = c-'0';
return (DIGIT);
}
...
}
Здесь при свертке по первому правилу нетерминал CONST
получает значение первой цифры, присвоенное в функции
yylex переменной yylval; при каждой свертке по второму
правилу явно вычисляется значение нового нетерминала
CONST.
Несколько иная ситуация в отношении использования псев-
допеременных имеет место для правил, содержащих действия
внутри правой части. На самом деле yacc интерпретирует пра-
вило вида
: B C {действие 1} D {действие 2}
K {действие 3}
как
: B C EMPTY1 D EMPTY2 K;
и в месте, где вставлено действие, при разборе
- 18 -
осуществляется свертка по пустому правилу, сопровождающаяся
выполнением указанного действия. При этом независимо от
характера действия очередной элемент в стеке значений отво-
дится для хранения значения неявно присутствующего "пустого"
нетерминала. В действии, находящемся в конце правила, согла-
шение о значениях псевдопеременных остается прежним, если
иметь в виду наличие дополнительных символов. В приведенном
выше правиле в действии 3 для доступа к значениям элементов
B, C, D, K следовало бы использовать соответственно псевдо-
переменные $1, $2, $4, $6; псевдоперемнные $3, $5 хранят
результаты действий 1 и 2. В действиях, находящихся внутри
правила, с помощью псевдоперемнных $i доступны значения рас-
положенных левее элементов, а также результаты предшествую-
щих вставленных в тело действий. Результатом внутреннего
действия (т.е. значением неявного нетерминала) является зна-
чение, присвоенное в этом действии псевдопеременной $$, при
отсутствии такого присваивания результат действия не опреде-
лен. Заметим, что присваивание значения псевдопеременной $$
во внутренних действиях не вызывает предварительной уста-
новки значения нетерминала, стоящего в левой части правила:
это значение в любом случае устанавливется только действием
в конце правила или считается равным значению $1.
В нашем примере в действии 1 доступными являются только
значения элементов B и C (им соответствуют псевдопеременные
$1 и $2), а в действии 2 - значения элементов B, C, D и
результат действия 1 с помощью псевдопеременных $1, $2, $4,
$3.
Следующий пример иллюстрирует варианты использования
псевдопеременных:
%token ИМЯ КЛЮЧ1 КЛЮЧ2 КОНЕЦ
. . .
%%
входной_поток: данные КОНЕЦ
{printf("Данные занесены в файл %s\n",$1);};
данные:
ИМЯ {abc = creat($1,0666);}
КЛЮЧ1 КЛЮЧ2 {option($3,$4);}
упр_строка '\n' {converse(0,$5,$6);
write($1,$6,80);}
текст {converse(1,$5,$8);
write($1,$6,$8);
close($1);};
упр_строка: ...
текст : ...
. . .
- 19 -
Управляющая строка и текст преобразуются в соответствии с
заданными ключами и записываются в файл с указанным именем.
Значением нетерминала данные в результате неявного действия
становится значение лексемы ИМЯ (адрес строки с именем файла
присваивается в лексическом анализаторе переменной yylval).
8. Конфликты грамматического разбора
Заданная грамматика является неоднозначной, если
существует входная строка, которая в соответствии с этой
грамматикой может быть разобрана двумя или более различными
способами. Рассмотрим, например, набор правил, описывающих
константное арифметическое выражение:
expr: CONST /*1*/
|
expr '+'expr /*2*/
|
expr '-'expr /*3*/
|
expr '*'expr /*4*/
|
expr '/'expr; /*5*/
Описывая возможность построения выражения из двух выра-
жений, соединенных знаком арифметической операции, правила
неоднозначно определяют путь разбора некоторых входных
строк. Так, строка вида:
expr*expr-expr
допускает два пути разбора, приводящих к различным группи-
ровкам ее элементов:
expr*(expr-expr) и (expr*expr) - expr
С точки зрения работы грамматического анализатора дан-
ная ситуация проявляется в неоднозначности выбора действия
при вводе лексемы "-" в момент, когда разобранная часть
строки приведена к виду expr*expr. Два возможных действия
анализатора состоят в следующем:
Можно ввести следующий символ и без применения правила
подстановки перейти в новое состояние. В разделе 1 мы
назвали такое действие сдвигом. Выбор сдвига приведет к
тому, что в одном из следующих состояний ко второй
части конструкции для приведения ее к expr будет приме-
нено правило (3), а затем вся полученная конструкция
сведется к expr применением правила (4).
- 20 -
Можно сразу применить к конструкции expr*expr правило
(4), тем самым приведя ее к expr, и без ввода нового
символа перейти в очередное состояние. Такое действие в
разделе 1 было названо сверткой. Использование свертки
в данном состоянии приведет к применению в дальнейшем
правила (3) для свертывания оставшейся части конструк-
ции в expr.
Неоднозначность такого рода будем называть конфликтом
"сдвиг/свертка". (Выше этот конфликт был умышленно показан
на примере выражения, порядок разбора которого существен в
связи с различием приоритетов операций. На самом деле конф-
ликт сдвиг/свертка возникает и при разборе такой строки, как
expr-expr-expr. В этом случае разница в разборе ведет лишь
к трактовке операции "-" как лево- или правоассоциативной.
Однако, как известно, ассоциативность иногда играет важную
роль, например, для операций присваивания, возведения в сте-
пень. Возможен другой вид конфликта, состоящий в выборе
между двумя возможными свертками; будем называть его конф-
ликтом "свертка/свертка". Для примера подобного конфликта
приведем грамматику, задающую десятичную и шестнадцатеричную
форму записи константы:
const: const_10 /*1*/
| const_16 ; /*2*/
const_10: dec_sequence; /*3*/
const_16: hex_sequence 'x'; /*4*/
dec_sequence:digit /*5*/
| dec_sequence digit; /*6*/
hex_sequence:digit /*7*/
| ABCDEF /*8*/
|hex_sequence digit /*9*/
|hex_sequence ABCDEF; /*10*/
ABCDEF : 'A'|'B'|'C'|'D'|'E'|'F';
digit:'0'|'1'|'2'|'3'|'4'|'5'|'6'
|'7'|'8'|'9';
При появлении на входе первой же десятичной цифры (если
с нее начинается последовательность) после ее замены нетер-
миналом digit возникает конфликт между двумя возможными
свертками: к нетерминалу dec_sequence в результате примене-
ния правила (5) и к нетерминалу hex_sequence с помощью пра-
вила (7). Заметим, что эта грамматика, в отличиe от грамма-
тики в предыдущем примере, не позволяет корректно разобрать
какую-либо строку двумя способами и в принципе нетерминал
const определен однозначно. Однако, алгоритм разбора с
просмотром вперед на 1 символ не в состоянии правильно осу-
ществить выбор нужного правила. Следовательно, в этом случае
речь идет о неоднозначности грамматики по отношению к приня-
тому в yacc методу разбора. Поскольку вопрос о принципиаль-
ной неоднозначности грамматики формально неразрешим, будем в
дальнейшем понимать под неоднозначностью невозможность для
- 21 -
анализатора в некоторые моменты разбора выбрать очередное
действие. Каждая ситуация (т.е. появление в некотором состо-
янии некоторой входной лексемы), которая при разборе спо-
собна вызвать конфликт "сдвиг/свертка" или "свертка/
свертка", выявляется yacc уже на этапе построения граммати-
ческого анализатора. При этом yacc выдает сообщение о числе
выявленных конфликтных ситуаций обоих видов, а в выходной
файл y.output (если он формируется) помещается подробное
описание всех конфликтов. Однако, yacc не считает наличие
конфликтов фатальной ошибкой грамматики и строит граммати-
ческий анализатор, заранее разрешая все возможные конфликты
путем выбора в каждой ситуации единственного действия.
При работе yacc используются два способа разрешения
конфликтов. Первый способ действует по умолчанию (т.е. при
отсутствии специальной пользовательской информации) и заклю-
чается в применении следующих двух правил для выбора дейст-
вия в конфликтных ситуациях:
В случае конфликта сдвиг/свертка по умолчанию делается
сдвиг.
В случае конфликта свертка/свертка по умолчанию дела-
ется свертка по тому из конкурирующих правил, которое
задано первым в спецификационном файле.
Грамматический анализатор, построенный с использованием
этих правил, может не обеспечивать "правильного" с точки
зрения пользовательской грамматики разбора. В частности,
для первого из приведенных выше примеров разбор заключался
бы в сворачивании арифметических выражений справа налево без
учета приоритетов операций. Во втором примере в результате
замены первой конструкции digit нетерминалом dec_sequence
все числа, начинающиеся с цифры, разбирались бы как десятич-
ные, а появление одной из букв от A до F или символа "x" в
конце числа неверно трактовалось как ошибка во входном
тексте.
Однако, в ряде ситуаций описанный способ разрешения
конфликтов приводит к нужному результату. Например, рассмот-
рим фрагмент грамматики языка программирования, описывающий
условный оператор:
оператор: if '(' условие ')' оператор /*1*/
|
if '(' условие ')' оператор else
оператор; /*2*/
Входная строка вида:
if(C1) if(C2) S1 else S2
вызвала бы при разборе конфликт сдвиг/свертка в момент
- 22 -
просмотра символа else. Введенная часть строки к этому вре-
мени имеет вид:
if (условие) if (условие) оператор
Если выполнить свертку второй части конструкции по правилу
(1), то строка сведется к:
if (условие) оператор
(Заметим, что применить еще раз правило(1) мешает просмот-
ренный заранее символ else). После ввода конструкции S2 и
замены ее нетерминалом оператор к строке:
if (условие) оператор else оператор
будет применено правило (2). Полученный разбор соответствует
следующей интерпретации входной строки:
if (C1) {if(C2) S1} else S2
При альтернативном подходе в случае применения сдвига в
момент появления else входная строка была бы введена пол-
ностью:
if (условие) if (условие) оператор
else оператор
Ко второй части строки можно применить правило (2), а затем
свернуть полученную конструкцию:
if (условие) оператор
по правилу (1). Такой разбор соответствует второй возможной
интерпретации входной строки:
if (C1) {if(C2) S1 else S2}
Как известно, в большинстве языков программирования принята
именно эта интерпретация (каждый else относится к ближайшему
предшествующему if). Значит, выбор сдвига, осуществляемый по
умолчанию, для данной грамматики верен.
В качестве рекомендации отметим,что применение принципа
умолчания для конфликтов сдвиг/свертка приводит к положи-
тельному результату, если в грамматике принята правоассоциа-
тивная интерпретация соответствующих конструкций и для них
отсутствует понятие приоритета. Что касается конфликтов
свертка/свертка, то стандартный способ их разрешения оказы-
вается полезным только тогда, когда при любых конфликтах
между данными двумя правилами справедлив выбор одного и того
же правила.
- 23 -
В любом случае, если yacc сообщил о наличии конфликтных
ситуаций, пользователь должен тщательно проанализировать
содержательный смысл каждого конфликта и правильность выб-
ранного yacc действия. Вся необходимая для этого информация
содержится в файле y.output, структура которого будет расс-
мотрена ниже. Если оказалось, что конфликты разрешены неу-
довлетворительно, то грамматика должна быть перестроена или
уточнена пользователем. В случае конфликтов свертка/свертка
всегда требуется изменение самих грамматических правил; для
конфликтов сдвиг/свертка есть возможность без перестройки
правил уточнить грамматику путем задания информации о прио-
ритетах и ассоциативности лексем и правил.
В качестве примеров устранения конфликтов путем измене-
ния правил приведем перестроенные варианты рассматривавшихся
выше грамматик. Поскольку исходные конфликтные грамматики
полностью удовлетворяют требованиям генерируемых ими языков,
но содержат недостаточно информации для однозначного раз-
бора, перестройка правил носит уточняющий характер.
Перестроенная грамматика константного арифметического
выражения:
expr: expr1
|
expr '+' expr1
|
expr '-' expr1;
expr1: CONST
|
expr1 '*' CONST
|
expr1 '/' CONST;
Ниже будет приведен также вариант грамматики, полученной из
исходной введением приоритетов (без перестройки правил).
Перестроенная грамматика для задания константы:
const: const_10
| const_16;
const_10: dec_sequence ;
const_16: hex_sequence 'x'
| dec_sequence 'x';
dec_sequence: digit
| dec_sequence digit;
hex_sequence: ABCDEF
| dec_sequence ABCDEF
| hex_sequence ABCDEF
|hex_sequence dec_sequence;
ABCDEF:...
digit:...
- 24 -
Рассмотрим теперь второй из используемых yacc способов раз-
решения конфликтов, базирующийся на задании пользователем
информации о приоритетах и ассоциативности. Отметим предва-
рительно две основные причины конфликтности грамматик:
принципиальная невозможность задать генерируемый язык
бесконфликтной грамматикой;
недостаточность информации для построения однозначного
грамматического разбора.
Грамматики, конфликтные по второй причине, всегда
допускают преобразование правил до полного устранения конф-
ликтов; в случае конфликтов сдвиг/свертка yacc всегда может
построить для этих грамматик корректный разбор путем разре-
шения конфликтов. Для грамматик, конфликтных по причине 1,
попытки разрешения конфликтов не приведут к нужному резуль-
тату. Однако, надо убедиться в том, что конфликтная грамма-
тика действительно отражает входной язык: возможно, конф-
ликты не имеют отношения к этому языку, а вызваны неодноз-
начностью другого, реально описанного языка. Вообще, конф-
ликты стоит рассматривать как повод проверить грамматику на
соответствие языку (хотя последнее не гарантируется и
отсутствием конфликтов). Задание приоритетов для неверной
грамматики не приведет к генерации нужного языка, но может
замаскировать ошибки, сняв вопрос о конфликтах.
Приоритетное разрешение конфликтов сдвиг/свертка сос-
тоит в том, что с обоими действиями yacc ассоциирует приори-
теты (со сдвигом - приоритет лексемы, чтение которой вызы-
вает данный конфликт, со сверткой - приоритет конкурирующего
правила) и выбирает более приоритетное действие. В случае
равенства приоритетов yacc руководствуется при выборе
свойством ассоциативности. Приоритеты и ассоциативность
отдельных лексем (явно) и правил (явно и неявно) задаются
пользователем, все остальные приоритеты считаются неизвест-
ными. yacc использует для разрешения конфликта данный спо-
соб, если известны приоритеты обоих конкурирующих действий.
Поэтому для разрешения ряда конфликтов на приоритетной
основе необходимо установить приоритеты участвующих в них
лексем и правил.
Следует понимать,что задание приоритетов не ведет к
устранению конфликтов и не делает грамматику однозначной. Но
в отличие от конфликтов, разрешаемых yacc по принципу умол-
чания, пользователь получает здесь возможность управлять
разрешением конфликтов. yacc, сообщая общее число конфлик-
тов, не учитывает в нем конфликтов, разрешенных в соответст-
вии с информацией о приоритетах и не включает в выходной
файл y.output описания этих конфликтов.
Приоритеты и ассоциативность лексем задаются в секции
деклараций с помощью директив трех видов:
- 25 -
%left <список_лексем>
%right <список_лексем>
%nonassoc <список_лексем>
Каждая директива приписывает всем перечисленным в списке
лексемам одинаковый приоритет. Директивы %left и %right
одновременно задают соответственно левую или правую ассоциа-
тивность лексем. Директива %nonassoc говорит об отсутствии
у перечисленных лексем свойства ассоциативности. Устанавли-
ваемый директивами приоритет не имеет численного выражения,
а его относительное значение возрастает сверху вниз.
Пример задания приоритетов лексем:
%token OR NOR XOR AND NAND
%right '='
%left OR NOR XOR
%left AND NAND
%left '+' '-'
%left '*' '/'
/* самый низкий приоритет имеет лексема "=",
самый высокий - лексемы "*" и "/"
лексемы само по себе не требует задания ее приоритета или
ассоциативности.
При первом появлении лексемы или литерала в секции дек-
лараций за каждым из них может следовать неотрицательное
целое число, рассматриваемое как номер типа лексемы. По
умолчанию номера типов всех лексеМ определяются yacc следую-
щим образом:
- для литерала номером типа лексемы считается числовое
значение данного литерального символа, рассматриваемого
как однобайтовое целое число;
- лексемы,обозначенные именами, в соответствии с очеред-
ностью их объявления получают последовательные номера,
начиная с 257;
- специальная лексема error, зарезервированная для обра-
ботки ошибок (раздел 7), получает номер типа 256.
Для каждого имени лексемы независимо от того, переопре-
делен ли ее номер пользователем, yacc генерирует в выходном
файле y.tab.c оператор макропрепроцессора
#define <имя_лексемы> <номер_типа>
В случае переопределения номера типа литеральной лек-
семы также формируется оператор #define, например, директива
%left 'z' 258
породит оператор
#define z 258
Заметим, что возможно переопределение номеров лишь для
буквенных литералов.
При вызове yacc с флагом -d последовательность операто-
ров #define помещается также в информационный файл y.tab.h.
Переопределив при необходимости ряд номеров типов
лексем,пользователь должен проверить уникальность номеров у
всех используемых лексем.
- 14 -
7. Декларация имени начального символа
%start <имя_начального_символа>
Директива отменяет действующий по умолчанию выбор в
качестве начального символа нетериминала, определяемого пер-
вым грамматическим правилом.
7.1. Секция программ
В секцию программ помещается описание пользовательских
процедур, которые должны быть включены в генерируемую прог-
рамму грамматического анализа. Любая из определяемых пользо-
вателем программных компонент может находиться в секции
программ спецификационного файла, либо присоединяться на
этапе вызова Си-компилятора для трансляции файла y.tab.c и
компоновки выходной программы. Перечислим процедуры, которые
одним из этих способов должны быть заданы:
- лексический анализатор - функция с именем yylex();
- все процедуры, вызовы которых содержатся в действиях,
связанных с грамматическими правилами;
- главная процедура main() при необходимости заменить ее
стандартный библиотечный вариант, который имеет вид
main() {return (yyparse();}
- процедура обработки ошибок yyerror() - также для замены
библиотечного варианта (его текст приводится ниже).
#include <stdio.h>
yyerror(s) char *s; {
fprintf(stderr, "%s\n", s);}
Для обеспечения корректной работы грамматического ана-
лизатора функция лексического анализа yylex должна быть сог-
ласована с конкретной спецификацией грамматики и удовлетво-
рять определенным требованиям. Основная задача функции yylex
состоит во вводе из входного потока ряда очередных символов
до выявления конструкции, соответствующей одной из лексем, и
возвращении номера типа этой лексемы. Для нелитеральных лек-
сем номером типа может служить объявленное в секции деклара-
ций имя лексемы (с помощью механизма #define yacc обеспечи-
вает замену его нужным номером), в случае литералов номером
типа является числовое значение символа (если оно не было
- 15 -
переопределено). Алгоритм поиска должен заключаться в
попытке нахождения сначала более сложных (нелитеральных)
лексем и лишь при несовпадении ни с одной из них текущих
элементов ввода возвращать номер типа литеральной лексемы
(любой однозначный символ, не начинающий ни одну из возмож-
ных лексем, сам образует лексему).
Приведем текст процедуры лексического анализа, распоз-
нающей идентификаторы и целые числа:
#include <stdio.h>
yylex() {char c;
while ((c=getc(stdin))==' '||c=='\n');
if(c>='0'&&c<='9'){
while((c=getc(stdin))>='0'&&c<='9');
ungetc(c,stdin));
return (CONST);}
if (c>='a'&&c<='z'){
while ((c=getc(stdin))>'a'&&c<='z'
||c>='0'&&c<='9');
ungetc(c,stdin); return (NAME);}
return (c); }
Сложность лексического анализатора зависит от того,
какие структурные единицы взяты за основу при описании грам-
матических правил. Детализовав грамматику до отдельных сим-
волов, можно обойтись простейшим лексическим анализатором,
осуществляющим только их ввод:
yylex() {return (getchar());}
Однако, в этом случае число правил растет, а граммати-
ческий разбор оказывается менее эффективным. Поэтому пользо-
ватель обычно должен найти некоторый компромисс при выборе
набора лексем.
В процедуре лексического анализа кроме выделения лексем
можно предусмотреть некоторую обработку лексем определенных
типов, в частности, запоминание конкретных значений лексем.
Кроме того, эти значения обычно требуется передать граммати-
ческому анализатору. С этой целью нужное значение должно
быть присвоено внешней переменной целого типа с именем yyl-
val. Если функция yylex находится в отдельном файле, то эта
переменная должна быть объявлена:
extern int yylval;
- 16 -
Уточним, что в дальнейшем значением лексемы мы будем
называть значение, присвоенное при ее распознавании перемен-
ной yylval; значение, возвращаемое функцией yylex, является
номером типа лексемы. Примером значения лексемы могут слуить
числовое значение цифры, вычисленное значение константы,
адрес идентификатора в таблице имен (построение таблицы имен
удобно осуществлять лексическим анализатором). Заметим,
что, хотя значение yylval устанавливается с целью использо-
вания его в действиях, непосредственное обращение к переМен-
ной yylval в действии не имеет смысла (поскольку в yylval
всегда находится значение последней выделенной лексемы).
Доступ в действиях к значениям лексем осуществляется с
помощью специального механизма, описанного в разделе 4.5.
7.2. Действия с использованием псевдопеременных
Для обеспечения связи между действиями, а также между
действиями и лексическим анализатором создаваемые yacc грам-
матические анализаторы поддерживают специальный стек, в
котором сохраняются значения лексем и нетерминальных симво-
лов. Значение лексемы автоматически попадает в стек после
ее распознавания лексическим анализатором (напомним, что им
считается текущее значение переменной yylval). После каждой
свертки вычисляется значение нетерминала, заместившего свер-
нутую строку, и помещается в вершину стека; значения элемен-
тов правой части примененного правила перед этим выталкива-
ются из стека. Заметим, что таким образом к моменту свертки
любого правила все значения нетерминалов в правой части ока-
зываются вычисленными в результате сверток. Способ вычисле-
ния значения нетерминала будет рассмотрен ниже.
Описанный механизм не требует вмешательства пользова-
теля и предоставляет ему следующие возможности:
- Использовать в действиях, осуществляемых после свертки
по правилу, значение любого элемента его правой части.
Доступ к этим значениям обеспечивается набором так
называемых псевдопеременных с именами $1,$2,..., где $i
соответствует значению i-го элемента; элементы правой
части правила нумеруются слева направо без различия
лексем и нетерминальных символов, например, в правиле
P_Head: P_name '(' P_list ')';
псевдопеременные $1,$2,$3,$4 относились бы соответст-
венно к P_name, '(', P_list, ')'.
- Формировать в действиях значение, образованного в
результате свертки нетерминала путем присвоения этого
значения псевдопеременной с именем $$. Так, в правиле
- 17 -
expr: expr '+' expr { $$=$1+$3; }
значением нового нетерминала expr станет сумма ранее
вычисленных значений двух других нетерминалов expr.
Eсли в действии не определяется значение переменной $$
(а также если действие отсутствует), значением нетерми-
нала после свертки по умолчанию становится значение
первого элемента правой части, т.е. неявно выполняется
присваивание
$$=$1;
Пример (вычисление значения целого числа)
%token DIGIT
%%
...
CONST: DIGIT
| CONST DIGIT {$$=$1*10+$2;}
...
%%
yylex()
{
char c;
if((c=getchar())>='0'&& c<='9') {
yylval = c-'0';
return (DIGIT);
}
...
}
Здесь при свертке по первому правилу нетерминал CONST
получает значение первой цифры, присвоенное в функции
yylex переменной yylval; при каждой свертке по второму
правилу явно вычисляется значение нового нетерминала
CONST.
Несколько иная ситуация в отношении использования псев-
допеременных имеет место для правил, содержащих действия
внутри правой части. На самом деле yacc интерпретирует пра-
вило вида
: B C {действие 1} D {действие 2}
K {действие 3}
как
: B C EMPTY1 D EMPTY2 K;
и в месте, где вставлено действие, при разборе
- 18 -
осуществляется свертка по пустому правилу, сопровождающаяся
выполнением указанного действия. При этом независимо от
характера действия очередной элемент в стеке значений отво-
дится для хранения значения неявно присутствующего "пустого"
нетерминала. В действии, находящемся в конце правила, согла-
шение о значениях псевдопеременных остается прежним, если
иметь в виду наличие дополнительных символов. В приведенном
выше правиле в действии 3 для доступа к значениям элементов
B, C, D, K следовало бы использовать соответственно псевдо-
переменные $1, $2, $4, $6; псевдоперемнные $3, $5 хранят
результаты действий 1 и 2. В действиях, находящихся внутри
правила, с помощью псевдоперемнных $i доступны значения рас-
положенных левее элементов, а также результаты предшествую-
щих вставленных в тело действий. Результатом внутреннего
действия (т.е. значением неявного нетерминала) является зна-
чение, присвоенное в этом действии псевдопеременной $$, при
отсутствии такого присваивания результат действия не опреде-
лен. Заметим, что присваивание значения псевдопеременной $$
во внутренних действиях не вызывает предварительной уста-
новки значения нетерминала, стоящего в левой части правила:
это значение в любом случае устанавливется только действием
в конце правила или считается равным значению $1.
В нашем примере в действии 1 доступными являются только
значения элементов B и C (им соответствуют псевдопеременные
$1 и $2), а в действии 2 - значения элементов B, C, D и
результат действия 1 с помощью псевдопеременных $1, $2, $4,
$3.
Следующий пример иллюстрирует варианты использования
псевдопеременных:
%token ИМЯ КЛЮЧ1 КЛЮЧ2 КОНЕЦ
. . .
%%
входной_поток: данные КОНЕЦ
{printf("Данные занесены в файл %s\n",$1);};
данные:
ИМЯ {abc = creat($1,0666);}
КЛЮЧ1 КЛЮЧ2 {option($3,$4);}
упр_строка '\n' {converse(0,$5,$6);
write($1,$6,80);}
текст {converse(1,$5,$8);
write($1,$6,$8);
close($1);};
упр_строка: ...
текст : ...
. . .
- 19 -
Управляющая строка и текст преобразуются в соответствии с
заданными ключами и записываются в файл с указанным именем.
Значением нетерминала данные в результате неявного действия
становится значение лексемы ИМЯ (адрес строки с именем файла
присваивается в лексическом анализаторе переменной yylval).
8. Конфликты грамматического разбора
Заданная грамматика является неоднозначной, если
существует входная строка, которая в соответствии с этой
грамматикой может быть разобрана двумя или более различными
способами. Рассмотрим, например, набор правил, описывающих
константное арифметическое выражение:
expr: CONST /*1*/
|
expr '+'expr /*2*/
|
expr '-'expr /*3*/
|
expr '*'expr /*4*/
|
expr '/'expr; /*5*/
Описывая возможность построения выражения из двух выра-
жений, соединенных знаком арифметической операции, правила
неоднозначно определяют путь разбора некоторых входных
строк. Так, строка вида:
expr*expr-expr
допускает два пути разбора, приводящих к различным группи-
ровкам ее элементов:
expr*(expr-expr) и (expr*expr) - expr
С точки зрения работы грамматического анализатора дан-
ная ситуация проявляется в неоднозначности выбора действия
при вводе лексемы "-" в момент, когда разобранная часть
строки приведена к виду expr*expr. Два возможных действия
анализатора состоят в следующем:
Можно ввести следующий символ и без применения правила
подстановки перейти в новое состояние. В разделе 1 мы
назвали такое действие сдвигом. Выбор сдвига приведет к
тому, что в одном из следующих состояний ко второй
части конструкции для приведения ее к expr будет приме-
нено правило (3), а затем вся полученная конструкция
сведется к expr применением правила (4).
- 20 -
Можно сразу применить к конструкции expr*expr правило
(4), тем самым приведя ее к expr, и без ввода нового
символа перейти в очередное состояние. Такое действие в
разделе 1 было названо сверткой. Использование свертки
в данном состоянии приведет к применению в дальнейшем
правила (3) для свертывания оставшейся части конструк-
ции в expr.
Неоднозначность такого рода будем называть конфликтом
"сдвиг/свертка". (Выше этот конфликт был умышленно показан
на примере выражения, порядок разбора которого существен в
связи с различием приоритетов операций. На самом деле конф-
ликт сдвиг/свертка возникает и при разборе такой строки, как
expr-expr-expr. В этом случае разница в разборе ведет лишь
к трактовке операции "-" как лево- или правоассоциативной.
Однако, как известно, ассоциативность иногда играет важную
роль, например, для операций присваивания, возведения в сте-
пень. Возможен другой вид конфликта, состоящий в выборе
между двумя возможными свертками; будем называть его конф-
ликтом "свертка/свертка". Для примера подобного конфликта
приведем грамматику, задающую десятичную и шестнадцатеричную
форму записи константы:
const: const_10 /*1*/
| const_16 ; /*2*/
const_10: dec_sequence; /*3*/
const_16: hex_sequence 'x'; /*4*/
dec_sequence:digit /*5*/
| dec_sequence digit; /*6*/
hex_sequence:digit /*7*/
| ABCDEF /*8*/
|hex_sequence digit /*9*/
|hex_sequence ABCDEF; /*10*/
ABCDEF : 'A'|'B'|'C'|'D'|'E'|'F';
digit:'0'|'1'|'2'|'3'|'4'|'5'|'6'
|'7'|'8'|'9';
При появлении на входе первой же десятичной цифры (если
с нее начинается последовательность) после ее замены нетер-
миналом digit возникает конфликт между двумя возможными
свертками: к нетерминалу dec_sequence в результате примене-
ния правила (5) и к нетерминалу hex_sequence с помощью пра-
вила (7). Заметим, что эта грамматика, в отличиe от грамма-
тики в предыдущем примере, не позволяет корректно разобрать
какую-либо строку двумя способами и в принципе нетерминал
const определен однозначно. Однако, алгоритм разбора с
просмотром вперед на 1 символ не в состоянии правильно осу-
ществить выбор нужного правила. Следовательно, в этом случае
речь идет о неоднозначности грамматики по отношению к приня-
тому в yacc методу разбора. Поскольку вопрос о принципиаль-
ной неоднозначности грамматики формально неразрешим, будем в
дальнейшем понимать под неоднозначностью невозможность для
- 21 -
анализатора в некоторые моменты разбора выбрать очередное
действие. Каждая ситуация (т.е. появление в некотором состо-
янии некоторой входной лексемы), которая при разборе спо-
собна вызвать конфликт "сдвиг/свертка" или "свертка/
свертка", выявляется yacc уже на этапе построения граммати-
ческого анализатора. При этом yacc выдает сообщение о числе
выявленных конфликтных ситуаций обоих видов, а в выходной
файл y.output (если он формируется) помещается подробное
описание всех конфликтов. Однако, yacc не считает наличие
конфликтов фатальной ошибкой грамматики и строит граммати-
ческий анализатор, заранее разрешая все возможные конфликты
путем выбора в каждой ситуации единственного действия.
При работе yacc используются два способа разрешения
конфликтов. Первый способ действует по умолчанию (т.е. при
отсутствии специальной пользовательской информации) и заклю-
чается в применении следующих двух правил для выбора дейст-
вия в конфликтных ситуациях:
В случае конфликта сдвиг/свертка по умолчанию делается
сдвиг.
В случае конфликта свертка/свертка по умолчанию дела-
ется свертка по тому из конкурирующих правил, которое
задано первым в спецификационном файле.
Грамматический анализатор, построенный с использованием
этих правил, может не обеспечивать "правильного" с точки
зрения пользовательской грамматики разбора. В частности,
для первого из приведенных выше примеров разбор заключался
бы в сворачивании арифметических выражений справа налево без
учета приоритетов операций. Во втором примере в результате
замены первой конструкции digit нетерминалом dec_sequence
все числа, начинающиеся с цифры, разбирались бы как десятич-
ные, а появление одной из букв от A до F или символа "x" в
конце числа неверно трактовалось как ошибка во входном
тексте.
Однако, в ряде ситуаций описанный способ разрешения
конфликтов приводит к нужному результату. Например, рассмот-
рим фрагмент грамматики языка программирования, описывающий
условный оператор:
оператор: if '(' условие ')' оператор /*1*/
|
if '(' условие ')' оператор else
оператор; /*2*/
Входная строка вида:
if(C1) if(C2) S1 else S2
вызвала бы при разборе конфликт сдвиг/свертка в момент
- 22 -
просмотра символа else. Введенная часть строки к этому вре-
мени имеет вид:
if (условие) if (условие) оператор
Если выполнить свертку второй части конструкции по правилу
(1), то строка сведется к:
if (условие) оператор
(Заметим, что применить еще раз правило(1) мешает просмот-
ренный заранее символ else). После ввода конструкции S2 и
замены ее нетерминалом оператор к строке:
if (условие) оператор else оператор
будет применено правило (2). Полученный разбор соответствует
следующей интерпретации входной строки:
if (C1) {if(C2) S1} else S2
При альтернативном подходе в случае применения сдвига в
момент появления else входная строка была бы введена пол-
ностью:
if (условие) if (условие) оператор
else оператор
Ко второй части строки можно применить правило (2), а затем
свернуть полученную конструкцию:
if (условие) оператор
по правилу (1). Такой разбор соответствует второй возможной
интерпретации входной строки:
if (C1) {if(C2) S1 else S2}
Как известно, в большинстве языков программирования принята
именно эта интерпретация (каждый else относится к ближайшему
предшествующему if). Значит, выбор сдвига, осуществляемый по
умолчанию, для данной грамматики верен.
В качестве рекомендации отметим,что применение принципа
умолчания для конфликтов сдвиг/свертка приводит к положи-
тельному результату, если в грамматике принята правоассоциа-
тивная интерпретация соответствующих конструкций и для них
отсутствует понятие приоритета. Что касается конфликтов
свертка/свертка, то стандартный способ их разрешения оказы-
вается полезным только тогда, когда при любых конфликтах
между данными двумя правилами справедлив выбор одного и того
же правила.
- 23 -
В любом случае, если yacc сообщил о наличии конфликтных
ситуаций, пользователь должен тщательно проанализировать
содержательный смысл каждого конфликта и правильность выб-
ранного yacc действия. Вся необходимая для этого информация
содержится в файле y.output, структура которого будет расс-
мотрена ниже. Если оказалось, что конфликты разрешены неу-
довлетворительно, то грамматика должна быть перестроена или
уточнена пользователем. В случае конфликтов свертка/свертка
всегда требуется изменение самих грамматических правил; для
конфликтов сдвиг/свертка есть возможность без перестройки
правил уточнить грамматику путем задания информации о прио-
ритетах и ассоциативности лексем и правил.
В качестве примеров устранения конфликтов путем измене-
ния правил приведем перестроенные варианты рассматривавшихся
выше грамматик. Поскольку исходные конфликтные грамматики
полностью удовлетворяют требованиям генерируемых ими языков,
но содержат недостаточно информации для однозначного раз-
бора, перестройка правил носит уточняющий характер.
Перестроенная грамматика константного арифметического
выражения:
expr: expr1
|
expr '+' expr1
|
expr '-' expr1;
expr1: CONST
|
expr1 '*' CONST
|
expr1 '/' CONST;
Ниже будет приведен также вариант грамматики, полученной из
исходной введением приоритетов (без перестройки правил).
Перестроенная грамматика для задания константы:
const: const_10
| const_16;
const_10: dec_sequence ;
const_16: hex_sequence 'x'
| dec_sequence 'x';
dec_sequence: digit
| dec_sequence digit;
hex_sequence: ABCDEF
| dec_sequence ABCDEF
| hex_sequence ABCDEF
|hex_sequence dec_sequence;
ABCDEF:...
digit:...
- 24 -
Рассмотрим теперь второй из используемых yacc способов раз-
решения конфликтов, базирующийся на задании пользователем
информации о приоритетах и ассоциативности. Отметим предва-
рительно две основные причины конфликтности грамматик:
принципиальная невозможность задать генерируемый язык
бесконфликтной грамматикой;
недостаточность информации для построения однозначного
грамматического разбора.
Грамматики, конфликтные по второй причине, всегда
допускают преобразование правил до полного устранения конф-
ликтов; в случае конфликтов сдвиг/свертка yacc всегда может
построить для этих грамматик корректный разбор путем разре-
шения конфликтов. Для грамматик, конфликтных по причине 1,
попытки разрешения конфликтов не приведут к нужному резуль-
тату. Однако, надо убедиться в том, что конфликтная грамма-
тика действительно отражает входной язык: возможно, конф-
ликты не имеют отношения к этому языку, а вызваны неодноз-
начностью другого, реально описанного языка. Вообще, конф-
ликты стоит рассматривать как повод проверить грамматику на
соответствие языку (хотя последнее не гарантируется и
отсутствием конфликтов). Задание приоритетов для неверной
грамматики не приведет к генерации нужного языка, но может
замаскировать ошибки, сняв вопрос о конфликтах.
Приоритетное разрешение конфликтов сдвиг/свертка сос-
тоит в том, что с обоими действиями yacc ассоциирует приори-
теты (со сдвигом - приоритет лексемы, чтение которой вызы-
вает данный конфликт, со сверткой - приоритет конкурирующего
правила) и выбирает более приоритетное действие. В случае
равенства приоритетов yacc руководствуется при выборе
свойством ассоциативности. Приоритеты и ассоциативность
отдельных лексем (явно) и правил (явно и неявно) задаются
пользователем, все остальные приоритеты считаются неизвест-
ными. yacc использует для разрешения конфликта данный спо-
соб, если известны приоритеты обоих конкурирующих действий.
Поэтому для разрешения ряда конфликтов на приоритетной
основе необходимо установить приоритеты участвующих в них
лексем и правил.
Следует понимать,что задание приоритетов не ведет к
устранению конфликтов и не делает грамматику однозначной. Но
в отличие от конфликтов, разрешаемых yacc по принципу умол-
чания, пользователь получает здесь возможность управлять
разрешением конфликтов. yacc, сообщая общее число конфлик-
тов, не учитывает в нем конфликтов, разрешенных в соответст-
вии с информацией о приоритетах и не включает в выходной
файл y.output описания этих конфликтов.
Приоритеты и ассоциативность лексем задаются в секции
деклараций с помощью директив трех видов:
- 25 -
%left <список_лексем>
%right <список_лексем>
%nonassoc <список_лексем>
Каждая директива приписывает всем перечисленным в списке
лексемам одинаковый приоритет. Директивы %left и %right
одновременно задают соответственно левую или правую ассоциа-
тивность лексем. Директива %nonassoc говорит об отсутствии
у перечисленных лексем свойства ассоциативности. Устанавли-
ваемый директивами приоритет не имеет численного выражения,
а его относительное значение возрастает сверху вниз.
Пример задания приоритетов лексем:
%token OR NOR XOR AND NAND
%right '='
%left OR NOR XOR
%left AND NAND
%left '+' '-'
%left '*' '/'
/* самый низкий приоритет имеет лексема "=",
самый высокий - лексемы "*" и "/"