Уравнение (выражение) синтаксический анализатор с приоритетом?

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

Говорят, Вы хотите оценить 1 + 2 * 3 + 4. Интуитивно, Вы "знаете", что необходимо сделать 2 * 3 первых, но как Вы получаете этот результат? Ключ должен понять при сканировании строки слева направо оценку оператора, когда оператор, который следует , это имеет более низкое (или равный) приоритет. В контексте примера вот то, что Вы хотите сделать:

1. Взгляд на: 1 + 2, ничего не делайте.
2. Теперь взгляд 1 + 2 * 3, все еще ничего не делайте.
3. Теперь взгляд 1 + 2 * 3 + 4, теперь Вы знаете, что 2 * 3 имеет быть оцененным, потому что следующий оператор имеет более низкий приоритет.

, Как Вы реализуете это?

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

Возвращение к примеру, это работает как это:

Н = [] операция в секунду = []

• Read 1. N = [1], операция в секунду = []
• Read +. N = [1], операция в секунду = [+]
• Read 2. N = [1 2], операция в секунду = [+]
• Read *. N = [1 2], операция в секунду = [+ *]
• Read 3. N = [1 2 3], операция в секунду = [+ *]
• Read +. N = [1 2 3], операция в секунду = [+ *]
  • Pop 3, 2 и выполняется 2 * 3 и продвигает результат на N. N = [1 6], операция в секунду = [+]
  • + левоассоциативна, таким образом, Вы хотите появиться 1, 6 прочь также и выполниться +. N = [7], операция в секунду = [].
  • Наконец продвигают [+] на стопку оператора. N = [7], операция в секунду = [+].
• Read 4. N = [7 4]. Операция в секунду = [+].
• Вы закончены от входа, таким образом, Вы хотите освободить стеки теперь. На который Вы получите результат 11.

Там, это не так трудно, не так ли? И это не делает вызовов ни к каким грамматикам или парсерам-генераторам.

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

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

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

Я нашел это на PIClist о алгоритм Сортировочной станции :

записи Harold:

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

Это - "алгоритм сортировочной станции", и это - то, что использует большинство синтаксических анализаторов машины. См. статью о парсинге в Википедии. Простой способ кодировать алгоритм сортировочной станции состоит в том, чтобы использовать два стека. Каждый - стопка "нажатия" и другой стопка "уменьшения" или "результата". Пример:

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

, запустите: маркер '1': isnumber, вставленный в pstack (нажатие) маркер '+ ': isoperator устанавливают precedence=2 если приоритет < previous_operator_precedence тогда уменьшают ()//, посмотрите ниже помещенного '+' в pstack (нажатие) маркер '2': isnumber, вставленный в pstack (нажатие) маркер '* ': isoperator, набор precedence=1, вставленный в pstack (нажатие)//проверяют приоритет как//выше маркера '3': isnumber, вставленный в pstack (нажатие) конец входа, должен уменьшить (целью является пустой pstack), уменьшают ()//сделанный

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

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

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

1*2+3

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

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

и затем продвинутый '+' и затем '3' и затем наконец уменьшенный:

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

, Таким образом, короткая версия: продвиньте числа, когда продвижение операторов проверит приоритет предыдущего оператора. Если это было выше, чем оператор, который должен быть продвинут теперь, сначала уменьшить, затем продвинуть текущий оператор. Для обработки parens просто сохраняют приоритет 'предыдущего' оператора и помещают метку на pstack, который говорит уменьшать алгоритму прекращать уменьшать при решении внутренней части paren пары. Закрытие paren инициировало сокращение, как делает конец входа, и также удаляет открытую метку paren из pstack и восстанавливает 'предыдущую операцию' приоритет, настолько анализирующий, может продолжиться после завершения paren, где это кончило. Это может быть сделано с рекурсией или без (подсказка: используйте стек для хранения предыдущего приоритета при обнаружении' ('...). Обобщенная версия этого должна использовать реализованный алгоритм сортировочной станции парсера-генератора, f.ex. использующий yacc или бизона или taccle (tcl аналог yacc).

Peter

