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

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

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

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

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

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

Возвращаясь к примеру, он работает следующим образом:

Северный = [ ] Оперативник = [ ]

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

Ну вот, это ведь не так уж и сложно, правда? И он не делает никаких обращений к каким-либо грамматикам или генераторам синтаксического анализатора.

Трудный путь

Вам нужен рекурсивный парсер спуска .

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

1+11*5

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

Все это кажется настолько болезненным даже для попытки объяснить, особенно с добавлением бессилия C. Видите ли, после разбора 11, если бы вместо этого * был фактически a+, вам пришлось бы отказаться от попытки сделать термин и вместо этого разобрать сам 11 как фактор. Моя голова уже взрывается. Это возможно с рекурсивной приличной стратегией, но есть и лучший способ...

Легкий (правильный) путь

Если вы используете инструмент GPL, такой как Bison, вам, вероятно, не нужно беспокоиться о проблемах лицензирования, так как код C, сгенерированный bison, не покрывается GPL (IANAL, но я уверен, что инструменты GPL не заставляют GPL генерировать code/binaries;, например, Apple компилирует код, например, Aperture с GCC, и они продают его без необходимости GPL указанного кода).

Скачать Bison (или что-то эквивалентное, ANTLR и т.д.).

Обычно есть некоторый пример кода, который вы можете просто запустить bison и получить нужный код C, который демонстрирует этот калькулятор четырех функций:

http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html

Посмотрите на сгенерированный код и убедитесь, что это не так просто, как кажется. Кроме того, преимущества использования такого инструмента, как Bison, заключаются в следующем: 1) Вы чему-то учитесь (особенно если Вы читаете книгу Dragon и изучаете грамматику), 2) вы избегаете попыток NIH изобрести колесо. С помощью реального инструмента парсер-генератор, вы на самом деле есть надежда на масштабирование позже, показывая другим людям, которых вы знаете, что Парсеры являются областью инструментов парсинга.

Обновление:

Люди здесь давали много разумных советов. Мое единственное предупреждение против пропуска инструментов парсинга или просто использования алгоритма маневрового двора или ручного рекурсивного приличного парсера состоит в том, что маленькие игрушечные языки ¹ могут когда-нибудь превратиться в большие реальные языки с функциями (sin, cos, log) и переменными, условиями и циклами для.

Flex/Bison вполне может быть излишним для небольшого, простого интерпретатора, но одноразовый парсер+оценщик может вызвать проблемы в будущем, когда необходимо внести изменения или добавить функции. Ваша ситуация будет меняться, и вам нужно будет использовать свое суждение; просто не наказывайте других людей за свои грехи ^[2] и построить менее адекватный инструмент.

Мой любимый инструмент для парсинга

Лучшим инструментом в мире для этой работы является библиотека Parsec (для рекурсивных приличных парсеров), которая поставляется с языком программирования Haskell. Это очень похоже на BNF, или на какой-то специализированный инструмент или доменный язык для синтаксического анализа (пример кода [3]), но на самом деле это просто обычная библиотека в Haskell, то есть она компилируется на том же этапе сборки, что и rest вашего кода Haskell, и вы можете написать произвольный код Haskell и вызвать его в своем синтаксическом анализаторе, и вы можете смешивать и сопоставлять другие библиотеки в том же коде . (Кстати, внедрение такого языка синтаксического анализа в язык, отличный от Haskell, приводит к нагрузкам синтаксического крафта. Я сделал это в C# году, и это работает довольно хорошо, но это не так красиво и лаконично.)

Записи:

1 Ричард Столлман говорит, Почему вы не должны использовать Tcl

Главный урок Emacs заключается в том, что язык для расширений не должен быть будьте просто "extension language". Оно должен быть настоящий язык программирования, предназначен для записи и поддержания в рабочем состоянии содержательные программы. Потому что люди Уилл захочет это сделать!

[2] Да, я навсегда изранен от использования этого "language".

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

[3] фрагмент синтаксического анализатора Haskell, использующего Parsec: калькулятор четырех функций, расширенный экспонентами, скобками, whitespace для умножения и константами (такими как pi и e).

aexpr   =   expr `chainl1` toOp
expr    =   optChainl1 term addop (toScalar 0)
term    =   factor `chainl1` mulop
factor  =   sexpr  `chainr1` powop
sexpr   =   parens aexpr
        <|> scalar
        <|> ident

powop   =   sym "^" >>= return . (B Pow)
        <|> sym "^-" >>= return . (\x y -> B Pow x (B Sub (toScalar 0) y))

toOp    =   sym "->" >>= return . (B To)

mulop   =   sym "*" >>= return . (B Mul)
        <|> sym "/" >>= return . (B Div)
        <|> sym "%" >>= return . (B Mod)
        <|>             return . (B Mul)

addop   =   sym "+" >>= return . (B Add) 
        <|> sym "-" >>= return . (B Sub)

scalar = number >>= return . toScalar

ident  = literal >>= return . Lit

parens p = do
             lparen
             result <- p
             rparen
             return result

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

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

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

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

Мне нравится 'precedence climbing' один.

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

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

Около 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;
    }    
}

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

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

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

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

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

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

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

