Сопоставление с образцом

[Илья Ермаков]

2Valeriy Solovey:

Если мы берём второй вариант (что допускаем строку 1.12341234), то будет такой КА, как на прилагаемом рисунке.

Если хотим первый вариант, то убираем переход q6->q2.

Вообще, достаточно одной семантики - жадной (как первый КА). Нежадная даётся расстановкой скобок: 1.(*123)4
В теории языков нет понятия "жадная/нежадная интерпретация регулярного выражения". Это уже самоделкинские придумки в реализациях.

Уверен в сказанном выше не на 100%, готов к возражениям

[Valery Solovey]

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

Лично я предпочитаю такой вариант, где не нужны возвраты. Подавляющее большинство реальных задач такой вариант покрывает. Правда, конечное регулярное выражение временами бывает слишком громоздким. Но зато сложнее написать такое выражение, которое вместо секунд будет выполняться неделями. Или его вообще невозможно написать таким тормознутым.

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

Код: [Выделить]

.*4 Движок выполняет разбор строки и доходит до символа "4". Появляется необходимость выбора: или этот символ покрывается частью выражения, представленного точкой, или частью выражения, представленного непосредственно символом 4. Та часть выражения, которая захватит символ, более жадная. То есть, жадность - это аналог приоритета операций в арифметических выражениях.

[Kemet]

abdabc *abc не пройдёт.

Да, недопонял задачу

[Kemet]

Исправленный вариант

Код: [Выделить]

MODULE Match;
IMPORT Strings;

  PROCEDURE MatchIt( CONST text, pattern : ARRAY OF CHAR;
                           posT, posP    : LONGINT;
                           lenT, lenP    : LONGINT ): BOOLEAN;

  VAR
    chT, chP: CHAR;
    iT,  iP : LONGINT;
   
    PROCEDURE NoMoreCharInPattern(): BOOLEAN;
    BEGIN
      WHILE ( pattern[ posP ] = '*' ) & ( posP < lenP ) DO
        INC( posP );
      END;
      RETURN posP = lenP;
    END NoMoreCharInPattern;

    PROCEDURE FindCharInText( ch: CHAR; pos: LONGINT ): BOOLEAN;
    BEGIN
      WHILE pos < lenT DO
        IF text[ pos ] = ch THEN posT:= pos; RETURN TRUE END;
        INC ( pos );
      END;
      RETURN FALSE;
    END FindCharInText;

  BEGIN
    iT := lenT;
    LOOP
      IF posT = lenT THEN
        RETURN NoMoreCharInPattern();
      ELSIF posP = lenP THEN
        RETURN FALSE;
      ELSE
        chT := text[ posT ];
        chP := pattern[ posP ];
        IF chP = '*' THEN
          INC( posP );
          IF NoMoreCharInPattern() THEN
            RETURN TRUE;
          ELSIF FindCharInText( pattern[ posP ], posT ) THEN
            iP := posP;
            INC( posP );
            INC( posT );
            iT := posT;
          ELSE
            RETURN FALSE;
          END;
        ELSIF ( chP = chT ) OR ( chP = '?' ) THEN
          INC( posP );
          INC( posT );
        ELSE
          IF ( iT < lenT ) & FindCharInText( pattern[ iP ] , iT ) THEN
            posP := iP;
            INC( posP );
            INC( posT );
            iT := posT;
          ELSE
            RETURN FALSE;
          END;
        END;
      END;
    END;
  END MatchIt;

  PROCEDURE DoMatch*( CONST text, pattern: ARRAY OF CHAR ): BOOLEAN;
  BEGIN
    RETURN MatchIt( text, pattern, 0, 0, Strings.Length( text ), Strings.Length( pattern ));
  END DoMatch;

END Match.


[Kemet]

Всё же более вразумительно нужно задачи формулировать ... хотя да, и мне нужно все читать,  а не по диагонали.

Код: [Выделить]