-Adam

Я отправил источник для крайнего компактного (1 класс, < 10 кибибайт) Математическое Средство анализа Java на моем веб-сайте. Это - синтаксический анализатор с рекурсивным спуском типа, который вызвал черепной взрыв для плаката принятого ответа.

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

Существует ли язык, который Вы хотите использовать? ANTLR позволит Вам сделать это с точки зрения Java. У Adrian Kuhn есть превосходное рецензия о том, как записать исполняемую грамматику в Ruby; на самом деле его примером является почти точно Ваш пример арифметического выражения.

Помогло бы, могли ли Вы описать грамматику, Вы в настоящее время используете для синтаксического анализа. Кажется, что проблема могла бы заключаться там!

Редактирование:

то, что Вы не понимаете вопроса о грамматике и что 'Вы записали, это вручную' очень вероятно объясняет, почему у Вас есть проблемы с выражениями формы '1+11*5' (т.е. с приоритетом оператора). Гугление для 'грамматики для арифметических выражений', например, должно привести к некоторым хорошим указателям. Такая грамматика не должна быть сложной:

<Exp> ::= <Exp> + <Term> |
          <Exp> - <Term> |
          <Term>

<Term> ::= <Term> * <Factor> |
           <Term> / <Factor> |
           <Factor>

<Factor> ::= x | y | ... |
             ( <Exp> ) |
             - <Factor> |
             <Number>

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

я предлагаю, чтобы Вы взглянули на этот поток, например.

Почти все введения в грамматики/парсинг рассматривают арифметические выражения как пример.

Примечание, что использование грамматики нисколько не подразумевает использование определенного инструмента ( а-ля Yacc, Бизон...). Действительно, Вы несомненно уже используете следующую грамматику:

<Exp>  :: <Leaf> | <Exp> <Op> <Leaf>

<Op>   :: + | - | * | /

<Leaf> :: <Number> | (<Exp>)

(или что-то вроде вида), не зная это!

Давным-давно, я составил свой собственный алгоритм парсинга, который я не мог найти ни в каких книгах по парсингу (как Книга Дракона). Смотря на указатели на алгоритм Сортировочной станции, я действительно вижу подобие.

приблизительно 2 года назад, я сделал сообщение об этом, вместе с исходным кодом Perl, на http://www.perlmonks.org/?node_id=554516 . Это легко к порту на другие языки: первая реализация, которую я сделал, была в ассемблере Z80.

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

Обновление , поскольку больше людей может читать (или работать) JavaScript, я повторно реализовал свой синтаксический анализатор в JavaScript, после того, как код был реорганизован. Целый синтаксический анализатор находится под 5k кода JavaScript (приблизительно 100 строк для синтаксического анализатора, 15 строк для функции обертки) включая сообщение об ошибке и комментарии.

можно найти живую демонстрацию в http://users.telenet.be/bartl/expressionParser/expressionParser.html .

// operator table
var ops = {
   '+'  : {op: '+', precedence: 10, assoc: 'L', exec: function(l,r) { return l+r; } },
   '-'  : {op: '-', precedence: 10, assoc: 'L', exec: function(l,r) { return l-r; } },
   '*'  : {op: '*', precedence: 20, assoc: 'L', exec: function(l,r) { return l*r; } },
   '/'  : {op: '/', precedence: 20, assoc: 'L', exec: function(l,r) { return l/r; } },
   '**' : {op: '**', precedence: 30, assoc: 'R', exec: function(l,r) { return Math.pow(l,r); } }
};

// constants or variables
var vars = { e: Math.exp(1), pi: Math.atan2(1,1)*4 };

