Парсер логических выражений

Question

Я пытаюсь создать синтаксический анализатор логических выражений для таких выражений, как: ((VariableA -> VariableB) И НЕ VariableC) Парсер должен иметь возможность возвращать, является ли результат истинным или ложным для заданных значений переменных.

В основном выражения будут содержать только переменные, логические операторы (или, косвенно, эквивалентность, отрицание и скобки).

Я хотел бы спросить, как лучше всего реализовать такой синтаксический анализатор (с использованием дерева AST или обратной польской нотации)? Или, может быть, уже существуют парсеры с открытым исходным кодом, которые могут выполнить эту работу?

Answer 1

На какой язык вы ориентируетесь?

Если вы хотите создать парсер, возможно ANTLR подойдет вам. Первоначально он основан на Java, но у него есть генераторы для разных языков (я использую его, например, для генерации синтаксического анализатора C #), и его не так уж сложно найти. У него есть хороший редактор (ANTLRWorks), который позволяет тестировать грамматику, что является хорошим плюсом.

Answer 2

Я бы использовал RPN на вашем месте. Это должно сэкономить вам немного времени при разборе, и алгоритм должен быть таким же простым, как нажатие и извлечение стека значений, когда приходят операторы. Вам также не придется дурачиться с круглыми скобками, что должно упростить жизнь. Единственным недостатком является то, что большинство людей не знакомы с постфиксной (AKA RPN) нотацией.

Возможно, с стеком будет проще работать, чем с деревом.

Только мои 2 ¢:)

Answer 3

Вы видели http://ncalc.codeplex.com?

Это расширяемое, быстрое (например, имеет собственный кэш) позволяет вам предоставлять пользовательские функции и переменные во время выполнения путем обработки событий EvaluateFunction / EvaluateParameter. Примеры выражений, которые он может анализировать:

Выражение e = новое выражение («Round (Pow (Pi, 2) + Pow ([Pi2], 2) + X, 2)»);

e.Parameters ["Pi2"] = новое выражение ("Pi * Pi"); e.Parameters ["X"] = 10;

e.EvaluateParameter + = делегат (имя строки, аргументы ParameterArgs) { если (имя == "Пи") args.Result = 3,14; };

Debug.Assert (117.07 == e.Evaluate ()); Он также обрабатывает Unicode и многие типы данных изначально. Он поставляется с файлом рога, если вы хотите изменить грамматику. Существует также форк, который поддерживает MEF для загрузки новых функций.

Answer 4

Если вы работаете в Python, попробуйте этот синтаксический анализатор / оценщик выражений , написанный как pyparsing , в качестве отправной точки.

Answer 5

Звучит как домашнее задание: -)

Сначала вы должны определить свой язык рекурсивно.

Переменная - это правильно сформированная форма (WFF)

если X является WFF, то не X является WFF

если X и Y - WFF, то (X -> Y) - WFF

если X и Y - WFF, тогда (X и Y -) WFF

Как только грамматика определена, используйте LEX или Flex или эквивалент для Java или ваш предпочитаемый язык для написания обычного сканера.

Используйте YACC или Bison или эквивалент для написания потомственного рекурсивного парсера.

Позже добавьте атрибуты к грамматике, чтобы получить оценку выражения, которое вы хотите оценить, потомственным рекурсивным способом.

Answer 6

Я уверен, что уже есть инструменты, которые делают это (логическая оценка), но я не смог найти ни одного. Если вы используете такой инструмент, как Bison (YACC, для C) или ANTLR (генерирует несколько языков, но использует Java), вам не придется сильно беспокоиться о разборе. Coco / R - это еще один генератор синтаксических анализаторов, который может генерировать много разных языков. Если вы хотите сделать это самостоятельно, я бы использовал RPN или префиксную нотацию (которая, я думаю, проще, чем RPN). Это значительно упростит анализ, но будет раздражать ваших пользователей.