Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Исключение тупиков




 

Правило A ® j By называется внешним тупиком, если не существует правила B ®x. (Из нетерминала B нет выхода).

 

Правило B® x называется внутренним тупиком, если B ¹ S и не существует правила A ® j By. (Нетерминал B не может появиться ни в одной сентенциальной форме, выводимой из начального символа грамматики. Внутренний тупик - это аналог недостижимого состояния конечного автомата).

 

Циклический тупик - это группа правил вида

A0® j1A1y1

A1® j2A2y2

..................

An® j0A0y0,

где Ai ¹ S и, при этом, либо для любого Ai не существует правил вида B ® lAim (циклический тупик внутреннего типа), либо для любого Ai не существует правил вида Ai ®c (циклический тупик внешнего типа). ƒ

 

Теорема 4.5. Для любой грамматики существует эквивалентная ей грамматика без тупиков.

 

Для доказательства данной теоремы достаточно вспомнить, что эквивалентные грамматики порождают один и тот же язык (множество терминальных цепочек, которое выводятся из начального символа грамматики). Очевидно, что правила, включающие тупики, при порождении терминальных цепочек из начального символа грамматики просто не могут использоваться.

Алгоритмы поиска тупиков и их устранения рассмотрим на примере.

 

Пример 4.4. Пусть задана грамматика c начальным символом S и следующим множеством правил

S® a A ½ c C ½ b D ½ q P ½ k T A® c C

C® k T® m

D® b T ½ f K P® c R

R® d K B® d Q ½ m

Q® p B ½ r B

Здесь выбрана автоматная грамматика только для того, чтобы наглядно проиллюстрировать ее графом состояний (рис. 4.1).

Построим новую грамматику, отбирая из исходной “хорошие” (производящие нетерминалы), из которых выводится терминальная цепочка. Для этого положим, что множество

X0 = S,

то есть X0 совпадает с множеством терминалов.

X1 = { A |$ A® x, где xÎ Xo },

то есть те нетерминалы, из которых терминальная цепочка получается за один шаг.

X2 = { A | $ A® x, где xÎ (Xo È X1) },

.......................................................

Xi = { A | $ A® x, где },

то есть Xi - множество нетерминалов, из которых терминальная цепочка получается не более, чем за i шагов (под шагом здесь понимается одновременная замена всех нетерминалов сентенциальной формы). На каждом шаге мы добавляем новые нетерминалы, их конечное число, следовательно конечен и данный процесс (X1 Í X2 Í... X i Í N).

Положим Z i , равным разности X i и X i-1,

Z i = X i \ X i-1 -

это те нетерминалы из которых терминальная цепочка получается ровно за i шагов. Если Z i = Æ, - пустое множество, то процесс формирования продуктивных нетерминалов пора закончить, так как из Z i = Æ следует, что Z i+1 = Æ и т.д.

Отобранные нетерминалы обладают тем свойством, что из них выводятся терминальные цепочки. Оставшиеся нетерминалы, терминальных цепочек не порождают и их можно удалить из грамматики вместе с правилами, содержащими их в левой или правой части. Этот алгоритм позволяет устранить все внешние тупики и циклические тупики внешнего типа.

В рассматриваемом примере

X0 = {a,c,b,q,k,m,f,d,p,r},

X1 = {C,T,B}, Z1 = {C,T,B},

X2 = {S,A,C,T,D,Q,B}, Z2 = {S,A,D,Q}

X3 = {S,A,C,T,D,Q,B}, Z3 = Æ.

Следовательно X3 - и есть то самое множество “хороших” нетерминалов. Удалив остальные нетерминалы и все ссылки на них в правилах грамматики мы получим грамматику:

S® a A ½ c C ½ b D ½ k T A® c C

C® k T® m

D® b T B® d Q ½ m

Q® p B ½ r B

Для устранения внутренних тупиков повторим процесс выбора “хороших” символов с другого конца. Положим

Y0 = { S },..., Y i = { A | $ B® jAy, где AÎ (SÈN) и BÎ Y i-1 },

то есть Y i - множество символов (терминалов и нетерминалов), которые могут появиться в сентенциальной форме на i - том шаге вывода.

В нашем примере

Y0 = {S},

Y1 = {a,A,c,C,b,D,k,T},

Y2 = {c,C,k,m,b,T},

Y3 = {k,l}.

Далее, определим

W i = Y i \ () Ç N,

то есть новые нетерминалы, появляющиеся на i - том шаге. Очевидно, что из W i = Æ, следует, что процесс можно закончить, так как все нетерминалы, выводимые из начального символа грамматики, уже получены. Остальные нетерминалы и содержащие их правила грамматики можно удалить.

В нашем случае

W0={S},

W1={A,C,D,T},

W2=Æ.

Нетерминалы B и Q - внутренние тупики. Таким образом, грамматика без тупиков имеет вид:

S® a A ½ c C ½ b D ½ k T A® c C

C® k T® m D® b T ƒ




Поделиться с друзьями:


Дата добавления: 2015-06-27; Просмотров: 663; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.