// input for parsing
// var r = { string: '123.45+33*8', offset: 0 };
// r is passed by reference: any change in r.offset is returned to the caller
// functions return the parsed/calculated value
function parseVal(r) {
    var startOffset = r.offset;
    var value;
    var m;
    // floating point number
    // example of parsing ("lexing") without aid of regular expressions
    value = 0;
    while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
    if(r.string.substr(r.offset, 1) == ".") {
        r.offset++;
        while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
    }
    if(r.offset > startOffset) {  // did that work?
        // OK, so I'm lazy...
        return parseFloat(r.string.substr(startOffset, r.offset-startOffset));
    } else if(r.string.substr(r.offset, 1) == "+") {  // unary plus
        r.offset++;
        return parseVal(r);
    } else if(r.string.substr(r.offset, 1) == "-") {  // unary minus
        r.offset++;
        return negate(parseVal(r));
    } else if(r.string.substr(r.offset, 1) == "(") {  // expression in parens
        r.offset++;   // eat "("
        value = parseExpr(r);
        if(r.string.substr(r.offset, 1) == ")") {
            r.offset++;
            return value;
        }
        r.error = "Parsing error: ')' expected";
        throw 'parseError';
    } else if(m = /^[a-z_][a-z0-9_]*/i.exec(r.string.substr(r.offset))) {  // variable/constant name        
        // sorry for the regular expression, but I'm too lazy to manually build a varname lexer
        var name = m[0];  // matched string
        r.offset += name.length;
        if(name in vars) return vars[name];  // I know that thing!
        r.error = "Semantic error: unknown variable '" + name + "'";
        throw 'unknownVar';        
    } else {
        if(r.string.length == r.offset) {
            r.error = 'Parsing error at end of string: value expected';
            throw 'valueMissing';
        } else  {
            r.error = "Parsing error: unrecognized value";
            throw 'valueNotParsed';
        }
    }
}

function negate (value) {
    return -value;
}

function parseOp(r) {
    if(r.string.substr(r.offset,2) == '**') {
        r.offset += 2;
        return ops['**'];
    }
    if("+-*/".indexOf(r.string.substr(r.offset,1)) >= 0)
        return ops[r.string.substr(r.offset++, 1)];
    return null;
}

function parseExpr(r) {
    var stack = [{precedence: 0, assoc: 'L'}];
    var op;
    var value = parseVal(r);  // first value on the left
    for(;;){
        op = parseOp(r) || {precedence: 0, assoc: 'L'}; 
        while(op.precedence < stack[stack.length-1].precedence ||
              (op.precedence == stack[stack.length-1].precedence && op.assoc == 'L')) {  
            // precedence op is too low, calculate with what we've got on the left, first
            var tos = stack.pop();
            if(!tos.exec) return value;  // end  reached
            // do the calculation ("reduce"), producing a new value
            value = tos.exec(tos.value, value);
        }
        // store on stack and continue parsing ("shift")
        stack.push({op: op.op, precedence: op.precedence, assoc: op.assoc, exec: op.exec, value: value});
        value = parseVal(r);  // value on the right
    }
}

function parse (string) {   // wrapper
    var r = {string: string, offset: 0};
    try {
        var value = parseExpr(r);
        if(r.offset < r.string.length){
          r.error = 'Syntax error: junk found at offset ' + r.offset;
            throw 'trailingJunk';
        }
        return value;
    } catch(e) {
        alert(r.error + ' (' + e + '):\n' + r.string.substr(0, r.offset) + '<*>' + r.string.substr(r.offset));
        return;
    }    
}

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

Я предложил бы обмануть и использовать Алгоритм Сортировочной станции . Это - легкое средство записи простого синтаксического анализатора типа калькулятора и имеет приоритет во внимание.

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

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

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

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

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

, Когда у Вас есть он в постфиксной форме, тогда это - кусок пирога с тех пор, так как Вы уже понимаете, как стек помогает.

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

#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))))

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

Задумывались ли вы об использовании Boost Spirit ? Это позволяет вам писать EBNF-подобные грамматики на C ++ следующим образом:

group       = '(' >> expression >> ')';
factor      = integer | group;
term        = factor >> *(('*' >> factor) | ('/' >> factor));
expression  = term >> *(('+' >> term) | ('-' >> term));

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

http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

Очень хорошее объяснение различных подходов:

• Распознавание рекурсивного спуска
• Алгоритм маневровой станции
• Классическое решение
• Восхождение на приоритетность

Написано простым языком и псевдокодом.

Мне нравится лазание по приоритету.