Lex и другие.

   Lex - программа для генерации сканеров (лексических анализа-
торов). Входной язык содержит описания лексем в терминах  регу-
лярных выражений. Результатом работы LEX'a  является  программа
на языке Си, которая читает файл yyin (обычно  это  стандартный
ввод) и выделяет из него последовательности символов (лексемы),
соответствующие регулярным выражениям.
   Рассмотрим способы записи регулярных  выражений  во  входном
языке Lex'а. Алфавит Lex'а совпадает с  алфавитом  используемой
ЭВМ. Символ из алфавита, естественно,  представляет  регулярное
выражение из одного символа. Специальные символы (в  том  числе
+-*?()[]{}|/\^$.<> ) записываются после  специального  префикса
\. Кроме того, применимы все традиционные  способы  кодирования
символа в языке C. Символы и цепочки  можно  брать  в  кавычки:
Например:
     а "а" \а  - три способа кодирования символа а
     \n \t \007 "continue"
Имеется возможность задания класса символов:
     [0-9] или [0123456789] - любая цифра
     [A-Za-z]               - любая буква
     [^0-7]                 - любой символ, кроме восьм. цифр
     .                      - любой символ, кроме \n
Грамматика для записи регулярных выражений (в порядке  убывания
приоритета):
    <р> : <р>*         - повторение 0 или более раз
    <р> : <р>+         - повторение 1 или более раз
    <р> : <р>?         - необязательный фрагмент
    <р> : <р><р>       - конкатенация
    <р> : <р>{m,n}     - повторение от m до n раз
    <р> : <р>{m}       - повторение m раз
    <р> : <р>{m,}      - повторение m или более раз
    <р> : ^<р>         - фрагмент в начале строки
    <р> : <р>$         - фрагмент в конце  строки
    <р> : <р>|<р>      - любое из выражений
    <р> : <р>/<р>      - первое выражение, если за ним  следует
                         второе
    <р> : (р)          - скобки, используются для группировки
Примеры:
    [A-Za-z]([A-Za-z0-9]{0,7}) - идентификатор (имя) в языке C
    ^#" "*define               - начало #define      в языке C
Программа на входном языке Lex состоит из трех  частей,  разде-
ленных символами %%:
   Описания
   %%
   Правила
   %%
   Программы
  Раздел описаний содержит определения макросимволов  (метасим-
волов) в виде:
ИМЯ ВЫРАЖЕНИЕ
Если в последующем тексте в  регулярном  выражении  встречается
{ИМЯ}, то оно заменяется на ВЫРАЖЕНИЕ. Если строка описаний на-
чинается с пробелов или заключена в скобки %{ ...  }%,  то  она
просто копируется в выходной файл.
  Раздел правил содержит строки вида
ВЫРАЖЕНИЕ {ДЕЙСТВИЕ}
ДЕЙСТВИЕ - это фрагмент программы  на  C,  который  выполняется
тогда, когда  обнаружена  цепочка,  соответствующая  ВЫРАЖЕНИЮ.
Действие, указанное в начале раздела без выражения, выполняется
до начала разбора. Lex делает попытку выделить наиболее длинную
цепочку из входного потока. Если несколько правил дают  цепочку
одинаковой длины, применяется первое правило. Так, при  разборе
по следующим правилам для цепочки "123" по будет применено пер-
вое правило, а для цепочки "123." - третье:
   [0-9]+
   (\+|\-)?[0-9]+
   (\+|\-)?[0-9]+"."[0-9]+
Если ни одно из правил не удастся применить, входной символ бу-
дет скопирован в yyout. Если это нежелательно, в  конец  правил
можно добавить, например, строки:
   .  {/* Ничего не делать */}
   \n { }
   Раздел программ может содержать произвольные тексты на  C  и
целиком копируется в выходной файл. Обычно  здесь  записывается
функция yywrap(), которая определяет, что делать при достижении
автоматом конца входного файла. Ненулевое возвращаемое значение
приводит к завершению разбора, нулевое - к  продолжению  (перед
продолжением, естественно, надо открыть какой-нибудь  файл  как
yyin).
   Интерпретатор таблиц КА имеет имя yylex(). Автомат прекраща-
