---------------------------------------------------------------------- (1) Mы компилируем несколько перестроек (см. слова о хранилище перестроек и об упорядоченности в нем). Компилировать можно "почти в любом порядке" -- главное не нарушать порядок вложенности итерационных переменных. ---------------------------------------------------------------------- (2) Все перестройки классифицированны по видам и для каждого образца можно выписать: -- условие (предикат) на длины: "не удастся отождествится" (отмечен как "==>"); -- ограничения на минимальную и максимальные длины (итерационных) e/v-переменных xK (отмечены как "[*K]"); В процессе компиляции классификацию перестроек, предикаты "==>" и "[*K]" надо пересчитывать. ---------------------------------------------------------------------- (3) Вот эта классификаци: о А1. "Жесткий" по длине образец (не путать с жестким образцом) Безвариантное отождествление Src : k1 ... kN ==> if (L_Src != (Lk1+ ... +LkN)) goto <>; о А2. Образец начинается и/или заканчивается непустыми фрагментами известной длины. Порождение безвариантных отождествлений Src : k1 ... kN pattern k'1 ... k'M где pattern = xj0 k"1 xj1 ... k"P xjP (x1 входит C1 раз, x2 входит C2 раз,... xK входит CK раз) ==> if (L_Src < (Lk1+ ... +LkN) +(Lk'1+ ... +Lk'M) +(Lk"1+ ... +Lk"P) +(C1*min1+...+CK*minK) ) goto <>; о А3.1 Случай закрытой (одна переменная) или квази-закрытой (многократные вхождения одной и той же переменной) e/v-переменной: Src : x1 k1 x1 ... x1 kN x1 (x1 входит C1 раз) Безвариантное отождествление. ==> if ( ((L_Src - Lk1 - ... LkN)%C1) /* если не делится на C1 */ || /* или */ ((Lx1 = ((L_Src-Lk1- ... -LkN)/C1)) < min1 /* коротковато будет */ ) ) goto <>; o А3.2 Итерационное (многовариантное) отождествление по e/v-переменной xj0. Src : xj0 k1 xj1 ... kN xjN (Пусть: x1 входит C1 раз, x2 -- C2 раз,... xK -- CK раз) Обозначим: L = L_Src - (L_k1+...+L_kN) - (C1*min1+...+CK*minK) Обозначим maxJ -- ограничение на максимальную длину xJ, которое вытекает по условиям >>данной<< перестройки. [*1] min1 <= Lx1 <= max1 where max1 = (L+C1*min1)/C1 [*2] min2 <= Lx2 <= max2 where max2 = (L+C2*min2)/C2 ... [*K] minK <= LxK <= maxK where maxK = (L+CK*minK)/CK ==> if ( (min1>max1) || (min2>max2) ... || (minK>maxK) ) goto <>; ---------------------------------------------------------------------- (4) Новые идеи к компиляции--помечены как [NEW!]: - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 4.1. Цикл компиляции: Пока хранилище перестроек не пусто: /* Assert: в хранилище перестройки отклассифицированы, условия "==>" и "[*K]" -- выписаны актуальными */ (а) [NEW!] генерируем ВСЕ (через "&&") предикаты на длины ("==>"); /* только надо избежать повторных проверок одних и тех же условий на длины ;-) */ (б) выбираем одну перестройку на компиляцию из хранилища--- лучше А1 или А3.1, если нет--А2, если нет, то самый левый А3.2. (в) компилируем... Ну, почти так, как это описано в pm.txt, только с поправочками: -- учтем, что предикат на длину "==>" уже сгенерирован; -- учтем важное уточнение компиляции случая А3.2 (см. 4.2) (г) в правильное место хранилища в правильном порядке разместим новые порожденные перестройки. (д) переклассифицируем перестройки в хранилище (** так как какие-то переменные могли стать "старыми" в силу **) и пересчитаем условия "==>" и "[*K]" - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 4.2. [NEW!] Что есть верхний предел цикла по открытой переменной? Антон заметил, что открытая переменная xK может входить в несколько перестроек. Тем самым ее верхний предел удлинения есть МИНИМУМ из верхних пределов (см. "[*K]"), предписанных ВСЕМИ условиями "[*K]" всех перестроек, в которую входит xK. Тем самым при генерации кода по 3.2 в генерации заголовка цикла я бы поступил бы так: ... for(L_xK = minK; L_xK <= <<код_L_max_xK>> ; L_xK++) { ^^^^^^^^^^^^^^^^ -- коррекция pm.txt xK = subexp(eSrc,0,L_xK); .... где <<код_L_max_xK>> -- перечисление кодов всех ограничений сверху на длину max_xK, связанных /* если их несколько */ функцией MIN(_, _) ========= Пример 1: ========= Рассмотрим пример: eSrc : е1 е2 (е3 е1 е4), << дальнейшие действия >> С коррекцией Антона это компилируется так: ... "скобки слева" -- действия по "eSrc : eSrc1 (eSrc2)" for (Lx1=0; Lx1 <= MIN(L_Src1, L_Src2); Lx1++){ ... отгрызаем е1 длиной Lx1 и ... закрываем е2 for (Lx3=0; Lx3 < (L_Src2-Lx1); Lx3++){ ... отгрызаем е3 длиной Lx3 ... проверяем старую e1 (если "нет" -- increment_x3) ... закрываем е4 << дальнейшие действия >> increment_x3: }; goto increment_x1; increment_x1: }; goto <>; Заметим, что "старый" pm.txt, предписывал вместо "MIN(L_Src1, L_Src2)" писать "L_Src1". Что не есть хорошо--вдруг в run-time выпадет такое: ...длина 100 000 термов...(...10 термов...) : е1 е2 (е3 е1 е4), << дальнейшие действия >> Вместо 10х10/5 итераций (новый вариант Антона) мы бы делали как минимум 100 000 итераций ("старый" pm.txt). - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - (5) [New!] Обсуждаемые методы компиляции перестройки, конечно, можно и нужно применять к цепочке перестроек, при условии, что в эту цепочку не затесался вызов какой-то функции (особенно с побочным эффектом). ========= Пример 2: ========= Фрагмент кода из "двух-подряд-перестроек": eSrc1 : е1 е2, eSrc2 : е3 е1 е4, << дальнейшие действия >> надо компилировать в код, описанный в примере 1 (включая Антонову оптимизацию "Lx1 < MIN(L_Src1, L_Src2)"). А фрагмент кода: eSrc1 : е1 е2, , eSrc2 : е3 е1 е4, << дальнейшие действия >> так компилировать НЕЛЬЗЯ ;-))