Я предлагаю вам взглянуть на эту нить, например.

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

Обратите внимание, что использование grammar вовсе не подразумевает использование конкретного инструмента ( a la Yacc, Bison,...). Действительно, Вы наверняка уже используете следующие grammar:

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

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

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

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

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

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

Когда вы задаете свой вопрос, нет никакой необходимости в рекурсии вообще. Ответ заключается в трех вещах: Постфиксная нотация ПЛЮС Алгоритм маневрового двора плюс оценка постфиксного выражения:

1). Постфиксная нотация = изобретена для устранения необходимости в явной спецификации приоритета. Читайте больше в сети, но вот суть этого: инфиксное выражение ( 1 + 2) * 3 в то время как легко для людей читать и обрабатывать не очень эффективно для вычислений с помощью машины. Что же это такое? Простое правило, которое гласит: "перепишите выражение путем кэширования в приоритетном порядке, а затем всегда обрабатывайте его left-to-right". Таким образом, инфикс ( 1 + 2) * 3 становится постфиксом 12+3*. POST, потому что оператор всегда помещается в операнды AFTER.

2). Оценка постфиксного выражения. Легко. Считывание чисел с постфиксной строки. Нажимайте их на стопку, пока не появится оператор. Проверить тип оператора-унарный? двоичный код? третичный? Извлеките из стека столько операндов, сколько необходимо для вычисления этого оператора. Оценивать. Нажмите результат обратно на стек! И u r почти закончила. Продолжайте делать это до тех пор, пока стек не будет иметь только одну запись = искомое значение u r.

Давайте сделаем ( 1 + 2) * 3, который в постфиксе "12+3*". читается первым числом = 1. Толкни его на стек. Читайте дальше. Число = 2. Толкни его на стек. Читайте дальше. Оператор. Какой именно? +. - Какого рода? Binary = нуждается в двух операндах. Pop stack дважды = argright равен 2, а argleft равен 1. 1 + 2 - это 3. Нажмите 3 назад на стек. Читать далее из постфиксной строки. Это просто номер. 3.Push. Читайте дальше. Оператор. Какой именно? *. - Какого рода? Binary = требуется два числа - > pop stack дважды. Первый раз заскочил в арграйт, второй раз-в арглефт. Оцените операцию-3 раза 3 равно 9.Push 9 на стеке. Прочитайте следующий постфиксный символ. Это null. Конец ввода. Pop stack onec = это ваш ответ.

3). Маневровый двор используется для преобразования человеческого (легко читаемого) инфиксного выражения в постфиксное выражение (также легко читаемое человеком после некоторой практики). Легко кодировать вручную. Смотрите комментарии выше и net.

Есть ли язык, который вы хотите использовать? ANTLR позволит вам сделать это с точки зрения Java. У Адриана Куна есть отличная запись о том, как написать исполняемый файл grammar в Ruby; на самом деле, его пример почти точно соответствует вашему примеру арифметического выражения.

Это зависит от того, как "general" вы хотите, чтобы это было.

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

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

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

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

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

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

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

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

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

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

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