MODULE Match;
IMPORT Strings;

PROCEDURE MatchIt( CONST text, pattern : ARRAY OF CHAR;
                         posT, posP    : LONGINT;
                         lenT, lenP    : LONGINT ): BOOLEAN;

VAR
  chT, chP: CHAR;
  iT,  iP : LONGINT;

  PROCEDURE NoMoreCharInPattern(): BOOLEAN;
  BEGIN
    WHILE ( pattern[ posP ] = '*' ) & ( posP < lenP ) DO
      INC( posP );
    END;
    RETURN posP = lenP;
  END NoMoreCharInPattern;

  PROCEDURE FindCharInText( ch: CHAR; pos: LONGINT ): BOOLEAN;
  BEGIN
    WHILE pos < lenT DO
      IF text[ pos ] = ch THEN posT:= pos; RETURN TRUE END;
      INC ( pos );
    END;
    RETURN FALSE;
  END FindCharInText;

  PROCEDURE Retry;
  BEGIN
    posP := iP;
    INC( posP );
    INC( posT );
    iT := posT;
  END Retry;

BEGIN
  iT := lenT;
  iP := lenP;
  LOOP
    IF posT = lenT THEN
      RETURN NoMoreCharInPattern();
    ELSIF posP = lenP THEN
      IF ( iP < lenP ) & FindCharInText( pattern[iP] , iT ) THEN
        Retry
      ELSE
        RETURN FALSE;
      END;
    ELSE
      chT := text[ posT ];
      chP := pattern[ posP ];
      IF chP = '*' THEN
        INC( posP );
        IF NoMoreCharInPattern() THEN
          RETURN TRUE;
        ELSIF FindCharInText( pattern[ posP ], posT ) THEN
          iP := posP;
          INC( posP );
          INC( posT );
          iT := posT;
        ELSE
          RETURN FALSE;
        END;
      ELSIF ( chP = chT ) OR ( chP = '?' ) THEN
        INC( posP );
        INC( posT );
      ELSE
        IF ( iP < lenP ) & FindCharInText( pattern[iP] , iT ) THEN
          Retry;
        ELSE
          RETURN FALSE;
        END;
      END;
    END;
  END;
END MatchIt;

PROCEDURE DoMatch*( CONST text, pattern: ARRAY OF CHAR ): BOOLEAN;
BEGIN
  RETURN MatchIt( text, pattern, 0, 0, Strings.Length( text ), Strings.Length( pattern ));
END DoMatch;

END Match.
Вроде как на всех тестовых данных прошло

[Geniepro]

Ну так и де у вас всех доказательства корректности, инварианты и всё такое? )))

[Илья Ермаков]

Лично я предпочитаю такой вариант, где не нужны возвраты. Подавляющее большинство реальных задач такой вариант покрывает. Правда, конечное регулярное выражение временами бывает слишком громоздким. Но зато сложнее написать такое выражение, которое вместо секунд будет выполняться неделями. Или его вообще невозможно написать таким тормознутым.

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

Понял про точку, ну так граф от этого не сильно меняется - просто выкидывается одно состояние и переход. Разница между жадностью и нежадностью, опять же, в наличии обратного перехода из последнего состояния. И имея жадную семантику, я всегда представлю нежадную: (.*)4.

А возвраты таки получаются, если сгенерирован недетерминированный автомат (а "обычный" алгоритм генерации КА из РВ такой и будет давать). Ну так кто мешает преобразовать его в детерминированный и избавиться от возвратов?

Пример с (.*)4, кстати, не даст НКА, - при соединении автомата для части в скобках и автомата для окончания выражения всё соединится детерминированно.

[Berserker]

Илья, интересно было бы Ваше решение.
Я обобщил задачу до заявленной функциональности магических символов (WILDCARDS) в API OS Windows. В частности:
"*" - нуль или более любых символов
"?" - один любой символ

Требуется проверить, соответствует (не содержит!) ли строка шаблону.