ет работу (происходит возврат из функции yylex()), если в одном
из действий выполнен оператор return (результат  yylex()  будет
совпадать с указанным в операторе) или достигнут конец файла  и
значение yywrap() отлично от 0 (результат yylex()  будет  равен
0).
   Традиционный пример входной программы для  Lex'а  -  подсчет
числа слов и строк в файле:

   /***************** Раздел определений *********************/

   /* NODELIM означает любой символ, кроме разделителей слов */
NODELIM     [^" "\t\n]
            int l, w, c;    /* Число строк, слов, символов */

%% /******************** Раздел правил ***********************/

                { l=w=c=0;          /* Инициализация */      }
{NODELIM}+      { w++; c+=yyleng;   /* Слово */              }
\n              { l++;              /* Перевод строки */     }
.               { c++;              /* Остальные символы */  }

%% /******************* Раздел программ **********************/

main() { yylex(); }

yywrap() {
  printf( " Lines - %d  Words - %d Chars - %d\n", l, w, c );
  return( 1 );
}

   Внутри действий в правилах можно использовать некоторые спе-
циальные конструкции и функции Lex'а:
   yytext    - указатель на отождествленную  цепочку  символов,
               терминированную нулем;
   yyleng    - длина этой цепочки
   yyless(n) - вернуть последние n символов цепочки обратно  во
               входной поток;
   yymore()  - считать следующие символы в буфер  yytext  после
               текущей цепочки
   yyunput(c)- поместить байт c во входной поток
   ECHO      - копировать текущую цепочку в yyout

   Упражнение: опишите  на  языке  регулярных  выражений  LEX'а
следующие регулярные множества:
   - комментарий Си
   - комментарий Паскаля
   - вещественная константа Си
   - целая константа Си ( 0, 12, -3, 0xFF )

   Программа для Lex'а, которая печатает все слова с переносами
из входного потока:

NODELIM [^, :\.;\n\-\-]
HYPHEN  [\-\-]
%%
{NODELIM}+{HYPHEN}\n{NODELIM}+ { printf ("%s\n",yytext); }
{NODELIM}*                   { /* Необязательно */ }
. | \n                       { }
%%
yywrap() { return(1); }
main() { yylex(); }

   Если убрать необязательное правило из предыдущей  программы,
программа по-прежнему будет работать, но значительно медленнее,
поскольку при этом механизм вызова  действий  будет  вызываться
для каждого символа (а не каждого слова).
   В некоторых случаях бывает удобно описать  необходимые  дей-
ствия в терминах нескольких разных состояний (т.е.  разных  ко-
нечных автоматов) с явным переключением с одного на  другое.  В
этом случае набор имен состояний следует перечислить  в  специ-
альной строке %Start, а перед выражениями записывать имя  соот-
ветствующего состояния в угловых скобках. Переключение в  новое
состояние выполняется с помощью оператора BEGIN. Например, сле-
дующая программа удаляет комментарии из программ на  C  (out  -
вне комментария, in - внутри):

%Start out in
%%
                { BEGIN out; }
<out>"/*"       { BEGIN in;  }
<out>.|\n       { printf("%s",yytext); }
<in> "*/"       { BEGIN out; }
<in> .|\n       { }
%%
yywrap() { return(1); }
main() { yylex(); }

   Для вызова программы Lex в ОС UNIX  следует  ввести  команду
"lex имя_исходного_файла". Выходной файл имеет имя "lex.yy.c".

Упражнения по программированию:
1. Написать  программу   для   Lex'а,   которая   заменяет   в
   Фортран-программе все слова DOUBLE PRECISION на REAL.
2. Написать программу для Lex'а, которая выводит все  встречен-
   ные в тексте слова, начинающиеся с заглавной буквы.
3. Написать программу для Lex'а для  удаления  комментариев  из
   программы на C, которая будет учитывать возможность  наличия
   вложенных комментариев и игнорировать "/*" внутри символьных
   констант.

                       Как устроен LEX.

   Мы попытаемся обсудить здесь то, как мог бы быть  реализован
