Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 33
Текст из файла (страница 33)
Алгоритм 26, Нахождение классов неразличи- мых состояний конечного автомата. Вход. Конечный автомат М =. Я, Х, 6, у„г"). Выход. Классы эквивалентности отношения ==. Метод. (!) Найти 6 2(у, а) (р ~ 6(р, а) д) для всех дЕ(! и аЕХ. Положить л2, =- ( у ! у ~ л! и 6 ' (у, а) ~= 5а). (2) Положить л,.= 1: и л =Я вЂ” Е. (3) Для всех аЕХ определить множества индексов ЕСЛИ Ф Ль, а ~» Ф ТЧ2, а> ! (а)— ( (2) в противном случае.
(4) Положить й=д. (5) Выбрать аЕ2 н !ЕЕ(а). Если 7(а)=Я для всех а~2, остановиться. Выход — множество классов л„л,, ..., лх,. (6) Удалить !' из множества ! (а). (7) Для всех !<Й, для которых существует у ~ л, и 6 (а, а) а л2, сделать шаги (а) — (г): (а) Положить я!= (д~ 6 (д, а) ~л! и д ~я!) и л';=-л — л,'. (б) Заменить л! па л! и положить л„=л";; построить новые л! „и л„„для всех а ц 2.
(в) Для всех або изменить ! (а), положив ( 7(а)(1(!), если 1!Г7(а) и О < Ф л,,,(Фл„„ ! (а) = ( !(а)В(й) в противном случае. (г) Положить й = й+ 1. (8) Перейти к шагу 5. Д 2.3.12. Примените алгоритм 2.6 к конечным автоматам нз примера 2.!5 и упр. 2.3.2.
2.3.13. Докажите, что алгоритм 2.6 правильно находит классы неразличимых состояний конечного автомата. *"2.3.14. Покажите, что алгоритм 2.6 можно реализовать за время а1опа. 2.3,13. Покажите, что следующие множества ие регулярны: (а) (Оа10а ~ а.х 1), (б) (~!шб(0. 1)*) (в) Е(6), где б определяется правилами  — аВЬЯ/с, (г) (а" (и ~1), 159 Гл. э. элементы тгаРИН языкОВ УПРАЖ11С ННЯ (д) (аг «р — простое число), (е) (щ ~ ц1 ц (О, 1)* и н1 имеет одинаковые числа нулей и единиц). 2.3.16.
Пусть Е(т) — монотонно возрастающая функция и для каждого п существует такое т, чта Е(т+1))Е(т)+а. Пока- жите, что множество (а1аа1 ~т. л1) не регулярно. Определение. Пусть Е, и Е,— языки. Определим следующие операции: (1) Е1/Е,=-(н11н1х~Е1 для некоторого хСЕ,,), (2) Пл(1Т(Е.1) =(ю)ц1хц Е., для некоторого х), (3) Г1!Л!(Е1) — (1э1хн1СЕ1 для некоторого х), (4) БУВ(Е,) =(н1~хн1ус 7.1 для некоторых х и у), (5) М1!л((Е,,) — --(н1!н1цЕ, и никакой собственный префикс це- почки н1 не принадлежит Е,), (5) МАХ (Е,) =(н11н1С Е., и не существует такого хзье, что н1х с Е.1). Пример 2.!8. Пусть Е, =(Оа1"Ож«а, т) 1) и Е.,=-1*0*.
Тогда Е.1ЕЕ, =Е,,0(0117!1~~1, 1(1) 1)л(!Т(Е.,)=Е,,(1(0'1'/1>1, 1~1) 00* И5)(Е.,) =(О'!70 ~8~1, 1>1, 1--1)()1 О" (1О Я)В(Е.,) — (011УОА«1 1)111*0 00 1 М1)Л) (Е.,) =-(Оа1а0!11)~ 1) МАХ (Е1) = 8 П *2.3.17. Пусть Ц н Е.,— регулярныс множества. Покажите, что следующие множества регулярны: (а) Ц!Е.„ (б) 1М1Т(Е,,), (в) Г1Ы (Е,), (г) Я)В(Е,,)„ (д) М114 (Е.',), (е) МАХ (Е.,).
*2.3.18. Пусть Е,— рсгулярное множество, а Е,— произволь- ный язык. Покажите, что множество Е1)Е, регулярно. Существует ли алгоритм, который находит конечный автомат для ~,11Е„если дан автомат для Е.,? ОпРеделение. ПуоизводнУла 0жи РегУлЯРного выРажениЯ сл по хЕА' можно определить рекурсивно: (1) 0,и=и. (2) Для а ЕВ (а) 0,1Р1 =,8, (б) 0,е=в, 140 ( 111, если а~Ь, (в) 0„Ь=- )а, еслиа — Ь, (г) 0,(и+1) —...0,и+О,!), / (0,и)!), если е(и, (д) 0,(ир) = «(0,и) «1+0,5, если еци, (е) 0,и" =.- (0,и) и', (3) 0,„и = 0„(0„и) для а с Х и х ц В", 2.3.19.
Покажите, что если и=!0*1, то (а) 0„= 10'1, (б) 0а1"" =- Ы (в) 0,и=-О'!. "2.3.20. Покажите, что если и — регулярное выражение, обо- значающее регулярное множество )т, то 0„и обозначает х))Е = (а «хю ~ )т ). а*2.3,21. Пусть Š— регулярное множество. Покажите, что мно- жество (х худ Е для некоторого у, такого, что «х)=«у«) регу- лярно. Следующее упражнение обобщает упр. 2.3.21. "А2.3.22. Пусть | — регулярное множества и Е (х) — полинам ат х с неотрицательными целымн коэффициентами.
Покажите, что множество «н1!н1уЕЕ для некоторого у, такого, что «у« — Е(«п1«)) регулярно. *2.3.23. Пусть Š†регулярн, множества и Ь вЂ” гомоморфизм, Покажите„что Й(Е,) и Ь '(Ц вЂ” регулярные множества. 2.3.24. Докажите корректность алгоритмов 2.4 и 2.5. 2.3.25. Оцените временную н емкостную сложности алгорит- мов 2.4 и 2.5. 2.3.26. Дайте формальное доказательство теоремы 2.10. Обратпте внимание, что недостаточно проста показать, что, скажем, для каждого регулярного выражения существует конечный автомат, допускающий обозначаемое им множество. Нужно показать, что существует алгоритм, который по регулярному выраже.
нию строит этот автомат. В этой связи см. приллер 2.17. *2.3.27. Дайте эффективный алгоритм минимизации числа состояний не полностью определенного детерминированного конечного автомата. 2.3.28. Дайте эффективные алгоритмы, решающие проблемы пРинадлежности, пустоты и эквивалентности для (а) Регулярных выражений, 6 А.
Ажк дж. Ъааыан, ж 1 ГЛ. 2. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ (б) праволннейных грамматик, (в) педетерминираванных конечных автоматов, "*2.3.29. Покажите, что проблемы принадлежности и эквивалентности неразрешимы для 'способа представления регулярных множеств, указанного в примере 2.17. е2.3.30. Покажите, что проблема: „Бесконечен лн язык 7. (М)уч разрешима для конечных автоматов. Указание: Покажите, что для автомата М с п состояниями язык Т. (М) бесконечен тогда и только тогда, когда 7.(М) содержит цепочку иг, для которой !1([иг(< 2п.
е2.3 31- Локажите алгоритмическую разрешимость проблемы включения 7,(М,) с=В(М,), где М, и М,— канечныс автоматы. Открытая проблегва 2.3.32. Найдите быстрый алгоритм (скажем, такой, который для автомата с и состояниями требует временн не более и", где й — нонстанга), дающий недетерминированный конечный автомат с минимальным числом состояний, эквивалентный данному. Упражнения на проераммироеание 2.3.33.
Напишите программу, которая воспринимает в качестве входа конечный автомат, праволинейную грамматику нли регулярное выражение н выдает на выходе эквивалентное регулярное выражение, конечный автомат или правалинейную грамматику. С помощью такой программы можно, например, по регулярному выражению построить эквивалентный ему конечный автомат. 2.3.34. Постройте программу, которая воспринимает в качестве входа описание конечного авталгата и выдает на выходе эквивалентный ему приведенный автомат. 2.3.35. Напишите программу, которая будет моделировать недетерминнрованный конечный автомат. 2.3.36. Постройте программу, определяющую, эквивалентны ли два описания регулярного множества (тнп описаний надо взять такой, чтобы проблема эквивалентности была разрешима).
Замечания па литературе Миннмиззпин конечного автомата впервые изучалась Хзфмеиом [1954) н Муром[19561. Свойства ззмкнутостн регулярных множеств н результаты о рззрешимоств взяты из статьи [Рзбип и Скотт, !959). Упражнения содержат лишь некоторые нз многггх результзтов, квсзгощихск конечных ззтомзтов и регулнрных выражений. Алгоритм 2.6 взнт из 162 2еь КОНТЕКСТНО-СВОВОДНЫВ ЯЗЫКИ зботы Хопкрофтз [1971). Результат из упр. 2.3.22 получен Косзрзю [1970). роизводнзк регулярного вырзженин была определена Бжозовскнлг [19641.
Существует много методов мипимиззпни не полностью определенного конечного автомата [упр. 2.3,27). Эту проблему рзссмзтрнвзли С. Гинзбург [!962) н Прзтер [19691, Частичное решение проблемы, сформулнровзнпой в упр. 2.3.32, дзио з работе Кзмеды и Вайнера [19681. Достаточно полно теории конечных автоматов излагается в книгах Гиллз [!962), С. ГинзбУРга [!9621, ХаРРисона [19651, Л1ллнского 11967), БУтз [ 1967], А.
Гинзбурга [!968), Арбибз [!969) н Сзломзз 11969з]'). Толгпсон 1!968] опггсывзет технику прогрзммвровзннн, полезиуго при построении распознавателя по регулярному вырзжеиню. 2.4. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Из четырех классов грамматик иерархии Хамского класс контекстно-свободных грамматик наиболее важен с точки зрения приложений к языкам программирования и компиляции. С помощью КС-гран!мат!гни можно определить большую часть синтаксической структуры языка программирования. 1(роме того, она служит основой различных схем задания переводов. В ходе самого процесса компиляции синтаксическую структуру, прндаваемую входной паограмме КС-грамлгатикой, можно использовать при построении перевода этой программы. Синтаксическую структуру входной цепочки можно определить по последовательности правил, примененных прн выводе этой цепочки.
Таким образом, на часть компилятора, называемую синтаксичесним анализатором, можно смотреть как на устройство, которое пытается выяснить, существует лн в некоторой фиксированной ](С-грамлгатике вывод входной цепочки. Однако это нетривиальная задача — по данной КС-грамматике О и входной цепочке иг выяснить, принадлежит ли го языку 7.
(О), и если да, то найти вывод цепочки иг в грамматике О. В гл. 4 — 7 зта проблема будет исследована подробно. В данном разделе мы построим гРундзмент, иа котором будет основано наше изучение синтаксического анализа. В частности, определим деревья выводов и изучим преобразования, которым можно подвергнуть КС-гралгматики, чтобы привести их к более удобному виду. 2 4 4 ° Деревья выводов В грамматике может быть несколько выводов, эквивалентных в том смысле, что во всех них применяются одни и те же правила в одних и тех же местах, по в различном порядке. Опрев" ".«РУ*Р "Р ) См. также книги Глушкова [1962] н Трзхтенбротз и Бзрздини [1970], Прим. перев.
6' ГЛ. 2. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ 2.С КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Рнс. 2тц Пример сечения; Рнс. 2.8. Деревья выводов. 165 1В4 произвольного вида сложно (см. упражнения к равд. 2.2), но в случае КС-грамматик можно ввести удобное графическое представление класса эквивалентных выводов, называемое деревом вывода.
Дерево вывода в КС-грамматике 6 =(Н, Е, Р, 5) — это помеченное упорядоченное дерево, каждая вершина которого помечена символом из множества Ы О 5 (1 (е). Если внутренняя вершина помечена символом А, а ее пряъгые потомки — силсволами Х„Х„..., Х„, то А — е Х,Х, ... Մ— правило этой грамматики.
Определение. Помеченное упорядоченное дерево В называется деревом нечеода (или деревом разбора) в КС-грамлсатике 6(А) = =(рч, 5, Р, А), если выполнены следующие условия: (1) Корень дерева В помечен А, (2) Если В„..., Ве — поддеревья, над которыми доминируют прямые потомки корня дерева, и корень дерева В, помечен Хн то А — Х, ... Хе — правило из множества Р.
В; должно быть деревом вывода в грамматике 6 (Х;) = (Ы, Х, Р, Х;), если Х,— нетерминал, и О, состоит из единственной вершины, помеченной Хн если Х,— терминал. (3) Если корень дерева имеет единственного гсотомка, помеченного е, то этот потомок образует дерево, состоящее нз единственной вершины, и А — с — правило из множества Р. Пример 2А9. На рис. 2.8 изображены деревья выводов в грамвсатике 6 =- 6 (5) с правилами 5 а5Ь5 ) Ь5а5 ) е. ( ) Заметим, что существует естественное упорядочение вершин упорядоченного дерева, при котором прямые потомки вершины , упорядочиваются „слева направо", как определено в равд. 0.8А. Расширим это упорядочение следующим образом, Допустим, что п — веРшина и и„..., лв — ее пРЯмые потомки. Тогда если 1< 1', то вершина и; и все ее потомки считаются расположенными левее вершины л и всех ее потомков.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