После очередного перерождения и нахождения пары ошибок, мой вариант:

Код: (delphi) [Выделить]

FUNCTION Match (CONST Str, Pattern: STRING): BOOLEAN;
CONST
  ONE_SYM_WILDCARD  = '?';
  ANY_SYMS_WILDCARD = '*';
  WILDCARDS         = [ONE_SYM_WILDCARD, ANY_SYMS_WILDCARD];

TYPE
  TState  =
  (
    STATE_STRICT_COMPARE,       // [abc]*?*?**cde?x*
    STATE_SKIP_WILDCARDS,       // abc[*?*?**]cde?x*
    STATE_FIRST_LETTER_SEARCH,  // abc*?*?**[c]de?x*
    STATE_MATCH_SUBSTR_TAIL,    // abc*?*?**c[de?x]*
    STATE_EXIT
  );

(*
  Non-greedy algorithm tries to treat ANY_SYMS_WILLCARD as the shortest possible string.
  Token is a substring between Base position and ANY_SYMS_WILLCARD or end of string in the template
  and corresponding matching substring in the string.
 
  Match "abcecd78e" against "a*cd*e": (Token is wrapped in parenthesis)
 
  (abcecd78e)
  (a*cd*e)
 
  => STRICT_COMPARE until * (success)
 
  (a  )(bcecd78e)
  (a* )(cd*e)
 
  => FIRST_LETTER_SEARCH "c" (success)
 
  (ab )(cecd78e)
  (a* )(cd*e)
 
  => MATCH_SUBSTR_TAIL "d" (fail)
 
  (abc)(ecd78e)
  (a* )(cd*e)
 
  => FIND_FIRST_LETTER "c" (success)
 
  (abce)(cd78e)
  (a*  )(cd*e)
 
  => MATCH_SUBSTR_TAIL "d" (success)
 
  (abce)(cd  )(78e)
  (a*  )(cd* )(e)
 
  => FIND_FIRST_LETTER "e" (success)
 
  (abce)(cd78)(e)
  (a*  )(cd* )(e)
 
  => EXIT
*)

(*
  Contracts for states:
    STATE_STRICT_COMPARE:
      - Entry state, not-reenterable
      - Matches character-to-character, including ONE_SYM_WILLCARD
      - Exits on mismatch
      - => STATE_SKIP_WILDCARDS
    STATE_SKIP_WILDCARDS:
      - Skips sequence of WILDCARDS
      - Increases position in the string for each ONE_SYM_WILDCARD
      - Exits on end of pattern
      - Initializes character "c" to current pattern character
      - => STATE_FIRST_LETTER_SEARCH
    STATE_FIRST_LETTER_SEARCH
      - Character [c] must be initialized before entering
      - Searches for character [c] in the string
      - Exits on end of string
      - Sets new token positions for string and token to current positions
      - => STATE_MATCH_SUBSTR_TAIL
    STATE_MATCH_SUBSTR_TAIL:
      - Matches character-to-character, including ONE_SYM_WILLCARD
      - Exits on end of string
      - Increases current token position in string by 1 and roll-backs to tokens positions in
        string and template on end of template or last character mismatch
      - => STATE_SKIP_WILDCARDS
*)
 
VAR
  State:          TState;
  StrLen:         INTEGER;
  PatternLen:     INTEGER;
  StrBasePos:     INTEGER;  // Start position of current token
  PatternBasePos: INTEGER;  // Start position of current token
  s:              INTEGER;  // Pos in Pattern
  p:              INTEGER;  // Pos in Str
  c:              CHAR;     // First letter to search for
 
 
  PROCEDURE SkipMatchingSubstr;
  BEGIN
    WHILE
      (p <= PatternLen)                 AND
      (s <= StrLen)                     AND
      (Pattern[p] <> ANY_SYMS_WILDCARD) AND
      (
        (Str[s]     = Pattern[p]) OR
        (Pattern[p] = ONE_SYM_WILDCARD)
      )
    DO BEGIN
      INC(p);
      INC(s);
    END; // .WHILE
  END; // .PROCEDURE SkipMatchingSubstr

