Преобразования нка

При построении лексич анализатора, над НКА необходимо выполнить ряд преобразований.

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

В таблице переходов НКА каждая запись представляет собой множество состояний; в таблице переходов ДКА — единственное состояние. Общая идея преобразования НКА в ДКА состоит в том, что каждое состояние ДКА соответствует множеству состояний НКА. ДКА использует свои состояния для отслеживания всех возможных состояний, в которых НКА может находиться после чтения очередного входного символа. Таким образом, после чтения входного потока ДКА находится в состоянии, которое представляет подмножество состояний НКА, достижимых из стартового состояния HКА по пути, помеченному как . Количество состояний ДКА может оказаться экспоненциально зависящим от количества состояний НКА.

На рис. 14 показан еще один НКА, допускающий язык (a|b)*abb. Этот автомат получен с использованием алгоритма построения НКА по регулярному выражению.

Рис. 14. НКА для (a|b)*abb

Преобразование НКА в ДКА путем построения подмножеств дает пять различных множеств состояний:

А = {0, 1, 2, 4, 7} D = {1, 2, 4, 5, 6, 7, 9}

В = {1, 2, 3, 4, 6, 7, 8} Е = {1, 2, 4, 5, 6, 7, 10}

С = {1, 2, 4, 5, 6, 7}

Состояние А является начальным, а E — единственным заключительным состоянием. Полностью таблица переходов показана на рис. 15.

Состояние	Входной символ
	a	b
А	В	C
В	В	D
С	В	С
D	В	Е
Е	В	С

Рис. 15. Таблица переходов для ДКА

Рис. 16. Результат применения построения подмножества к рис. 15.

Граф переходов, полученного в результате преобразований ДКА показан на рис. 16. Следует заме­тить, что ДКА на рис. 13 также допускает язык (а | b) *abb и имеет на одно состояние меньше.

Далее необходимо минимизировать количество состояний ДКА.

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

Изначально разбиение состоит из двух групп: заключительные состояния и незаключительные. Основной шаг состоит в том, чтобы взять некоторую группу символов скажем А = и входной символ а и посмотреть, какие переходы имеют состояния для этого входного символа. Если эти переходы представляют переходы в состояния, попадающие в две или более различных групп текущего разбиения, группу А разбиваем на подгруппы так, чтобы для каждого из подмножества переходы ограничивались одной группой текущего разбиения.

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

67. Синтаксический анализ: роль синтаксического анализатора, контекстно-свободные грамматики (КС-грамматики) как основной инструмент формального изучения синтаксиса языков программирования: определение КС-грамматики, дерево вывода в КС-грамматике, однозначность КС-грамматик и языков, связь между КС-языками и МП-автоматами, автоматы с магазинной памятью, описание, функционирование, способы задания МП-автомата, недетерминированные и детерминированные МП-автоматы.

Синтаксический анализатор (синтаксический разбор) - это часть компилятора, кот отвечает за выявление основных синтаксич конструкций входного языка.