Сдвиг / уменьшение конфликта несмотря на правила приоритета

Question

Язык, для которого я пишу парсер, имеет три соответствующие конструкции: ord оператор, представленный TOK_ORD, который преобразует символьные выражения в целочисленные выражения, и [] а также ., которые используются для индекса и доступа к полю, соответственно, как в C.

Вот выдержка из моих правил старшинства:

%right TOK_ORD
%left  PREC_INDEX PREC_MEMBER

В моей грамматике нетерминал expr, который представляет выражения. Вот некоторые соответствующие фрагменты из грамматики (TOK_IDENT это регулярное выражение для идентификаторов, определенных в моем .l файл):

expr     : TOK_ORD expr                         { /* semantic actions */ }
         | variable                             { /* semantic actions */ }
         ;
variable : expr '[' expr ']' %prec PREC_INDEX   { /* semantic actions */ }
         | expr '.' TOK_IDENT %prec PREC_MEMBER { /* semantic actions */ }
         ;

Вот информация о конфликте сдвига / уменьшения из выходного файла зубров:

state 61

42 expr: expr . '=' expr
43     | expr . TOK_EQ expr
44     | expr . TOK_NE expr
45     | expr . TOK_LT expr
46     | expr . TOK_LE expr
47     | expr . TOK_GT expr
48     | expr . TOK_GE expr
49     | expr . '+' expr
50     | expr . '-' expr
51     | expr . '*' expr
52     | expr . '/' expr
53     | expr . '%' expr
57     | TOK_ORD expr .
72 variable: expr . '[' expr ']'
73         | expr . '.' TOK_IDENT

'['  shift, and go to state 92
'.'  shift, and go to state 93

'['       [reduce using rule 57 (expr)]
'.'       [reduce using rule 57 (expr)]
$default  reduce using rule 57 (expr)

Состояния 92 и 93, для справки:

state 92

72 variable: expr '[' . expr ']'

TOK_FALSE      shift, and go to state 14
TOK_TRUE       shift, and go to state 15
TOK_NULL       shift, and go to state 16
TOK_NEW        shift, and go to state 17
TOK_IDENT      shift, and go to state 53
TOK_INTCON     shift, and go to state 19
TOK_CHARCON    shift, and go to state 20
TOK_STRINGCON  shift, and go to state 21
TOK_ORD        shift, and go to state 22
TOK_CHR        shift, and go to state 23
'+'            shift, and go to state 24
'-'            shift, and go to state 25
'!'            shift, and go to state 26
'('            shift, and go to state 29

expr       go to state 125
allocator  go to state 44
call       go to state 45
callargs   go to state 46
variable   go to state 47
constant   go to state 48


state 93

73 variable: expr '.' . TOK_IDENT

Я не понимаю, почему существует конфликт сдвига / уменьшения. Моя грамматика четко определяет индекс и доступ к полям, чтобы иметь более высокий приоритет, чем ordНо этого, похоже, недостаточно.

Если вам интересно, да, это домашнее задание, но задание уже сдано и оценено. Я возвращаюсь назад и пытаюсь исправить конфликты сдвига / уменьшения, чтобы я мог лучше понять, что происходит.

Answer 1

Разрешение приоритетов конфликтов сдвига / уменьшения работает путем сравнения приоритета производства (или сокращения, если вы предпочитаете) с приоритетом токена (токена предварительного просмотра).

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

Как сказано в руководстве для бизонов:

… Разрешение конфликтов работает путем сравнения приоритета рассматриваемого правила с приоритетом маркера прогнозирования. Если приоритет токена выше, выбор заключается в смещении. Если приоритет правила выше, выбор состоит в том, чтобы уменьшить.

Теперь вы определяете приоритет двух variable производства с использованием явных объявлений:

variable : expr '[' expr ']' %prec PREC_INDEX   { /* semantic actions */ }
         | expr '.' TOK_IDENT %prec PREC_MEMBER { /* semantic actions */ }

Но эти постановки никогда не участвуют в конфликтах сдвига / уменьшения. Когда конец любого из variable правила достигнуты, нет возможности сдвига. Наборы элементов, в которых эти произведения могут быть уменьшены, не имеют сдвиговых действий.

В состоянии, которое содержит конфликт сдвига / уменьшения, конфликт между потенциальным сокращением:

 expr: TOK_ORD expr

и возможные сдвиги с использованием жетонов предпросмотра . а также [, Эти конфликты будут разрешены путем сравнения приоритетов TOK_ORD сокращение с приоритетами жетонов предпросмотра . а также [ соответственно. Если эти токены не имеют объявленных приоритетов, то конфликт сдвига / уменьшения не может быть разрешен с использованием механизма приоритетов.

В этом случае, однако, я ожидал бы, что будет большое количество конфликтов сдвига / уменьшения в других состояниях, где есть варианты уменьшить бинарный оператор (такой как expr: expr '+' expr) или сдвинуть . / [ продлить самый правый expr. Поэтому, если нет таких сдвигов / сокращений, объяснение более сложное, и мне нужно было бы увидеть намного больше грамматики, чтобы понять это.