BEGIN
  StrLen          :=  LENGTH(Str);
  PatternLen      :=  LENGTH(Pattern);
  StrBasePos      :=  1;
  PatternBasePos  :=  1;
  s               :=  1;
  p               :=  1;
  c               :=  #0;
  State           :=  STATE_STRICT_COMPARE;
  RESULT          :=  FALSE;
 
  WHILE State <> STATE_EXIT DO BEGIN
    CASE State OF
      STATE_STRICT_COMPARE:
        BEGIN
          SkipMatchingSubstr;
         
          IF (p > PatternLen) OR (Pattern[p] <> ANY_SYMS_WILDCARD) THEN BEGIN
            State :=  STATE_EXIT;
          END // .IF
          ELSE BEGIN
            STATE :=  STATE_SKIP_WILDCARDS;
          END; // .ELSE
        END; // .CASE STATE_STRICT_COMPARE
       
      STATE_SKIP_WILDCARDS:
        BEGIN
          WHILE (p <= PatternLen) AND (Pattern[p] IN WILDCARDS) DO BEGIN
            IF Pattern[p] = ONE_SYM_WILDCARD THEN BEGIN
              INC(s);
            END; // .IF
           
            INC(p);
          END; // .WHILE
         
          IF p <= PatternLen THEN BEGIN
            c     :=  Pattern[p];
            State :=  STATE_FIRST_LETTER_SEARCH;
          END // .IF
          ELSE BEGIN
            State :=  STATE_EXIT;
          END; // .ELSE
        END; // .CASE STATE_SKIP_WILDCARDS
       
      STATE_FIRST_LETTER_SEARCH:
        BEGIN
          WHILE (s <= StrLen) AND (Str[s] <> c) DO BEGIN
            INC(s);
          END; // .WHILE
         
          IF s > StrLen THEN BEGIN
            State :=  STATE_EXIT;
          END // .IF
          ELSE BEGIN
            StrBasePos      :=  s;
            PatternBasePos  :=  p;
            INC(p);
            INC(s);
            State           :=  STATE_MATCH_SUBSTR_TAIL;
          END; // .ELSE
        END; // .CASE STATE_FIRST_LETTER_SEARCH
       
      STATE_MATCH_SUBSTR_TAIL:
        BEGIN
          SkipMatchingSubstr;
         
          IF s > StrLen THEN BEGIN
            State :=  STATE_EXIT;
          END // .IF
          ELSE IF (p > PatternLen) OR (Pattern[p] <> ANY_SYMS_WILDCARD) THEN BEGIN
            INC(StrBasePos);
            p     :=  PatternBasePos;
            s     :=  StrBasePos;
            State :=  STATE_FIRST_LETTER_SEARCH;
          END // .ELSEIF
          ELSE BEGIN
            State :=  STATE_SKIP_WILDCARDS;
          END; // .ELSE
        END; // .CASE STATE_MATCH_SUBSTR_TAIL
    END; // .SWITCH State
  END; // .WHILE
 
  RESULT  :=  (s = (StrLen + 1)) AND (p = (PatternLen + 1));
END; // .FUNCTION Match

ASSERT(     Match('',               ''));
ASSERT(NOT  Match('a',              ''));
ASSERT(NOT  Match('',               'a'));
ASSERT(     Match('',               '*'));
ASSERT(NOT  Match('aaa',            'bbb'));
ASSERT(     Match('12345abc',       '123*abc'));
ASSERT(NOT  Match('12345abc*d*',    '123*abc'));
ASSERT(NOT  Match('abceabcdef',     'abcd*f*'));
ASSERT(     Match('abceabcdef',     '*abcd*f*'));
ASSERT(     Match('abceabcdef',     '*ab*d*f*'));
ASSERT(     Match('abcdefgabcefg',  'abc*efg'));
ASSERT(NOT  Match('abceabcdef',     'abc*efg*efg'));
То же на pastebin

