Comments 12
Такое представление хорошо, когда AST статично. Но это как-то несерьёзно. Даже в банальном Питоне программа может модифицировать своё AST в рантайме.
Перевод ужасный. Лучше читать оригинал.
структура отягощённая указателями
Использовать индексы вместо указателей
Если кто-то не понял тайный смысл статьи: всё в ней обсуждаемое актуально только в языке Rust, потому что адекватное ast на нём написать невозможно. Именно так, через костыли и массивы реализовано ast в компиляторе Rust
В нормальном языке люди пишут естественно через указатели, при этом если им нужно дооптимизироваться, они делают арену памяти, откуда аллоцируют ast ноды и в итоге получают все преимущества без недостатков
Осталось сделать один шаг до обратной польской нотации и совсем избавиться от индексов.
Если ограничиваться только арифметическими выражениями, то да. А если требуется расширить язык условными выражениями (а так же переходами, циклами и т.д.), то в массив обратной польской записи так или иначе придётся вставлять индекс на ячейку для перехода.
Но да, на протяжении всей статьи не покидало ощущение, что автор оригинала изобрёл ОПЗ, слегка его усложнив
В своём компиляторе я использую классический подход с выделением памяти (почти) под каждый узел синтаксического дерева. Может это и не так быстро, как плоское представление, но мне производительности достаточно. В процессе компиляции парсинг (построение этого дерева) занимает всего пару процентов времени и что-то там оптимизировать не имеет смысла. Всё остальное время занимает построение промежуточного кода и оптимизации. В языковом сервере парсинг тоже достаточно быстр, чтобы его можно было вызывать на каждое нажатие кнопки.
Плоская структура имеет какой-то смысл наверное только в интерпретаторах, где деревья многократно проходятся. В компиляторах же это обычно не так.
Не понимаю что мешает автору использовать тот же массив но вместо индексов оставить ссылки. Будет и локальность данных и те же ееш линии.
Ведь все эти сжатия адресов до 32 бит, относительное индексирование итд ведёт к большему количеству багов.
Интересная статья, спасибо! Добавлю что еще одно потенциальное преимущество индексов перед указателями - возможность максимально просто сдампить такое AST в файл и загрузить из файла обратно в память. Зачем это может быть нужно? Например хранить частично скомпилированный код каких-то библиотек, содержащих метапрограммы (те же шаблоны или макросы). Хранение этого в классических *.lib файлах невозможно.
Для такого дерева, где только операции и литералы, никакие индексы не нужны. Вполне можно воспользоваться https://ru.wikipedia.org/wiki/Двоичная_куча
Друзья, здесь не про "лучше-хуже" (как известно во всём есть множество +/-) и не про "нормальные языки", и не про "как можно сделать" а рассказ об аренах, и пример как их можно заюзать в AST. Демонстрация техники использования арен, только и всего. (Хоть, и не самая ясная.)
Выравнивание AST (и других структур данных, используемых при работе с компилятором)