Анализатор уравнений (выражений) с приоритетом?
https://stackoverflow.com/questions/28256
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я разработал анализатор уравнений, используя простой стековой алгоритм, который обрабатывает двоичные (+, -, |, &, *, / и т. д.) операторы, унарные (!) операторы и круглые скобки.
Однако использование этого метода оставляет мне все, что имеет одинаковый приоритет — он оценивается слева направо независимо от оператора, хотя приоритет можно обеспечить с помощью круглых скобок.
Итак, сейчас «1+11*5» возвращает 60, а не 56, как можно было бы ожидать.
Хотя это подходит для текущего проекта, я хочу иметь процедуру общего назначения, которую я смогу использовать в последующих проектах.
Отредактировано для ясности:
Какой хороший алгоритм анализа уравнений с приоритетом?
Меня интересует что-то простое в реализации, и я понимаю, что могу писать код самостоятельно, чтобы избежать проблем с лицензированием доступного кода.
Грамматика:
Я не понимаю грамматического вопроса - я написал это от руки.Это настолько просто, что я не вижу необходимости в YACC или Bison.Мне просто нужно вычислить строки с помощью таких уравнений, как «2+3 * (42/13)».
Язык:
Я делаю это на C, но меня интересует алгоритм, а не решение для конкретного языка.C является достаточно низким уровнем, поэтому его можно будет легко преобразовать в другой язык, если возникнет такая необходимость.
Пример кода
я разместил тестовый код для анализатора простых выражений Я говорил о выше.Требования проекта изменились, и поэтому мне никогда не приходилось оптимизировать код по производительности или занимаемому пространству, поскольку он не был включен в проект.Он представлен в исходной подробной форме и должен быть легко понятен.Если я сделаю с ним что-нибудь еще с точки зрения приоритета операторов, я, вероятно, выберу макрос хак потому что он соответствует остальной части программы по простоте.Однако если я когда-нибудь буду использовать это в реальном проекте, я выберу более компактный/быстрый парсер.
Связанный вопрос
-Адам
Решение
Трудный путь
Вы хотите парсер рекурсивного спуска.
Чтобы получить приоритет, вам нужно мыслить рекурсивно, например, используя образец строки:
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).
Скачать Бизон (или что-то подобное, ANTLR и т. д.).
Обычно есть пример кода, который вы можете просто запустить bison и получить желаемый код C, демонстрирующий этот калькулятор с четырьмя функциями:
http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html
Посмотрите на сгенерированный код и убедитесь, что это не так просто, как кажется.Кроме того, преимущества использования такого инструмента, как Bison, заключаются в том, что 1) вы чему-то учитесь (особенно если вы читаете книгу Дракона и изучаете грамматику), 2) вы избегаете Национальные институты здравоохранения США пытаюсь изобрести велосипед.Имея настоящий инструмент синтаксического анализа-генератора, у вас действительно есть надежда на дальнейшее расширение, показывая другим людям, которых вы знаете, что синтаксические анализаторы — это область инструментов синтаксического анализа.
Обновлять:
Люди здесь дали много здравых советов.Мое единственное предостережение против пропуска инструментов синтаксического анализа или простого использования алгоритма Shunting Yard или приличного рекурсивного парсера, собранного вручную, заключается в том, что маленькие игрушечные языки1 может когда-нибудь превратиться в большие настоящие языки с функциями (sin, cos, log) и переменными, условиями и циклами for.
Flex/Bison вполне может быть излишним для небольшого и простого интерпретатора, но одноразовый парсер + оценщик может вызвать проблемы в дальнейшем, когда необходимо внести изменения или добавить функции.Ваша ситуация будет меняться, и вам придется руководствоваться своим суждением;просто не надо наказывать других людей за свои грехи [2] и создать менее чем адекватный инструмент.
Мой любимый инструмент для парсинга
Лучший в мире инструмент для работы – это Парсек библиотека (для хороших рекурсивных парсеров), входящая в состав языка программирования Haskell.Это очень похоже на БНФ, или какой-то специализированный инструмент или предметно-ориентированный язык для синтаксического анализа (пример кода [3]), но на самом деле это просто обычная библиотека в Haskell, а это означает, что она компилируется на том же этапе сборки, что и остальная часть вашего кода Haskell, и вы можете написать произвольный код Haskell и вызывать его в своем парсере, а также можете смешивать и сопоставлять другие библиотеки. все в одном коде.(Кстати, встраивание такого языка синтаксического анализа в язык, отличный от Haskell, приводит к множеству синтаксических сложностей.Я сделал это на C#, и это работает неплохо, но не так красиво и лаконично.)
Примечания:
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
Другие советы
А алгоритм сортировочной станции это подходящий инструмент для этого.Википедия действительно путает по этому поводу, но в основном алгоритм работает так:
Допустим, вы хотите вычислить 1 + 2 * 3 + 4.Интуитивно вы «знаете», что сначала вам нужно выполнить 2 * 3, но как получить этот результат?Ключевым моментом является понимание того, что при сканировании строки слева направо вы будете оценивать оператор, когда оператор, который следует он имеет более низкий (или равный) приоритет.В контексте примера вот что вы хотите сделать:
- Посмотри на:1+2, ничего не делай.
- Теперь посмотрите на 1+2*3, все равно ничего не делайте.
- Теперь посмотрите на 1 + 2 * 3 + 4. Теперь вы знаете, что необходимо оценить 2 * 3, поскольку следующий оператор имеет более низкий приоритет.
Как вы это реализуете?
Вам нужно иметь два стека: один для чисел, другой для операторов.Вы постоянно помещаете числа в стек.Вы сравниваете каждый новый оператор с оператором на вершине стека, если оператор на вершине стека имеет более высокий приоритет, вы извлекаете его из стека операторов, извлекаете операнды из стека чисел, применяете оператор и отправляете результат. в стек чисел.Теперь вы повторяете сравнение с оператором вершины стека.
Возвращаясь к примеру, это работает следующим образом:
N = [] ops = [
- Прочтите 1.N = [1], Операции = [ ]
- Читай +.N = [1], Операции = [+]
- Прочтите 2.N = [1 2], Опс = [+]
- Читать
*.N = [1 2], Опс = [+ *] - Прочтите 3.N = [1 2 3], Ops = [+ *]
- Читай +.N = [1 2 3], Ops = [+ *]
- Поп 3, 2 и выполнить 2
*3 и отправить результат на N.N = [1 6], Опс = [+] +остается ассоциативным, поэтому вы также хотите удалить 1, 6 и выполнить +.Н = [7], Опс = [].- Наконец, поместите [+] в стек операторов.N = [7], Ops = [+].
- Поп 3, 2 и выполнить 2
- Прочтите 4.Н = [7 4].Опс = [+].
- У вас закончились входные данные, поэтому вы хотите очистить стопки сейчас.После чего вы получите результат 11.
Вот это не так уж и сложно, не так ли?И он не вызывает никаких грамматик или генераторов синтаксического анализатора.
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
Очень хорошее объяснение различных подходов:
- Распознавание рекурсивного спуска
- Алгоритм работы сортировочной станции
- Классическое решение
- Восхождение по приоритету
Написано простым языком и псевдокодом.
Мне нравится «восхождение по приоритету».
Есть хорошая статья здесь об объединении простого анализатора рекурсивного спуска с анализом приоритета операторов.Если вы недавно писали парсеры, чтение должно быть очень интересным и поучительным.
Давным-давно я разработал свой собственный алгоритм синтаксического анализа, которого не смог найти ни в одной книге по синтаксическому анализу (например, в Книге Дракона).Глядя на указатели на алгоритм сортировочной станции, я вижу сходство.
Около двух лет назад я опубликовал об этом пост с исходным кодом 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;
}
}
Было бы полезно, если бы вы могли описать грамматику, которую вы сейчас используете для анализа.Похоже, проблема может заключаться именно здесь!
Редактировать:
Тот факт, что вы не понимаете вопрос по грамматике и что «вы написали это вручную», скорее всего, объясняет, почему у вас возникают проблемы с выражениями формы «1+11*5» (т. е. с приоритетом операторов). .Например, поиск в Google «грамматики арифметических выражений» должен дать несколько хороших указаний.Такая грамматика не должна быть сложной:
<Exp> ::= <Exp> + <Term> |
<Exp> - <Term> |
<Term>
<Term> ::= <Term> * <Factor> |
<Term> / <Factor> |
<Factor>
<Factor> ::= x | y | ... |
( <Exp> ) |
- <Factor> |
<Number>
например, справится с этой задачей, и его можно тривиально расширить, чтобы обрабатывать некоторые более сложные выражения (включая функции, например, или степени,...).
Я предлагаю вам взглянуть на этот нить, например.
Почти во всех введениях в грамматику/синтаксический анализ в качестве примера рассматриваются арифметические выражения.
Обратите внимание, что использование грамматики вовсе не подразумевает использование определенного инструмента (а-ля Якк, Бизон,...).Действительно, вы наверняка уже используете следующую грамматику:
<Exp> :: <Leaf> | <Exp> <Op> <Leaf>
<Op> :: + | - | * | /
<Leaf> :: <Number> | (<Exp>)
(или что-то в этом роде), даже не зная об этом!
Вы думали об использовании Повышение духа?Он позволяет вам писать EBNF-подобные грамматики на C++ следующим образом:
group = '(' >> expression >> ')';
factor = integer | group;
term = factor >> *(('*' >> factor) | ('/' >> factor));
expression = term >> *(('+' >> term) | ('-' >> term));
Когда вы задаете свой вопрос, рекурсия вообще не нужна.Ответ состоит в трех вещах:Постфиксная нотация плюс алгоритм сортировочной станции плюс оценка постфиксного выражения:
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. Нажмите.Читайте дальше.Оператор.Который из?*.Какие?Двоичный = требуется два числа -> дважды извлечь стек.Сначала загляните в арграйт, второй раз в арглефт.Оцените операцию: 3 раза по 3 равно 9. Поместите 9 в стек.Читать следующий постфиксный символ.Это ноль.Конец ввода.Pop stack onec = это ваш ответ.
3).Shunting Yard используется для преобразования (легко) читаемого человеком инфиксного выражения в постфиксное выражение (также легко читаемое человеком после некоторой практики).Легко кодировать вручную.Смотрите комментарии выше и в сети.
Это зависит от того, насколько «общим» вы хотите, чтобы это было.
Если вы хотите, чтобы он был действительно очень общим, например, имел возможность анализировать математические функции, например sin(4+5)*cos(7^3), вам, вероятно, понадобится дерево разбора.
При этом я не думаю, что здесь уместно вставлять полную реализацию.Я бы посоветовал вам посмотреть одну из печально известных "Книга Дракона".
Но если вам просто нужна поддержка приоритета, то вы можете сделать это, сначала преобразовав выражение в постфиксную форму, в которой алгоритм, который можно скопировать и вставить, должен быть доступен из Google или я думаю, вы можете сами закодировать это с помощью двоичного дерева.
Если у вас есть постфиксная форма, то с этого момента это проще простого, поскольку вы уже понимаете, как стек помогает.
Я бы предложил обмануть и использовать Алгоритм маневровой станции.Это простой способ написания простого анализатора типа калькулятора, который учитывает приоритет.
Если вы хотите правильно токенизировать вещи, иметь переменные и т.если вам просто нужен парсер в стиле калькулятора, то этого алгоритма должно быть достаточно :-)
Я нашел это на PIClist о Алгоритм сортировочной станции:
Гарольд пишет:
Я помню, как давно читал алгоритм, который преобразовал алгебраические выражения в RPN для легкой оценки.Каждое значение инфикс или оператор или скобка были представлены железнодорожным автомобилем на трассе.Один тип автомобиля разделился на другую трассу, а другой продолжался прямо вперед.Я не помню детали (очевидно!), Но всегда думал, что это было бы интересно для кода.Это возвращается, когда я писал 6800 (не 68000) код сборки.
Это «шунтирующий двор алгоритм», и это то, что использует большинство анализаторов машины.См. Статью о разборе в Википедии.Простой способ кодировать Awunting Yard Algorythm - использовать два стека.Один из них - стек «push», а другой - стек «уменьшить» или «результат».Пример:
PSTACK = () // Пусто RSTACK = () Вход:1+2*3 Procedence = 10 // Самое низкое снижение = 0 // Не уменьшайте
начинать:токен '1':Isnumber, положите в токен PSTACK (PUSH) '+':Isoperator устанавливает Precedence = 2, если приоритет <предыдущая_оперитор_педенция, то уменьшите () // См. Ниже положить «+» в токен PSTACK (push) '2':Isnumber, положите в токен PSTACK (PUSH) '*':Isoperator, установлен PRACEDENCE = 1, вставьте в PSTACK (push) // Проверьте приоритет как // выше токена '3':Isnumber, положить в конец ввода pStack (push), необходимо уменьшить (цель пустого pStack) уменьшить () // Готово
Чтобы уменьшить, поп -элементы из стека PUSH и поместите их в стек результатов, всегда меняйте 2 лучших элемента на PSTACK, если они имеют форму «оператор» «номер»:
стек:'1' '+' '2' '''3' стек:() ...стек:() рстек:'3' '2' '' '1' '+'
если бы выражение было:
1*2+3
Тогда спусковой крючок был бы показанием токена «+», который имеет более низкую достояние, чем уже толчок «*», так что это было бы сделано:
стек:'1' '' '2' рстек:() ...стек:() рстек:'1' '2' ''
а затем натолкнулся «+», а затем «3», а затем, наконец, уменьшился:
стек:'+' '3''1' '2' '... ...стек:() рстек:'1' '2' '' '3' '+'
Итак, короткая версия:Нажатие номера при толчке операторов проверяют приоритет предыдущего оператора.Если он был выше, чем у оператора, который должен быть нажат сейчас, сначала уменьшите, тогда нажмите текущего оператора.Для обработки парней просто сохранить приоритет «предыдущего» оператора и положить след на PSTACK, который сообщает об уменьшению алгоритма прекратить уменьшение при решении внутренней части пары.Заключительная парена запускает сокращение, как и конец ввода, а также удаляет открытую парену от PSTACK и восстанавливает прецедентность «предыдущей операции», чтобы анализ может продолжаться после закрытия парена, где он остановился.Это можно сделать с помощью рекурсии или без (подсказка:Используйте стек для хранения предыдущего приоритета при столкновении с '(' ...).Обобщенная версия этого состоит в том, чтобы использовать генератор анализатора, реализованный Shunting Yard Algorythm, F.Ex.Использование YACC или Bison или TACCLE (TCL аналог yacc).
Питер
-Адам
Я разместил исходный код для ультракомпактного (1 класс, <10 КиБ) Java-математический оценщик на моем веб-сайте.Это анализатор рекурсивного спуска того типа, который вызвал черепной взрыв плаката с принятым ответом.
Он поддерживает полный приоритет, круглые скобки, именованные переменные и функции с одним аргументом.
я выпустил парсер выражений, основанный на Маневровый двор Дейкстры алгоритм, согласно условиям Лицензия Апач 2.0:
Еще одним ресурсом для анализа приоритета является Анализатор приоритета операторов запись в Википедии.Охватывает алгоритм сортировочной станции Дейкстры и алгоритм альтернативного дерева, но, в частности, описывает действительно простой алгоритм замены макросов, который может быть тривиально реализован перед любым синтаксическим анализатором, не знающим приоритета:
#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))))
Это потрясающе в своей простоте и очень понятно.
Я реализовал парсер рекурсивного спуска на Яве в Парсер MathEclipse проект.Его также можно использовать в качестве Веб-инструментарий Google модуль
В настоящее время я работаю над серией статей о создании анализатора регулярных выражений в качестве инструмента обучения шаблонам проектирования и читаемому программированию.Вы можете взглянуть на читаемый код.В статье представлено наглядное использование алгоритма сортировочной станции.
Я написал анализатор выражений на F# и писал об этом здесь.Он использует алгоритм сортировочной станции, но вместо преобразования из инфикса в РПН я добавил второй стек для накопления результатов вычислений.Он правильно обрабатывает приоритет операторов, но не поддерживает унарные операторы.Я написал это, чтобы изучить F #, а не для изучения анализа выражений.
Решение Python с использованием pyparsing можно найти здесь.Анализ инфиксной записи с использованием различных операторов с приоритетом довольно распространен, поэтому pyparsing также включает в себя infixNotation (ранее operatorPrecedence) построитель выражений.С его помощью вы можете легко определять логические выражения, используя, например, «И», «ИЛИ», «НЕ».Или вы можете расширить свою четырехфункциональную арифметику, используя другие операторы, например !для факториала или «%» для модуля или добавьте операторы P и C для вычисления перестановок и комбинаций.Вы можете написать инфиксный анализатор для матричной записи, который включает обработку операторов «-1» или «T» (для инверсии и транспонирования).Пример оператораPrecedence для 4-функционального синтаксического анализатора (с '!', добавленным для развлечения): здесь и более полнофункциональный анализатор и оценщик здесь.
Я знаю, что это запоздалый ответ, но я только что написал крошечный синтаксический анализатор, который позволяет всем операторам (префиксным, постфиксным и инфиксным слева, инфиксным правым и неассоциативным) иметь произвольный приоритет.
Я собираюсь расширить это для языка с произвольной поддержкой DSL, но я просто хотел указать, что не нужны специальные анализаторы для определения приоритета операторов, можно использовать обобщенный анализатор, который вообще не нуждается в таблицах, и просто ищет приоритет каждого оператора по мере его появления.Люди упоминали специальные парсеры Пратта или анализаторы сортировочных станций, которые могут принимать незаконные входные данные — этот не требует настройки и (если нет ошибки) не будет принимать неправильные входные данные.В каком-то смысле он не является полным, он был написан для проверки алгоритма, и его входные данные представлены в форме, требующей некоторой предварительной обработки, но есть комментарии, которые проясняют это.
Примечание. Некоторые общие виды операторов отсутствуют, например, такого оператора, используемого для индексации IE Table [Index] или вызова функции функции (экспрессия параметров, ...) Я собираюсь добавить их, но подумайте об обоих как постфикс Операторы, в которых то, что происходит между делиметрами, «['и'] 'или' ('и') ', проанализируется с другим экземпляром анализатора выражения.Извините, что пропустил это, но постфиксная часть присутствует — добавление остальной части, вероятно, почти удвоит размер кода.
Поскольку парсер представляет собой всего лишь 100 строк рэкетного кода, возможно, мне следует просто вставить его сюда, надеюсь, это не длиннее, чем позволяет stackoverflow.
Несколько подробностей о произвольных решениях:
Если постфиксный оператор с низким приоритетом конкурирует за те же инфиксные блоки, что и префиксный оператор с низким приоритетом, побеждает префиксный оператор.Это не встречается в большинстве языков, поскольку в большинстве из них нет постфиксных операторов с низким приоритетом.- например:((Данные a) (слева 1 +) (до 2 не) (данные b) (post 3!) (слева 1 +) (данные c)) - это +не b! +c, где нет оператора префикса и!Оператор Postfix, и оба имеют более низкий приоритет, чем+, поэтому они хотят группироваться несовместимыми способами либо (A+Not B!)+C, либо как+(не B!+C) В этих случаях оператор префикса всегда побеждает, поэтому, так что Во -вторых, то, как он анализирует
Неассоциативные инфиксные операторы действительно существуют, поэтому вам не нужно притворяться, что операторы, которые возвращают разные типы, чем они принимают, имеют смысл вместе, но без разных типов выражений для каждого из них это ляп.Таким образом, в этом алгоритме неассоциативные операторы отказываются ассоциироваться не только с собой, но и с любым оператором с тем же приоритетом.Это распространенный случай, поскольку < <= == >= и т. д. не связаны друг с другом в большинстве языков.
Вопрос о том, как разные типы операторов (левый, префикс и т. д.) нарушают связи по приоритету, не должен подниматься, потому что на самом деле нет смысла назначать операторам разных типов одинаковый приоритет.Этот алгоритм что-то делает в таких случаях, но я даже не пытаюсь выяснить, что именно, потому что такая грамматика изначально является плохой идеей.
#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;
}
следующие библиотеки могут быть полезны: юпана - строго арифметические операции; крошечныйэкспр - арифметические операции + математические функции C + одна предоставленная пользователем; ПДК - парсер-комбинаторы
Объяснение
Давайте зафиксируем последовательность символов, представляющих алгебраическое выражение.Первый — это число, то есть десятичная цифра, повторяющаяся один или несколько раз.Будем называть такое обозначение продукционным правилом.
number -> [0..9]+
Оператор сложения со своими операндами — еще одно правило.Это либо number или любые символы, которые представляют sum "*" sum последовательность.
sum -> number | sum "+" sum
Попробуйте заменить number в sum "+" sum это будет number "+" number который, в свою очередь, может быть расширен до [0..9]+ "+" [0..9]+ что, наконец, можно было бы свести к 1+8 что является правильным выражением сложения.
Другие замены также дадут правильное выражение: sum "+" sum -> number "+" sum -> number "+" sum "+" sum -> number "+" sum "+" number -> number "+" number "+" number -> 12+3+5
Постепенно мы могли бы напоминать набор производственных правил. она же грамматика которые выражают все возможные алгебраические выражения.
expression -> sum
sum -> difference | difference "+" sum
difference -> product | difference "-" product
product -> fraction | fraction "*" product
fraction -> term | fraction "/" term
term -> "(" expression ")" | number
number -> digit+
Чтобы контролировать приоритет оператора, измените положение его производственного правила относительно других.Посмотрите на грамматику выше и обратите внимание, что правило производства для * находится ниже + это заставит product оценить перед sum.Реализация просто сочетает в себе распознавание образов с оценкой и, таким образом, точно отражает правила производства.
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);
}
Здесь мы оцениваем term сначала и вернуть его, если нет * персонаж после него это оставленный выбор в нашем производственном правиле в противном случае — оценить символы после и вернуть term.value * product.value это правильный выбор в нашем производственном правиле, т.е. term "*" product
