Glob

algorithm.md

1. Построить синтаксическое дерево из строки шаблона
2. Скомпилировать программу с учетом переданных разделителей S
   1. (A) Пусть N - дерево, результат п.1
   2. (F) Скопмилировать N

      1. Если N это nodePattern

         1. Обойти дочерние элементы. Пусть M это список программ

            1. Взять следующий дочерний узел N;
            2. Пусть P это результат применения (A) к N;
            3. Пусть P' это результат применения оптмизаций к P
            4. Положить P' в M

         2. (B) Пусть M' это минимизированное количество программ в M:

            1. Пусть X = 0; Y = length(M); COUNT = 0; RESULT = NIL; LEFT, RIGHT = 0;

               1. (C) Пусть LIST = M[X:Y];

                  1. (D) Пусть P это результат склеивания программ:

                     1. Пусть P1 это результат преобразование в EveryOf:

                        1. Итерация по LIST:

                           1. Пусть E это следующий элемент LIST, MIN = 0, SEP = "";
                           2. Если E это не Super, Any, Single, List, вернуть NIL;
                           3. Если E это первый элемент, SEP = E.SEP
                           4. Есди E.SEP != SEP вернуть NIL;
                           5. Если E это Single или List, то M = M+1;

                        2. Вывод

                           1. Если все программы в LIST это Super вернуть новую программу Super;
                           2. Если все программы в LIST это Any вернуть новую программу Any;
                           3. Если LIST содержит Any или Super, а SEP - пустая строка вернуть новую программу Min{MIN};
                           4. Иначе:
                           5. пусть P это программа EveryOf;
                           6. если M > 0, добавить Min{MIN} в P;
                           7. если LIST не содержит Any и Super, положить Max{M} в P;
                           8. если SEP != "", положить NotContains{SEP} в P;
                           9. вернуть P;

                     2. Пусть P2 это результат преобразование в Row:

                        1. Итерация по LIST, пусть P это программа Row:
                           1. Пусть E это следующий элемент LIST;
                           2. Если E не имеет фиксированной длины, вернуть NIL;
                           3. Положить E в P;
                        2. Вернуть P;

                  2. Если P1 == P2 == NIL, то P = NIL

                  3. Если P1 == NIL то P = P2

                  4. Если P2 == NIL то P = P1

                  5. Если P1.LEN() > P2.LEN() то P = P1, иначе P = P2

                  6. Если P == NIL, то переход на п.10;

                  7. Если RESULT == NIL, то переход на п.9;

                  8. Если P и RESULT имеют фиксированную длину, и P.LEN() > RESULT.LEN(), то переход на п.9;

                  9. Если Y -X > COUNT, то переход на п.9

                  10. RESULT = P, COUNT = Y - X, LEFT = X, RIGHT = Y;

                  11. Если Y > X, то Y = Y-1; Продолжить (C)

                  12. Если X < length(M), то X = X + 1; Y = length(M); Продолжить (C)

            2. Если RESULT == NIL вернуть M;

            3. Пусть NEXT = [ M[:LEFT]..., RESULT, M[RIGHT:]... ];

            4. Если length(NEXT) == length(M) вернуть NEXT;

            5. Вернуть (B) от NEXT;

         3. (E) Скомпилировать M':

            1. Если length(M') == 1, вернуть M'[0];
            2. Пусть P это (D) от M';
               1. Если P != NIL, вернуть P;
            3. Пусть MAX это программа из M' с наибольшей фиксированной длиной, а I это ее индекс в M';
               1. Пусть LEFT = M'[:I], RIGHT = NIL;
               2. Если I+1 < length(M'), то RIGHT = M'[I+1:]
               3. Пусть T это программа BTree;
                  1. T.Value = MAX;
                  2. Если length(LEFT) > 0, то установить в T.Left результат (E) от LEFT;
                  3. Если length(RIGHT) > 0, то установить в T.Right результат (E) от RIGHT;
               4. Вернуть T;

      2. Если N это nodeAnyOf,

         1. Обойти дочерние элементы. Пусть M это список программ
            1. Взять следующий дочерний узел N
            2. Пусть P это результат (F) от N
            3. Пусть P' это результат применения оптмизаций к P
            4. Положить P' в M
         2. Вернуть программу AnyOf{M}

      3. Если N это nodeList

         1. Вернуть программу List{N.Chars, N.Not}

      4. Если N это nodeRange

         1. Вернуть программу Range{N.Low, N.High, N.Not}

      5. Если N это nodeAny

         1. Вернуть программу Any{S}

      6. Если N это nodeSuper

         1. Вернуть программу Super

      7. Если N это nodeSingle 2. Вернуть программу Single{S}

      8. Если N это nodeText

         1. Вернуть программу Raw{N.Text}