Нисходящий распознаватель с возвратом
(подбором альтернатив)
Данный распознаватель моделирует работу МП автомата с одним состоянием.
q: R({q},V,z,δ,q,S,{q})
Начальная конфигурация (q,α,S) определяется следующим образом:
- автомат находится в своем единственном состоянии q,
- считывающая головка находится вначале входной цепочки символов,
- в стеке лежит символ соответствий целевому символу грамматики.
Конечная конфигурация (q,l,l):
- автомат находится в единственном состоянии q,
- считывающая головка находится за пределами цепочки символов,
- в стеке ничего не содержится.
Работа алгоритма с использованием псевдокодов.
1. если на верхушке стека нах-ся символ АÎVN, то А можно заменить на цепочку символов α (А→αÎР), и считывающая головка не сдвигается – этот шаг называется подбор альтернатив
всё если
2. если на верхушке стека нах-ся символ аÎVT: а=текущий символ входной цепочки символов, то а можно выбросить из стека и передвинуть считывающую головку →1, этот шаг называется выброс.
всё если
Решение о том, какой шаг нужно выполнить, принимается однозначно. Моделирующий алг-м должен обеспечить выбор 1-ой из возможных альтернатив и хранение информации о том, какие альтернативы и на каком шаге были выбраны.
Данный МП автомат строит левосторонние выводы, читает цепочку входных символов слева-направо, поэтому построение дерева-вывода идет сверху-вниз (Þнисходящий распознаватель с возвратом), грамматика должна быть леворекурсивной.
|
|
|
Символ АÎVN называется рекурсивным, если для него существует цепочка вывода А=>+αAβ
α=λ β≠λ левая рекурсия
α≠λ β=λ правая рекурсия
α=λ β=λ образуется цикл
Недостаток: значительная временная емкость, т.к. имеется экспоненциальная зависимость, необходимых для работы алгоритма вычислительных ресурсов.
Преимущества: 1) простота реализации 2) универсальность
Принципы работы восходящего распознавателя
По алгоритму «сдвиг - свертка»
Данный расп-ль моделирует работу расширенного МП автомата R({q},V,z,δ,q,S.{qi}). Начальная конфигурация данного МП автомата определяется (q,α,λ). Конечная – (q,λ,S)
Реализация алгоритма с использованием псевдокода:
если на верхушке стека нах-ся цепочка символов γ
то γ заменяется на АÎVN(A→γÎP) (данный шаг наз свертка)
всё если
если считывающая головка в стек и передвинуть считывающую головку на 1 позицию справа
все если
Данный расширенный МП автомат строит правосторонним выводом и читает цепочку слева-направо, поэтому построение дерева идет снизу-вверх и называется восходящим распознавателем с возвратом.
|
|
|
Недостаток: значительная временная емкость.
Преимущество: а)простота реализации б)универсальность.
Распознаватели КС языков без возврата
Существует 2 класса:
1. нисходящие расп-ли порождают цепочки левостороннего вывода сверху вниз, строят дерево вывода сверху вниз и используют модификацию алгоритма с подбором альтернатив.
К этому классу отн-ся следующие:
а) расп-ль на основе рекурсивного спуска
б) расп-ль на основе LL(K)-граматики
в) расп-ль на основе LL(1)-граматики
2) восходящие распознаватели порождают цепочки правостороннего вывода, строят дерево вывода снизу вверх, используют модификацию алг-ма сдвиг-свертка
К этому классу отн-ся следующие:
а) расп-ль на основе 2R(K)
б) расп-ль 2R(0)
в) расп-ль 2R(1)
Распознаватель на основе грамматик
Предшествования
Принцип организации таких расп-лей основан на том, что для каждой упорядоченной пары символов грамматики, устан-ся отношения предшествования.
Грамматика предшествования:
1. грамматика простого предшествования
2. расширенное предшествование
3. слабого предшествования
4. смешанной стратегии предшествования
5. грамматики операторного предшествования
Самые распространенные и простые 1 и 5:
1. Грамматика простого предшествования – это такая приведенная КС грамматика G(VT,VN,P,S) в которой:
|
|
|
1) для каждой упорядоченной пары VT и VN вып-ся не более, чем одно из 3-х отношений предшествования
2) различные порождающие правила должны иметь разные правые части
Отношения предшествования для символов обозначаются =,<,>
Строится матрица предшествования.
Для построения матрицы предшествования используются множество крайних левых и множество крайних правых символов относительно нетерминальных символов грамматики.
Матрицу предшествования необходимо дополнить символами ┴Н и ┴К(символ начала и конца строки)
Недостаток: не всякий детерминированный КС язык может быть задан грамматикой простого предшествования; если в грамматике много терминальных и нетерминальных символов, то увел-ся матрица предшествования
5. Операторная грамматика - это такая приведенная КС грамматика, в которой правые части всех правил не содержат смежных недетерминированных символов и отношения предшествования определены на множестве терминальных символов.
Грамматика операторного предшествования – это операторная КС грамматика, в которой:
- для каждой упорядоченной пары терминальных символов выполняется не более чем одно из 3-х отношений предшествования:
|
|
|
а) а=b
b) а<b
c) a>b
- различные порождающие правила имеют различные правые части
Для практического использования матрицу предшествования дополняют символами 
Н и К.
Свойства КС языков
Произвольные КС языки замкнуты относительно следующих операций:
-подстановки,
-объединения,
-контетенации,
-итерации
-гомоморфизм
КС языки не замкнуты отн-но:
-пересечения,
-дополнения
Детерм-ные КС языки замкнуты отн-но операции дополнения и не замкнуты отн-но:
-объединения
-пересечения.
Две основные цели преобразования КС языков:
-упрощение правил грамматики
-обеспечение создания распознавателя языка
Дата добавления: 2018-05-31; просмотров: 575; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!