Delphi World - Основы компиляции - Лекция 2
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Основы компиляции - Лекция 2

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

Материал к лекции 2. Иерархия Хомского. Регулярные языки.

Классификация грамматик по сложности соответствующих прог¦ рамм-распознавателей называется иерархией Хомского. В ней выде¦ лены 4 класса грамматик (в порядке возрастания сложности):

  • регулярные (или автоматные). Правила имеют вид: A : xB или A : x, где x - цепочка терминалов или e Примеры - упражнение.
  • контекстно-свободные (или КС). Правила имеют вид: A : y, где y - цепочка из терминалов и нетерминалов Примеры - "скобочный язык" из предыдущей лекции, язык арифметических формул
  • контекстно-зависимые (неукорачивающие). Правила имеют вид : z : y, где z и y - цепочки из терминалов и нетерми¦ налов, z содержит нетерминал, |z| <= |y| n n n Пример: a b c
  • без ограничений

Класс языка определяется классом самой простой (в смысле иерархии Хомского) из описывающих его грамматик. Следующие вло¦ жения для классов языков очевидны, если не рассматривать КС-грамматики, содержащие так называемые e-правила - правила с пустой правой частью. (Упражнение: показать, что любой КС-язык может быть описан грамматикой без e-правил).

а < б < в < рекурсивные множества < г = рек.перечислимые мн-ва

Для языка, определенного регулярной грамматикой, всегда мож¦ но написать контекстно-свободную грамматику (и даже грамматику без ограничений!). Тем не менее, все вложения строгие: в каждом классе существуют языки, которые нельзя задать грамматиками бо¦ лее простого класса.

Конечные автоматы

Рассмотрим другой способ задания регулярных языков. (Неде¦ терминированный) конечный автомат задается:

  • алфавитом входных символов E;
  • множеством состояний S;
  • тернарным отношением переходов на множестве { S, E U e, S };
  • начальным состоянием - выделенным состоянием в S, и
  • конечными состояниями - непустым подмножеством S.

Принято изображать автомат в виде ориентированного графа, узлы которого соответствуют состояниям (конечные состояния мы будем заключать в двойную рамку), а ребра, помеченные символами вход¦ ного алфавита или е, изображают отношение переходов.

Цепочка допускается автоматом если и только если существует пусть из начального в одно из конечных состояний, такой что, прочитав метки ребер вдоль этого пути, мы получим исходную це¦ почку (буква e, естественно, не читается). Например, автомат

            --------¬  0  --------¬  1  -T-----T¬
            ¦   S   +-->--+   B   +-->--+¦  C  ¦¦
            L--------     L---T----     L+--T--+-
                              L------<-------0

допускает цепочки (01)+. Этот язык можно описать регулярной грамматикой:

        S : 0 B     B : 1 C     C : 0 B     C : e

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

Детерминированный конечный автомат - частный случай неде¦ терминированного, в котором:

  • нет e-переходов,
  • отношение переходов является однозначной функцией
         f:( S x E U e ) -> S,

определенной, может быть, не для всех пар из SxEUe. В терминах графа это означает, что из одного состояния выходит не более одного ребра с одинаковой меткой.

Для детерминированного автомата очень просто проверять при¦ надлежность цепочки из E* языку. Добавив, если нужно, еще одно "тупиковое" состояние, можно сделать функцию переходов опреде¦ ленной на всех парах из S x E.

    ----T------¬
    ¦   ¦ 0  1 ¦   s := начальное состояние
    +---+------+   цикл для каждого символа цепочки c выполнить
    ¦ S ¦ B  F ¦   . s := f( s, c )
    ¦ B ¦ F  C ¦   конец цикла
    ¦ C ¦ B  F ¦   ответ := s - конечное состояние
    ¦ F ¦ F  F ¦
    L---+-------

Такая интерпретация детерминированного конечного автомата более наглядна и общепринята: KA - устройство, которое может находится в конечном множестве состояний и переходит из одного состояния в другоe под действием внешних событий из алфавита E.

