Как заставить flex попробовать второе самое длинное соответствующее регулярное выражение?

Question

Этот вопрос может показаться немного запутанным.Я использую Flex для передачи токенов Бизону.

Мне нужно поведение, чтобы Flex соответствовал самому длинному регулярному выражению и передавал этот токен (он ДЕЙСТВИТЕЛЬНО работает так), но если этот токен не работает с грамматикой, то он совпадает со вторым самым длинным регулярным выражениеми передает этот жетон.

Я изо всех сил пытаюсь придумать способ создать такое поведение.Как я мог это сделать?

Чтобы уточнить, например, скажем, у меня есть два правила:

"//"    return TOKEN_1;
"///"   return TOKEN_2;

Учитывая строку "///", я бы хотел, чтобы она сначала прошла TOKEN_2 (это делает).Если TOKEN_2 не соответствует грамматике, указанной в Bison, она передает TOKEN_1 (что также допустимо).

Как я могу создать это поведение?

Answer 1

В flex вы можете иметь правило, которое пытается что-то сделать, но терпит неудачу и пробует второе лучшее правило, используя макрос REJECT:

REJECT направляет сканер, чтобы перейти к «второе лучшее» правило, которое соответствует входу (или префикс ввода). Правило выбрано как описанный выше в разделе «Как сопоставляется вход», и yytext и yyleng настроены соответствующим образом. Это может либо тот, который соответствует столько текста, сколько изначально выбранное правило, но позже пришло гибкое входной файл или файл, который соответствует меньшему количеству текста.

(источник: Страница руководства по Flex ).

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

Обратите внимание, что flex будет работать медленнее при использовании REJECT, потому что ему необходимо поддерживать дополнительную логику, чтобы "отступать" к худшим совпадениям в любой точке. Я бы предложил использовать это, только если нет другого способа исправить вашу проблему.

Answer 2

Это сложно для бизона / яка, так как он не возвращает назад. Даже если вы используете генератор парсера с возвратом, например btyacc , это не поможет, если только он не вернется назад через лексер (что, вероятно, потребует генератора парсера со встроенным лексером).

Я бы предложил, чтобы лексер сразу распознал косую черту, а затем специально косую черту и вернул другой токен:

\//\/       return SLASH;
\/          return '/';   /* not needed if you have the catch-all rule: */
.           return *yytext;

Теперь вам нужно «собрать» жетоны с несколькими слэшами как нетерминалы в грамматике.

single_slash:  SLASH | '/' ;
double_slash:  SLASH SLASH | SLASH '/' ;
triple_slash:  SLASH SLASH SLASH | SLASH SLASH '/' ;

Однако теперь вы, скорее всего, обнаружите, что у вас есть конфликты в грамматике из-за того, что одного обращения с токеном недостаточно. Вы можете решить их с помощью btyacc или опции %glr-parser от bison.

Answer 3

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

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

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

Другими словами, вы не можете использовать действия с ошибками Yacc для запуска поиска с возвратом другого анализа.

Answer 4

Извините, но вы не можете этого сделать. Я на самом деле не уверен, сколько изгиб говорит с бизоном. Я знаю, что есть режим для анализа REPL, и я знаю, что есть другой режим, который анализирует все это.

Вы должны включить правило. Например, вместо // и / вы пишете правило, которое принимает ///, затем другое, которое предполагает /// означает // /. Но это становится грязным, и я сделал это только в конкретном случае в моем коде.