Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 38
Текст из файла (страница 38)
Тогда, заметив, что Гхг =--КВ."+ 14, можно получить систем определяющих уравнений 0 =- 1(0+ Й с неизвестными . Отмеу тим, 11то если 0 Р— 0 н 12 — матрицы порядка и, то система состоит дг . тмеиз и' уравнении. Лемма 2.19. Пусть А — --А)4+  — система опрсделяющих урав- нгний в алфавитах Л и Х. Пусть 0 — матрица того жг порядка, что и 11, причем всг ге элслгенты — различные новые символь. огда сиспггма опрт)гляюи(их уравнении', сослгоящая из А = , ол г. 0-РВ и 0 = П0+гт, иггеггп наименьшую неподвижную точк, кото ая у, А=АЙ+В.
р совпадает на Л с наилгеньшгй неподвижной точкой системьг Доказательство. Упражнение. Дадим другой алгоритм преобразования приведенной граммагики к нормальной форме Грейбах. !вб 2Л, КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Алгоритм 2.15. Преобразование к нормальной форме Грейбах. Вход. Приведенная грамматика 6=(Х, гч Р, В) без правил вида  — г. Выход. Эквивалентная грамматика б'=(гч', Тч Р' В) в нормальной форме Грейбих. Метод. (1) По грамматике 6 построить систему определяющих уравнений А=- АР+В в алфавитах Ь! и Х.
(2) Пусть 0 — матрица порядка п, состоящая из новых символов, и ~ Х=и. Построить новую систему определяющих уравнений А = ВО+В, 0 — ВО+ й и соответствующую грамматику 6,. Так как в векторе В каждая компонента, отличная от Гсг, начинается терминалом, а такие компоненты должны быть в силу приведениости грамматики 6, то для А ЕХ все А-правила грамматики' 6, будут начинаться терминалами.
(3) Так как б — приведенная грамматика, то е не является элементом матрицы В. Поэтому для каждого элемента у матрицы 0 все соответствующие у-правила грамматики 6, начинаются символами из Х(! г.. В тех правых частях этих правил, которые начинаются нетермнналом, заменить этот нетерминал А правымп частями всех А-правил, В результате получится грамматика, у которой правые части всех правил начинаются терминалом. (4) Если в правой чисти некоторого правила терминал а встречается не на первом месте, заменить его новым нетерминалом а' н добавить правило а' — а. Результирующую грамматику обозначить через б'.
[) Теорема 2.20. Алгоритм 2.15 дает граммаглику 6' в нормальной форме Гргйбах и 7. (6) =й(б'). Доказательство. Так как грамматика б приведенная и не содержит 5 — с, то б' грамматика в нормальной форме Грейбах, поскольку в не является компонентой вектора В и матрицы К. Из лемм 2.!4, 2.17 и 2.19 следует, что 5(6') =- ~(6). И Пример 2.30. Рассмотрим грамматику, соответствующую системе определяющих уравненей (2.4.7): А в АаВ!ВВ!Ь В вЂ” аА ) ВАа ~ Вй ! с Перепишем систему (2.4,7), согласно шагу (2) алгоритма 2.15, в виде (2.4 8) (А, В]=(Ь, аА+с] ~ ~1+~5, аА+с] газ гл. г.
Злгменты теОРин языкОВ Затем добавим систему (2.4.9) 1, 7. = В Аа+с( 1' Л + В Аа-'-гг Системам (2.4.8) и (2.4.9) соответствует грамматика Ь)лт ( ал ?' ~ с?' ~ Ь В вЂ” ЬХ(аАЛ)с_#_(аА(с )1т аВУ' ( аВ Х- аВХ К вЂ” Вйг1ла3 1с(?'1 В Л вЂ” ВХ(ла2!г)Е!Аа(с( Заметим, что Х вЂ” бесполезный символ, На гпаге (3) в правилах ?' — В)Р" 1ла?'(В и Л- ВХ1Ла7.)ла нетерминалы А и В заменяются соответствующими правыми частями правил. Так как это преобразование и преобразование на шаге (4) уже знакомы читателю, мы их опускаем.
() УПРАЖНЕНИЯ 2.4.1. Пусть 6 определяется правилами 5- АВ А Аа(Ь  — а15Ь Постройте деревья выводов следующих выводимых цепочек: (а) ЬааЬааЬ, (б) ЬВАВЬ, (в) Ьа5Ь. 2.4.2. Постройте левый и правый выводы цепочки ЬааЬааЬ в грамматике нз упр. 2.4.1.
2.4.3. Постройте все сечения дерева, изображенного на рис. 2.14. ве Рве. 2.14. Неоолгевенное дерево вывода 2.4.4. Покажите, что следующие утверждения о КС-грамматике 6 н цепочке нг эквивалентны: 188 упРАЖ не ния (а) нг — крона двух различных деревьев выводов в 6, (б) нг имеет два различных левых вывода в 6, (в) аг имеет два различных правых вывода в 6. **2.4.6. Каково наибольшее число выводов, которые пред- ставляются одним и тем же деревом с гг вершинами? 2.4.6. Преобразуйте грамматику 5- А(В А — аВ)ЬВ(Ь В вЂ” АВ(Ва  — А5(Ь в эквивалентную КС-грамматику, не содержащую бесполезных символов.
2.4.7, Докажите, что алгоритм 2.8 правильно устраняет не- достижимые символы. 2.4.8. Дополните доказательство теоремы 2.13. 2.4.9. Оцените временную н емкостную сложности алгорит- ма 2.8. В качестве вычислительной модели возьмите машину с произвольным доступом к памяти. 2.4.10. Постройте алигритм, вычисляющий для КС-грамма- тики 6=-()лг, 2, Р, 5) множество (А (А =>*с, А Е)л?). Насколько быстр Ваш алгорггглг? 2.4.11. Найдите грамматику бсз е-правнл, эквивалентную грамматике 5 АВС А- ВВ(е  — СС1а с лл'ь 2.4.12. Дополните доказательство теоремы 2.14.
2,4.13. Найдите приведенную грамматику, эквивалентную грамматике 5-Л(В л с~в В- 0)Е С вЂ” 51а)е Х> — 5(Ь Е вЂ” 51с(е 2.4.14. Докажите теорему 2.16. 2.4.13. Докажите лемму 2.14. ГЛ. 2. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОЕ упР Аж н е ни я 2.4.16. Преобразуйте следующие грамматики к нормальной форме Хамского: (а) 5 в 051/01 (ЬА )ЬАА)а аВВ) Ь (б) 5 — аВ А — а5 В Ь5( 2.4.17. Если 6. (Ь), г, Р, 5) — грамматика в нормальной форме Хомского, 5=>лов, !а~- и и шаг.", то каково !г? 2.4.18. Дайте подробное доказательство теоремы 2.17.
2.4.10. Преобразуйте к нормальной форме Грейбах грамматику 5 — Ва!АЬ А — 5а(ААЬ )а  — 5Ь(ВВа!Ь Определение. КС-грамматика называется операторной, если в правых частях ее правил нет двух стоящих рядом нетермнна лов. "2.4.27. Покажите, что каждый КС-язык определяется операторной грамматикой, Указание: Начпитс с грамматики в пор. мальной форме Грейбах. *2.4.28.
Покахплте, что каждый КС-язык порождается грамматикой, все правила которой имеют вид А- аВЬС, А — аВЬ, используя (а) алгоритм 2.14, (б) алгоритм 2.!5, "2.4.20. Постройте быстрый алгоритм, проверяющий, леворе- курсивна ли КС-грамматика 6. 2.4,21. Постройте быстрый алгоритм, устраняющий в КС-грам- матике правую рекурсию. 2.4.22. Дополните доказательство леммы 2.15. *4.4.23. Докажите леммы 2.17 — 2.19. 2А.24. Завершите преобразования примера 2.30 и получите приведенную грамматику в нормальной форме Грейбах. 2.4.25. Сравните относительные достоинства алгоритмов 2.14 и 2.!5, особенно с точки зрения объема резулыирующей грам- матики.
*2.4.26. Покажите, что каждый КС-язык, не содержащий пу- стой цепочки е, определяется грамматккой, все правила которой имеют вид А аВС, А- аВ или А — а. А- аВ или А — а. Если е Е7. (6), то допускается еще правило 5- е, ""2.4.20. Рассмотрим грамматику с двумя правялами 5 — 55!а. Покажите, что число Х„различных левых выводов цепочки а" находится из соотношсния Х„= ~ Х,Х 1+/=Р лье !~ о где Х,=!. Покажите, что ('2п) (числа такого вида называются числами Каталана). *2.4.30. Покажите, что КС-язык Г., не содержащий цепочек, длина которых меньше 2, порождается грамматикой с правилами вида А — ааЬ.
2.4.31. Покажите, что каждый КС-язык определяется грамматикой, удовлетворяющей условию: если Х,Х, ... Хл †прав часть правила, то все Х„ ..., Хл различны. Определение. КС-грамматика 6=-(гч, г,, Р, 5) называется линейной, если каждое ее правило имеет вид А — шВх или А — и, где ВЕЗ, а ш и х принадлежат Г~. 2А.32. Покажите, что каждый линейный язык, не содержащий пустой цепочки, определяется грамматикой, все правила которой имеют вид А — аВ, А Ва или А — а, е2.4.33. Покажите, что каждый КС-язык определяется такой грамматикой 6=-(Х, г„Р, 5), что если А ЕЕ! — (5), то язык (ш~ А=''ш и ш~ Х*) бесконечен. 2.4.34.
Покажите, что каждый КС-язык определяется рекурсивной грамматикой. Указание: Используйте лемму 2.14 и упр. 2,4.33. ь2.4.35, Назовем КС-грамматику 6=(г(, Е, Р, 5) кеазилинейной, если для каждого правила А Х, ... Хл существует ие более одного символа Хп порождающего бесконечное множество терминальных цепочек. Покажите, что каждая квазилинейная Грамматика порождает линейный язык. Определение. Графом КС-грамматики 6=-(4, л, Р, 5) назовем такой ориентированный неупорядоченный граф (гл О г' О (е), Я), что А)7Х тогда и только тогда, когда А- аХр — правило грамматики для некоторых а и 6. ГЛ.
2. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ лпмж не папе! Замечания по литературе 192 2.4.36. Покажите, что если грамматика не содержит бесполезных символов, та все вершины ее графа достижимы из 3. Верно ли обратное утверждение? 2.4.37. Пусть Т вЂ преобразован КС-грамматик, определенное в лемме 2,14, т, е. 7 отображает О в О', где б и О' †грамматики из леммы 2.!4.
Покажите, что алгоритмы 2.10 и 2,!! можно реализовать повторными применениями преобразования Т. Упрпаенгния нп прогрпммпровпниг 2.4.38. Постройте программу, устраняющую в КС-грамматике бесполезные символы. 2.4.39. Постройте программу, которая преобразует КС-грамматику в эквивалентную приведенную КС-грамматику. 2.4.40. Постройте программу, устраняющую в КС-грамматике левую рекурсию. 2.4А[. Постройте программу, которая решает, является ли данное дерево деревом вывода в КС-грамматике, Дерево вывода имеет немело других назнлнпй, среди которых: дерево порождення, диаграмма разбора, дерево разбора, дерево анализа, снятакснческое дереео, дерево составляющих.
Анллогнчыое понятие хорошо известно в лингвистике. Понятие левого вывода появилось в работе Эын [1963[. Многие алгоритмы этой главы были известны сщс н начале !960.х годов, хотя часть нз пнх появилась н литературе значнтельно позже. Теорема 2,!7 (нормлльная форма Хомского) впервые доказана Хомским [1959а1. Теорема 2.16 (нормальная форма Грейблх) впервые доказана Грейбех [19651.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