Можно ли подобным образом интерпретировать недетерминирован¦ ный автомат (или хотя бы эффективно определять принадлежность цепочки языку)? Да, можно считать, что в том случае, когда воз¦ можен более чем один переход, создается необходимое число эк¦ земпляров КА, которые переводятся во все возможные в этой ситу¦ ации состояния. Цепочка считается допущенной, если хотя бы один из экземпляров оказался в конечном состоянии.

               -<--------------------------¬0
           ----+---¬  0  --------¬  1  -T--+--T¬
           ¦   S   +-->--+   B   +-->--+¦  C  ¦¦
           L--------     L---T----     L+--T--+-
                             L<-------------0

Какие цепочки допускает этот автомат? - упражнение. Заметим, что если несколько экземпляров недетерминированного КА оказались в одном состоянии, то в дальнейшем можно рассмат¦ ривать только один из них. Таким образом, максимальное коли¦ чество экземпляров не превосходит числа состояний. Проверить, допускает ли недетерминированный конечный автомат цепочку символов, также несложно:

        S := e-замыкание( { начальное состояние } )
        цикл для каждого символа цепочки c выполнить
        . S := e-замыкание( F( S, c ) )
        конец цикла
        ответ := ( S П конечные состояния ) - непусто

Здесь:  S                - подмножество множества состояний KA;
        e-замыкание( S ) - множество состояний, достижимых из S
                           за 0 и более e-переходов;
        F( S, c )        - множество состояний, достижимых из S
                        за один переход, помеченный символом c.

Упражнение по программированию: придумайте структуры данных для представления детерминированного и недетерминированного ко¦ нечных автоматов и запрограммируйте проверку допуска строки из символов ASCII KA. Это можно (и следует) делать за время

- O(длина цепочки)                  для детерминированного и
- O(длина цепочки*число состояний) для недетерминированного КА.

Преобразование недетерминированного КА в детерминированный

Недетерминированный КА всегда можно преобразовать в эквива¦ лентный (т.е. допускающий то же множество цепочек) детерминиро¦ ванный КА. Рассмотрим новый КА, состояниями которого будут под¦ множества множества состояний исходного КА (если исходный авто¦ мат имел m состояний, сколько их будет у нового? - упражнение). Исходным для нового автомата будет состояние {Начало}, конечны¦ ми - все состояния, содержащие исходное конечное состояние. Пе¦ реход A -> B по символу d имеется в новом автомате тогда и только тогда, когда в исходном автомате для любого состояния b из B, существует a из A такое, что по символу d возможен пере¦ ход a -> b, и других переходов по d из A нет. Новый автомат бу¦ дет детерминированным и эквивалентным исходному.

Действительно, состояние нового автомата a+b соответствуют размещению экземпляров исходного недетерминированного КА в сос¦ тояниях a и b, а переход в новом автомате соответствует перехо¦ дам всех экземпляров недетерминированного КА.

Для практических целей применяется аналогичный алгоритм: На¦ зовем состояния неразличимыми, если в них происходит переход из одного и того же состояния при одном и том же входном символе. Возьмем любое множество неразличимых состояний и добавим в спи¦ сок состояний КА еще одно - их "сумму", перемещая переходы:

       Было:                 ¦           Стало:
--¬1 --¬0 --¬                ¦  --¬1 ----¬0
¦ +->+Б+->+В¦                ¦  ¦ +->+Б+Г+>T->¬
¦А¦  L--  L--                ¦  ¦А¦  L---- ¦  ¦
¦ ¦1 --¬0 --¬                ¦  ¦ ¦  --¬0 -+¬ ¦
¦ +->+Г+->+Д¦                ¦  ¦ ¦  ¦Б+->+В¦ ¦
L--  LT-  L--                ¦  L--  L--  L-- ¦
--¬1  ¦                      ¦  --¬1 --¬0    -+¬
¦Е+->--                      ¦  ¦Е+->+Г+->---+Д¦
L--                          ¦  L--  L--     L--