Это и есть "shunting yard algorythm" и это то, что большинство машинных парсеров использовать. Смотрите статью о парсинге в Википедия. Простой способ кодирования алгоритм маневрового двора заключается в использовании двух скирды. Одним из них является стек "push" и другой - это "reduce" или "result" стек. Пример:

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

начало: маркер '1': ечисло, положить в pstack (push) токен '+': isoperator установить приоритет=2, если приоритет < тогда previous_operator_precedence reduce() / / смотрите ниже поставить ' + ' в pstack (push) токен '2': isnumber, положить в pstack (push) токен '*': isoperator, set precedence=1, put in кстати (толчок) // проверяем приоритет // выше токена '3': isnumber, put in pstack (push) конец ввода, необходимо уменьшить (цель-пустой pstack) reduce() //done

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

кстати: '1' '+' '2' '' '3' этих: () ... кстати: () этих: '3' '2' '' '1' '+'

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

1*2+3

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

кстати: этих '1' '' '2': () ... кстати: () этих: '1' '2' ' '

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

кстати: '+' '3' этих: '1' '2' ' ' ... кстати: () этих: '2' '1' '' '3' '+'

Итак, короткая версия такова: push numbers, при нажатии операторы проверяют приоритет предыдущего оператора. Если она была выше, чем у оператора это нужно сделать сейчас, в первую очередь уменьшите, а затем нажмите на ток оператор. Для обработки скобок просто сохранить приоритет 'previous' оператор, и поставьте метку на pstack это говорит о снижении алгоритма до остановите уменьшение при решении внутренности из пары парен. Закрывающая скобка вызывает сокращение, как и конец ввода, а также удаляет открытые парень Марк из кстати, и восстанавливает 'previous operation' приоритет, так что разбор может продолжаться после близкого паренька куда он ушел прочь. Это можно сделать с помощью рекурсии или без (подсказка: используйте стек для хранения предыдущий приоритет когда столкнувшись с" ("...). То обобщенный вариант этого заключается в использовании реализован генератор парсера маневровый двор алгоритму, f.ex. с помощью yacc или bison или taccle (аналог tcl yacc).

Питер

-Adam

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

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

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

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

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

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

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

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

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

Я знаю, что это поздний ответ, но я только что написал крошечный парсер, который позволяет всем операторам (префикс, постфикс и инфикс-левый, инфикс-правый и неассоциативный) иметь произвольный приоритет.

Я собираюсь расширить это для языка с произвольной поддержкой DSL, но я просто хотел отметить, что для приоритета операторов не нужны пользовательские Парсеры, можно использовать обобщенный парсер, который вообще не нуждается в таблицах, и просто ищет приоритет каждого оператора, как он появляется. Люди упоминали пользовательские Парсеры Pratt или Парсеры shunting yard, которые могут принимать незаконные входы - этот не нужно настраивать и (если нет ошибки) не будет принимать плохой вход. Он не является полным в каком-то смысле, он был написан для тестирования алгоритма, и его ввод находится в форме, которая потребует некоторой предварительной обработки, но есть комментарии, которые делают его понятным.

Примечание. некоторые распространенные типы операторов отсутствуют, например, тип оператора, используемый для индексирования ie table[index] или вызова функции function (parameter-expression, ...) Я собираюсь добавить их, но подумайте об обоих как о постфиксных операторах, где то, что находится между разделителями " ["и"] " или " ("и")", анализируется с помощью другого экземпляра синтаксического анализатора выражений. Извините, что я это упустил, но постфиксная часть находится внутри - добавление rest, вероятно, почти удвоит размер кода.

Поскольку парсер - это всего лишь 100 строк кода ракетки, возможно, мне следует просто вставить его сюда, я надеюсь, что это не длиннее, чем позволяет stackoverflow.

Несколько подробностей о произвольных решениях:

