Контекстно-свободные языки и грамматики
Контекстно-свободные языки определяются грамматиками типа G(VT,VN,P,S), в которых правила Р имеют вид:
P: A →VN, где AÎVN, βÎV+=VNυVT
Приведенные грамматики - это КС грамматики, которые не содержат недостижимых, бесплодных символов, циклов, λ-правил (пустых правил).
Для преобразования произвольной КС грамматики к приведенному виду нужно:
1. удалить все бесплодные символы. AÎVN.
А - называется бесплодным, если из него нельзя вывести ни одной цепочки терминальных символов.
2. удалить все недостижимые символы хÎ( VNυVT).
x - называется недостижимым, если он не встречается не в одной сентенциальной форме грамматики G(VT,VN,P,S).
3.удалить все λ-правила: A → λ, где AÎVN
4. удалить цепные правила.
Циклический вывод: А=›*А
А→В
А,В Î VN
Все удаляется только в этом порядке.
Распознаватели КС языков
Распознавателями для КС-языков являются автоматы с магазинной памятью – МП-автоматы – односторонние недетерминированные распознаватели с линейно ограниченной магазинной памятью (стек).
Определение: R(Q, V, Z, d, q0, z0, F), где
Q - Множество состояний автомата.
V - Множество входных символов.
z - Спец. конечный алфавит магазинных символов автомата.
d - Функция переходов.
z0 – Начальный символ магазина.
F – Множество конечных состояний.
Переход из одного состояния в другое зависит не только от входного символа, но и от одного или нескольких верхних символов в стеке.
|
|
|
(q, λ, n)
За 1-й такт работы из стека удаляется верхний символ, соотв. условию перехода и добавляются цепочка, соотв. правилу перехода. 1-й символ цепочки становится верхушкой стека.
Конфигурация автомата на каждом шаге работы определяется следующим образом: (q,α,ω)α=(β,n), где
q - текущее состояние, где qÎQ;
ω - содержимое стека. ωÎz;
β - вся цепочка
n - положение указателя в текущий момент.
При выполнении такта из магазина удаляется верхний символ, соответствующий условию перехода и добавляется цепочка, соответствующая правилу перехода. 1-ый символ этой цепочки становится верхушкой стека.
Допускается λ-переходы, при которых входной символ игнорируется (он будет входным символом при следующем переходе).
Автомат не обязательно извлекает символы из магазина.
МП-автомат называются недетерминированным, если из одной и той же конфигурации возможен более чем один переход в следующую конфигурацию .
МП-автомат называются детерминированным, если из одной и той же конфигурации возможен не более чем один переход в следующую конфигурацию
Начальная конфигурация Мп определяется следующим образом: (q0,α,z0), а конечная (q,λ,ω).
МП автомат допускает цепочку символов, если на входе в эту цепочку он может перейти в одну из конечных конфигураций.
|
|
|
МП автомат допускает цепочку с опустошением магазина, если при окончании разбора автомат находится в одной из конечных конфигураций, а стек пуст.
Расширенный МП автомат может заменить конечную цепочку длины в верхней части стека на другую цепочку символов конечной длины.
Распознаватели КС языков с возвратом.
Распознаватели с возвратом – самые примитивные, моделируют работу недетерминированного МП автомата.
Т.к. моделируется работа недетерминированного автомата, значит на некотором шаге работы возможно возникновение нескольких допустимых следующих состояний автомата. Используются 2 варианта реализации:
1. На каждом шаге работы, алгоритм должен запоминать все возможные следующие состояния, выбирать одно из них, переходить к нему и т.д. до тех пор, пока не будет конечного состояния, иначе автомат не перейдет в такую конфигурацию, переходы из которой не определены. Время выполнения алгоритма имеет экспоненциальную зависимость от длины входной цепочки символов. Необходимый объем памяти линейно зависит от длины исход. цепочки символов.
2. На каждом шаге при возникновении неоднозначности запускается новая копия для обработки каждого состояния. Время линейно зависит, объем памяти – экспоненциально.
|
|
|
Особенность моделирования производимого МП автомата заключается в следующем: разбор может не завершиться за конечное число шагов. Для исключения подобных ситуаций алгоритмы разбора с возвратами строятся не для произв-ных МП автоматов, а для МП автоматов, удовлетворяющих некоторым заданным условиям.
Дата добавления: 2018-05-31; просмотров: 383; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!