Суть алгоритма, в принципе, частями изложена в комментариях. Основная проблема в вопросе, сколько символов должен кушать магический знак "*".  В текущей реализации он следует принципу не-жадности. Это значит, что будет "съедена" минимально возможная строка.

Было выделено 5 ключевых состояний:

• Строгое сравнение. Обрабатывает ряд символов в начале строки до первой "*".
  [abc]*?*?**cde?x*
• Пропуск магических знаков. Пропускает цепочку из "*" и "?". За каждый обнаруженный символ "?" позиция в строке увеличивается на 1. При этом позиция в строке может уйти далеко за пределы её границы, но это не проблема. Успех функции -  если позиции ровно в конце строки  и в конце шаблона.
  abc[*?*?**]cde?x*
• Поиск первого символа. За цепочкой магических знаков следует обычный символ, задающий начало новой подстроке. Если символ удаётся найти, то запоминается текущая позиция в шаблоне и строке, как новая стартовая. Она используется в будущем для откатов.
  abc*?*?**[c]de?x*
• Проверка хвоста или тела подстроки. Посимвольный проход с учётом "?". Если очередной символ не совпадает, то увеличиваем на 1 базовую позицию в строке и откатываемся как в строке, так и в шаблоне до базовых позиций. После чего переходим к поиску первого символа снова. Если же строка совпала до "*", то очередная часть пути пройдена, переходим к пропуску магических знаков.
  abc*?*?**c[de?x]*
• Выход

[ilovb]

Как же отвратны все эти бесконечные паскалЁвые BEGIN'ы... 

ps Звиняюсь за оффтоп

[Berserker]

Увы. В Object Pascal старый синтаксис.

[Kemet]

Ну так и де у вас всех доказательства корректности, инварианты и всё такое? )))

Ну инвариантов и все такое у меня вообще не было, потому что, видимо плохо проснувшись, решил, что нужно сделать поиск по образцу (а это LL), и написал рекурсивную процедуру, с 3-мя или 4-мя вызовами, без цикла, откаты получались автоматически, потом увидел слово рекурсия, стал от нее избавляться, мысль про откаты уже не всплывала (ибо в рекурсии они шли автоматом и в логике это как-то не отложилось как сколь-нибудь значимое), заменил рекурсию на бесконечный цикл и граничные выходы. Потом ещё почитал, и понял, что нужен не поиск по образцу(LL), а сравнение с образцом(LR), но переписывать уже лень, в принципе и так работает, хотя оно и ищет только слева-направо, а не с концов к центру.
Весь текст модуля (тот же что и выше )  + тестовая процедура и результаты (для запуска требуется A2):

Код: [Выделить]

MODULE Match;
IMPORT Log := KernelLog, Strings;

PROCEDURE MatchIt( CONST text, pattern : ARRAY OF CHAR;
                         posT, posP    : LONGINT;
                         lenT, lenP    : LONGINT ): BOOLEAN;

VAR
  chT, chP: CHAR;
  iT,  iP : LONGINT;

  PROCEDURE NoMoreCharInPattern(): BOOLEAN;
  BEGIN
    WHILE ( pattern[ posP ] = '*' ) & ( posP < lenP ) DO
      INC( posP );
    END;
    RETURN posP = lenP;
  END NoMoreCharInPattern;

  PROCEDURE FindCharInText( ch: CHAR; pos: LONGINT ): BOOLEAN;
  BEGIN
    WHILE pos # lenT DO
      IF text[ pos ] = ch THEN posT:= pos; RETURN TRUE END;
      INC ( pos );
    END;
    RETURN FALSE;
  END FindCharInText;

  PROCEDURE Retry;
  BEGIN
    posP := iP;
    INC( posP );
    INC( posT );
    iT := posT;
  END Retry;

