Как разобрать этот тип выражений?

Question

У меня нет фона компиляторов, поэтому я не уверен, что это сообщение в этой области. Существуют ли стандартные методы для анализа таких выражений? (Say, вкладка показывает глубину)

And 
    A + B = 1 
    C + D = 1 
    Or 
     P + Q = 1 
     K = 1 
    And 
     Q = 1 
     R = 2 

Должен быть проанализирован как:

((A+B=1) AND (C+D=1) AND ((P+Q=1) OR (K=1)) AND ((Q=1) AND (R=2))) 

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

Любые предложения по простому способу достижения этого?

Answer 1

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

Один эффективный подход называется «сверху вниз приоритет оператора», а может быть, и «приоритет оператора», и синтаксический анализ «приоритет». Вот некоторые хорошие источники, объясняющие подход подробно:

• Pratt parsing (а также original paper)

• Douglas Крокфорд-х take на нем

• Pythonist-х take на нем

• в Java version

Действительно аккуратная вещь - это то, как мало кода на самом деле.

Ключевые понятия:

• Приставка против инфикса против mixfix

• старшинства: это 3 + 4 * 5 разобранным, как (3 + 4) * 5 или 3 + (4 * 5)?

• ассоциативность: есть x - y - z разобран как x - (y - z) или (x - y) - z?

совпадению, я только учусь этот материал в последнее время и в конечном итоге писать статью на моем блоге о подобном подходе к оператору разборе, который вы можете найти here. В моем подходе я имею дело с операциями infix, prefix, postfix и mixfix (т. Е. ? :); приоритеты и ассоциативности указаны в таблицах; Я использую стек для отслеживания операторов, операнды которых еще не найдены. Затем синтаксический анализатор создает дерево разбора, где каждый узел является подвыражением.