Получим новый (быть может, вновь недетерминированный) КА. Будем повторять наши действия, пока в КА остаются неразличимые состо¦ яния. Этот процесс в конце концов завершится (почему? - упраж¦ нение). При этом мы получим детерминированный автомат, эквива¦ лентный исходному (почему? - упражнение).

Применив этот метод к недетерминированному КА из примера в этой лекции, получим:

                                     --<----------¬ 1
       --------¬ 0  --------¬ 1  -T--+--T¬0  -----+----¬
       ¦   S   +->--+   B   +->--+¦  C  ¦+-->+  S + B  ¦
       L--------    L---T----    L+-----+-   L----T-----
                        L--<----------------------- 0

Минимизация конечного автомата

По конечному автомату часто можно построить автомат с мень¦ шим числом состояний, эквивалентный исходному. Соответствующий процесс называется минимизацией конечного автомата. Вначале выбросим из автомата все состояния, недостижимые из начального. Затем разобьем все состояния КА на классы эквивалентности сле¦ дующим способом: в первый класс отнесем все конечные состояния, а во второй - все остальные. Назовем эти состояния 0-эквива¦ лентными. Теперь построим новое 1-эквивалентное разбиение, вы¦ делив те состояния, которые по одинаковым символам переходят в 0-эквивалентные состояния. Последовательно строя n+1-эквива¦ лентные состояния по n-эквивалентным, мы будем увеличивать чис¦ ло классов эквивалентности. Прекратим этот процесс тогда, когда n+1-эквивалентное состояние совпадет с n-эквивалентным. Каждый полученный класс эквивалентности и будет состоянием нового ми¦ нимизированного КА, эквивалентного исходному (почему? - упраж¦ нение).

Рассмотрим, например, следующий КА:

                --------¬1   -T-----T¬ 0--------¬
     -------¬0->+   B   +->--+¦  D  ¦+<-+   F   ¦
     ¦Начало+-- L-T------   -++---T-+-  L---T-T--
     ¦      ¦     ¦  --<-----0 -->- ¦1   -->- ¦1
     ¦      ¦     ¦  ¦         ¦    ¦    ¦    ¦
     ¦      ¦     L<-+------¬0 ¦1 -<-    ¦0 -<-
     ¦  A   +-¬ -----+--¬1  LTT+--+-T¬ 1-+--+---¬
     L-------1L>+   C   +->--+¦  E  ¦¦<-+   G   ¦
                L--------    L+-----+-  L--------

Состояния F и G недостижимы (это можно выяснить, например, вы¦ числив транзитивное замыкание отношения "есть переход"). Пос¦ троим классы n-эквивалентности для оставшихся состояний:

       n        Классы
       0      (ABC) (DE)
       1      (A) (BC) (DE)
       2      (A) (BC) (DE)

Результат:

            ------¬0,1  ------¬1    -T---T¬
            ¦  A  +---->+ B+C +---->+¦D+E¦¦
            L------     L--T---     L+-T-+-
                           L-<----------0

Упражнение: докажите, что для любого КА существует и единственен с точностью до изоморфизма минимальный эквива¦ лентный ему конечный автомат. Покажите, что описанный выше ал¦ горитм минимизации получает на выходе минимальный автомат.

Упражнение по программированию: придумайте структуры данных и запрограммируйте процедуры построения детерминированного КА, и минимизации КА. Какая временная и пространственная сложность предложенных вами алгоритмов в терминах числа состояний исход¦ ного и выходного автоматов?

Регулярные языки и регулярные выражения

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