Если постфиксный оператор с низким приоритетом конкурирует за те же блоки инфикса, что и префиксный оператор с низким приоритетом, то префиксный оператор выигрывает. Это не встречается в большинстве языков, так как большинство из них не имеют постфиксных операторов с низким приоритетом. - например: ((данные а) (слева 1 +) (до 2 Не)(данные б) (пост 3 !) (слева 1 +) (Данные c)) это а+не б!+c где не является префиксным оператором и ! является постфиксным оператором и оба имеют более низкие значения приоритетнее, чем+, поэтому они хотят сгруппироваться несовместимыми способами либо как (а+б!)+c или как а+(не б!+c) в этих случаях префиксный оператор всегда выигрывает, поэтому второй-это способ его разбора

Неассоциативные операторы инфикса действительно существуют, так что вам не нужно притворяться, что операторы, возвращающие разные типы, чем они принимают, имеют смысл вместе, но без наличия разных типов выражений для каждого из них это Клудж. Таким образом, в этом алгоритме неассоциативные операторы отказываются ассоциироваться не только с собой, но и с любым оператором с тем же приоритетом. Это распространенный случай, поскольку < <= = = > = etc не ассоциируются друг с другом в большинстве языков.

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

#lang racket
;cool the algorithm fits in 100 lines!
(define MIN-PREC -10000)
;format (pre prec name) (left prec name) (right prec name) (nonassoc prec name) (post prec name) (data name) (grouped exp)
;for example "not a*-7+5 < b*b or c >= 4"
;which groups as: not ((((a*(-7))+5) < (b*b)) or (c >= 4))"
;is represented as '((pre 0 not)(data a)(left 4 *)(pre 5 -)(data 7)(left 3 +)(data 5)(nonassoc 2 <)(data b)(left 4 *)(data b)(right 1 or)(data c)(nonassoc 2 >=)(data 4)) 
;higher numbers are higher precedence
;"(a+b)*c" is represented as ((grouped (data a)(left 3 +)(data b))(left 4 *)(data c))

