- •Формальные грамматики и языки.
- •Задача разбора
- •Классификация грамматик по Холмскому.
- •Диаграмма состояний
- •Отношения предшествования
- •Распознаватель
- •Матрица предшествования
- •Некоторые приемы приведения к грамматикам простого предшествования.
- •Представление автоматов.
- •Концевые маркеры и выходы из распознавания.
- •Эквивалентность состояний.
- •Проверка эквивалентности двух состояний.
- •Недостижимые состояния.
- •Алгоритм составления списка достижимых состояний.
- •Приведённые автоматы.
- •Получение минимального автомата.
- •Недетерминированные автоматы.
- •Эквивалентность недетерминированных и детерминированных конечных распознавателей (нкр и дкр).
- •Задание:
- •Транслятор.
- •Введение таблицы символов.
- •Включение неявной информации.
- •Обнаружение ошибок.
- •Макрообработка и операции, выполняемые во время компиляции.
- •Синтез объектной программы.
- •Оптимизация.
- •Генерация кода.
- •Редактирование связей и загрузки.
- •Задача идентификации. Реализация ка при работе трансляторов.
- •Хранение информации о лексемах.
- •Механизм запоминания.
- •Метод хеширования.
- •Нисходящий разбор с возвратами.
- •Начальная установка.
- •Новый человек.
- •Неудача
- •Класс грамматик, допускающих нисходящий распознаватель.
- •Статистические управляемые схемы перевода и атрибутные грамматики.
- •Контекстные условия
Получение минимального автомата.
Метод проверки эквивалентности состояний, рассмотренный выше, использовать для приведения автоматов не удобно, т.к. он позволяет обработать только 2 состояния. Рассмотрим другой, более практичный метод – «метод разбиения». Он заключается в разбиении множества состояний на непересекающиеся подмножества, такие что не эквивалентные состояния попадают в разные блоки.
Сначала состояния разбиваются на 2 блока: один содержит допускающие состояния, другой – отвергающие. В нашем примере начальное разбиение Р0 = ({1, 2 , 3 , 4} , {5, 6, 7})
{1, 2 , 3 , 4} – отвергающие; {5, 6, 7} – допускающие
Ни одно состояние из первого блока не эквивалентно никакому состоянию (ни одному ) второго блока, т.к. нарушаются условия подобия.
-
y
z
1
2
3
4
5
6
7
6
7
1
4
7
4
4
3
3
5
6
3
1
2
0
0
0
0
1
1
1
Теперь посмотрим, что происходит с состоянием первого блока под действием входного символа а. Состояния 3 и 4 переходят в состояния, принадлежащие первому блоку (1 и 4), тогда как состояния 1 и 2 переходят в состояний, принадлежащие второму блоку ( 6 и 7). Это означает, что для любого состояния из множества {1, 2} и любого из {3, 4} соответствующие состояния – приемники по входу а будут не эквивалентны. Это позволяет произвести новое разбиение P1=({1,2}, {3,4}, {5, 6, 7}), причем состояния из разных блоков всегда неэквивалентны, причём получили состояния Р1 и Р0, разбивая блок {2,3,4} относительно входа а. теперь попытаемся найти такой входной символ и такой блок в Р1, чтобы его можно было разбить относительно этого входного символа и получить тем самым новое разбиение. Для этого разбиение также будет выполняться свойство неэквивалентности состояний, принадлежащих разным блокам. Повторяем процесс пока дальнейшее разбиение становится невозможным. Т.к. мы не остановили порядок, в котором входные символы и блоки проверяются на возможность разбиения, последовательность разбиений можно порождать многими способами. Последнее разбиение будем одним и тем же во всех случаях. В нашем примере, разбивая блок {3,4} из Р1 относительно а и получаем: P2=({1,2}, {3}, {4}, {5, 6, 7}). Далее разбиваем {5, 6, 7} из P2 относительно а или b, получаем: P3=({1,2}, {3}, {4}, {5}, {6, 7}). P3 – не допускает дальнейшего разбиения. Все состояния блока {1,2} переходят относительно а в состояния блока {6,7}, а относительно b в {3}. Аналогично блок {6,7} переходит в {4} и {1,2} относительно а и b соответственно. Оставшееся блоки имеют по одному элементу, по этому автоматически исключают дальнейшее разбиение.
Когда процедура закончена, состояния внутри каждого блока эквивалентны. В примере: 1~2 и 6~7. Блоки последнего разбиения можно использовать для построения нового автомата, который эквивалентен исходному и не содержит эквивалентных состояний.
-
a
b
{1,2}
{3}
{4}
{5}
{6,7}
{6,7}
{1,2}
{4}
{6,7}
{4}
{3}
{5}
{6,7}
{3}
{1,2}
0
0
0
1
1
Множество состояний нового автомата – это множество блоков последнего разбиения. Переходы нового автомата получены из старого, прослеживая переходы из блока в блок, для каждого входного символа. Автомат не имеет недостижимых состояний и является, поэтому минимальным. В общем случае процедура разбиения должна сопровождается выбрасыванием недостижимых состояний в целях получения минимального автомата. Не имеет значения, какая из двух процедур выполняется первой.