генератор сканеров, из этого обсуждения не следует,  что  UNIX'
овская программа LEX устроена именно так.
   Для каждого из регулярных  выражений  r1,  ...  rn  несложно
построить недетерминированный конечный автомат, затем,  следует
объединить полученные автоматы, создав новое  начальное  состо-
яние с e-переходами в начальные состояния  каждого  регулярного
выражения. (Полученный автомат будет распознавать выражение r1|
r2|...rn). Например, для выражений a, abb, a*b+, будет построен
следующий автомат:

       e  --¬ a -+-+¬
  ----->--+1+->-+¦2¦¦                    a
+-+-+     +--   ++-+-
¦   ¦  e  --¬ a --¬ b --¬ b -+-+¬
¦ 0 +-->--+3+->-+4+->-+5+->-+¦6¦¦        abb
¦   ¦     +--   +--   +--   ++-+-
+-+-+      -<¬a   --<¬b
  ¦    e  -+¬¦  -+++¬¦
  +---->--+7++>-+¦8¦+-                   a*b+
          +-- b ++-+-

   Для выделения лексем из входной цепочки можно применить нем-
ного модифицированный алгоритм моделирования  недетерминирован-
ного КА. Отличие состоит в том, что наличие в текущем множестве
состояний конечного состояния не является основанием для  оста-
новки автомата - не исключено, что цепочка может быть продолже-
на до более длинной лексемы. В этом  случае  следует  запомнить
лексему и соответствующее ей регулярное выражение (более точно,
то из подходящих  выражений,  которое  было  записано  выше  по
тексту в исходной LEX-программе) и продолжить интерпретацию КА.
   Этот процесс завершается, если из текущего множества  состо-
яний КА нет перехода для очередного символа из входной цепочки.
Только теперь можно считать распознанной последнюю  запомненную
лексему,  выполнить  соответствующее  ей  действие,  возвратить
"лишние" просмотренные символы в  входную  цепочку,  установить
автомат в начальное состояние и продолжить поиск следующей лек-
семы.  Построенный  выше  автомат  при  интерпретации   цепочки
aaba... пройдет следующие множества состояний:

+-------+ a +-----+ a +-+ b +-+ a +----+
¦0,1,3,7+->-+2,4,7+->-+7+->-+8+->-+stop¦
+-------+   +-----+   +-+   +-+   +----+
             a(a)         aab(a*b+)

В результате будет распознана лексема aab, как отвечающая регу-
лярному выражению a*b+.
   Детерминированный КА, полученный из построенного выше  неде-
терминированного КА также может быть использован для  выделения
лексем. Напомним, что  состояние  ДКА  соответствует  множеству
состояний НКА. Если это множество содержит  конечные  состояния
НКА, то следует пометить соотвествующее  ему (конечное)  состо-
яние ДКА, первым регулярным  выражением. Например для  рассмот-
ренного выше примера может быть построен следующий ДКА:

        -----------T-------T-----T-------------¬
        ¦Состояние ¦   a   ¦ b   ¦Рег.выражение¦
        +----------+-------+-----+-------------+
        ¦ 0,1,3,7  ¦ 2,4,7 ¦ 8   ¦     -       ¦
        ¦ 2,4,7    ¦   7   ¦ 5,8 ¦     а       ¦
        ¦ 8        ¦   -   ¦ 8   ¦     a*b+    ¦
        ¦ 7        ¦   7   ¦ 8   ¦     -       ¦
        ¦ 5,8      ¦   -   ¦ 6,8 ¦     a*b+    ¦
        ¦ 6,8      ¦   -   ¦ 8   ¦     abb     ¦
        L----------+-------+-----+--------------

   Упражнение: На прошлой лекции была предложена схема  постро-
ения НКА для регулярного выражения, содержащего операции *,  |,
скобки и конкатенацию. Распространите эту схему  на  регулярные
выражения, допускаемые LEX'ом:
   1. Р+, Р?, Р{m,n}, Р{m}, Р{m,};
   2. ^P, P$ (в начале и в конце строки);
   3. Р1/P2  (P1, за которым следует Р2).

   Упражнение: Естественные  структуры  данных,  представляющие