---------------------T-----------T----------------------------¬
¦    Регулярное      ¦Регулярное ¦    Конечный автомат        ¦
¦     множество      ¦ выражение ¦                            ¦
+--------------------+-----------+----------------------------+
¦  Пустая цепочка    ¦     e     ¦   ------¬   e   -T---T¬    ¦
¦                    ¦           ¦   ¦  S  +--->---+¦ E ¦¦    ¦
¦                    ¦           ¦   L------       L+---+-    ¦
+--------------------+-----------+----------------------------+
¦ Один символ a из E ¦     a     ¦   ------¬   а   -T---T¬    ¦
¦                    ¦           ¦   ¦  S  +--->---+¦ E ¦¦    ¦
¦                    ¦           ¦   L------       L+---+-    ¦
+--------------------+-----------+----------------------------+
¦                    ¦           ¦ ----¬ e --T-----T-¬ e -T-T¬¦
¦  P U Q             ¦    p|q    ¦ ¦   +->-+s¦Авт.P¦e+->-+¦ ¦¦¦
¦                    ¦           ¦ ¦ S ¦   L-+-----+--   ¦¦E¦¦¦
¦                    ¦           ¦ ¦   ¦ e --T-----T-¬ e ¦¦ ¦¦¦
¦                    ¦           ¦ ¦   +->-+s¦Авт.Q¦e+->-+¦ ¦¦¦
¦                    ¦           ¦ L----   L-+-----+--   L+-+-¦
+--------------------+-----------+----------------------------+
¦  PQ (конкатенация) ¦    pq     ¦ ----T-----T----T-----TT-T¬ ¦
¦                    ¦           ¦ ¦ S ¦Авт.P¦ es ¦Авт.Q¦¦Е¦¦ ¦
¦                    ¦           ¦ L---+-----+----+-----++-+- ¦
+--------------------+-----------+----------------------------+
¦  P* (итерация)     ¦    p*     ¦          ---<----¬e        ¦
¦                    ¦           ¦ ----¬ e -+T-----T+¬ e -T-T¬¦
¦                    ¦           ¦ ¦ S +->-+s¦Авт.P¦e+->-+¦E¦¦¦
¦                    ¦           ¦ L-T--   L-+-----+--   L+T+-¦
¦                    ¦           ¦  eL---------->-----------  ¦
+--------------------+-----------+----------------------------+
¦   P (просто скобки)¦    (p)    ¦    ------T-------TT---T¬   ¦
¦                    ¦           ¦    ¦  S  ¦ Авт.P ¦¦ E ¦¦   ¦
¦                    ¦           ¦    L-----+-------++---+-   ¦
L--------------------+-----------+-----------------------------

В регулярном выражении "*" имеет больший приоритет, чем кон¦ катенация, а конкатенация - больший чем "|". Примеры регулярных выражений: (0|1)*, (0|1)(0|1)*. Какие множества они описывают?

Для регулярного выражения предложен способ построения неде¦ терминированного конечного автомата, допускающего соответству¦ ющее выражению регулярное множество. Предложенная конструкция не является самой экономной (автомат обычно содержит много "лишних" e-переходов), однако построенный автомат обладает следующими полезными свойствами:

  • у него только одно конечное состояние,
  • в начальное состояние не входит ни одно ребро,
  • из конечного состояния не выходит ни одно ребро.

Таким образом, мы доказали, что регулярные множества < регу¦ лярные языки = языки, допускаемые КА. Покажем, что допускаемое КА множество - регулярно. (Это утверждение называется теоремой Клини).

Доказательство: Пусть S1,...Sn - состояния детерминированно¦ го КА, S1 - начальное состояние. Рассмотрим все пути в графе переходов с началов в Si, концом в Sj, промежуточными узлами из множества {S1...Sk} (1<=i<=n, 1<=j<=n, 0<=k<=n) и множества це¦ почек из E - L(i,j,k), соответствующие этим путям. Докажем ин¦ дукцией по k, что множества L - регулярны.

L(i,j,0) - состоит из меток ребер, ведущих из Si в Sj, сле¦ довательно, регулярно. Для 0<=k<=n-1 L(i,j,k+1) = L(i,j,k) U L(i,k+1,k) L(k+1,k+1,k)* L(k+1,j,k) получено с помощью регулярных операций из регулярных мно¦ жеств, следовательно, регулярно.

Множество цепочек, допускаемых КА, представляет собой объеди¦ нение цепочек L(1,j,n), таких, что Sj - конечное состояние КА, следовательно, регулярно. (Конец доказательства).

Мы рассмотрели 4 способа описания языков:

  • регулярные (автоматные, праволинейные) грамматики,
  • недетерминированные КА,
  • детерминированные КА,
  • регулярные выражения,