BEGIN
  iT := lenT;
  iP := lenP;
  LOOP
    IF posT = lenT THEN
      RETURN NoMoreCharInPattern();
    ELSIF posP = lenP THEN
      IF ( iP # lenP ) & FindCharInText( pattern[iP] , iT ) THEN
        Retry
      ELSE
        RETURN FALSE;
      END;
    ELSE
      chT := text[ posT ];
      chP := pattern[ posP ];
      IF chP = '*' THEN
        INC( posP );
        IF NoMoreCharInPattern() THEN
          RETURN TRUE;
        ELSIF FindCharInText( pattern[ posP ], posT ) THEN
          iP := posP;
          INC( posP );
          INC( posT );
          iT := posT;
        ELSE
          RETURN FALSE;
        END;
      ELSIF ( chP = chT ) OR ( chP = '?' ) THEN
        INC( posP );
        INC( posT );
      ELSE
        IF ( iP # lenP ) & FindCharInText( pattern[iP] , iT ) THEN
          Retry;
        ELSE
          RETURN FALSE;
        END;
      END;
    END;
  END;
END MatchIt;

PROCEDURE DoMatch*( CONST text, pattern: ARRAY OF CHAR ): BOOLEAN;
BEGIN
  RETURN MatchIt( text, pattern, 0, 0, Strings.Length( text ), Strings.Length( pattern ));
END DoMatch;

  PROCEDURE Test;
  BEGIN
    Log.String( "=========================================" ); Log.Ln;

    Log.String(         " 1)'' $ '' = " );
      Log.Boolean( DoMatch( '' , '' ));
    Log.Ln;

    Log.String(         " 2)'' $ 'a' = " );
      Log.Boolean( DoMatch( '' , 'a' ));
    Log.Ln;

    Log.String(         " 3)'' $ '*' = " );
      Log.Boolean( DoMatch( '' , '*' ));
    Log.Ln;

    Log.String(         " 4)'a' $ '' = " );
      Log.Boolean( DoMatch( 'a' , '' ));
    Log.Ln;

    Log.String(         " 5)'abcxyz' $ '*' = " );
      Log.Boolean( DoMatch( 'abcxyz' , '*' ));
    Log.Ln;

    Log.String(         " 6)'abcxyz' $ 'ab*' = " );
      Log.Boolean( DoMatch( 'abcxyz' , 'ab*' ));
    Log.Ln;

    Log.String(         " 7)'abcxyz' $ '*ab' = " );
      Log.Boolean( DoMatch( 'abcxyz' , '*ab' ));
    Log.Ln;

    Log.String(         " 8)'abcxyz' $ '*yz' = " );
      Log.Boolean( DoMatch( 'abcxyz' , '*yz' ));
    Log.Ln;

    Log.String(         " 9)'abcxyz' $ '*yz*' = " );
      Log.Boolean( DoMatch( 'abcxyz' , '*yz*' ));
    Log.Ln;

    Log.String(         "10)'abcxyz' $ 'ab*yz' = " );
      Log.Boolean( DoMatch( 'abcxyz' , 'ab*yz' ));
    Log.Ln;

    Log.String(         "11)'abcxyz' $ '*cx*' = " );
      Log.Boolean( DoMatch( 'abcxyz' , '*cx*' ));
    Log.Ln;

    Log.String(         "12)'abcxyz' $ '*a*c*y*' = " );
      Log.Boolean( DoMatch( 'abcxyz' , '*a*c*y*' ));
    Log.Ln;

    Log.String(         "13)'abcxyz' $ 'a*b***c*z' ) = " );
      Log.Boolean( DoMatch( 'abcxyz' , 'a*b***c*z' ));
    Log.Ln;

    Log.String(         "14)'abcxyz' $ '**a*b***y*z**' ) = " );
      Log.Boolean( DoMatch( 'abcxyz' , '**a*b***y*z**' ));
    Log.Ln;

    Log.String(         "15)'abcxyz' $ 'ab*x*c*yz' ) = " );
      Log.Boolean( DoMatch( 'abcxyz' , 'ab*x*c*yz' ));
    Log.Ln;

    Log.String(         "16)'abcxyz' $ '*cx' ) = " );
      Log.Boolean( DoMatch( 'abcxyz' , '*cx' ));
    Log.Ln;

    Log.String(         "17)'abcxyxyz' $ '*xyz' ) = " );
      Log.Boolean( DoMatch( 'abcxyxyz' , '*xyz' ));
    Log.Ln;

    Log.String(         "18)'abcxyzxy' $ '*xyz' ) = " );
      Log.Boolean( DoMatch( 'abcxyzxy' , '*xyz' ));
    Log.Ln;

    Log.String(         "19)'abcxyzxyz' $ '*xyz' ) = " );
      Log.Boolean( DoMatch( 'abcxyzxyz' , '*xyz' ));
    Log.Ln;

    Log.String(         "20)'abcxyzxyz' $ '*xyz*xyz' ) = " );
      Log.Boolean( DoMatch( 'abcxyzxyz' , '*xyz*xyz' ));
    Log.Ln;

    Log.String( "=========================================" ); Log.Ln;
  END Test;


PROCEDURE Do*;
BEGIN
  Test;
END Do;

END Match.

SystemTools.Free Match ~

Match.Do~

=========================================
 1)'' $ '' = TRUE
 2)'' $ 'a' = FALSE
 3)'' $ '*' = TRUE
 4)'a' $ '' = FALSE
 5)'abcxyz' $ '*' = TRUE
 6)'abcxyz' $ 'ab*' = TRUE
 7)'abcxyz' $ '*ab' = FALSE
 8)'abcxyz' $ '*yz' = TRUE
 9)'abcxyz' $ '*yz*' = TRUE
