Основы конструирования компиляторов

          

Построение детерминированного конечного автомата по недетерминированному


Рассмотрим алгоритм построения по недетерминированному конечному автомату детерминированного конечного автомата, допускающего тот же язык.

 

Алгоритм 3.2. Построение детерминированного конечного автомата по недетерминированному.

Вход. НКА M = (Q, T, D, q0, F).

Выход. ДКА M' = (Q', T, D', q0', F'), такой что L(M) = L(M').

Метод. Каждое состояние результирующего ДКА - это некоторое множество состояний исходного НКА.

В алгоритме будут использоваться следующие функции:

e-closure(R) (R

Построение детерминированного конечного автомата по недетерминированному
Q) - множество состояний НКА, достижимых из состояний, входящих в R, посредством только переходов по e, т.е. множество

Построение детерминированного конечного автомата по недетерминированному

move(R, a) (R

Построение детерминированного конечного автомата по недетерминированному
Q) - множество состояний НКА, в которые есть переход на входе a для состояний из R, т.е. множество

Построение детерминированного конечного автомата по недетерминированному

 

Вначале Q' и D' пусты. Выполнить шаги 1-4:

  • Определить q0' = e-closure({q0}).
  • Добавить q0' в Q' как непомеченное состояние.
  • Выполнить следующую процедуру:

    while (в Q' есть непомеченное состояние R){

    пометить R;

    for (каждого входного символа a

    Построение детерминированного конечного автомата по недетерминированному
    T){

    S = e-closure(move(R, a));

    if (S

    Построение детерминированного конечного автомата по недетерминированному
    Построение детерминированного конечного автомата по недетерминированному
    ){

    if (S

    Построение детерминированного конечного автомата по недетерминированному
    Q')

    добавить S в Q' как непомеченное состояние;

    определить D'(R, a) = S;

    }

    }

    }

  • Определить F' = {S|S
    Построение детерминированного конечного автомата по недетерминированному
    Q', S
    Построение детерминированного конечного автомата по недетерминированному
    F
    Построение детерминированного конечного автомата по недетерминированному
    Построение детерминированного конечного автомата по недетерминированному
    }.

Пример 3.6. Результат применения алгоритма 3.2 приведен на рис. 3.10.

Построение детерминированного конечного автомата по недетерминированному


Рис. 3.10:


Приведем теперь алгоритм построения по регулярному выражению детерминированного конечного автомата, допускающего тот же язык[10].

Пусть дано регулярное выражение r в алфавите T. К регулярному выражению r добавим маркер конца: (r)#. Такое регулярное выражение будем называть пополненным. В процессе своей работы алгоритм будет использовать пополненное регулярное выражение.

Алгоритм будет

оперировать с синтаксическим деревом для пополненного регулярного выражения (r)# , каждый лист которого помечен символом a

Построение детерминированного конечного автомата по недетерминированному
T
Построение детерминированного конечного автомата по недетерминированному
{e, #}, а каждая внутренняя вершина помечена знаком одной из операций: .

(конкатенация), | (объединение), * (итерация).

Каждому листу дерева (кроме e-листьев) припишем уникальный номер, называемый позицией, и будем использовать его, с одной стороны, для ссылки на лист в дереве, и, с другой стороны, для ссылки на символ, соответствующий этому листу. Заметим, что если некоторый символ

используется в регулярном выражении несколько раз, он имеет несколько позиций.

Теперь, обходя дерево T снизу-вверх слева-направо, вычислим четыре функции: nullable, firstpos, lastpos и followpos. Функции nullable, firstpos и lastpos определены на узлах дерева, а followpos - на множестве позиций. Значением всех функций, кроме nullable, является множество позиций. Функция followpos вычисляется через три остальные функции.

Функция firstpos(n) для каждого узла n синтаксического дерева регулярного выражения дает множество позиций, которые соответствуют

первым символам в подцепочках, генерируемых подвыражением с вершиной в n. Аналогично, lastpos(n) дает множество позиций, которым соответствуют последние символы в подцепочках, генерируемых подвыражениями с вершиной n. Для узла n, поддеревья которого (т.е. деревья, у которых узел n является корнем) могут породить пустое слово, определим nullable(n) = true, а для остальных узлов nullable(n) = false.

Таблица для вычисления функций nullable, firstpos и lastpos приведена на рис. 3.11.

Построение детерминированного конечного автомата по недетерминированному


Рис. 3.11:

Пример 3.7.


Рассмотрим теперь алгоритм построения ДКА с минимальным числом состояний, эквивалентного данному ДКА [10].

Пусть M = (Q, T, D, q0, F) - ДКА. Будем называть M всюду определенным, если D(q, a)

Построение детерминированного конечного автомата по недетерминированному
Построение детерминированного конечного автомата по недетерминированному
для всех q
Построение детерминированного конечного автомата по недетерминированному
Q и a
Построение детерминированного конечного автомата по недетерминированному
T.

Лемма. Пусть M = (Q, T, D, q0, F) - ДКА, не являющийся всюду определенным. Существует всюду определенный ДКА M', такой что L(M) = L(M'). Доказательство. Рассмотрим автомат M' = (Q

