Существует одна распространенная ситуация, в которой приведенных выше правил разрешения конфликтов недостаточно: это распознавание арифметических выражений. Большинство используемых конструкций естественно описываются с помощью понятия предшествования операторов и левой или правой ассоциативности. Оказывается, что неоднозначная грамматика с правилами однозначности приводит к построению распознавателей, работающих быстрее, нежели распознаватели, созданные по однозначной грамматике. Основой этого подхода служит запись всех правил для бинарных и унарных операций в виде
expr: expr OP expr
expr: UNARY expr
При этом получается сильно неоднозначная грамматика с большим количеством конфликтов. В качестве правила однозначности задается предшествование для всех операций и ассоциативность бинарных операций. Этой информации достаточно для разрешения конфликтов и построения распознавателя, понимающего предшествование и ассоциативность.
Предшествование и ассоциативность связываются с лексемами в разделе определений. Это выполняется с помощью ключевых слов %left, %right и %noassoc, за которыми идет список лексем. Все
лексемы на одной строке обладают одним уровнем предшествования и ассоциативности. Строки перечисляются в порядке возрастания приоритета. Таким образом:
%left '+' '-'
%left '*' '/'
определяют предшествование и ассоциативность четырех арифметических операций. Плюс и минус имеют левую ассоциативность и меньший приоритет, чем звездочка и дробная черта. Ключевое слово %right описывает правую ассоциативность, ключевое слово %noassoc описывает операторы, аналогичные оператору .LT. ФОРТРАНА, которые нельзя использовать в выражении подряд (A.LT.B.LT.C). Приведем в качестве примера следующее описание:
%right '='
%left '+' '-' %left '*' '/'
%%
expr: expr'='expr | expr '+' expr | expr '-' expr | expr '*' expr | expr '/' expr | NAME ;
Если на вход подается строка
a=b=c*d-e-f*g
она будет распознана следующим образом:
a=(b=(((c*d)-e)-(f*g)))
При использовании этого механизма приоритет выше у унарных операций. Иногда унарная и бинарная операции имеют одинаковый синтаксис, но разный приоритет. Примером может служить минус: унарный минус имеет такую же силу, как и умножение, тогда как приоритет бинарного минуса ниже приоритета умножения. Ключевое слово %prec меняет уровень приоритета, связанный с данным правилом. Оно ставится непосредственно после тела правила перед действием или завершающим символом `;', после него идет имя лексемы или литерала. Это приводит к тому, что приоритет правила становится равным приоритету указанной лексемы или литерала. Например, чтобы приоритеты унарного минуса и умножения совпадали, строки могут выглядеть следующим образом:
%left '+' '-'
%left '*' '/'
%%
expr: expr'='expr | expr '+' expr | expr '-' expr | expr '*' expr | expr '/' expr | '-' expr %prec '*'| NAME;
Лексемы, указанные в аргументах директив %left, %right и %noassoc не обязательно, хотя и не запрещено указывать в директиве %token. Предшествование и ассоциативность используются yacc для разрешения конфликтов с помощью правил однозначности. Формально, правила работают следующим образом:
- Для соответствующих лексем и литералов записывается предшествование и ассоциативность.
- С каждым грамматическим правилом связывается предшествование и ассоциативность: они совпадают с предшествованием и ассоциативностью последнего литерала или лексемы в теле правила. Конструкция %prec переопределяет правила по умолчанию. Для некотрых правил предшествование и ассоциативность могут отсутствовать.
- При наличии конфликтов свертка-свертка или сдвиг-свертка при отсутствии либо у входного символа, либо у правила предшествования или ассоциативности, применяются описанные ранее правила однозначности. Также сообщается обо всех конфликтах.
- При конфликте сдвиг-свертка и наличии предшествования и ассоциативности как у правила, так и у входного символа, конфликт разрешается в пользу действия (сдвига или свертки), чей приоритет выше. Если приоритеты одинаковы, применяется ассоциативность: левая ассоциативность подразумевает свертку, права сдвиг. Отсутствие ассоциативности считается ошибкой.
Конфликты, разрешенные по приоритетам, в число сообщаемых yacc конфликтов не попадают. Это означает, что ошибки при задании предшествования могут скрыть ошибки во входной спецификации. Лучше всего использовать задание предшествования так, как сказано в руководстве, пока вы не приобретете достаточного опыта. Для выяснения, что же на самом деле делает распознаватель, очень полезен файл y.output.
