По работе пишу DSL, в котором смешиваются декларативные и императивные подходы. Застрял на фазе генерации промежуточного кода, потому что непонятно, как подобрать такой дизайн, который можно будет легко расширять. Например, известная форма SSA — какие абстрации выбрать для результатов операций? Должна ли "инструкция" хранить ссылку на результат, или же генератор промежуточного кода должен возвращать кортеж из адреса и инструкции? Или адреса и аккумулятора инструкций? И всё в таком духе.

Какие можно посмотреть проекты, где идеи компиляторов реализованы на бОльшем уровне нежели студенческая курсовая, но при этом не так сложно, как в GCC и LLVM? В книжках (Modern Compiler Design, Engineering a Compiler), к сожалению, очень-очень-очень поверхностный псевдокод и куча "капитанских" идей, до которых человек, решивший писать компилятор, в состоянии дойти самостоятельно. Парадокс, но the dragon book на фоне остальных смотрится куда как более фундаментальной, хотя есть мнение, что для разработки современных компиляторов её даже открывать не стоит.

P.S. Открыл код CPython. Лексер и парсер реализованы вручную. Закрыл код CPython.

Сначала придумай LLVM = Low Level Virtual Machine

Здравствуйте, cppguard, Вы писали:

C>По работе пишу DSL, в котором смешиваются декларативные и императивные подходы. Застрял на фазе генерации промежуточного кода, потому что непонятно, как подобрать такой дизайн, который можно будет легко расширять. Например, известная форма SSA — какие абстрации выбрать для результатов операций? Должна ли "инструкция" хранить ссылку на результат, или же генератор промежуточного кода должен возвращать кортеж из адреса и инструкции? Или адреса и аккумулятора инструкций? И всё в таком духе.
Я компилируемые dsl не делал, хватало интерпретируемых. Но простые варианты компиляции у меня просто эммитили бинарный код под целевую платформу без сложных оптимизаций.

C>Какие можно посмотреть проекты, где идеи компиляторов реализованы на бОльшем уровне нежели студенческая курсовая, но при этом не так сложно, как в GCC и LLVM? В книжках (Modern Compiler Design, Engineering a Compiler), к сожалению, очень-очень-очень поверхностный псевдокод и куча "капитанских" идей, до которых человек, решивший писать компилятор, в состоянии дойти самостоятельно. Парадокс, но the dragon book на фоне остальных смотрится куда как более фундаментальной, хотя есть мнение, что для разработки современных компиляторов её даже открывать не стоит.

Хз, но вот несколько ссылок может пригодиться

SSA-based Compiler Design
An Incremental Approach to Compiler Construction
https://github.com/MattPD/cpplinks/blob/master/compilers.md

ps: Самый простой компилятор получается для forth-а на стековой машине

Здравствуйте, cppguard, Вы писали:

C>P.S. Открыл код CPython. Лексер и парсер реализованы вручную. Закрыл код CPython.

Я никогда не писал языков, сравнимых по сложности, скажем, с Си. Но для более простых языков, написание парсера что на bison, что руками занимает примерно одинаковое время и количество усилий. Потом, парсер, написанный на bison-е, проще поддерживать (например, проще вносить изменения в сам язык), но вот зато от рукописного парсера проще добиться внятной реакции на синтаксические ошибки. Парсер, написанный компилятором компиляторов, просто срывается в случае ошибки, и дальше его несет.

В g++ несколько лет назад переписали парсер руками. Вот примерно по этой причине. Надо сказать, написание парсера C++ — титанический труд, из-за сложности самого языка и его нерегулярности. Даже понять для себя его грамматику, во всех нюансах и детялях, весьма непросто. Так что это решение вызывает уважение.

Здравствуйте, cppguard, Вы писали:

C>По работе пишу DSL, в котором смешиваются декларативные и императивные подходы. Застрял на фазе генерации промежуточного кода, потому что непонятно, как подобрать такой дизайн, который можно будет легко расширять. Например, известная форма SSA — какие абстрации выбрать для результатов операций? Должна ли "инструкция" хранить ссылку на результат, или же генератор промежуточного кода должен возвращать кортеж из адреса и инструкции? Или адреса и аккумулятора инструкций? И всё в таком духе.
Тут непонятно, какая у вас будет целевая "машина". И непонятно, какие фичи вы хотите от своего DSL и его компилятора.
А примерно всё зависит как раз от этого.

