Как сравнить приоритетность токенов с различной ассоциативностью в yacc? - PullRequest
Новая
       12

Как сравнить приоритетность токенов с различной ассоциативностью в yacc?

0 голосов
/ 01 августа 2011 
%left TOKEN1
%left TOKEN2
%right TOKEN3

В приведенном выше примере TOKEN2 имеет более высокий приоритет, чем TOKEN1, но как насчет TOKEN3?

Гарантируется ли, что TOKEN3 имеет более высокий приоритет, чем TOKEN2 илинет?

Ответы [ 2 ]

1 голос
/ 02 августа 2011

Это объявляет, что TOKEN3 имеет более высокий приоритет, чем TOKEN2, но из-за ваших комментариев вы можете неправильно понять, что означает «более высокий приоритет» для yacc / bison.

В yacc / bison все, что имеет значение для этого приоритета, разрешаетсяконфликты сдвига / уменьшения - всякий раз, когда возникает конфликт уменьшения сдвига, генератор анализатора сравнивает приоритет токена, который должен быть сдвинут, с приоритетом правила, которое должно быть уменьшено, и делает то, что имеет более высокий приоритет (если они одинаковы,тогда% left одобряет уменьшение, а% right благоприятствует сдвигу).Это все.В частности, приоритет не имеет никакого влияния на конфликты уменьшения / уменьшения.

Таким образом, в случае чего-то вроде висячего другого, приоритет токена ELSE будет сравниваться с приоритетом if-with-no-остальное производство.Если последний имеет более высокий приоритет, он будет уменьшен, что противоположно тому, что диктует большинство языков (и здравый смысл).Он также не сможет работать с анализатором LALR (1) (хотя он будет работать с анализатором LR (1)) из-за способа объединения состояний.

edit

Вы можете следовать рекомендации Айманаду, чтобы попытаться заставить вещи работать, но это не сработает вообще в yacc (из-за того, что это LALR (1)) и не будет работать даже анализатор LR (1).Чтобы понять почему (и понять, почему это ДЕЙСТВИТЕЛЬНО не имеет смысла), рассмотрим входные данные 

if (a) if (b) c else d else e

Обратите внимание, что d может быть произвольно большим {} -замкнутым блоком.Теперь, если вы связываете первый else с первым if (что произойдет без произвольного просмотра), когда парсер перейдет ко второму else, у него не будет if для сопоставления си вы получите синтаксическую ошибку.С анализатором LALR (1) из-за слияния состояний эта проблема возникает даже с 

if (a) b else c

. В этом случае, если вы дадите еще более низкий приоритет, он уменьшит if (a) b как-with-no-else, оставляя висячее другое вызывать синтаксическую ошибку.

Если вы действительно хотите делать то, что говорите, вам нужно использовать метод синтаксического анализа, который может выполнить произвольный просмотр (например,с обратным отслеживанием), или может недетерминированно анализировать альтернативы для устранения неоднозначностей (таких как GLR).Но это обычно приводит к языку, который не понятен читателям, так как значение небольшого фрагмента кода может зависеть от того, что появляется в коде намного позже.

0 голосов
/ 05 января 2012

Вы можете установить явные приоритеты, которые могут вам помочь

ЕСЛИ ЕЩЕ ПРИМЕР 

%nonassoc LOWER_THAN_ELSE

%nonassoc ELSE

%%
stmt   :    IF expr stmt %prec LOWER_THAN_ELSE ;
       |    IF expr stmt ELSE stmt;
...