Операторы переменной длины в обратной польской нотации (постфикс)
Справочная информация: в традиционной обратной польской нотации все операторы должны иметь фиксированную длину, что позволяет легко вычислять RPN и управлять им с помощью кода, поскольку каждый токен, выражение и подвыражение являются «автономными», так что можно вслепую заменить y в x y * для y 1 +, чтобы получить x y 1 + *, что является еще одним допустимым выражением, которое делает именно то, что вы хотите. Вот интерактивная демонстрация простого калькулятора RPN с поддержкой именованных переменных. Обратите внимание, что демонстрации пытаются представить суть алгоритма; они не соотносятся с производственным кодом и не представляют его.
var rpn = prompt("Please enter RPN string, where each token is " +
"separated by a space", "x 1 x + * 2 /").trim().split(/\s+/);
var stack = [], variables = [], values = [];
for (let i = 0, len = rpn.length|0; i < len; i=i+1|0) {
if (/^\d*(\.\d*)?$/.test(rpn[i]) && rpn[i] !== "") {
stack.push( rpn[i] );
} else if (/^[a-z]$/i.test(rpn[i])) {
stack.push( rpn[i] );
if (!~variables.indexOf(rpn[i])) variables.push( rpn[i] );
} else {
if (stack.length<2)throw Error("No operand for " + rpn[i]);
const firstPop = stack.pop(); //lacks check if stack empty
stack.push( "(" + stack.pop() + rpn[i] + firstPop + ")" );
}
}
if (stack.length !== 1) throw Error("Invalid RPN got: " + stack);
for (let i = 0, len = variables.sort().length|0; i < len; i=i+1|0)
values[i] = +prompt(variables[i] + " = ", Math.random()*10|0);
variables.push("'use strict';return(" + stack.pop() + ")");
alert("Result: " + Function.apply(0, variables).apply(0, values));Вопрос: Как можно модифицировать или адаптировать RPN для работы с «операторами» переменной длины (вспомните функции)?
Исследования и предлагаемые решения. Я использую RPN в качестве промежуточного представления кода до того, как он будет преобразован в определенный кодовый язык. Я хочу сохранить как можно больше полезности и простоты RPN, по-прежнему представляя операторы переменной длины. Я разработал три решения и реализовал их в довольно упрощенных демонстрациях ниже.
- Специальный оператор префикса ARGUMENTS_BEGIN (мы будем использовать
#для целей этого вопроса). Это решение идет вразрез с традиционной RPN, поскольку оно добавляет префиксные операторы для обозначения начала аргументов. Это заставляет список аргументов автоматически расширяться по размеру и помогает при отладке, поскольку подстановка неправильно сформированного токена не может нарушить список аргументов, что позволяет легче локализовать ошибку. Это может усложнить манипулирование аргументами из-за необходимости большего количества кода для обработки таких случаев, как вызовы вложенных функций, но я не совсем уверен, какие сложности могут возникнуть. Я предполагаю, что я столкнусь с препятствиями при разборе синтаксиса, который включает префиксные и постфиксные операторы. Это также затрудняет прямое вычисление, поскольку для определения начала аргументов требуется обратный поиск или отдельный стек.
var rpn = prompt("Please enter a RPN string, where each token is " +
"separated by a space", "# # x 210 gcd x 6 * 126 gcd").trim()
.split(/\s+/);
var stack = [], variables = [], values = [];
for (let i = 0, len = rpn.length|0; i < len; i=i+1|0) {
if (/^\d*(\.\d*)?$/.test(rpn[i]) && rpn[i] !== "") {
stack.push( rpn[i] );
} else if (/^[a-z]$/i.test(rpn[i])) {
stack.push( rpn[i] );
if (!~variables.indexOf(rpn[i])) variables.push( rpn[i] );
} else if (/^[a-z]\w*$/i.test(rpn[i])) {
const s = stack.lastIndexOf("#");
if (s<0) throw Error("No start of arguments to " + rpn[i]);
stack.push( rpn[i]+"(" + stack.splice(s).slice(1) + ")" );
} else if (rpn[i] === '#') {
stack.push( '#' ); // sparks a syntax error if misused
} else {
if (stack.length<2)throw Error("No operand for " + rpn[i]);
const firstPop = stack.pop();
stack.push( "(" + stack.pop() + rpn[i] + firstPop + ")" );
}
}
if (stack.length !== 1) throw Error("Invalid RPN got: " + stack);
for (let i = 0, len = variables.sort().length|0; i < len; i=i+1|0)
values[i] = +prompt(variables[i] + " = ", Math.random()*10|0);
variables.push( "gcd" );
values.push( function gcd(a, b) {return b ? gcd(b, a % b) : a;} );
variables.push("'use strict';return(" + stack.pop() + ")");
alert("Result: " + Function.apply(0, variables).apply(0, values));- Операторы запятой для группировки аргументов (мы будем использовать
,для группировки последних двух элементов и~для обозначения группы нулевой длины для целей этого вопроса). Это решение является традиционным RPN, за исключением немного особой обработки операторов запятой и нулевой группы. Каждый оператор переменной длины считается имеющим длину, равную единице (нулевые аргументы представлены с помощью~). Запятые формируют списки аргументов из двух элементов, каждый из которых может быть обычным токеном, списком аргументов или оператором нулевой группы. К преимуществам относятся простота манипулирования и разбора кода, соблюдение простоты RPN и сохранение токен-независимости RPN. Недостатки включают RPN, который сложнее отлаживать, потому что крошечный искаженный токен может нарушить весь список аргументов и выйти из-под контроля, как снежный ком, без возможности определить, было ли это преднамеренным или случайным.
var rpn = prompt("Please enter RPN string, where each token is " +
"separated by a space", "x 6 * 126 , 210 , gcd ~ PI %")
.trim().split(/\s+/);
var stack = [], variables = [], values = [];
for (let i = 0, len = rpn.length|0; i < len; i=i+1|0) {
if (/^\d*(\.\d*)?$/.test(rpn[i]) && rpn[i] !== "") {
stack.push( rpn[i] );
} else if (/^[a-z]$/i.test(rpn[i])) {
stack.push( rpn[i] );
if (!~variables.indexOf(rpn[i])) variables.push( rpn[i] );
} else if (/^[a-z]\w*$/i.test(rpn[i])) {
if (stack.length<1)throw Error("No operand for " + rpn[i]);
stack.push( rpn[i] + "(" + stack.pop() + ")" );
} else if (rpn[i] === ',') {
if (stack.length<2)throw Error("No operand for " + rpn[i]);
const p2 = "" + stack.pop(), p1 = "" + stack.pop();
stack.push( p1 && p2 ? p1 + "," + p2 : p1 || p2 );
} else if (rpn[i] === '~') {
stack.push( "" ); // zero-length group
} else {
if (stack.length<2)throw Error("No operand for " + rpn[i]);
const firstPop = stack.pop(); //lacks check if stack empty
stack.push( "(" + stack.pop() + rpn[i] + firstPop + ")" );
}
}
if (stack.length !== 1) throw Error("Invalid RPN got: " + stack);
for (let i = 0, len = variables.sort().length|0; i < len; i=i+1|0)
values[i] = +prompt(variables[i] + " = ", Math.random()*10|0);
variables.push( "gcd", "PI" );
values.push( function gcd(a, b) {return b ? gcd(b, a % b) : a;} );
values.push( function PI() {return Math.PI;} );
variables.push("'use strict';return(" + stack.pop() + ")");
alert("Result: " + Function.apply(0, variables).apply(0, values));- Оператор по своей сути сохраняет свою длину (мы добавим число к имени функции для целей этого вопроса). Это решение унаследовало все преимущества традиционной RPN. Кроме того, это упрощает чтение синтаксического анализатора. Кроме того, отладка упрощается, поскольку новые аргументы не вставляются случайно. Однако это усложняет манипуляции и генерацию кода RPN. Обновление и создание списков аргументов затруднено, потому что это решение отклоняется от аспекта независимости токенов RPN, так что добавление аргумента (и изменение арности) требует двух действий и одного поиска (по сравнению с традиционным одним действием и нулевым поиском): (1.) вставить аргумент, (2.) найти позицию оператора переменной длины и (3.) обновить длину оператора.
var rpn = prompt("Please enter RPN string, where each token is " +
"separated by a space", "x 210 gcd2 x 6 * 126 gcd3").trim()
.split(/\s+/);
var stack = [], variables = [], values = [];
for (let i = 0, len = rpn.length|0, m; i < len; i=i+1|0) {
if (/^\d*(\.\d*)?$/.test(rpn[i]) && rpn[i] !== "") {
stack.push( rpn[i] );
} else if (/^[a-z]$/i.test(rpn[i])) {
stack.push( rpn[i] );
if (!~variables.indexOf(rpn[i])) variables.push( rpn[i] );
} else if (m = rpn[i].match(/^([a-z]+)(\d+)$/i)) {
if (stack.length<m[2])throw Error("No operand for "+rpn[i]);
stack.push( m[1] + "(" + stack.splice(-m[2]) + ")" );
} else {
if (stack.length<2)throw Error("No operand for " + rpn[i]);
const firstPop = stack.pop(); //lacks check if stack empty
stack.push( "(" + stack.pop() + rpn[i] + firstPop + ")" );
}
}
if (stack.length !== 1) throw Error("Invalid RPN got: " + stack);
for (let i = 0, len = variables.sort().length|0; i < len; i=i+1|0)
values[i] = +prompt(variables[i] + " = ", Math.random()*10|0);
variables.push( "gcd" );
values.push( function gcd(a, b) {return b ? gcd(b, a % b) : a;} );
variables.push("'use strict';return(" + stack.pop() + ")");
alert("Result: " + Function.apply(0, variables).apply(0, values));- Вложенные массивы в стеке (демонстрация невозможна). Это решение предполагает сохранение аргументов в списке перед оператором в стеке, что делает прямое выполнение кода очень простым. Однако это нарушает все принципы и преимущества RPN, заключающиеся в наличии плоского списка элементов. Возможно, если бы списки были только одиночными, не было бы слишком большой проблемы; однако для моего варианта использования я бы получил глубоко вложенные списки. Таким образом, манипулирование RPN и генерация RPN становятся очень сложными.
Экстраполяция единственного вопроса: есть ли другие возможные решения этой проблемы? Каково стандартное (наиболее часто используемое) решение этой проблемы? Существуют ли фундаментальные проблемы с моими решениями (пожалуйста, приведите встречные примеры)? Я упустил из виду некоторые плюсы/минусы моих решений? Можно ли улучшить алгоритмы моих решений?
@RaymondChen Спасибо за ваш вклад. Ваша идея - тот же алгоритм, что и третий вариант, указанный выше, который заключается в том, чтобы где-то хранить длину как явное целое число. Независимо от того, хранится ли длина как часть имени функции (как в демонстрации) или как другой параметр (как в вашем предложении), это один и тот же алгоритм, потому что длина находится в той же атомарной единице, что и оператор. Что касается вашего вопроса, я говорю об изменении арности, потому что мой оптимизатор выбросит концепцию фиксированного количества аргументов в окно и добавит аргументы в код JS для уменьшения размера.
Я бы использовал объектно-ориентированный язык программирования для разработки Вашего калькулятора. Вам нужно только заботиться о связи между именем, которое вводит пользователь, и внутренним массивом, переменной, значением или функцией. Поэтому, если вы определяете функцию, которая принимает n аргументов, арность этой функции не имеет значения, поскольку аргументы находятся в стеке и обрабатываются оттуда.
@Каплан Спасибо. Вы правы, что я использую объектно-ориентированный JavaScript. Однако я не разрабатываю калькулятор; Я представляю синтаксис кода, не зависящий от языка, в RPN, чтобы его можно было оптимизировать перед преобразованием в целевой язык кода. Арность функций имеет большое значение, потому что я генерирую фрагмент текста кода (не выполняя RPN, а просто объединяя RPN вместе в фрагмент текста, написанный на целевом языке кода). Кроме того, демо вообще не представляют мой реальный код. Фактический код представляет собой один внутренний этап в длинном конвейере.
В данном случае я бы предпочел вариант 3. Очень интересно. Мне любопытно увидеть что-то в результате. Если вам нужны какие-либо предложения, здесь это язык RPN, который выглядит весьма полезным.
RetroForth, Factor, Joy, RPL (обратная полировка Lisp) и другие поддерживают списки в стеке. Используя это, вариационная функция просто принимает список аргументов.
@AshleyF Это возможная идея. Добавлю в список возможных предложений. Тем не менее, я почти наверняка не смогу его использовать, потому что он устраняет самое большое преимущество RPN, а именно представление плоского списка.
7 решает эту проблему, используя специальное слово fn, которое отделяет параметры от остальной части стека. Смотрите help fn.
@Kaplan Спасибо за ваш вклад. Я не очень хорошо знаю 7-й, но похоже, что fn служит той же цели, что и # в варианте 1. fn, кажется, начинает список аргументов, заканчивающихся функцией, с помощью которой они вызываются, что позволяет вкладывать несколько уровней fn. Это то же поведение, что и # в первом варианте. Пожалуйста, поправьте меня, если я ошибаюсь.
Это похоже. fn — это заполнитель в стеке. Однако в основном он предназначен для вызова функций Java. Для 7-го слова fn>cnt необходимо удалить fn и поместить в стек количество следующих параметров. Как в Форте, как сказал Чен.
Ответы 2
Я думаю, вы уже рассмотрели варианты: если вам нужно передать список аргументов переменной длины, то либо ваш язык должен иметь собственную структуру данных, позволяющую всему списку быть одним значением в стеке (т.е. вложенные списки, как в #4, или их подобие, как в #2, где списки представлены в виде строк, разделенных запятыми, и не могут содержать другие списки), иначе элементы списка должны быть отдельными значениями в стеке. В этом случае переменная длина должна определяться либо дозорным (как в #1), либо полем длины (как в #3). Это кажется исчерпывающим.
Что касается преимуществ и недостатков:
- № 2 в основном является версией № 4, но со странной семантикой (оператор
,может либо создать список из 2 элементов, добавить или добавить элемент в список, либо объединить два списка, в зависимости от контекста), и списки не являются объекты первого класса, потому что список не может содержать списки. - № 1 и № 3 аналогичны сходствам / различиям между строками с нулевым завершением и строками с префиксом длины. В настоящее время обычно считается, что последовательности с префиксом длины лучше, чем использование дозорного, потому что вы можете прочитать длину за время O (1), и если какое-то значение обрабатывается по-другому как дозорный, то оно не может встречаться в последовательности ( если нет способа избежать этого).
Лично я предпочитаю вариант № 4, потому что язык программирования не очень полезен для общих целей, если в нем нет списков/массивов в качестве первоклассных объектов. Я не уверен, что именно вы подразумеваете под «это нарушает всю заповедь и преимущество RPN [...] манипулирование RPN и создание RPN становится очень трудным». Вполне возможно иметь синтаксис для создания списков и вложенных списков в конкатенативный язык вроде RPN.
Взяв в качестве примера мой собственный игрушечный язык fffff, код [1 2 3]. создает последовательность, открывая новый стек с помощью оператора [, помещая буквальные значения 1, 2 и 3 в этот новый стек, а затем закрывая новый стек с помощью оператор ]., который также помещает ссылку на новый стек в ранее текущий стек. Это подчиняется свойству конкатенации, потому что, если, например, функция three_and_close определена как выполняющая 3 ]., тогда код [1 2 three_and_close ведет себя так же, как исходный код; поэтому выделение частей кода по-прежнему так же просто, как и в стандартном RPN.
Спасибо за конструктивный ответ. #2 и #4 отличаются тем, что используют несвязанные алгоритмы. Удивительно, но я на самом деле склоняюсь к № 2, потому что это кажется более сплоченным продолжением RPN. Никогда нет необходимости иметь вложенные списки из-за того, как работает rpn (вложенные списки всегда будут вызывать ошибки. Думайте о них как о варагах: вы не можете вкладывать список аргументов). Кроме того, семантика для № 2 довольно проста: 1 2 , -> [1, 2]; и ~ 1 , -> [*empty*, 1] -> [1]; и 1 ~ , -> [1, *empty*] -> [1]. Вложенные запятые сглаживаются в 1-глубокий список. Проблема
У меня есть с № 1, № 3 и № 4, что это добавляет дополнительную семантику, которую необходимо учитывать. Он отличается от простой модели RPN. В #2 запятые ведут себя так же, как оператор сложения. В #1, #3 и #4 требуется дополнительная логика для обнаружения и обработки особых случаев, что делает код более сложным, поэтому его сложнее разрабатывать, а отладка может занять больше времени. Позвольте мне прояснить: я еще не решил. Я задаю этот вопрос на случай, если есть какие-то аспекты № 1, № 3 и № 4, которые я не принял во внимание. Я не хочу использовать # 2, а потом понимаю, что мне нужно перезапустить с нуля
При этом вы правы в том, что № 2 и № 4 являются концептуальными близнецами друг друга. Каждый оператор имеет список аргументов, которые сопровождают его. № 2 выглядит многообещающе для меня по тем же причинам, что и № 4, и причина, по которой я смотрю на № 2, заключается в том, что его гораздо проще реализовать, потому что он гораздо более связный в том смысле, что с точки зрения реализации он остается соответствует концепции постфиксных операторов и фиксированного числа операндов. Кроме того, я согласен с вашим сравнением между № 1 и № 3, и я согласен с тем, что № 3 было бы легче реализовать, чем № 1.
Что касается «вы не можете вложить список аргументов», вы можете, если функция принимает списки в качестве своих аргументов. Я не совсем уверен, что вы имеете в виду под особыми случаями в # 4 - если вы имеете в виду, что такие операции, как +, должны будут проверять, что их операнды являются числами, а не массивами, то у вас все еще есть эта проблема, например, с кодом, таким как 1 2 , 3 +.
Спасибо за ваши идеи. Это отличный момент, когда операторы должны будут проверять типы своих входных данных. Причина, по которой вы не можете вложить список аргументов, заключается в том, что список аргументов сам по себе ничего не значит. Чтобы создать массив, вам нужен специальный оператор, например MAKE_ARRAY. При этом выполнение 1 2 , 3 , mean вызовов означает с тремя аргументами, тогда как 1 2 , 3 , MAKE_ARRAY mean вызовов означает с одним аргументом. Чтобы вложить: 1 2 , MAKE_ARRAY 3 4 , MAKE_ARRAY , 5 6 , MAKE_ARRAY , MAKE_ARRAY flatten эквивалентно flatten([[1,2],[3,4],[5,6]]).
Я не уверен, что ваш план состоит в том, чтобы рассматривать каждую функцию, которую вы реализуете, как отдельный оператор со своей собственной отличной арностью или иметь один оператор «вызова функции», который извлекает необходимое количество аргументов из стека операндов оценщика перед вызовом функция.
Если последнее, самое простое преобразование обратного польского может быть из:
имя(выражение1, выражение2...выражениеN)
к этому:
имя expr1 expr2...exprN N callFunc
Имея в виду, что любое "exprX" может быть сколь угодно сложным, включая вызовы собственных функций. Это не имеет значения; к моменту достижения "callFunc" вам нужно беспокоиться только о самых верхних элементах N+2 в стеке операндов. Самым сложным моментом является отслеживание того, сколько аргументов действительно присутствует, и обеспечение того, чтобы количество попадало в RPN непосредственно перед «callFunc».
Для этого нужен какой-то стек для учета вложенных функций, но в остальном это не так уж сложно. На самом деле можно использовать стек операторов (сохраняйте счетчик «под» оператором «callFunc», известным смещением и обновляйте его каждый раз, когда встречается запятая. Это, естественно, заботится о вложенности функций, но это не единственный способ) .
При выполнении "callFunc" принимает один аргумент, N, количество аргументов для извлечения из стека операндов. Их вы можете поместить в список или массив, который вы можете передать «имени», как только вы это сделаете и вызовете (скорее всего, косвенно, используя какой-то словарь).
Чтобы быть полным, вы, вероятно, захотите выполнить проверку ошибок во время синтаксического анализа, чтобы убедиться, что количество и тип аргументов верны для вызываемой функции (вы можете хранить эту информацию в том же словаре, который указывает на код, который оценивает функцию). Также следите за появлением запятых там, где их быть не должно, как и во всех неправильных выражениях. Тогда оценщик может весело работать, не беспокоясь ни о чем из этого.
Не уверен, что вы подразумеваете под «добавление аргумента требует двух действий и одного поиска (в отличие от традиционного одного действия и нулевого поиска)». В традиционных функциях с фиксированной арностью вы не можете добавить аргумент, не удалив другой аргумент для сохранения арности. В любом случае, другой вариант - сделать арность еще одним параметром оператора.
arg1 arg2 arg3 ... argN N op. Это то, что делают слова Forthpickиroll.