10)'abcxyz' $ 'ab*yz' = TRUE
11)'abcxyz' $ '*cx*' = TRUE
12)'abcxyz' $ '*a*c*y*' = TRUE
13)'abcxyz' $ 'a*b***c*z' ) = TRUE
14)'abcxyz' $ '**a*b***y*z**' ) = TRUE
15)'abcxyz' $ 'ab*x*c*yz' ) = FALSE
16)'abcxyz' $ '*cx' ) = FALSE
17)'abcxyxyz' $ '*xyz' ) = TRUE
18)'abcxyzxy' $ '*xyz' ) = FALSE
19)'abcxyzxyz' $ '*xyz' ) = TRUE
20)'abcxyzxyz' $ '*xyz*xyz' ) = TRUE
=========================================


[Peter Almazov]

Я обобщил задачу до заявленной функциональности магических символов (WILDCARDS) в API OS Windows. В частности:
"*" - нуль или более любых символов
"?" - один любой символ

А квадратные скобки что означают: [abc]?

[Berserker]

Часть шаблона, к которой относится указанное состояние.

[Peter Almazov]

Ясности не добавилось. Мне бы попроще, типа такого:
[ ]: Any single character within the specified range ([a-f]) or set ([abcdef]).

[Илья Ермаков]

Илья, интересно было бы Ваше решение.

Решать задачу в духе интерпретации сейчас времени нет. Думаю, что Ваше решение вполне себе.

Компилирующая реализация - мой давний Rocot и Рефал-0 (http://www.oberoncore.ru/library/ermakov_refal-0_rocot, http://www.oberoncore.ru/bbcc/subs/rocot/start).
Там паттерны ограничиваются максимум двумя звёздочками (e-переменными в терминах Рефала), при произвольном количестве ? (s-переменных) - и для такого максимального случая генерируется код концевых сравнений и цикл линейного поиска центральной части (того, что между двумя звёздочками).
Ну а произвольная мощность разбора уже может быть достигнута за счёт того, что язык - Тьюринг-полный и рекурсивный.