Денис Загаевский

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

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

Польская нотация учитывает всё, что угодно. В смысле, что напишешь, то и будет.
унарные операторы? Делай две операции - UNARY_MINUS, MINUS. 1 1 UNARY_MINUS MINUS == 2
Сложные операторы? A B C TERNARY (не лениво? ну можно и лениво сделать)
Функции? a b c d 4 max call. Здесь a, b, c, d, 4, max - аргументы, они все ложатся в стек. Интерпретатор видит call, достает из стека функцию (max), понимает, что это функция с переменным числом аргументов, достает это число (4), достает остальные аргументы по количеству, вызывает функцию max(a b c d).
В Полизе могут быть инструкции, управляющие потоком выполнения 1234 JUMP - переводит курсор на адрес 1234.
Всё зависит от твоей извращенности, короче.
Чтобы не быть голословным, вот мой пет-проект, там вычисление как раз на Полизе реализовано.

У польской нотации есть минусы - сложно анализировать программу, вычислять типы. Сложно оптимизировать. Для этого лучше подходят AST.

В целом вы верно поняли про деревья разбора. Тема довольно обширная, освещать её в ответе здесь - сложно. Я бы посоветовал вот эту книжку: ftp://sp.cs.msu.ru/victor/compilers.pdf
Там довольно подробно освещено это всё.