Обратная Польская нотация: Операторы после операндов В обратном польском обозначении оператор ставится после его операндов, в отличие от инфиксной формы. Последовательность 2 1 + дает 3, а (2 + 1) 3 * становится 2 1 + 3 *, что дает 9. Цель состоит в том, чтобы реализовать интерпретатор RPN в сборке x86-64. Удивительно, но эта версия оказалась более понятной и сжатой, чем попытка использовать C, хотя некоторые алгоритмы по-прежнему проще создавать на C.
Минимальный каркас ELF64 и повторное использование библиотеки ввода-вывода Создайте минимальную программу ELF64 с общедоступной точкой входа и разделами текста/данных. Используйте существующую библиотеку ввода-вывода для доступа к системным вызовам и печати, включая процедуру печати целых чисел, которая обрабатывает негативы. Создайте процедуру интерпретации, которая принимает входную строку и возвращает вычисленное число. Подготовьте строку тестового выражения, заканчивающуюся нулевым байтом.
Сканирование до конца и пропуск пробелов Обведите входные данные указателем в RDX до нулевого значения. Сравните каждый байт с 0, чтобы определить конец, и с пробелом, чтобы пропустить разделители. Этот предварительный проход гарантирует, что будут обработаны только значимые токены. Для аккуратного отображения результатов используются процедуры вывода.
Токенизация, которая обрабатывает числа и именованные операторы Считывайте по одному символу за раз и различайте число и оператор. Представляйте операторы в виде строк, а не отдельных символов, чтобы сделать интерпретатор расширяемым (например, добавляя abs, neg, flip). Это позволяет избежать жесткого кодирования односимвольных сравнений и обеспечивает соответствие новых функций тем же правилам синтаксического анализа. Токены разделяются пробелами.
Считывание маркера и измерение его длины Реализуйте цикл чтения, который накапливает счетчик длины токена. Продвигайтесь вперед до тех пор, пока не встретите нулевой байт или пробел, затем остановитесь. Счетчик (в RTX) фиксирует точную длину текущего токена. Используйте метку для быстрого считывания, чтобы перейти к разделителю, как только он будет найден.
План регистрации и трюк с временным аннулированием Регистры распределения: RDX содержит входной указатель, RTX - длину токена, а RBX/RAX служат для обработки стека вычислений и арифметических результатов. Используйте R8/R9, чтобы сохранить байт-разделитель и запомнить, как далеко нужно продвинуться. Временно запишите ноль в конце маркера, чтобы рассматривать его как отдельную строку в стиле C. После обработки восстановите сохраненный байт и переместите указатель вперед на сохраненное смещение.
Сопоставление операторов или преобразование чисел Сравните подстроку токена с известными именами операторов (сложение, вычитание, умножение, деление). Если найдено совпадение, выполните соответствующую процедуру; в противном случае обработайте токен как число. Преобразуйте числа с помощью строковой функции в целое число из библиотеки и поместите результат в RAX. Метка на промежуточном этапе возвращает поток в основной цикл сканирования.
Поток оценки на основе стека Отправляйте числа в стек процессора по мере их обработки. Когда появится оператор, введите два последних значения, выполните операцию с результатом, стандартизированным в RAX, и отправьте результат обратно. Это позволяет выполнять цепную оценку: 5 + 2 становится 7, которые затем можно умножать или комбинировать иным образом. После каждого токена восстанавливайте разделитель и продвигайтесь вперед, используя точную длину токена.
Сохранение регистров и выдача результата По завершении вставьте конечное значение из стека в RAX, чтобы получить возвращаемое функцией значение. Поскольку используется несколько регистров, сохраняйте их при вводе и восстанавливайте в обратном порядке при выходе. В ранних запусках показано значение 7 для простого сложения и получения правильных результатов по мере добавления большего количества чисел и операций. Таким образом, проверяется базовый интерпретатор.
Выполнение операций вычитания, умножения и деления Вычитание требует сохранения порядка операндов при выводе значений. При умножении используется IMUL с RAX в качестве конечного значения, чтобы избежать искажения RDX. Деление выполняется только целыми числами с помощью IDIV, при этом RDX подготавливается соответствующим образом, так что частное в конечном итоге получается в RAX. Тесты подтверждают 10 2 - = 8, 10 2 * = 20, 10 2 / = 5, и значение составного выражения равно 7.
Добавление ABS, NEG и FLIP в качестве операций стека ABS использует одно значение, проверяет, является ли оно отрицательным, и при необходимости отменяет его. NEG меняет знак для одного значения. FLIP меняет местами два верхних значения стека, позволяя изменять порядок таких важных операций, как деление; например, при замене 2 и 10 перед делением получается 5. Комбинированные последовательности с отрицательным значением, умножением и ABS дают ожидаемые результаты.
От рабочего калькулятора RPN до планов на будущее Благодаря этим компонентам интерпретатор становится компактным и практичным калькулятором RPN на ассемблере. Перспективным направлением является калькулятор в стиле Lisp, который вычисляет вложенные выражения с использованием аналогичных механизмов. Функция интегрирована в массовую библиотеку на GitHub, готовую к загрузке и встраиванию в пользовательские инструменты.