Happy/YACC уменьшается, когда он должен смещаться

Question

Я работаю над парсером и очень расстроен.В языке мы можем иметь такое выражение:

new int[3][][]

или

new int[3]

Большая часть его анализируется правильно, за исключением пустых массивов в конце.В моем парсере у меня есть:

Expression : int
             char
             null
             (...many others...)
             new NewExpression

и тогда NewExpression:

NewExpression : NonArrayType '[' Expression ']' EmptyArrays
              | NonArrayType '[' Expression ']' 

а затем EmptyArrays — это одна или несколько пустых фигурных скобок. Если EmptyArrays извлекает пустую строку, он добавляет 20 конфликтов сдвига/сокращения:

EmptyArrays : EmptyArrays EmptyArray
            | EmptyArray
EmptyArray  : '[' ']'

Однако, когда я смотрю в .info файл для парсера, я получаю это:

State 214¬
¬
▸   NewExpression -> NonArrayType lbrace Expression rbrace . EmptyArrays    (rule 80)¬
▸   NewExpression -> NonArrayType lbrace Expression rbrace .    (rule 81)¬
¬
▸   dot            reduce using rule 81¬
▸   ';'            reduce using rule 81¬
▸   ','            reduce using rule 81¬
▸   '+'            reduce using rule 81¬
▸   '-'            reduce using rule 81¬
▸   '*'            reduce using rule 81¬
▸   '/'            reduce using rule 81¬
▸   '<'            reduce using rule 81¬
▸   '>'            reduce using rule 81¬
▸   '<='           reduce using rule 81¬
▸   '>='           reduce using rule 81¬
▸   '=='           reduce using rule 81¬
▸   '!='           reduce using rule 81¬
▸   ')'            reduce using rule 81¬
▸   '['            reduce using rule 81    --I expect this should shift
▸   ']'            reduce using rule 81¬
▸   '?'            reduce using rule 81¬
▸   ':'            reduce using rule 81¬
▸   '&&'           reduce using rule 81¬
▸   '||'           reduce using rule 81

Однако я ожидаю, что если мы находимся в состоянии 214 и видим левую скобку, нам следует переместить ее в стек и продолжить анализ EmptyArrays.

Я не совсем уверен, что происходит, потому что, когда я удаляю все лишнее из багажа (например), начиная анализ с NewExpression, дополнительные скобки анализируются правильно.Выражение, утверждение или любой нетерминал в грамматике не может начинаться с левой скобки.Тем более, что у меня есть аналогичное правило для операторов if/else, которое генерирует конфликт сдвига/сокращения, но выбирает сдвиг, если следующий токен является else (эта проблема хорошо документирована).

Можете ли вы помочь мне понять, что происходит не так?Я очень ценю вашу помощь, я действительно пытаюсь разобраться в проблеме.

Answer 1

Вероятно, у вас установлен приоритет для '[' и/или ']' примерно так: %left '[' что вызывает такое поведение.Удалите это объявление приоритета, и это обнаружит конфликт сдвига/сокращения, который у вас есть.Что касается конфликта сдвига/сокращения, у вас, вероятно, тоже есть правило:

Expression: Expression '[' Expression ']'

для доступа к массиву.Проблема в том, что, поскольку NewExpression является Expression за ним может следовать такой индекс, и при просмотре опережающего просмотра '[' он не может определить, является ли это началом индексного выражения или началом EmptyArray - для этого потребуется предварительный просмотр с двумя токенами.

В этом конкретном случае вы могли бы попробовать заставить лексер выполнить дополнительный предварительный просмотр, необходимый здесь, и распознать [] как один токен.