и показали, что они описывают один класс языков - регулярные языки. Этот класс языков "устроен очень хорошо" - для всех ти¦ пичных вопросов известны ответы и эффективные алгоритмы. Приме¦ ры таких вопросов (получение ответов - упражнение):

  • является ли объединение, пересечение, дополнение регулярных языков регулярным,
  • является ли регулярный язык конечным, пустым,
  • совпадают ли два регулярных языка,
  • является ли один регулярный язык подмножеством другого, и т.д.

(Замечание. Для других классов иерархии Хомского дела обстоят значительно хуже, например, проблема эквивалентности для КС-языков алгоритмически неразрешима.)

Лемма о разрастании для регулярных языков

Так называмые "леммы о разрастании" для классов языков - удобный способ доказательства того, что конкретный язык не от¦ носится к данному классу.

Лемма для регулярного языка: Существует такое число m, что любую цепочку x, |x| > m, принадлежащую языку, можно разбить на три части: x = uvw так, что 0<|v|<=m и цепочки uv*w также будут принадлежать языку. Доказательство: построим КА для распознава¦ ния языка. Пусть этот автомат имеет m состояний. Тогда при раз¦ боре цепочки x хотя бы одно из состояний (например, А) прохо¦ дится дважды (почему? - упражнение). Разобьем цепочку x на три части - до состояния А, от А до А, остальное. Это и есть цепоч¦ ки u,v,w (почему v можно размножать, сохраняя принадлежность цепочки языку? - упражнение).

                           n n
   Как показать, что язык 0 1 не является регулярным? -  упраж¦
нение.

Задачи и упражнения

  1. Написать регулярную грамматику и регулярное выражение, порождающие тот же язык, что и грамматика:
       S : AB ;   A : X|Y ;   X : x|xX ;   Y : y|yY ;   B : b|bB
    
  2. Построить регулярную грамматику и конечный автомат, соот¦ ветствующие регулярному выражению:
            (101)*(010)*
    
  3. Постройте недетерминированный а затем детерминированный конечные автоматы, воспринимающие регулярное выражение:
            (101)*(110)*
    
  4. Построить детерминированные конечные автоматы для следу¦ ющих регулярных выражений. Для каждого полученного автомата построить эквивалентный минимальный автомат. Убедиться в изо¦ морфизме минимальных автоматов, следовательно, в эквивалентнос¦ ти исходных выражений:
       (a|b)*   (a*|b*)*   ((e|a)b*)*
    
  5. Написать регулярное выражение, описывающее следующий язык
    • слово, буквы которого расположены в алфавитном порядке
    • последовательность цифр, в которой нет повторяющихся цифр
    • последовательность цифр, в которой не более чем одна цифра встречается несколько раз
    • строка из нулей и единиц, в которой нет подстроки 0 0 1
    • строка из нулей и единиц, в которой нет подпоследователь¦ ности 0 0 1
  6. Опишите регулярной грамматикой и приведите регулярное вы¦ ражение для идентификатора Фортрана. (До шести букв или цифр, первый символ должен быть буквой).
  7. Напишите программу распознавания вещественных констант. Она должна воспринимать константы вида:
    1.2  -0.4 +3.14 .2 1. -1.е38 1е+2 +0.5е-23 и т.д.
    
  8. Построить минимальные детерминированные конечные автоматы для следующих регулярных выражений
       (a|b)*a(a|b)
       (a|b)*a(a|b)(a|b)
       (a|b)*a(a|b)(a|b)(a|b)
    

    Доказать, что любой детерминированный конечный автомат для вы¦ ражения (a|b)a(a|b)(a|b)...(a|b), содержащего n-1 (a|b) в конце содержит не менее чем 2**n состояний.

  9. Напишите программу, которая проверяет, является ли имя файла частным случаем разновидности регулярного выражения, в котором метасимвол * обозначает любую (в том числе и пустую) последовательность символов кроме ".", а метасимвол ? - любой символ кроме "."

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

Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования