Почему 2 + 3 * 4
не 20

Токены складываются в дерево так, чтобы операции с более высоким приоритетом (умножение и деление) оказались глубже, чем сложение и вычитание — вычисление дерева всегда идёт снизу вверх, поэтому глубокие узлы считаются первыми. Форма дерева и есть приоритет операций, а не отдельное правило поверх него.

Дерево обходится рекурсивно снизу вверх: сначала считаются самые глубокие узлы, их результат подставляется в родительский узел, и так до самого верха.

Шаги 1-2 выше — токенизация и построение AST — это буквально то же самое, что делает любой настоящий компилятор, включая, например, swiftc (компилятор Swift), просто с гораздо большим числом видов узлов: функции, классы, протоколы, а не только числа и арифметика.

Разница начинается на шаге 3. Наш инструмент дерево вычисляет — сразу получает число. Настоящий компилятор дерево не вычисляет, а превращает в другой код, шаг за шагом:

SIL (Swift Intermediate Language) — собственное промежуточное представление Swift, на котором компилятор делает специфичные для языка оптимизации (например, для автоматического подсчёта ссылок, ARC), прежде чем передать результат в LLVM — тот же бэкенд, что используют Clang (C/C++) и Rust, только каждый язык приходит в него уже через своё промежуточное представление.

Выражение 6 ÷ 2(1 + 2) не раз становилось вирусным именно потому, что разные калькуляторы (и разные люди) реально дают разные ответы:

Попробуйте набрать 6 / 2 (1 + 2) на шаге 1 этой страницы — вы получите настоящую ошибку разбора, а не число. Наша грамматика (как и почти любой язык программирования) вообще не поддерживает «слитное» умножение без явного знака * — и именно поэтому у формальных языков такой неоднозначности в принципе не бывает: неоднозначную запись они просто не принимают, вместо того чтобы выбирать одну из двух трактовок.