Потому что если вы, скажем, хотите просто порождать Java-код, то вам достаточно трансформировать AST вашего языка в AST Java, и дать javac/JVM делать всё остальное.
Если вы хотите генерировать неуправляемый код — то вы будете, очевидно, порождать LLVM.
Если вы хотите, чтобы ваш компилятор умел делать какие-то оптимизации до того, как выплюнуть представление для следующих этапов конвеера, то всё зависит в первую очередь от того, какие оптимизации вы хотите делать.

C>P.S. Открыл код CPython. Лексер и парсер реализованы вручную. Закрыл код CPython.
Я в последнее время фанатею по PEG. Там не нужно пилить никакой лексер, а можно сразу писать грамматику.
Если брать, скажем, flow9 с его модулем lingo, то затраты труда на парсер, отдающий готовое CST, минимальны.
Как и затраты на написание трансформеров этого CST в примерно всё, что угодно. (Поэтому курс Методы Трансляции и Компиляции у нас читается как раз на этом языке).

Если не хочется экзотики, то вполне неплох Ohm-js. Правда, там semantic actions надо писать отдельно, что несколько затрудняет конверсию из AST в CST. Но тоже вполне подъемно.
Написание компиляторов на языках типа С/С++ мне представляется особой формой мазохизма; но это, наверное, оттого, что я сильно избалован.

Здравствуйте, cppguard, Вы писали:

C>Например, известная форма SSA — какие абстрации выбрать для результатов операций? Должна ли "инструкция" хранить ссылку на результат, или же генератор промежуточного кода должен возвращать кортеж из адреса и инструкции? Или адреса и аккумулятора инструкций? И всё в таком духе.
Вдогонку: SSA, как таковая, это просто некоторое ограничение на CFG.
Допустим есть у вас CFG, в котором есть присваивания "переменным". Преобразование в SSA-форму получает на выходе примерно такой же CFG, только в нём для каждой переменной присваивание ровно одно.
То есть узлы у нового CFG — точно такие же. За исключением Phi-nodes, которые собственно помогают "склеить" разные значения для одной и той же переменной в одну.
Трансформация "Multiple assignment" CFG в "Single static assignment" — штука совершенно рутинная.

И нужна она, опять-таки, только если этого требует целевой код. Например, если вы хотите делать всякие оптимизации над промежуточным представлением, или порождать SSA-форму типа того же LLVM IR.
Вы можете запросто обойтись вовсе без этого, если ваша целевая платформа не требует SSA. Например, в вашем DSL коде вовсе нет переменных, а есть только стек вычислений.
Или вы порождаете дотнетовый MSIL, в котором разрешены модификации переменных.

В общем, DSL бывают катастрофически разные. Очень трудно дать какие-то универсальные советы за пределами примитива вроде "как написать парсер".
Да и с написанием парсера в реальной жизни проблемы возникают не с тем, как выполнить собственно разбор корректного кода, а как сделать внятную диагностику ошибок.
Общая схема — генерализовать грамматику, разрешив "некорректные" с точки зрения строгого языка конструкции, и ругаться на них уже на этапе анализа AST/CST.
Ну, и жадный парсер вроде того же Ohm, который умеет выдавать результат в виде "expected a variable name, a constant, or a member name" тоже помогает.

Pzz>В g++ несколько лет назад переписали парсер руками.
Pzz>несколько лет назад
Ну или точнее двадцать лет назад