Построение детерминированного конечного автомата по недетерминированному
{q'}, T, D', q0, F), где q'
Построение детерминированного конечного автомата по недетерминированному
Q - некоторое новое

состояние, а функция D' определяется следующим образом:

  • Для всех q
    Построение детерминированного конечного автомата по недетерминированному

    Q и a

    Построение детерминированного конечного автомата по недетерминированному
    T, таких что D(q, a)
    Построение детерминированного конечного автомата по недетерминированному
    Построение детерминированного конечного автомата по недетерминированному
    , определить D'(q, a) = D(q, a).
  • Для всех q
    Построение детерминированного конечного автомата по недетерминированному

    Q и a

    Построение детерминированного конечного автомата по недетерминированному
    T, таких что D(q, a) =
    Построение детерминированного конечного автомата по недетерминированному
    , определить D'(q, a) = q'.
  • Для всех a
    Построение детерминированного конечного автомата по недетерминированному

    T определить D'(q', a) = q'.

Легко показать, что автомат M' допускает тот же язык, что и M. __

Приведенный ниже алгоритм получает на входе всюду определенный автомат. Если автомат не является всюду определенным, его можно сделать таковым на основании только что приведенной леммы.

 

Алгоритм 3.4. Построение ДКА с минимальным числом состояний.

Вход. Всюду определенный ДКА M = (Q, T, D, q0, F).

Выход. ДКА M' = (Q', T, D', q0', F'), такой что L(M) = L(M') и M' содержит наименьшее возможное число состояний.

