Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 24
Текст из файла (страница 24)
, Конфигурация называется начальной, если управляющее устройство находится в заданном начальном состоянии, входная головка обозревает самый левый символ иа входной лепте и память имеет зарэпес установленное начальное содержимое. Конфигурация называется гиключительной, если управляющее устройство находится в одном из состояний заранее выделенного множества заключительных состояний, а входная головка обозревает правый концевой маркер или, если маркер отсутствует, сошла с правого конца входной ленты.
Часто требуют, чтобы память в заключительной конфигурации тоже удовлетворяла некоторым условиям. Говорят, что распознаватель допускает входную цепочку ил, если, начиная с начальной конфигурации, в которой цепочка лэ 115 ГЛ. З. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ записана на входной ленте, распознаватель может проделать последовательность шагов, заканчивающуюся заключительной конфигурацией.
Следует указать, что, начиная с данной начальной конфигурации, недетерминированный распознаватель может проделать много различных последовательностей шагов. Если хотя бы одна из этих последовательностей заканчивается заключительной конфигурацией, то начальная входная цепочка будет допущена. Язык, определяемый распознавателем,— это множество входных цепочек, которые он допускает. Для каждого класса грамматик нз иерархии Хомского существует естественный класс распознавателей, определяющий тот же класс языков.
Этими распознавателями являются конечные автоматы, автоматы с магазинной памятью, линейно ограниченные автоматы и машины Тьюринга. Точйее, языкн из иерархии Хомского можно охарактеризовать так: (1) Язык Ь праволинейный тогда н только тогда, когда он определяется (односторонним детерминированным) конечным автоматом. (2) Язык ~ контекстно. свободный тогда и только тогда, когда он определяется (односторонним недетерминированным) автоматом с магазинной памятью.
(3) Язык Е контекстно-зависимый тогда и только тогда, когда он определяется (двусторонним недетерминированным) линейно ограниченным автоматом. (4) Язык й рекурсивно перечислнмый тогда н только тогда, когда он определяется машиной Тьюринга. Точные определения этих распознавателей можно найти в упражнениях и в дальнейших разделах. Конечные автоматы и автоматы с магазинной памятью играют важную роль в теории компиляции, и в этой главе мы их подробно изучим.
7ПРМКНИНИЯ 2.1.1. Постройте праволинейные грамматики для языков, состоящих нз (а) идентификаторов, которые могут быть произвольной длины, но должны начинаться с буквы (как в Алголе); б) идентификаторов, которые должны содержать от одного до шести символов и начинаться с буквы 1, ',7, К, Т., М или й! (как идентификаторы целых переменных в Фортране); (в) вещественных констант, как в ПА~1 илн Фортране, например 10.8, 3.!4159, 2., 6.625Е-27; (г) всех цепочек нз нулей и единиц, имеющих четное число нулеи и четное число единиц. 116 уп Р ажн в ни я 2.1.2. Постройте КС-грамматики, порождающие а) все цепочки из нулей н единиц с одинаковым числом тех и других; б) (а,а,,а„а„...а,а,)ать(О, 1), 1~(~п); в) правильно построенные формулы исчисления высказываний; г) (О'17 ) 1~) и 1, 1')д); д) всевозможные последовательности правильно расставленных скобок.
+2.1.3. Опишите язык, порождаемый правилами 5 — Ь55(а. Заметьте, что не всегда легко описать язык, порождаемый конкретной грамматикой. "2,1.4. Постройте КЗ-грамматики, порождающие (а) а" !п' "-1); (б) ихв ~ тв 6 (а, Ь) т) (в) 1ш«эта (а, Ь, с)' и число букв а в цепочке ш равно числу букв Ь, равному числу букв с); г) «атЬпатЬт ) т и ..т 1) Указание: Представьте себе множество правил КЗ-грамматики как программу. Вы можете взять специальные нетерминальные символы в роли комбинаций „входной головки" с терминальными символами.
"2.1.5. „Истинно" контекстно-зависимая грамматика 6 †э грамматика (Ь(, л., Р, 5), в которой каждое правило имеет вид аАр ау5, где и, «) Е (Ь! !) л.)", у Е ( т'() л)+ и А Е Ь!. Такое правило можно истолковать в том смысле, что А можно заменить на у только в контексте и, 5. Покажите, что каждый КЗ-язык может порождаться „истинно" контекстно-зависимой грамматикой.
**2.1.6. Какой класс языков может порождаться грамматиками, использующими только левый контекст, т. е. грамматиками, в которых каждое правило имеет вид аА — я)), где аЕ(Ь)() Х)*, «) Е (тт' 0 м)'? 2.1.7. Покажите, что каждый КС-язык может порождаться грамматикой 6=(Ь«, лэ Р, 5), в которой каждое правило нмеет вид либо А- и, аЕХ', либо А- ш, шЕХ', 2.1.8. Покажите, что каждый КЗ-язык может порождаться грамматикой 6=(тт", Х, Р, 5), в которой каждое правнло имеет вид либо а р, где а, ~Ей(+, либо А ш, где А6ХииЕХ.".
2.1.9. Докажите, что Т. (6) =(а"Ь"с")и) 1), где 6 — грамматика из примера 2.5. *2.1.10. Можете ли Вы описать множество КС-грамматик с помощью КС-грамматикир !17 ГЛ. З ЗЛРМЕНТЫ ТЕОРИИ ЯЗЫКОН *2.1.11. Покажите, что каждое рекурсивио перечислимое множество может порождаться грамматикой, использующей нс более двух иетерминальных символов. Может ли произвольное рекурсивно перечислнмое множество порождаться грамматикой, использующей только один нетсрмипальный символу 2.1.12.
Покажите, что если грамматика 6 = ()А(, Х, Р, 5) такова„что ~ !ч'=и и Х пе содержит символов А„А„..., то существует эквивалентная ей грамматика 6' — (г!', Х, Р', А,), у которой (Ч'= (А„А„..., А„). 2.1.13. Докажите, что грамматика 6, из примера 2.! порождает язык (О" !" ! л) !). Указание: Обратите внимание, что каждая выводимая цепочка содержит не более одного нетерминала. Таким образом, правила можно применять только в одном месте цепочки.
Определение. В грамматике без ограничений 6 данную цепочку можно вывести многими способами, которые по существу одинаковы и отличаются лишь порядком, в котором применяются правила. Если грамматика 6 контекстно-свободная, то эти по существу одинаковые выводы можно представить с помощью одного дерева вывода. Однако если грамматика 6 контекстнозависимая или без ограничений, то классы эквивалентных выводов можно определить следующим образом, Пусть 6=(п(, Х, Р, 5) — грамматика без ограничений.
Пусть 0 — множество всех выводов вида 5=>' ш, т. е. элементами множества В служат такие последовательности вида (и„и„...,и„), что а„= 5, и„Е Х' и а,, =>ио 1 ~1(л. Определим отношение В, на множестве О, положив (а„а„..., я.) 1!,((1„(1„..., р„) тогда и только тогда, когда найдется такой индекс ! между 1 и л — 1, что (!) и,.=б для всех 1()-=.л, !Ф11 (2) можно писать а,,=-у1у,удау~ и и 1 'у Ьузеуч "Ричем в Р есть правила у,— б и у,— е, и либо и;=у,будд, и В=у у~у~ау„либо наоборот. Пусть Я вЂ” наименьшее отношение эквивалентности, содержащее Р,.
Каждый класс эквивалентности отношения )У образован по существу одинаковыми выводами данной цепочки. *"2.1.14. Каков максимальный объем класса эквивалентности отношения Я (как функция от и и 1а„(), если грамматика 6 (а) праволинейная? (б) контекстно-свободная? (в) такова, что каждое ее правило имеет вид и — (1 и И<)РР 11В УПРАЖНЕ пня "2.1.15. Пусть 6 определяется правилами 5- АОВ ! В!А А ВВ(Π — АА)! Каков объем класса эквивалентности отношения В, содержащего вывод 5=->А ОВ=~ В ВО В= > ! ВОВ=> ! АЛОВ>10АО В~1 000В=> ! 0001 2 к Определение. Грамматика 6 называется однозначной, есл аждая цепочка ш из /, (6) появляется в качестве последней компоненты вывода в одном и только в одном классе эквивалентности определенного выше отношения В.
Например, грамматика 5- аЬС(аВ В-- Ьс 86 Ьс (5 аВ, аЬс) п неоднозначная, так как последовательности (5, оЬ6 ,ас)и (, а, аЬс) принадлежат двум различным классам эквивалентности, *2.1.16. П .. 6. окажите, что каждый праволинейный язык определяется однозначной праволинейной грамматикой. *2.1.17. Пусть 6=(!ч, Х, Р, 5) — КЗ-грамматика н "Р(ВХ содержит т элементов. Пусть ш — слово из языка Л (6). Покажите, что 5=Ос ш, где л ~ (и+ 1)1 2.1.18.
Покажите, что каждый КЗ-язык рекурсивен. Указание: С помощью результата упр. 2.!.17 постройте алгоритм, определяющий для произвольного слова ш и КЗ-грамматики 6, принадлежит ли ш языку В(6). 2.1.1 . .. 9. Покажите, что каждый КС-язык рекурснвен. Указание: Используйте упр. 2.1. !8, но обратите внимание на пустое слово. *2.1.26. Покажите, что если 6=((ч, Х, Р, 5) — грамматика без ограничений. то существует такая КЗ-граммати 6' = ( ', Ц(с),, 5 ), что шЕТ.(6) тогда н только тогда, когда ка н 1сс'ЕЕ(6') для некоторого 1.-О. Указание: Дополните каждо е контекстно-зависимое правило грамматики 6 буквами с. Затем ж ое добавьте правила, позволяющие буквам с сдвигаться к правому концу любой выводимой цепочки. 2.1.21. П к о ажнте, что если В=!. (6) для произвольной грамматики 6, то существуют такой КЗ-язык Ь, и такой гомоморфизм й, что Л = й (1.,).
ГЛ. й. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ УПРАЖНЕ НИЯ 2.1.22. Пусть (А„А„... ) — счетное множество нетерминальных символов, не содержащее символы 0 и 1. Покажите, что каждый КЗ-язык Е = (О, 1)* имеет КЗ-грамматику б =- =(4, (0,1), Р, А,), в которой )Ч=-(А„А„..., А ) для некоторого 1. Мы будем называть такую КЗ-грамматику нормализованной. *2.1.23. Покажите, что множество определенных выше норма. лизованных КЗ-грамматик счетно. "2.1.24. Покажите, что суп1ествует рекурсивное множество, содержащееся в (О, 1)Р, которое не является КЗ-языком. Указание: Упорядочите нормализованные КЗ-грамматики, чтобы можно было говорить об 1-й грамматике. Аналогично задайте лексикографический порядок на множестве (О, 1)*, чтобы можно было говорить об 1-Й цепочке в (О, 1) *.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
