I. 1. Обратная польская запись - madwareru/drafting-interpreters GitHub Wiki

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

3 4 9 + * 7 -

Дословно можно расшифровать её так:

1. Положить на стек число 3
2. Положить на стек число 4
3. Положить на стек число 9
4. Снять со стека два операнда, выполнить над ними операцию сложения, и положить результат на стек
5. Снять со стека два операнда, выполнить над ними операцию умножения, и положить результат на стек
6. Положить на стек число 7
7. Снять со стека два операнда, выполнить над ними операцию вычитания, и положить результат на стек

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

Sub(Mul(3, Add(4, 9)), 7)

где Sub, Mul и Add это функции от двух операндов, выполняющих операции вычитания, умножения и сложения соответственно, или же привычного нам инфиксного выражения

3 * (4 + 9) - 7

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