Метод. Выполнить шаги 1-5:

  • Построить начальное разбиение
    Построение детерминированного конечного автомата по недетерминированному
    множества состояний из двух групп: заключительные состояния Q и остальные Q - F, т.е.
    Построение детерминированного конечного автомата по недетерминированному
      =  {F, Q - F}.
  • Применить к
    Построение детерминированного конечного автомата по недетерминированному
    следующую процедуру и получить новое разбиение
    Построение детерминированного конечного автомата по недетерминированному
    new:

    for (каждой группы G в

    Построение детерминированного конечного автомата по недетерминированному
    ){

    разбить G на подгруппы

    так, чтобы

    состояния s и t из G оказались

    в одной подгруппе тогда и только тогда,

    когда для каждого входного символа a

    состояния s и t имеют переходы по a

    в состояния из одной и той же группы в

    Построение детерминированного конечного автомата по недетерминированному
    ;

    заменить G в

    Построение детерминированного конечного автомата по недетерминированному
    new на множество всех

    полученных подгрупп;

    }

  • Если
    Построение детерминированного конечного автомата по недетерминированному
    new =
    Построение детерминированного конечного автомата по недетерминированному
    , полагаем
    Построение детерминированного конечного автомата по недетерминированному
    res =
    Построение детерминированного конечного автомата по недетерминированному
    и переходим к шагу 4, иначе повторяем шаг 2 с
    Построение детерминированного конечного автомата по недетерминированному
    :=
    Построение детерминированного конечного автомата по недетерминированному
    new.
  • Пусть
    Построение детерминированного конечного автомата по недетерминированному
    res = {G1, ..., Gn}. Определим:

    Q' = {G1, ..., Gn};

    q0' = G, где группа G

    Построение детерминированного конечного автомата по недетерминированному
    Q' такова, что q0
    Построение детерминированного конечного автомата по недетерминированному
    G;

    F' = {G|G

    Построение детерминированного конечного автомата по недетерминированному
    Q' и G
    Построение детерминированного конечного автомата по недетерминированному
    F
    Построение детерминированного конечного автомата по недетерминированному
    Построение детерминированного конечного автомата по недетерминированному
    };

    D'(p', a) = q', если D(p, a) = q, где p

    Построение детерминированного конечного автомата по недетерминированному
    p' и q
    Построение детерминированного конечного автомата по недетерминированному
    q'.

    Таким образом, каждая группа в

    Построение детерминированного конечного автомата по недетерминированному
    res становится состоянием нового автомата M'.


    Синтаксическое дерево для пополненного регулярного выражения (a|b)*abb# с результатом вычисления функций firstpos и lastpos приведено на рис. 3.12. Слева от каждого узла расположено значение firstpos, справа от узла - значение lastpos. Заметим, что эти функции могут быть вычислены за один обход дерева.

    Построение детерминированного конечного автомата по недетерминированному


    Рис. 3.12:
    Построение детерминированного конечного автомата по недетерминированному


    Рис. 3.13:
    Если i - позиция, то followpos(i) есть множество позиций j таких, что существует некоторая строка ...cd..., входящая в язык, описываемый регулярным выражением, такая, что позиция i соответствует этому вхождению c, а позиция j - вхождению

    d.

    Функция followpos может быть вычислена также за один обход дерева снизу-вверх по следующим двум правилам.

    1. Пусть n - внутренний узел с операцией .

    (конкатенация), u и v - его потомки. Тогда для каждой позиции i, входящей в lastpos(u), добавляем к множеству значений followpos(i) множество firstpos(v).

    2. Пусть n - внутренний узел с операцией *

    (итерация), u - его потомок. Тогда для каждой позиции i, входящей в lastpos(u), добавляем к множеству значений followpos(i) множество firstpos(u).

    Пример 3.8. Результат вычисления

    функции followpos для регулярного выражения из предыдущего примера приведен на рис. 3.13.

    Алгоритм 3.3. Прямое построение ДКА по регулярному выражению.

    Вход. Регулярное выражение r в алфавите T.

    Выход. ДКА M = (Q, T, D, q0, F), такой что L(M) = L(r).

    Метод. Состояния ДКА соответствуют множествам позиций.

    Вначале Q и D пусты. Выполнить шаги 1-6:


    • Построить синтаксическое дерево для пополненного регулярного выражения (r)#.


    • Обходя синтаксическое дерево, вычислить значения функций nullable, firstpos, lastpos и followpos.

    • Определить q0 = firstpos(root), где root - корень синтаксического дерева.


    • Добавить q0 в Q как непомеченное состояние.


    • Выполнить следующую процедуру:

      while (в Q есть непомеченное состояние R){

      пометить R;

      for (каждого входного символа a
      Построение детерминированного конечного автомата по недетерминированному
      T , такого, что

      в R имеется позиция, которой соответствует a){

      пусть символ a в R соответствует позициям



      p1, ..., pn, и пусть S =
      Построение детерминированного конечного автомата по недетерминированному


      1<i<nfollowpos(pi);

      if (S
      Построение детерминированного конечного автомата по недетерминированному
      Построение детерминированного конечного автомата по недетерминированному
      ){

      if (S
      Построение детерминированного конечного автомата по недетерминированному
      Q)

      добавить S в Q как непомеченное состояние;

      определить D(R, a) = S;

      }

      }

      }


    • Определить F как множество всех состояний из Q, содержащих позиции, связанные с символом #.


    Пример 3.9. Результат применения алгоритма 3.3 для регулярного выражения (a|b)*abb приведен на рис. 3.14.

    Построение детерминированного конечного автомата по недетерминированному


    Рис. 3.14:


    Если группа содержит начальное состояние автомата M, эта группа становится начальным состоянием автомата M'. Если группа содержит заключительное состояние M, она становится заключительным состоянием M'. Отметим, что каждая группа
    Построение детерминированного конечного автомата по недетерминированному
    res либо состоит только из состояний из F, либо не имеет состояний из F. Переходы определяются очевидным образом.


  • Если M' имеет «мертвое» состояние, т.е. состояние, которое не является допускающим и из которого нет путей в допускающие, удалить его

    и связанные с ним переходы из M'. Удалить из M' также все состояния, недостижимые из начального.


  • Пример 3.10. Результат применения алгоритма 3.4 приведен на рис. 3.15.

    Построение детерминированного конечного автомата по недетерминированному


    Рис. 3.15:

    Содержание раздела