Операционная система UNIX. Руководство программиста


         

СТАРШИНСТВО ОПЕРАЦИЙ


Есть ситуация, в которой приведенные выше методы разрешения конфликтов не подходят. Имеется в виду разбор арифметических выражений. Большинство конструкций, обычно используемых в арифметических выражениях, можно естественным образом описать при помощи понятия уровней старшинства (приоритетов) операций и информации о левой или правой ассоциативности. Применяя данный механизм, можно использовать неоднозначные грамматики с соответствующими правилами разрешения неоднозначностей для порождения алгоритмов разбора, которые быстрее и легче задавать, чем алгоритмы, построенные из однозначных грамматик. Основная идея заключается в том, чтобы записать грамматические правила для всех требуемых бинарных и унарных операций в виде

expr : expr OP expr

или

expr : UNARY expr

В результате получается неоднозначная грамматика с очень большим числом конфликтов. В качестве метода разрешения неоднозначностей пользователь специфицирует приоритеты (степень связывания) всех операций и ассоциативность бинарных операций. Этой информациии достаточно, чтобы дать возможность yacc'у разрешить конфликты и построить алгоритм разбора, реализующий заданные приоритеты и ассоциативности.

Приоритеты и ассоциативности связываются с лексемами в секции определений. Это делается в группе строк, начинающихся с ключевых слов yacc'а %left, %right или %nonassoc, за которыми следуют списки лексем. Считается, что все лексемы в одной строке имеют одни и те же приоритет и ассоциативность; строки указываются в порядке возрастания приоритета. Так, строки

%left '+' '-' %left '*' '/'

задают приоритет и ассоциативность четырех арифметических операций. '+' и '-' левоассоциативны и имеют меньший приоритет, чем также левоассоциативные '*' и '/'. Для описания правоассоциативных операций используется ключевое слово %right, а для описания операций, подобных операции .LT. в Фортране, которые не являются ассоциативными, - ключевое слово %nonassoc. Например, выражение

A .LT. B .LT. C

некорректно в Фортране; поэтому такую операцию следует описать в yacc при помощи ключевого слова %nonassoc. Действие названных ключевых слов иллюстрирует спецификация



Содержание  Назад  Вперед