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

Ответ 1

Жесткий путь

Вы хотите рекурсивный парсер спуска.

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

1+11*5

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

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

Легкий (правый) способ

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

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

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

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

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

Update:

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

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

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

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

Примечания:

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

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

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

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

[3] Фрагмент анализатора Haskell с использованием Parsec: калькулятор с четырьмя функциями, расширенный с показателями, скобками, пробелами для умножения и константами (например, 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

Ответ 2

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

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

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

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

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

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

N = [] Ops = []

• Чтение 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 = [+ *]
  • Поп 3, 2 и выполните 2 * 3, и нажмите результат на N. N = [1 6], Ops = [+]
  • + оставлен ассоциативным, поэтому вы хотите также выставить 1, 6 и выполнить+. N = [7], Ops = [].
  • Наконец, нажмите [+] на стек оператора. N = [7], Ops = [+].
• Чтение 4. N = [7 4]. Ops = [+].
• У вас закончились входные данные, поэтому вы хотите очистить стеки сейчас. После чего вы получите результат 11.

Там, что не так сложно, не так ли? И он не вызывает никаких обращений к генераторам грамматики или синтаксического анализатора.

Ответ 3

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

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

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

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

Мне нравится "приоритет восхождения".

Ответ 4

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

Ответ 5

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

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

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

Обновить. Поскольку больше людей могут читать (или запускать) Javascript, я переопределял свой парсер в Javascript после того, как код был реорганизован. Весь анализатор составляет менее 5 килобайт кода 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;
    }    
}

Ответ 6

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

Edit:

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 7

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

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

Ответ 8

По мере того как вы ставите свой вопрос, нет необходимости в рекурсии. Ответ - три вещи: нотация Postfix плюс алгоритм Shunting Yard плюс оценка выражения Postfix:

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

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

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

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

Ответ 9

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

Ответ 10

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

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

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

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

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

Ответ 11

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

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

Ответ 12

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

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

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

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

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

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

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

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 numbers, при нажатии операторов приоритет предыдущего оператора. Если бы он был выше, чем у оператора который должен быть отодвинут сейчас, сначала уменьшить, а затем нажать текущий оператор. Для обработки парнеров просто сохраняйте приоритет "предыдущих" оператора, и пометьте метку на pstack что говорит об уменьшении алгоритма прекратить сокращение при решении внутри пары пар. Закрывающий парик вызывает сокращение, как и конец ввода, а также удаляет открытые знак paren из pstack и восстанавливает "предыдущую операцию" приоритет, поэтому синтаксический анализ может продолжаться после того, как он закрыт, выкл. Это можно сделать с помощью рекурсии или без (подсказка: используйте стек для хранения предыдущий приоритет, когда столкнувшись с "("...). обобщенная версия этого использования реализован генератор синтаксического анализатора шунтирующий двор algorythm, f.ex. с помощью yacc или bison или taccle (tcl аналог Yacc).

Петр

-Adam

Ответ 13

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

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

Ответ 14

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

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

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

Ответ 15

я выпустил синтаксический анализатор выражений, основанный на алгоритме Dijkstra Shunting Yard в терминах Apache License 2.0:

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

Ответ 16

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

Ответ 17

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

Ответ 18

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

Ответ 19

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

Ответ 20

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

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

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

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

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

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

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

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

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

Ответ 21

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

}