YACC - Yet Another Compiler Compiler

[ Содержание ] [ Предыдущая ] [ Следующая ]

Глава 6. Приоритеты

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

expr : expr OP expr

expr : UNARY expr

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

Приоритеты и ассоциативности приписываются токенам в секции объявлений. Это делается с помощью последовательности строк, начинающихся с ключевых слов Yacc-а %left, %right и %nonasoc, за которыми следует список токенов. Все токены на одной строке, считаются имеющими одинаковый уровень приоритета и ассоциативность; строки перечислены в порядке возрастающего приоритета или силы связывания. Таким образом,

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

описывает приоритет и ассоциативность четырех арифметических операторов. Плюс и минус левоассоциативны и имеют меньший приоритет, чем звездочка и дробь, которые также являются левоассоциативными. Ключевое слово %right используется для описания правоассоциативных операторов, а ключевое слово %nonassoc - для описания таких операторов, как .LT. в Фортране, которые не могут ассоциироваться друг с другом; таким образом,

A .LT. B .LT. C

недопустимо в Фортране и такой оператор должен описываться с помощью ключевого слова %nonassoc в Yacc-е. В качестве примера поведения этих объявлений, описание

%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 изменяет уровень приоритета, связанный с конкретным грамматическим правилом. %prec появляется сразу после тела грамматического правила перед действием или закрывающей точкой с запятой и завершается именем токена или литерала. Hапример, чтобы придать унарному минусу тот же приоритет, что умножению, правила должны выглядеть как:

%left  '+' '-'
%left  '*' '/'
%%
expr : expr '+' expr
     | expr '-' expr
     | expr '*' expr
     | expr '/' expr
     | '-' expr %prec '*'
     | NAME
     ;

Токен, объявленный с помощью %left, %right и %nonassoc также не должен, хотя может, также объявляться с помощью %token.

Приоритеты и ассоциативность иcпользуются Yacc-ом для разрешения конфликтов при разборе; они вызывают действие правил устранения двусмысленноси. Формально правила работают следующим образом:

Приоритеты и ассоциативности записываются для тех токенов и литералов, имеющих таковые.
Приоритет и ассоциативность связываются с каждым грамматическим правилом; это приоритет и ассоциативность последнего токена или литерала в теле правила. Конструкция %prec при использовании переопределяет значение по умолчанию. Hекоторые грамматические правила могут не иметь связанных приоритета и ассоциативности.
При существовании конфликта понижение/понижение или сдвиг/понижение и либо входной символ или грамматическое правило не имеют приоритета или ассоциативности, тогда используются два правила устранения двусмысленности, приведенных в начале секции и сообщается о конфликте.
Если есть конфликт сдвиг/понижение и грамматическое правило и входной символ имеют связанные приоритет и ассоциативность, то конфликт разрешается в пользу действия (сдвига или понижения) с наибольшим приоритетом. Если приоритеты одинаковы, используется ассоциативность; левая ассоциативность предполагает понижение, правая ассоциативность - сдвиг, а отсутствие ассоциативности - ошибку.

Конфликты, разрешенные с помощью приоритета не включаются в число конфликтов сдвиг/понижение и понижение/понижение, о которых сообщает Yacc. Это означает, что ошибки в указании приоритетов могут скрывать ошибки во входной грамматике; следует умеренно использовать приоритеты и в основном использовать их в "стиле поваренной книги", пока не приобретете некоторый опыт. y.output очень полезен при решении, делает ли парсер то, что требуется.

[ Содержание ] [ Предыдущая ] [ Следующая ]

c 1998-2000 SoloTony (Antonio Solo)

solotony@mail.ru