Разобрать выражение для его компонентов и подкомпонентов.

Question

Мне нужно разобрать выражение, такое как: neg(and(X,Y))

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

LOAD X;
LOAD Y;
EXEC and;
EXEC neg;

Но пока машинный код не является проблемой, как я могу разобрать / разбить мою входную строку выражения на все его подвыражения?

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

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

private boolean evaluateExpression(String expression) {

    int brackets = 0;
    int beginIndex = -1;
    int endIndex = -1;

    for (int i = 0; i < expression.length(); i++) {
        if (expression.charAt(i) == '(') {
            brackets++;

            if (brackets == 0) {
                endIndex = i;
                System.out.println("the first expression ends at " + i);
            }
        }
        if (expression.charAt(i) == ')') {
            brackets--;

            if (brackets == 0) {
                endIndex = i;
                System.out.println("the first expression ends at " + i);
            }
        }
    }
    // Check for 1st bracket
    for (int i = 0; i < expression.length(); i++) {
        if (expression.charAt(i) == '(') {
            beginIndex = i;
            break;
        }
    }

    String subExpression = expression.substring(beginIndex, endIndex);
    System.out.println("Sub expression: " + subExpression);

    evaluateExpression(subExpression);

    return false;

}

Я просто ищу базовое решение, оно должно только сделать: и, или, нег

Answer 1

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

Вы можете создать не зависящий от контекста грамматику, которая представляет этот язык выражений, и использовать синтаксический анализатор CFG для его анализа.

Одним из существующих Java-инструментов, который делает это (и более), является JavaCC, хотя здесь это может быть излишним.
Еще один алгоритм для анализа предложений с использованием CFG - это CYK, который довольно легко программировать и использовать.

---

Здесь CFG, представляющий доступные выражения:

S -> or(S,S)
S -> and(S,S)
S -> not(S)
S -> x | for each variable x

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

Answer 2

На самом деле, если вы хотите, чтобы ваш синтаксический анализатор был достаточно сильным, чтобы справляться с большинством случаев, вы хотели бы использовать токенизатор (в java реализован класс токенизатора), чтобы сначала маркировать строку, а затем попытаться распознать каждое выражение, храня операнды и операторы в древовидная структура, затем оцените их рекурсивно.

Если вы хотите иметь дело только с некоторыми простыми ситуациями, не забудьте использовать рекурсию, которая является основной частью ~

Answer 3

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

Processing items left to right the tree would be populated like this

1arg_fcall(neg)
        2arg_fcall(and)
            Load Y                      
            Load X

Now we can recursively visit this tree bottom to top to get
Load X
Load Y
EXEC and //on X and Y
EXEC neg //on result of and