Автор: А.Г.Дымченко

Материал к лекции 3. 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; }
"/*"       { BEGIN in;  }
.|\n       { printf("%s",yytext); }
 "*/"       { BEGIN out; }
 .|\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 -T-T¬
  ----->--+1+->-+Ұ2ҰҰ                    a
--+-¬     L--   L+-+-
Ұ   Ұ  e  --¬ a --¬ b --¬ b -T-T¬
Ұ 0 +-->--+3+->-+4+->-+5+->-+Ұ6ҰҰ        abb
Ұ   Ұ     L--   L--   L--   L+-+-
L-T--      -<¬a   --<¬b
  Ұ    e  -+¬Ұ  -T+T¬Ұ
  L---->--+7++>-+Ұ8Ұ+-                   a*b+
          L-- b L+-+-

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

Этот процесс завершается, если из текущего множества состоҰ яний КА нет перехода для очередного символа из входной цепочки. Только теперь можно считать распознанной последнюю запомненную лексему, выполнить соответствующее ей действие, возвратить "лишние" просмотренные символы в входную цепочку, установить автомат в начальное состояние и продолжить поиск следующей лекҰ семы. Построенный выше автомат при интерпретации цепочки aaba... пройдет следующие множества состояний:

--------¬ a ------¬ a --¬ b --¬ a -----¬
Ұ0,1,3,7+->-+2,4,7+->-+7+->-+8+->-+stopҰ
L--------   L------   L--   L--   L-----
             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

        ----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; i0 && 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 -T-T¬
         --->-+1+->-+Ұ3ҰҰ
         Ұ    L--   L+-+-
        -+¬ e --¬ n --¬ d -T-T¬ i --¬ f -T--T¬
        Ұ0+->-+2+->-+4+->-+Ұ6Ұ+->-+8+->-+Ұ10ҰҰ
        L--   LT-   L--   L+-+-   L--   L+--+-
               Ұ  l --¬ s --¬ e -T-T¬
               L-->-+5+->-+7+->-+Ұ9ҰҰ
                    L--   L--   L+-+-

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

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

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

  Упражнение: изобретите алгоритм BM до конца.

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

  - конец материала к лекции 3 -