ДКА, выделяющий лексемы, просты:
   состояние s   - целое число из диапазона 1..число состояний,
   Функция переходов - f:(s,c)->s,
   Рег.выражение - вектор целых с индексом  1..число состояний
        (элемент вектора - номер регулярного выражения или ноль
         для состояний автомата, не являющихся конечными).
   Реализация функции переходов в виде таблицы очень эффективна
с точки зрения скорости, но требует слишком много памяти.  (Ко-
нечный автомат типичного сканера может содержать 100-500 состо-
яний, входной алфавит - 256 символов. Память 25-250 Кбайт, тре-
буемая для такой таблицы, часто неприемлемо велика.)
   Предложите достаточно быстрый, но более экономный по  памяти
способ хранения функции переходов. Разумеется, он должен учиты-
вать вид "типичной" функции f.


                  Поиск регулярных множеств.

   Рассмотрим задачу поиска регулярного множества R  в  цепочке
символов L. (Вряд ли она часто встречается при реализации  ком-
пиляторов, но лежит в непосредственной близости от рассматрива-
емых вопросов и весьма популярна. Так, например, в системе UNIX
имеется по крайней мере три программы для решения этой  задачи:
grep, egrep, fgrep - Get Regular Expression Pattern.)
   Эта задача, очевидно, эквивалентна задаче принадлежности це-
почки L регулярному множеству (.*)(R)(.*) и может  быть  решена
построением детерминированного или недетерминированного  конеч-
ного автомата и применением его к цепочке L. Какой из автоматов
лучше? Ответ  "конечно,  детерминированный,  т.к.  он  работает
быстрее", в общем случае, неверен. Проблема заключается в  том,
что существуют семейства регулярных выражений, для которых чис-
ло состояний минимального ДКА экспоненциально зависит от  длины
выражения, в то время как число состояний НКА, полученного пря-
мо из регулярного выражения,  линейно  зависит  от  его  длины.
(Пример такого семейства - упражнение в предыдущей лекции). Это
делает невозможным применение ДКА для поиска некоторых регуляр-
ных множеств, описываемых регулярными выражениями  весьма  уме-
ренной длины.
   Для таких приложений более эффективной чем  НКА  может  ока-
заться так называемая "ленивая" техника. Она основана на тех же
самых идеях, что и виртуальная или cache-память. В этом  случае
ДКА строится в процессе просмотра цепочки, причем вычисляются и
заносятся в cache-буфер только необходимые для  данной  цепочки
состояния и переходы ДКА. По-видимому,  можно  придумать  класс
задач, на которых этот метод будет  эффективнее  ДКА  (большой,
требующий много времени для вычисления ДКА, в  котором  реально
используется небольшое подмножество).
   Упражнение: продумайте детали реализации  "ленивого"  поиска
регулярного выражения.


                       Поиск подцепочки.

   Полученные результаты, примененные к задаче поиска подстроки
R (частный случай регулярного выражения)  в  последовательности
символов  L  дают  неплохой  результат:   ДКА   требует   время
O(|L|+|R|) + время построения ДКА, что для  длинных  последова-
тельностей лучше наивного алгоритма, который  в  худшем  случае
требует O(|L|*|R|). Весьма неожиданный результат, учитывая  не-
адекватно сложные методы для столь элементарной задачи.
   Упражнение: докажите, что минимальный  ДКА  для  регулярного
выражения (.)*r1r2...rn(.)* имеет ровно n+1 состояние.
   Вполне естественная задача - придумать столь же  эффективный
алгоритм поиска подстроки, не  требующий  трудоемкого  процесса
построения ДКА. Одно из решений - алгоритм Кнута-Морриса-Пратта
   Предобработка: для образца поиска R[1:k] вычисляется так на-
