Как я могу написать недвусмысленную грамматику для логических операторов поиска

Question

Контекст

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

Цель

Я хотел бы написать грамматику, которая может анализировать строку запроса, содержащую логические операторы (например, AND, OR, NOT). Давайте использоватьAND для этого вопроса как тривиального случая.

Например, грамматика должна распознавать эти примерные строки как допустимые:

• брюки
• штаны И носки
• прыжки гнезда

Попытка

Моя наивная попытка выглядит примерно так:

query -> 
    statement
  | statement "AND" statement

statement -> .:+

Эта проблема

Приведенная выше попытка грамматики неоднозначна, потому что .:+будет соответствовать буквально любой строке. Я действительно хочу, чтобы первое условие соответствовало любой строке, которая не содержитANDв этом. Как только появится "И", я хочу ввести только второе условие.

Вопрос

Как я могу обнаружить эти два разных случая без двусмысленной грамматики?

Я беспокоюсь, что упускаю что-то фундаментальное; Я могу представить массу вариантов использования, в которых мы хотим, чтобы произвольный текст был разделен известными операторами.

Answer 1

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

Где-то вы захотите определить свой базовый набор токенов, по крайней мере, что-то вроде \S+ а затем как эти жетоны могут быть составлены.

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

Похоже, Неарли - это синтаксический анализатор Эрли, и, как отмечается в википедии, он эффективен для левой рекурсии.

Это всего лишь риск предположить, но что-то вроде этого может, по крайней мере, привести вас к соединению.

CONJUNCTION -> AND | OR
STATEMENT -> TOKENS | (TOKENS CONJUNCTION STATEMENT)
TOKENS -> [^()]+

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