Логический запрос / выражение в конкретное синтаксическое дерево

Question

Я создаю форму поиска, которая допускает логические выражения, например: "foo AND bar" или "foo AND NOT bar".

Существует ли библиотека для PHP, Ruby или Java, которая может преобразовывать логические выражения в конкретное синтаксическое дерево?

(я мог бы написать свой собственный лексер / парсер, но я скорее использую что-то проверенное и проверенное)

РЕДАКТИРОВАТЬ: Чтобы уточнить, я не анализирую аритмические выражения. Он будет использоваться для анализа полнотекстовых запросов, допускающих логические операторы.

Answer 1

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

Он включает в себя инструмент для анализа выраженийвне строки ввода:

Expression<String> expr = ExprParser.parse("( ( (! C) | C) & A & B)")

Вы также можете сделать довольно простое упрощение:

Expression<String> simplified = RuleSet.simplify(expr);
System.out.println(expr);

дает

(A & B)

Надеюсь, это поможет.

Answer 2

Я рекомендую Верх дерева . Это миниязык, который генерирует парсер для вашей PEG ( Грамматика выражения синтаксического анализа ). С ним легче работать, чем с грамматикой LALR, и он более мощный, чем синтаксический анализатор с рекурсивным спуском (т. Е. Он может выполнять некоторые операции просмотра более чем на один символ).

Хотя Treetop не так сложен, для начала есть несколько простых примеров. Вы найдете их в древовидных примерах threedaymonk .

Answer 3

Для большинства каркасов синтаксического анализатора одной из стандартных вводных грамматик обычно является синтаксический анализатор математических выражений.Он анализирует такие вещи, как 3+4*5-(6/-7) и т. Д. Некоторые учебники могут пойти еще дальше и показать, как построить синтаксическое дерево и оценить выражение.

Типичная грамматика выражения boolean обычно прямо аналогична математическому выражению.грамматика в этой записи инфикса.

• AND и OR - это двоичные операторы (т.е. они принимают 2 операнда), так же как + и *
• NOT является унарным оператором (требуется 1 операнд), так же как и унарный -
• Некоторые операторы имеют более высокий приоритет, чем другие
• Вы можете использовать (…) для группировки подвыражений

Следовательно, вы должны иметь возможность просмотреть руководство по калькулятору большинства пакетов синтаксического анализатора и адаптировать его к вашей проблеме.Фактически, во многих отношениях boolean синтаксический анализ выражений проще, например:

• В математических выражениях оператор - перегружен (может быть двоичным или унарным)
• Некоторыеоператор, например возведение в степень, является ассоциативным справа

В boolean грамматике выражения, как правило, операторы не перегружены, и все является левоассоциативным.

Ссылки

• antlr.org - Руководство по калькулятору

Answer 4

просто наткнулся на это, ища спутниковый решатель ... http://jboolexpr.sourceforge.net/ может быть именно то, что вам нужно.

Answer 5

$patterns=array(
   '/\band\b/i',
   '/\bor\b/i',
   '/\bfoo\b/i',
   '/\bbar\b/i',
   '/\bnot\b/i');
$replace=array(
   '*',  // value for 'and'
   '+',  // value for 'or'
   '1',  // value for 'foo'
   '0',  // value for 'bar'
   '!'); // value for 'not'
$expression="foo AND NOT bar";
$result=eval(preg_replace($pattern, $replace, $expression));

Вы можете легко добавить свои собственные факты, он будет автоматически обрабатывать скобки и приоритет.Было бы неплохо подумать о том, как вы будете обрабатывать неожиданные входные данные в выражении $ (подсказка, что замененная версия должна содержать только 1, 0, +, *, (,) и!)

C.