Я работаю с помощью алгоритма Shunting-yard , как описано в Википедии.
Описание алгоритма при работе с операторами выглядит следующим образом:
Если токен является оператором o1, то:
в то время как есть токен оператора, o2, на вершине стека операторов, и либо
o1 is left-associative and its precedence is less than or equal to that of o2, or o1 is right associative, and has precedence less than that of o2,
затем вытолкните o2 из стека операторов в очередь вывода;
нажмите o1 на стек оператора.
Однако они приводят следующий пример:
Входные данные:
sin max 2 3 / 3 * 3.1415
Когда алгоритм /
получает токен, описание того, что должно произойти, выглядит следующим образом:
Token | Action | Output (in RPN) | Operator Stack
...
/ | Pop token to output | 2 3 max | / sin
...
Они выталкивают токен функции max
из stack
и помещают в queue
. Согласно их алгоритму, это может означать, что маркер функции является одновременно оператором и имеет приоритет меньше, чем у /
оператора.
Нет никакого объяснения относительно того, действительно ли это так. Итак, для Shunting-yard
алгоритма, каков приоритет функции? Являются ли функции правыми или левыми ассоциативными? Или Википедия просто неполная / неточная?
источник
sin( max( 2 3) / 3 * 3.1415)
if there is a left parenthesis at the top of the operator stack, then: pop the operator from the operator stack and discard it
следует добавить еще одну строку: если сейчас есть имя функции в верхней части стека, извлеките его из стека и вставьте в вывод . Другими словами, левый '(' всегда должен появляться вместе с именем функции, если они размещены вместе, как предполагает синтаксис функции: "name(
".Есть два разных случая для рассмотрения, в зависимости от синтаксиса вашего языка. Если ваш язык использует скобки для обозначения приложения функции (например
f(2+1)
), то приоритет не имеет значения. Функция должна быть помещена в стек и выдана после (для примера выше, результат равен2 1 + f
). В качестве альтернативы вы можете рассматривать функцию как значение и выводить ее немедленно и выводить операцию вызова функции после закрывающей круглой скобки (которая в противном случае должна обрабатываться так же, как любая другая скобка), напримерf 2 1 + $
, где$
находится операция вызова функции.Если ваш язык, однако, не использует круглые скобки для обозначения вызова функции, а вместо этого помещает аргумент непосредственно после функции без какой-либо специальной пунктуации (например
f 2 + 1
), как это, очевидно, имеет место в примере из Википедии, тогда все немного сложнее. Обратите внимание, что выражение, которое я только что привел в качестве примера, неоднозначно: применяется ли f к 2 и 1, добавляется к результату, или мы добавляем 2 и 1 вместе, а затем вызываем f с результатом?Опять же, есть два подхода. Вы можете просто поместить функцию в стек операторов, когда встретите ее, и назначить ей любой приоритет, какой захотите. Это самый простой подход, и, очевидно, это то, что сделал приведенный пример. Однако есть практические проблемы. Во-первых, как вы определяете функцию? Если у вас есть конечный набор, это легко, но если у вас есть определенные пользователем функции, это означает, что вашему анализатору требуется слишком обратная связь с вашей средой, которая может быстро запутаться. А как вы обрабатываете функции с несколькими аргументами?
Мне кажется, что для этого стиля синтаксиса использование функций в качестве значений, которые более удобны для оператора приложения функции, имеет гораздо больше смысла. Затем вы можете просто ввести оператор приложения всякий раз, когда вы читаете значение, и последнее, что вы прочитали, было также значением, поэтому вам не требуется особый способ сообщить, какие идентификаторы являются функциями. Вы также можете работать с выражениями, которые возвращают функции (что сложно или невозможно со стилем «функция как операция»). А это означает, что вы можете использовать каррирование для обработки функций с несколькими аргументами, что является огромным упрощением по сравнению с попыткой обрабатывать их напрямую.
Тогда единственное, что вам нужно решить - это приоритет применения функций. Выбор за вами, но на каждом используемом мной языке, который работает подобным образом, он был наиболее сильным обязательным оператором в языке и был правильно ассоциативным. (Единственный интересный вариант - это Haskell, который, помимо описанной версии с сильной привязкой, также имеет синоним для него с символом,
$
который является наиболее слабой связывающей операцией в языке, позволяя выражениям типаf 2 + 1
применять f к 2 иf $ 2 + 1
применять это ко всему остальному выражению)источник
Я реализовал запрашиваемые «функции в маневровом дворе» после прочтения оригинального мышления Дейкстры (стр. 7-11 в статье компилятора Algol 60, https://ir.cwi.nl/pub/9251 ), и мне понадобилось надежное решение. сделал следующее:
синтаксический анализ:
Инфикс-постфикс (маневровый двор):
Прекрасно работает в сложных тестах и сложных сценариях. В моем приложении (расширитель, содержащий аргументы, содержащиеся в командной строке), я поддерживаю функции с несколькими аргументами и запятую ",", чтобы разделить их, и они проходят через весь процесс.
Примеры выглядят как «sqrt (3 ^ 2 + 4 ^ 2)», который становится «3 2 ^ 4 2 ^ + sqrt» и, в конечном счете, «5», что является аргументом программы. Это bignum, поэтому "" binomial (64, 32) / gcd (binomial (64, 32), binomial (63, 31)) "==> большие вещи ==>" 2 "полезно." 123456 ^ 789 " на моем MacBookPro - 40 173 цифры, и время показывает «оценка = 0,000390 сек», так быстро.
Я также использую это, чтобы расширить данные в таблицах, и нахожу это удобным. В любом случае, это мой совет о том, как аккуратно обрабатывать вызовы функций, множественные аргументы и глубокое вложение в контексте маневрового двора Дейкстры. Просто сделал это сегодня из независимого мышления. Не знаю, могут ли быть лучшие способы.
источник