Уравнение (выражение) парсер с приоритетом?

Question

Я разработал синтаксический анализатор уравнений с использованием простого стекового алгоритма, который будет обрабатывать двоичные (+, -, |, &, *, / и т. Д.) Операторы, унарные (!) Операторы и скобки.

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

Так что сейчас "1 + 11 * 5" возвращает 60, а не 56, как можно было бы ожидать.

Хотя это подходит для текущего проекта, я хочу иметь программу общего назначения, которую можно использовать для более поздних проектов.

Отредактировано для ясности:

Что такое хороший алгоритм для анализа уравнений с приоритетом?

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

Грамматика:

Я не понимаю вопроса грамматики - я написал это от руки. Это достаточно просто, и я не вижу необходимости в YACC или Bison. Мне просто нужно вычислить строки с помощью таких уравнений, как «2 + 3 * (42/13)».

Язык:

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

Пример кода

Я разместил тестовый код для простого синтаксического анализатора выражений , о котором я говорил выше. Требования проекта изменились, и поэтому мне никогда не приходилось оптимизировать код для производительности или пространства, так как он не был включен в проект. Это в оригинальной многословной форме, и должно быть легко понятно. Если я сделаю что-то еще с точки зрения приоритета операторов, я, вероятно, выберу макрос взломать , потому что он по простоте соответствует остальной части программы. Если я когда-нибудь буду использовать это в реальном проекте, я пойду на более компактный / быстрый парсер.

Смежный вопрос

Умный дизайн математического парсера?

-Adam

Answer 1

Это зависит от того, насколько "общим" вы хотите, чтобы оно было.

Если вы хотите, чтобы он был действительно действительно общим, таким как возможность разбора математических функций, а также, например, sin (4 + 5) * cos (7 ^ 3), вам, вероятно, понадобится дерево разбора .

В котором я не думаю, что здесь можно вставить полную реализацию. Я бы посоветовал вам проверить одну из печально известных " Книга Дракона ".

Но если вы просто хотите, чтобы поддержка приоритетов , то вы могли бы сделать это, сначала преобразовав выражение в постфиксную форму, в которой алгоритм, который вы можете копировать и вставлять, должен быть доступен из google. или я думаю, что вы можете сами кодировать его с помощью двоичного дерева.

Когда он у вас есть в форме постфикса, с этого момента это будет просто, поскольку вы уже понимаете, как помогает стек.

Answer 2

Я разместил на своем веб-сайте исходники для ультракомпактного (1 класс, <10 КиБ) <a href="http://tech.dolhub.com/Code/MathEval" rel="nofollow noreferrer"> Java Math Evaluator . Это парсер рекурсивного спуска того типа, который вызвал черепной взрыв для плаката с принятым ответом.

Он поддерживает полный приоритет, скобки, именованные переменные и функции с одним аргументом.

Answer 3

Я нашел это в PIClist об алгоритме Маневрового двора :

Гарольд пишет:

Я помню, как читал давным-давно алгоритм, который преобразовал алгебраические выражения в RPN для легкой оценки. Каждое значение инфикса или оператор или скобки были представлены вагоном на трек. Один тип машины откололся на другую трассу, а другой продолжал движение прямо вперед. Я не помню детали (очевидно!), Но всегда думал, что это было бы интересно, чтобы код. Это вернулся, когда я писал 6800 (не 68000) код сборки.

Это «алгоритм маневрового двора» и это то, что большинство машинных парсеров использовать. Смотрите статью о разборе в Wikipedia. Простой способ кодировать Алгоритм маневрового двора должен использовать два стеки. Одним из них является стек "толчок" и другой «уменьшить» или «результат» стек. Пример:

pstack = () // пусто rstack = () вход: 1 + 2 * 3 приоритет = 10 // низший уменьшить = 0 // не уменьшать

начало: токен '1': номер, положить в pstack (push) токен '+': isoperator установить приоритет = 2, если приоритет < previous_operator_precedence затем Reduce () // см. ниже положить «+» в токен pstack (push) '2': isnumber, положить в pstack (push) токен '*': isoperator, установить приоритет = 1, положить в pstack (push) // проверяем приоритет как // над токеном '3': isnumber, вставляем pstack (push) конец ввода, нужно уменьшить (цель пустого pstack) уменьшить () // сделано

чтобы уменьшить попсовые элементы от толчка сложить и положить их в результат стек, всегда поменяйте местами 2 лучших Pstack, если они имеют форму 'оператор' 'номер':

pstack: '1' '+' '2' '' '3' rstack: () ... pstack: () rstack: '3' '2' '' '1' '+'

если бы выражение было:

1 * 2 + 3

тогда триггер уменьшения будет иметь было чтение токена '+' который имеет более низкий приоритет, чем «*» уже нажал, так что было бы сделано:

pstack: '1' '' '2' rstack: () ... pstack: () rstack: '1' '2' ''

, затем нажмите «+», затем «3» и затем, наконец, уменьшилось:

pstack: '+' '3' rstack: '1' '2' '' ... pstack: () rstack: '1' '2' '' '3' '+'

