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

Question

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

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

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

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

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

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

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

Грамматика:

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

Язык:

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

Пример кода

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

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

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

-Adam

Answer 1

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

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

1. Посмотрите на: 1 + 2, ничего не делайте.
2. Теперь посмотрите на 1 + 2 * 3, все еще ничего не делайте.
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.

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

Answer 2

Трудный путь

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

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

1+11*5

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

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

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

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

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

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

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

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

---

Обновление:

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

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

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

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

Примечания:

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

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

[2] Да, я вечно боюсь использовать этот "язык".

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

[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

Answer 3

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

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

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

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

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

Answer 4

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

Answer 5

Давным-давно я создал свой собственный алгоритм синтаксического анализа, который я не смог найти ни в одной книге по синтаксическому анализу (например, в Книге Дракона). Глядя на указатели на алгоритм 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;
    }    
}

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

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

Answer 7

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

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

Answer 8

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

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

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

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

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

Answer 9

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

Answer 10

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

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