зываемая  функция  возвратов  f[i]  -  длина  самого   длинного
собственного суффикса цепочки R[1:i], совпадающего с началом R.
Другими словами f[i]=j 1<=i<=k, если и только если j (0<=j<i) -
максимальное, такое что R[1:j] = R[i-j+1:i]. Например:

        ----T---T---T---T---T---T---¬
        ¦   ¦ 1 ¦ 2 ¦ 3 ¦ 4 ¦ 5 ¦ 6 ¦
        +---+---+---+---+---+---+---+
        ¦ R ¦ a ¦ b ¦ a ¦ b ¦ a ¦ c ¦
        +---+---+---+---+---+---+---+
        ¦ f ¦ 0 ¦ 0 ¦ 1 ¦ 2 ¦ 3 ¦ 0 ¦
        L---+---+---+---+---+---+----

/* Вычисление функции возвратов f[1..k] для цепочки r[1..k] */
    for( s=0, f[1]=0, i=1; i<k; i++ ) {
        while( s>0 && r[i+1]!=r[s+1] ) s=f[s];
        f[i+1] = r[i+1]==r[s+1] ? ++s : 0;
    }

Упражнения:
 - докажите, что программа правильно вычисляет функцию f;
 - докажите, что время работы программы O(k).

Поиск:
/* Поиск подцепочки r[1..k] в цепочке l[1..n] */
    for( s=0, i=1; i<=n; i++ ) {
        while( s>0 && l[i]!=r[s+1] ) s=f[s];
        if( l[i]==r[s+1] ) if( ++s == k ) return YES;
    }
    return NO;

Упражнения:
 - докажите, что программа правильно ищет вхождение R в L;
 - докажите, что время работы программы O(k+n);
 - используя функцию возвратов f, предложите алгоритм, строящий
   ДКА для выражения (.)*r1r2...rк(.)* за время O(k).

   Обобщите КМП-алгоритм для поиска одного слова  из  заданного
множества в цепочке символов. Для  этого  постройте  структуру,
которую называют  бором  (переводчики  книги  Кнута  "Искусство
программирования для ЭВМ" так  перевели  термин  trie  -  нечто
среднее между tree и retrieval: бор - имеет отношение как к вы-
БОРке, так и к деревьям). Бор для множества { if, else,  endif,
end } выглядит так:

            i +-+ f ++-++
         --->-+1+->-+¦3¦¦
         ¦    +-+   ++-++
        ++¬ e +-¬ n +-¬ d ++-+¬ i +-¬ f -+--+¬
        ¦0+->-+2+->-+4+->-+¦6¦+->-+8+->-+¦10¦¦
        +--   ++-   +--   ++-+-   +--   ++--+-
               ¦  l +-+ s +-+ e -+-+¬
               +-->-+5+->-+7+->-+¦9¦¦
                    +-+   +-+   ++-+-

 - определите функцию возвратов на множестве узлов бора,
 - предложите алгоритм вычисления функции возвратов за время
   O(число вершин бора),
 - предложите линейный алгоритм поиска одного из ключевых слов,
   использующий функцию возвратов,
 - используя функцию возвратов,  предложите  линейный  алгоритм
   построения минимального ДКА для выражения (.)*(W1|...Wn)(.)*

   Еще один эффективный (по-видимому более быстрый  в  типичных
приложениях) алгоритм изобрели Boyer и Moore в конце  70-х  го-
дов. Идея - сравнивать символы цепочки и образца справа-налево.
Несовпадение очередной пары символов часто дает достаточно  ин-
формации для того, чтобы  передвинуть  образец  для  следующего
сравнения сразу на несколько  символов  вперед.  Так,  например
достаточно всего двух сравнений, чтобы убедиться, что подстрока
"дракон" не содержится в цепочке "абракадабра":

        абракадабра
        дракон
           дракон

   Упражнение: изобретите алгоритм BM до конца.
   Упражнение по программированию:  аккуратно  запрограммируйте
несколько алгоритмов поиска подстроки и получите  результаты  о
скорости их работы. Тестовые данные должны включать  образцы  и
строки различной длины и разной природы - например, текстовые и
двоичные файлы, случайные последовательности нулей и  единиц  и
т.д.