S>И нужна она, опять-таки, только если этого требует целевой код. Например, если вы хотите … порождать SSA-форму типа того же LLVM IR.
Разве это кто-то делает вручную? Я думал пользуются mem2reg и т.п. (https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/LangImpl07.html#memory-in-llvm)

Здравствуйте, Sinclair, Вы писали:

S>В общем, DSL бывают катастрофически разные. Очень трудно дать какие-то универсальные советы за пределами примитива вроде "как написать парсер".
S>Да и с написанием парсера в реальной жизни проблемы возникают не с тем, как выполнить собственно разбор корректного кода, а как сделать внятную диагностику ошибок.
S>Общая схема — генерализовать грамматику, разрешив "некорректные" с точки зрения строгого языка конструкции, и ругаться на них уже на этапе анализа AST/CST.
S>Ну, и жадный парсер вроде того же Ohm, который умеет выдавать результат в виде "expected a variable name, a constant, or a member name" тоже помогает.

Суть моего DSL в возможности определять ячейки, значения которых вычисляются на каждой итерации. Опционально можно задавать выражение для инициализации. Например, экспоненциальное скользащее среднее можно задать двумя выражениями:

ema = input
ema : alpha * input + (1 — alpha) * @

Выражения для ячеек могут включать значения других ячеек, поэтому частью процесса компиляции/трансляции является разрешение зависимостей с выявлением циклических зависимостей. Транслировать нужно как в Java/Python для выполнения в отладочном режиме, так и в C++/LLVM для генерации независимой программмы, которая реализует процедуры итеративного вычисления. Самое главное — нужна поддержка шаблонов в стиле С++. Чтобы пример выше можно было бы обобщить для произвольных alpha и input.

В принципе я бы мог обойтись простой трансляцией AST, но я точно знаю, что возникнут (уже возникли) различные требования к процессу трансляции, которые удобно выполнить в виде оптимизирующих проходов, потому и возникла идея реализовать IR и отдельные компиляторы IR-Python, IR-C++ и т.д.д

Здравствуйте, σ, Вы писали:

S>>И нужна она, опять-таки, только если этого требует целевой код. Например, если вы хотите … порождать SSA-форму типа того же LLVM IR.
σ>Разве это кто-то делает вручную?
σ>Я думал пользуются mem2reg и т.п. (https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/LangImpl07.html#memory-in-llvm)
Дело вкуса.

Здравствуйте, cppguard, Вы писали:

C>Суть моего DSL в возможности определять ячейки, значения которых вычисляются на каждой итерации. Опционально можно задавать выражение для инициализации. Например, экспоненциальное скользащее среднее можно задать двумя выражениями:

C>

C>ema = input
C>ema : alpha * input + (1 — alpha) * @

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

C>Транслировать нужно как в Java/Python для выполнения в отладочном режиме, так и в C++/LLVM для генерации независимой программмы, которая реализует процедуры итеративного вычисления. Самое главное — нужна поддержка шаблонов в стиле С++. Чтобы пример выше можно было бы обобщить для произвольных alpha и input.
По примеру непонятно, чего именно вы хотите от шаблонов. Вы хотите описывать не только прямые выражения для ячеек, но и именованные функции?
Вообще, шаблоны С++ — одна из самых замудрёных вещей в современном программировании. Мало кто задуряется с тем, чтобы поддерживать весь этот compile-time ужоснах с частичными специализациями и SFINAE.
Более конструктивный подход — это что-то типа семантических макросов, например, генерики дотнета.

C>В принципе я бы мог обойтись простой трансляцией AST, но я точно знаю, что возникнут (уже возникли) различные требования к процессу трансляции, которые удобно выполнить в виде оптимизирующих проходов, потому и возникла идея реализовать IR и отдельные компиляторы IR-Python, IR-C++ и т.д.д
Вот как раз непонятно, что именно вы там хотите делать в виде оптимизирующих проходов. Я бы просто выплёвывал код метода "выполнить итерацию" в соответствующем IR, а все дополнительные оптимизации типа constant propagation, common subexpression elimination и прочие dead code removal оставил бы следующим этапам конвеера.

Когда я пилил Linq2d, то напоролся на ограничения дотнетового джита — у него есть пороговые значения типа количества локальных переменных, после которого он перестаёт делать оптимизацию распределения регистров, и откатывается к memory always. Кроме того, некоторые оптимизации джит делать не умеет и не собирается — вроде loop peeling. Они для общего случая слишком дорогие. А для моего частного случая их сделать несложно, т.к. я порождал код для совершенно конкретной задачи (обход 2d-массива с вычислениями). Поэтому мне не нужно было детектировать циклы и угадывать, сколько итераций peel-нуть в начале и конце — эта информация доступна мне сразу же, т.к. все циклы я конструирую сам же. Так что некоторые рудиментарные оптимизации я делал сам.
Но опять же, такие оптимизации не шибко зависят от бэкенда, и работают на уровне исходных выражений. Т.е. я сначала порождаю тело цикла, внутри которого есть развесистые conditional expressions.
Затем я, зная пороговые значения для этих conditional expressions, порождал реплики этого тела с учётом ограничений. Например, если у нас в теле есть выражение типа (i > 0) ? a[i-1, j] : 0, то я делал отдельный цикл по j для i==0, и подставлял известное значение i в тело:

// i == 0:
for(j = 0; j < jMax; j++)
  t[i, j] = 0; // == (0 > 0) ?  a[i-1, j] : 0; условие тождественно ложно, поэтому можно выбросить левую ветку.

А потом порождал цикл, в котором i заведомо > 0:

// i >= 1: 
for(i = 1; i < iMax; i++)
  for(j = 0; j < jMax; j++)
    t[i, j] = a[i-1, j]; // == (i > 0) ?  a[i-1, j] : 0; условие тождественно ложно, поэтому можно выбросить правую ветку.

Поверх этого прикручивал как раз common subexpressions, и заодно повторно использовал локальные переменные (мне же известно, что они больше не потребуются за пределами одной итерации конкретного цикла).
Хороший компилятор такое делает сам, поэтому если бы я генерировал LLVM, то не задурялся бы и этим.

C>>Например, известная форма SSA — какие абстрации выбрать для результатов операций? Должна ли "инструкция" хранить ссылку на результат, или же генератор промежуточного кода должен возвращать кортеж из адреса и инструкции? Или адреса и аккумулятора инструкций? И всё в таком духе.
S>Вдогонку: SSA, как таковая, это просто некоторое ограничение на CFG.

SSA форма она не про control flow, а про data flow.

Здравствуйте, Sinclair, Вы писали:

S>По AST строим граф зависимостей, выполняем топологическую сортировку (заодно детектируя циклы), и, собственно, всё.
Звучит просто, я тоже так думал. Первый раз я споткнулся на том, что инициализация и итерации это разные блоки, должны быть разнесены в разные графы. Далее возможны различные комбинации: у ячейки есть инициализация, но нет итерации (константа по сути), обратный вариант, полный вариант (как в примере). Теперь чтобы сгенерировать результат из AST напрямую, нужно сразу знать адрес, по которому лежит ячейка. А чтобы его знать, нужно пройтись по графу зависимостей. Можно было бы сперва генерировать блок инициализации, назначать адреса ячейкам, у которых есть шаг инициализации, а потом запускать генерацию итеративного блока. Но тут есть маааленький нюанс — для эффективной обработка данных (ячеек у нас ожидается ооочень много) хорошо было бы назначать адреса ячейкам в порядке их использования (чтобы cache line не инвалидировать). То есть, если a зависит от b и с, то результат для b и c мы положем где-то рядом с a. Конечно, всегда можно составить такую программу, где последняя ячейка зависит от первой, но мы предполагаем, что так не будет. И вот получается, что чтобы назначить адреса оптимальным образом, нам нужно сгенерировать интеративный блок, а его мы не можем сгенерировать без инициализирующего блока. А если им будем сразу пытататься назначить адреса в инициализирующем блоке, то адреса будут неоптимальными. Поэтому и пришёл я к тому, что неплохо было бы генерировать SSA, а адреса ячеек назначать позднее, когда у нас есть линейное IR.

S>По примеру непонятно, чего именно вы хотите от шаблонов. Вы хотите описывать не только прямые выражения для ячеек, но и именованные функции?
S>Вообще, шаблоны С++ — одна из самых замудрёных вещей в современном программировании. Мало кто задуряется с тем, чтобы поддерживать весь этот compile-time ужоснах с частичными специализациями и SFINAE.
S>Более конструктивный подход — это что-то типа семантических макросов, например, генерики дотнета.

Не, всю мощь С++ я не собираюсь реализовывать. Мне нужно, чтобы алгоритм вычисления ячеек можно было параметризовывать константами и/или другими ячейками. Грубо говоря, чтобы были функции. В примере я привёл алгоритм вычисления EMA, но он жёстко завязан на ячейку с именем "input" и константу "alpha"/ Tак как у нас вычисления все сугубо чистые, то можно функцию один раз вычислить, и потом переиспользовать. И тут два варианта. Либо честно реализовать синтаксис вызова функций и добавись мемоизацию, либо шаблоны. Я выбрал шаблоны, потому что я просто буду разворачивать их в поддеревья AST и дальше генерировать код как для обычных ячеек.

S>Вот как раз непонятно, что именно вы там хотите делать в виде оптимизирующих проходов. Я бы просто выплёвывал код метода "выполнить итерацию" в соответствующем IR, а все дополнительные оптимизации типа constant propagation, common subexpression elimination и прочие dead code removal оставил бы следующим этапам конвеера.

Так для конвеера и нужна реализация IR, а её пока нет. Или хотя бы просто переход от древовидного представления к блочно-линейному. А нет, потому что я не понимаю, как это по-нормальному сделать, чтобы не было гигантских if-else или switch-case. Не понимаю, какие абстракции выбирать, чтобы IR представить. Всё крутится вокруг шаблона Visitor. Посмотрел, как сделано в llvm/clang, и не совсем понял их иерархию. Попросил GPT накидать мне примеров с генерацией кода из С++ в LLVM, и каждый раз это были какие-то встроенные вызовы, которые сразу берут исходник и по нему генерируют LLVM IR.

Здравствуйте, cppguard, Вы писали:
C>Звучит просто, я тоже так думал. Первый раз я споткнулся на том, что инициализация и итерации это разные блоки, должны быть разнесены в разные графы.
Непонятно. Что значит "разные блоки"?

C>Далее возможны различные комбинации: у ячейки есть инициализация, но нет итерации (константа по сути), обратный вариант, полный вариант (как в примере). Теперь чтобы сгенерировать результат из AST напрямую, нужно сразу знать адрес, по которому лежит ячейка.
C>А чтобы его знать, нужно пройтись по графу зависимостей. Можно было бы сперва генерировать блок инициализации, назначать адреса ячейкам, у которых есть шаг инициализации, а потом запускать генерацию итеративного блока. Но тут есть маааленький нюанс — для эффективной обработка данных (ячеек у нас ожидается ооочень много) хорошо было бы назначать адреса ячейкам в порядке их использования (чтобы cache line не инвалидировать).

C>То есть, если a зависит от b и с, то результат для b и c мы положем где-то рядом с a. Конечно, всегда можно составить такую программу, где последняя ячейка зависит от первой, но мы предполагаем, что так не будет. И вот получается, что чтобы назначить адреса оптимальным образом, нам нужно сгенерировать интеративный блок, а его мы не можем сгенерировать без инициализирующего блока.
Выглядит как-то сложно. Блоки нужно генерировать тогда, когда уже есть все нужные данные.
1. Построили полный список ячеек.
2. Построили граф зависимостей.
3. Отсортировали ячейки в соответствии с топологией зависимостей (тут я немного плаваю, но, судя по всему, вы уже решили эту задачу)
4. Породили адреса для каждой ячейки
5. Сгенерировали код.
Всё.

C>А если им будем сразу пытататься назначить адреса в инициализирующем блоке, то адреса будут неоптимальными. Поэтому и пришёл я к тому, что неплохо было бы генерировать SSA, а адреса ячеек назначать позднее, когда у нас есть линейное IR.
Не очень понятно, зачем вам тут SSA. В вашем языке на каждой итерации ячейка вычисляется только один раз?
Опять же, не очень понятно, как должна работать формула вида a = a + b. Берётся значение a с предыдущей итерации, и прибавляется значение b с текущей итерации?

C>Не, всю мощь С++ я не собираюсь реализовывать. Мне нужно, чтобы алгоритм вычисления ячеек можно было параметризовывать константами и/или другими ячейками. Грубо говоря, чтобы были функции. В примере я привёл алгоритм вычисления EMA, но он жёстко завязан на ячейку с именем "input" и константу "alpha"/ Tак как у нас вычисления все сугубо чистые, то можно функцию один раз вычислить, и потом переиспользовать. И тут два варианта. Либо честно реализовать синтаксис вызова функций и добавись мемоизацию, либо шаблоны. Я выбрал шаблоны, потому что я просто буду разворачивать их в поддеревья AST и дальше генерировать код как для обычных ячеек.
Не очень понятно, зачем вам шаблоны. Можно же делать простые чистые функции, типа

def ema(coeff, signal, prevValue) => coeff * signal + (1 — coeff) * prevValue;

C>Так для конвеера и нужна реализация IR, а её пока нет.
Всё работает в зависимости от ЯП, выбранного для компилятора.
Скажем, если бы речь шла о каком-нибудь ФП, то вместо IR у вас было бы несколько CST (представленных в виде каких-то алгебраических типов), и набор функций, преобразующих одно в другое.
Например, на первом этапе у вас в формулах термы были бы просто IntConst | CellName, а на втором этапе вместо CellName были бы CellId. Преобразователь при этом был бы несложной функцией с паттерн-матчингом.
Если вы пишете на императивном ОО-языке, то в термах были бы CellRef, которые сразу ссылаются на экземпляры CellDefinition. И в каком-то из проходов вы в каждый CellDefinition пропишете его адрес.

C>Или хотя бы просто переход от древовидного представления к блочно-линейному. А нет, потому что я не понимаю, как это по-нормальному сделать, чтобы не было гигантских if-else или switch-case.
Эмм, все обработки программ делаются при помощи обходов дерева. Если ООП — то паттерн "визитор", если ФП — то паттерн-матчинг.

Всё, никаких вариантов нету .
То же самое блочно-линейное представление порождается (в ООП) при помощи Visitor, который кладёт узлы дерева в соответствующий block writer.
Например, берём арифметическое выражение и преобразуем его в обратную польскую запись — если вычислять его нужно на стековой VM. А если не нужно — то просто записываем это выражение в виде инструкций LLVM IR и алга.

Здравствуйте, cppguard, Вы писали:

C> Теперь чтобы сгенерировать результат из AST напрямую, нужно сразу знать адрес, по которому лежит ячейка. А чтобы его знать, нужно пройтись по графу зависимостей.

Это называется аннотированное AST. Сначала собирается AST, затем оно прогоняется через ряд процессоров, каждый из которых добавляет какие-то метаданные к узлам AST. Затем AST, обвешанное дополнительными атрибутами, уходит в кодогенератор. Если не любите мутабельное состояние, можно дополнительные метаданные собирать в отдельных структурах, смотря как удобнее.

Здравствуйте, Sinclair, Вы писали:

S>Непонятно. Что значит "разные блоки"?

Блок с выражениями типа "a = b" испольняется один раз, блок с выражениями типа "a : a + b" исполняется столько раз, сколько есть итераций. Каждый из них не зависит от другого, поэтому оба можно генерировать независимо.

S>Выглядит как-то сложно. Блоки нужно генерировать тогда, когда уже есть все нужные данные.
S>1. Построили полный список ячеек.
S>2. Построили граф зависимостей.
S>3. Отсортировали ячейки в соответствии с топологией зависимостей (тут я немного плаваю, но, судя по всему, вы уже решили эту задачу)
S>4. Породили адреса для каждой ячейки
S>5. Сгенерировали код.

Вот контрпример:

b = 1
a = b
b : a + b

Если не разделять шаг инициализации и шаг итерации, то получается циклическая зависимость и простой топологической сортировкой задача не решается, нужно обрабатывать блоки "=" и ":" отдельно.

S>Опять же, не очень понятно, как должна работать формула вида a = a + b. Берётся значение a с предыдущей итерации, и прибавляется значение b с текущей итерации?
Да, в этом и основная суть DSL. Только с "=" такое не прокатит, потому что это выражение для инициализации. А итеративное вычисление задаётся в виде "a : a + b".

Здравствуйте, cppguard, Вы писали:

C>Блок с выражениями типа "a = b" испольняется один раз, блок с выражениями типа "a : a + b" исполняется столько раз, сколько есть итераций. Каждый из них не зависит от другого, поэтому оба можно генерировать независимо.
Ну и прекрасно. Так и пишем:

function generateCode(ast, targetBuilder)
{
   generateInitBlock(ast, targetBuilder)
   generateIterationBlock(ast, targetBuilder);
}

function generateInitBlock(ast, targetBuilder)
{
   let initExpressions = getInitExpressions(ast);
   for(var initExpression of initExpressions)
     generate(initExpression, targetBuilder);
}

const getInitExpressions = (ast) => ast.expressions.filter(e => isInitExpression(e));
const getIterExpressions = (ast) => ast.expressions.filter(e => isIterExpression(e));


function generateIterationBlock(ast, targetBuilder)
{
   let iterationExpressions = getIterationExpressions(ast);
   generateIterationCycle(targetBuilder, header = ..., body = (b) => generateSingleIteration(iterationExpressions, targetBuilder);
}

S>>Выглядит как-то сложно. Блоки нужно генерировать тогда, когда уже есть все нужные данные.
S>>1. Построили полный список ячеек.
S>>2. Построили граф зависимостей.
S>>3. Отсортировали ячейки в соответствии с топологией зависимостей (тут я немного плаваю, но, судя по всему, вы уже решили эту задачу)
S>>4. Породили адреса для каждой ячейки
S>>5. Сгенерировали код.

C>Вот контрпример:
C>

C>b = 1
C>a = b
C>b : a + b
C>

C>Если не разделять шаг инициализации и шаг итерации, то получается циклическая зависимость и простой топологической сортировкой задача не решается, нужно обрабатывать блоки "=" и ":" отдельно.
Эмм, ну значит надо разделять шаг инициализации и итерации. Не вижу в этом ничего особенного.
Для начала можно это делать "на ходу", как в примере выше, где каждый раз, как нам нужны "только init" или "только iter", мы бежим по списку и выполняем фильтрацию.
Если окажется, что фильтры по ходу компиляции отрабатывают многократно, то можно это соптимизировать, поменяв форму дерева.
Вначале у нас было "дерево" вида

{ 
  expressions: AnyExpression[] // AnyExpression = InitExpression | IterExpression
}

Берём и преобразуем его к виду

{ 
  initExpressions: InitExpression[],
  iterExpressions: IterExpression[]
}

Можно это делать при помощи двукратного вызова фильтра. А можно — за один проход:

const splitAst = fold(ast, { initExpressions:[], iterExpressions:[] }, 
  (sa, expr) => expr is InitExpression 
    ? { [...sa.initExpressions, expr], sa.iterExpressions}
    : { sa.initExpressions, [...sa.iterExpressions, expr]})
}

И дальше уже пользуемся готовыми массивами.
Оптимизировать инициализацию не надо, т.к. она в любом случае исполняется один раз. Так что при выборе порядка размещения ячеек надо анализировать только граф зависимостей в iter-части.

C>Да, в этом и основная суть DSL. Только с "=" такое не прокатит, потому что это выражение для инициализации. А итеративное вычисление задаётся в виде "a : a + b".
То есть порядок вычисления выражений внутри итерации семантически не важен, т.к. справа в любом случае берутся "старые" значения?

Здравствуйте, Sinclair, Вы писали:

S>То есть порядок вычисления выражений внутри итерации семантически не важен, т.к. справа в любом случае берутся "старые" значения?

Да. Можно сказать, что DSL это текстовое описание электронных таблиц. Я сперва даже хотел найти готоввый движок, но ничего путного не нашёл, а выдирать кусок LibreCalc показалось слишком неправильным подходом.