// $Source$
// $Revision$
// $Date$
$use Access Arithm Box List StdIO Table;
/*
* Во время компиляции каждого модуля все статические константые выражения
* складываются в ящик
*/
$box Static;
/*
* Каждое выражение представлено термом вида (t.name expr).
*/
Init_Consts = ;
Create_Static {
/*empty*/ = /*empty*/;
(REF t.name) = (REF t.name);
expr = {
: e (t.name expr) e =
(STATIC t.name); // FIXME: Add comment?
(>) :: t.name,
,
(STATIC t.name);
};
};
Get_Static (STATIC t.name), : e (t.name expr) e = expr;
/*
* Накопленные в процессе компиляции модуля константные выражения лежат в
* &Static. Теперь необходимо отобразить их в CONSTEXPR из ASAIL.
* Эта форма имеет следующий синтаксис:
*
* t.const ::= (CONSTEXPR s.linkage t.name (e.comment) e.const-expr)
* s.linkage ::= EXPORT | LOCAL
* t.name ::= t.QualifiedName | (STATIC t.QualifiedName)
* e.const-expr ::= e.compound-expr | e.subexpr
* e.compound-expr ::= [empty] | t.const-term e.const-expr
* t.const-term ::= s.symbol | (PAREN e.const-expr)
* | (REF t.QualifiedName)
* | (STATIC t.QualifiedName)
* e.subexpr ::= (SUBEXPR t.name s.pos s.len)
* s.pos, s.len ::= [int]
*
* e.comment содержит выражение в том виде, в котором оно встретилось в
* Рефал-программе. Может быть полезным для получения более читабельной
* программы на императивном языке.
*
* REF -- ссылка на $const'анту или объект.
*
* STATIC -- обозначение константного статического выражения.
*
*
* Выражения из &Static должны создаваться после того, как объявлены все
* функции, объекты и константы, потому что могут ссылаться на них.
* Они также ссылаются друг на друга, с целью минимизации ресурсов, требуемых
* на их хранение. Если выражение встречается как подвыражение в другом, то
* оно должно являться просто ссылкой. Несколько примеров того, как надо
* заводить константы с учётом этого правила:
*
* 1. ABCD, ABC --> ABC должно заводиться после ABCD, как подвыражение.
*
* 2. A(BCD)E, BC --> BCD, затем A(BCD)E, затем BC, как подвыражение BCD.
*
* 3. A(BC(DE)FG)H, E --> DE, затем A(BC(DE)FG)H, затем E.
*
* 4. A(BC(DE)FG)H, C(DE)F --> BC(DE)FG, затем A(BC(DE)FG)H, затем C(DE)F.
*
* 5. (AB)(ABC)(BC) --> ABC, затем (AB)(ABC)(BC), причём AB и BC -- ссылки на ABC.
*
*
* Итак, если из двух имеющихся выражений одно является подвыражением другого,
* то первым делом заводится минимальное выражение в скобках, содержащее
* подвыражение, а искомые выражения получаются из него либо операцией SUBEXPR,
* либо одеванием скобок и конкатенацией.
*
* Для каждого подвыражения в скобках: если оно является подвыражением верхнего
* уровня какого-нибудь другого выражения или подвыражения в скобках, то
* сначала заводится выражение, содержащее его на верхнем уровне.
*
*
* Обеспечивать такую схему будем в два приёма. Сначала выпишем все выражения,
* которые необходимо завести, а затем определим порядок их заведения,
* удовлетворяющий зависимостям между ними.
*
* На первом шаге все статические выражения, и все их подвыражения в скобках
* выписываются в табличку
*/
$table St_Table;
/*
* Ключами являются сами выражения. Значения имеют следующий вид:
*
* e.value ::= t.expr-name (e.context) (e.position)
* t.expr-name ::= () | ([int])
* e.context ::= expr
* e.position ::= [empty] | s.pos s.len expr
*
* Пустое имя означает, что это выражение вспомогательное, нужное для
* обеспечения выше приведённых правил, и нормальное имя для него будет
* необходимо сгенерировать в случае, если его действительно потребуется
* завести.
*
* e.context -- это уровень в объемлющем выражении, содержащий наше. Например,
* если наше выражение -- это A B, входящее в X (Y (A B) (Z (Z))) X, то
* контекстом будет Y (A B) (Z (Z)). Это поле нужно для определения выражений,
* которые всегда используются в одном и том же контексте и, следовательно, не
* требуют заведения. Пустой контекст означает, что выражение используется в
* разных ситуациях. Выражение необходимо завести тогда и только тогда, когда
* контекст пуст.
*
* e.position -- это координаты для тех выражений, которые являются
* подвыражениями каких-либо других. Такие выражения необходимо заводить после
* тех, на которые они ссылаются.
*
*
* Опишем рекурсивный алгоритм раскладывания очередного выражения по табличке.
*/
$func Bind_Subexprs s.Isnew t.expr_name (e.context) (e.current) expr = s.Isnew;
/*
* Будем искать подвыражения среди уже имеющихся в табличке, начиная с самых
* глубоких. Если на каком-то уровне окажется, что такого подвыражения в
* табличке ещё не было (оно новое), значит там нет и никакого подвыражения
* более высокого уровня. Эту информацию будем хранить в s.new?, и она поможет
* нам сэкономить на просмотрах имеющейся таблицы.
*
* Если s.new? есть Old, значит есть вероятность, что текущее выражение в
* табличке уже имеется. Если New, значит текущее выражение новое, в табличке
* его точно нет.
*
* Возвращает функция также флаг s.new?, показывающий удалось ли найти текущий
* уровень в табличке, и надо ли, соответственно, искать там следующий уровень.
*
* e.context -- контекст текущего уровня.
*
* e.current -- текущий уровень.
*
* expr -- остаток текущего уровня, который надо просмотреть на предмет
* подвыражений.
*
* Для проверки того, что выражение e1 является подвыражением в скобках для
* выражения e2 (откуда следует, что e1 не может быть заведено после e2), далее
* используется функция
*/
$func? IsSubexpr (e1) e2 = ;
IsSubexpr (e1) e2, \{
e1 : e2;
e2 : e3 (PAREN e4) e5, ;
};
Bind_Subexprs s.Isnew (e.name) (e.context) (e.current) expr, {
/*
* Прежде всего, заносим в таблицу все подвыражения. Если какого-то из них
* в таблице не оказалось, значит там нет и текущего выражения.
*/
expr : e1 (PAREN e2) e3 =
(e.name) (e.context) (e.current) e3>;
/*
* Если все подвыражения оказались в таблице, значит там может оказаться и
* весь текущий уровень.
* Если его контекст уже пуст, значит он таким и остаётся.
* Если он совпадает с текущим контекстом, опять всё остаётся как было.
* Если же контекст раньше был иным, значит текущее подвыражение необходимо
* заводить. Его контекст обнуляется. И мы можем не искать в таблице
* следующий уровень (ведь единственный возможный оказался не совпадающим с
* контекстом), поэтому возвращаем New.
*/
s.Isnew : Old, : (e.tbl_name) (e.tbl_context) t.tbl_pos =
{
e.tbl_name : /*empty*/ = e.name;
e.tbl_name;
} :: e.tbl_name,
{
e.tbl_context : /*empty*/ = e.tbl_context Old;
e.tbl_context : e.context = e.tbl_context Old;
/*empty*/ New;
} :: e.tbl_context s.Isnew,
,
s.Isnew;
/*
* Если известно, что текущего уровня в таблице ещё нет, надо искать в ней
* его подвыражения. Если хотя бы одно такое подвыражение нашлось, значит
* текущий уровень необходимо заводить. Это контролирует флаг s.needed?.
*
* Однако возможна ситуация, когда найденое подвыражение необходимо для
* заведения текущего. Это проверяется функцией Subexpr?. Если она не
* $fail'ится, значит подвыражение необходимо для построения текущего
* уровня и, следовательно, его нельзя заводить вырезанием из него.
*
* Также, текущий уровень может оказаться подвыражением какого-либо
* имеющегося выражения. Тогда это выражение должно быть заведено,
* поэтому его контекст обнуляется. Позиция текущего уровня в этом
* выражении запоминается в t.pos.
* Если про текущее выражение известно, чо оно новое, то такой ситуации
* быть не может.
*/
"Not-Needed" () $iter {
e.domain : (e.key) e.rest, {
: e.tbl_params (),
e.current : e1 e.key e2,
# =
e.current))>,
e.rest Needed t.pos;
s.Isnew : Old, t.pos : (), e.key : e1 e.current e2 =
: t.tbl_name t.tbl_context t.tbl_pos,
,
e.rest s.Isneeded ( e.key);
e.rest s.Isneeded t.pos;
};
} :: e.domain s.Isneeded t.pos,
e.domain : /*empty*/ =
{
s.Isneeded : Needed = /*empty*/;
e.context;
} :: e.context,
,
New;
};
/*
* Выражение из &Static кладётся в таблицу с помощью функции:
*/
$func Bind_Static e = e;
Bind_Static (t.name expr) = : e;
/*
* Теперь перейдём ко второму этапу -- составлению списка нужных выражений в
* виде форм CONSTEXPR.
*
* Для заведения новых имён нам понадобиться свободный индекс.
*/
$box FreeIdx;
/*
* Функция
*/
$func Name e.idx = t.name;
/*
* Получает индекс -- тогда она делает имя из него, либо пустое выражение --
* тогда она генерирует незанятый индекс, после чего делает из него имя.
*/
Name {
/*empty*/ =
: s.free,
>,
(STATIC (s.free));
s.idx =
(STATIC (s.idx));
};
/*
* Функция
*/
$func Subexprs_To_Constexprs expr = (e.constexprs) e.const_expr_or_its_name;
/*
* Возвращает список всех форм CONSTEXPR, которые нужны для заведения выражения
* expr (т.е. форму, соответствующую expr, а также все, на которые она
* ссылается, и которые не были заведены раньше). Если expr необходимо
* заводить как именованное выражение, то его форма включается в e.constexprs и
* вторым параметром возвращается сгенерированное имя. Иначе, второй
* параметр -- это форма, соответствующая expr.
*
* Заведённые выражения помечаются как Constructed в таблице &St-Table.
*
* На случай, если пустое выражение попало в табличку, обрабатываем его
* отдельно.
*/
Subexprs_To_Constexprs {
/*empty*/ = () /*empty*/;
expr, : {
Constructed e.const = () e.const;
(e.name) (e.context) (e.pos) =
{
e.pos : s.left s.len e.source =
:: (e.constexprs) e.source,
(e.constexprs) (SUBEXPR e.source s.left s.len);
expr () () $iter {
expr : e1 (PAREN e2) e3 =
:: (e2_consts) e2,
e3 (e.constexprs e2_consts) (e.const e1 (PAREN e2));
/*empty*/ (e.constexprs) (e.const expr);
} :: expr (e.constexprs) (e.const),
expr : /*empty*/ =
(e.constexprs) e.const;
} :: (e.constexprs) e.const,
{
e.context : /*empty*/ =
:: t.name,
(e.constexprs (CONSTEXPR LOCAL t.name (expr) e.const)) t.name;
(e.constexprs) e.const;
} :: (e.constexprs) e.const,
,
(e.constexprs) e.const;
};
};
/*
* Выражение из &Static преобразуется в список CONSTEXPR-форм (для него, и всех
* необходимых ему) с помощью функции:
*/
$func Static_To_Constexprs e.static_expr = e.constexprs;
Static_To_Constexprs (t.name expr) =
:: (e.constexprs) e = e.constexprs;
/*
* Теперь, проинициализировав таблицу и свободный индекс, мы можем
* сгенерировать список всех CONSTEXPR-форм.
*/
Comp_Consts =
,
>>,