Итак, короткая версия: push-номера, при нажатии операторы проверяют приоритет предыдущего оператора. Если бы он был выше, чем у оператора это должно быть выдвинуто сейчас, сначала уменьшить, затем протолкнуть ток оператор. Чтобы справиться с парнями, просто сохраните приоритет «предыдущего» оператор и поставить отметку на pstack что говорит алгоритм уменьшения прекратить уменьшать при решении изнутри парной пары. Закрытие парен вызывает сокращение, как и конец ввода, а также удаляет открытые родословная от pstack, и восстанавливает «предыдущую операцию» приоритет, чтобы анализ мог продолжаться после близкого парня, где он оставил выкл. Это можно сделать с помощью рекурсии или без (подсказка: используйте стек для хранения предыдущий приоритет, когда столкнувшись с '(' ...). обобщенная версия это использовать реализован генератор парсера Алгоритм маневрового двора, например с помощью YACC или бизон или Taccle (аналог Tcl Yacc).

Peter

-Adam

Answer 4

я выпустил синтаксический анализатор выражений на основе алгоритма Shijnting Yard Дейкстры в соответствии с лицензией Apache 2.0 :

http://projects.congrace.de/exp4j/index.html

Answer 5

Другим ресурсом для разбора приоритетов является запись оператора-приоритета *1001* в Википедии. Охватывает алгоритм маневрового двора Дейкстры и алгоритм альтернативного дерева, но, что более важно, охватывает действительно простой алгоритм замены макросов, который может быть тривиально реализован перед любым неосведомленным синтаксическим анализатором предшествования:

#include <stdio.h>
int main(int argc, char *argv[]){
  printf("((((");
  for(int i=1;i!=argc;i++){
    if(argv[i] && !argv[i][1]){
      switch(argv[i]){
      case '^': printf(")^("); continue;
      case '*': printf("))*(("); continue;
      case '/': printf("))/(("); continue;
      case '+': printf(")))+((("); continue;
      case '-': printf(")))-((("); continue;
      }
    }
    printf("%s", argv[i]);
  }
  printf("))))\n");
  return 0;
}

Вызовите его как:

$ cc -o parenthesise parenthesise.c
$ ./parenthesise a \* b + c ^ d / e
((((a))*((b)))+(((c)^(d))/((e))))

Что удивительно своей простотой и очень понятно.

Answer 6

Я реализовал парсер рекурсивного спуска в Java в проекте MathEclipse Parser . Его также можно использовать в качестве модуля Google Web Toolkit

Answer 7

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

Answer 8

Python-решение с использованием pyparsing можно найти здесь . Разбор инфиксной записи с различными операторами с приоритетом является довольно распространенным явлением, поэтому pyparsing также включает в себя построитель выражений infixNotation (ранее operatorPrecedence). С его помощью вы можете легко определить логические выражения, используя, например, «И», «ИЛИ», «НЕ». Или вы можете расширить свою четырехфункциональную арифметику, чтобы использовать другие операторы, такие как! для факториала, или «%» для модуля, или добавьте операторы P и C для вычисления перестановок и комбинаций. Вы можете написать инфиксный парсер для матричной нотации, который включает обработку операторов '-1' или 'T' (для инверсии и транспонирования). Пример operatorPrecedence синтаксического анализатора с 4 функциями (с добавлением '!' Для развлечения): здесь , а более полнофункциональный анализатор и оценщик - здесь .

Answer 9

Я написал синтаксический анализатор выражений на F # и написал об этом здесь . Он использует алгоритм маневрового двора, но вместо преобразования из инфикса в RPN я добавил второй стек для накопления результатов вычислений. Он правильно обрабатывает приоритет операторов, но не поддерживает унарные операторы. Я написал это для изучения F #, а не для изучения парсинга выражений.

Answer 10

Вот простое рекурсивное решение, написанное на Java. Обратите внимание, что он не обрабатывает отрицательные числа, но вы можете добавить это, если хотите:

public class ExpressionParser {

public double eval(String exp){
    int bracketCounter = 0;
    int operatorIndex = -1;

    for(int i=0; i<exp.length(); i++){
        char c = exp.charAt(i);
        if(c == '(') bracketCounter++;
        else if(c == ')') bracketCounter--;
        else if((c == '+' || c == '-') && bracketCounter == 0){
            operatorIndex = i;
            break;
        }
        else if((c == '*' || c == '/') && bracketCounter == 0 && operatorIndex < 0){
            operatorIndex = i;
        }
    }
    if(operatorIndex < 0){
        exp = exp.trim();
        if(exp.charAt(0) == '(' && exp.charAt(exp.length()-1) == ')')
            return eval(exp.substring(1, exp.length()-1));
        else
            return Double.parseDouble(exp);
    }
    else{
        switch(exp.charAt(operatorIndex)){
            case '+':
                return eval(exp.substring(0, operatorIndex)) + eval(exp.substring(operatorIndex+1));
            case '-':
                return eval(exp.substring(0, operatorIndex)) - eval(exp.substring(operatorIndex+1));
            case '*':
                return eval(exp.substring(0, operatorIndex)) * eval(exp.substring(operatorIndex+1));
            case '/':
                return eval(exp.substring(0, operatorIndex)) / eval(exp.substring(operatorIndex+1));
        }
    }
    return 0;
}

}