(struct prec-parse ([data-stack #:mutable #:auto]
                    [op-stack #:mutable #:auto])
  #:auto-value '())

(define (pop-data stacks)
  (let [(data (car (prec-parse-data-stack stacks)))]
    (set-prec-parse-data-stack! stacks (cdr (prec-parse-data-stack stacks)))
    data))

(define (pop-op stacks)
  (let [(op (car (prec-parse-op-stack stacks)))]
    (set-prec-parse-op-stack! stacks (cdr (prec-parse-op-stack stacks)))
    op))

(define (push-data! stacks data)
    (set-prec-parse-data-stack! stacks (cons data (prec-parse-data-stack stacks))))

(define (push-op! stacks op)
    (set-prec-parse-op-stack! stacks (cons op (prec-parse-op-stack stacks))))

(define (process-prec min-prec stacks)
  (let [(op-stack (prec-parse-op-stack stacks))]
    (cond ((not (null? op-stack))
           (let [(op (car op-stack))]
             (cond ((>= (cadr op) min-prec) 
                    (apply-op op stacks)
                    (set-prec-parse-op-stack! stacks (cdr op-stack))
                    (process-prec min-prec stacks))))))))

(define (process-nonassoc min-prec stacks)
  (let [(op-stack (prec-parse-op-stack stacks))]
    (cond ((not (null? op-stack))
           (let [(op (car op-stack))]
             (cond ((> (cadr op) min-prec) 
                    (apply-op op stacks)
                    (set-prec-parse-op-stack! stacks (cdr op-stack))
                    (process-nonassoc min-prec stacks))
                   ((= (cadr op) min-prec) (error "multiply applied non-associative operator"))
                   ))))))

(define (apply-op op stacks)
  (let [(op-type (car op))]
    (cond ((eq? op-type 'post)
           (push-data! stacks `(,op ,(pop-data stacks) )))
          (else ;assume infix
           (let [(tos (pop-data stacks))]
             (push-data! stacks `(,op ,(pop-data stacks) ,tos))))))) 

(define (finish input min-prec stacks)
  (process-prec min-prec stacks)
  input
  )

(define (post input min-prec stacks)
  (if (null? input) (finish input min-prec stacks)
      (let* [(cur (car input))
             (input-type (car cur))]
        (cond ((eq? input-type 'post)
               (cond ((< (cadr cur) min-prec)
                      (finish input min-prec stacks))
                     (else 
                      (process-prec (cadr cur)stacks)
                      (push-data! stacks (cons cur (list (pop-data stacks))))
                      (post (cdr input) min-prec stacks))))
              (else (let [(handle-infix (lambda (proc-fn inc)
                                          (cond ((< (cadr cur) min-prec)
                                                 (finish input min-prec stacks))
                                                (else 
                                                 (proc-fn (+ inc (cadr cur)) stacks)
                                                 (push-op! stacks cur)
                                                 (start (cdr input) min-prec stacks)))))]
                      (cond ((eq? input-type 'left) (handle-infix process-prec 0))
                            ((eq? input-type 'right) (handle-infix process-prec 1))
                            ((eq? input-type 'nonassoc) (handle-infix process-nonassoc 0))
                            (else error "post op, infix op or end of expression expected here"))))))))

;alters the stacks and returns the input
(define (start input min-prec stacks)
  (if (null? input) (error "expression expected")
      (let* [(cur (car input))
             (input-type (car cur))]
        (set! input (cdr input))
        ;pre could clearly work with new stacks, but could it reuse the current one?
        (cond ((eq? input-type 'pre)
               (let [(new-stack (prec-parse))]
                 (set! input (start input (cadr cur) new-stack))
                 (push-data! stacks 
                             (cons cur (list (pop-data new-stack))))
                 ;we might want to assert here that the cdr of the new stack is null
                 (post input min-prec stacks)))
              ((eq? input-type 'data)
               (push-data! stacks cur)
               (post input min-prec stacks))
              ((eq? input-type 'grouped)
               (let [(new-stack (prec-parse))]
                 (start (cdr cur) MIN-PREC new-stack)
                 (push-data! stacks (pop-data new-stack)))
               ;we might want to assert here that the cdr of the new stack is null
               (post input min-prec stacks))
              (else (error "bad input"))))))

(define (op-parse input)
  (let [(stacks (prec-parse))]
    (start input MIN-PREC stacks)
    (pop-data stacks)))

(define (main)
  (op-parse (read)))

(main)

Вот простой случай рекурсивного решения, написанного в 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;
}

}

Алгоритм может быть легко закодирован в C как рекурсивный парсер спуска.

#include <stdio.h>
#include <ctype.h>

/*
 *  expression -> sum
 *  sum -> product | product "+" sum
 *  product -> term | term "*" product
 *  term -> number | expression
 *  number -> [0..9]+
 */

typedef struct {
    int value;
    const char* context;
} expression_t;

expression_t expression(int value, const char* context) {
    return (expression_t) { value, context };
}

/* begin: parsers */

expression_t eval_expression(const char* symbols);

expression_t eval_number(const char* symbols) {
    // number -> [0..9]+
    double number = 0;        
    while (isdigit(*symbols)) {
        number = 10 * number + (*symbols - '0');
        symbols++;
    }
    return expression(number, symbols);
}

expression_t eval_term(const char* symbols) {
    // term -> number | expression
    expression_t number = eval_number(symbols);
    return number.context != symbols ? number : eval_expression(symbols);
}

expression_t eval_product(const char* symbols) {
    // product -> term | term "*" product
    expression_t term = eval_term(symbols);
    if (*term.context != '*')
        return term;

    expression_t product = eval_product(term.context + 1);
    return expression(term.value * product.value, product.context);
}

expression_t eval_sum(const char* symbols) {
    // sum -> product | product "+" sum
    expression_t product = eval_product(symbols);
    if (*product.context != '+')
        return product;

    expression_t sum = eval_sum(product.context + 1);
    return expression(product.value + sum.value, sum.context);
}

expression_t eval_expression(const char* symbols) {
    // expression -> sum
    return eval_sum(symbols);
}

/* end: parsers */

int main() {
    const char* expression = "1+11*5";
    printf("eval(\"%s\") == %d\n", expression, eval_expression(expression).value);

    return 0;
}

_{следующие библиотеки могут быть полезны: yupana} -строго арифметические операции;