Как я могу написать однозначную грамматику Nearley для булевых операторов поиска - PullRequest
Новая
       55

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

1 голос
/ 24 сентября 2019

Контекст

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

Цель

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

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

  • брюки
  • брюки Иноски
  • прыжковые домкраты

Попытка

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

query -> 
    statement
  | statement "AND" statement

statement -> .:+

Проблема

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

Вопрос

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

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

1 Ответ

1 голос
/ 26 сентября 2019

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

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

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

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

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

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

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

...