Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 46
Текст из файла (страница 46)
Рассмотримследующий класс программ Алгола: Е= (бей!гг !Н1еиег в; в': ---1; епг!)вЕ(с, !)') Пусть Ел — множество всех правильных программ Алгола н )лг — регулярное множество, Обозначаемое регулярным выражением Ьед!и 1Н1еиег(с+))', (с+))': =1' епб 226 Тогда Е =Ел П гг'.
Наконец, пусть Ь вЂ” такой гомоморфизм, что Ь(с) =с, Ь(7) =) н Ь (Х) =е в остальных случаях. Тогда Ь(!.) = (ихс ! в Е (с, !) ). Следовательно, если 7л — КС-язык, то Ь(Ел!) )7) —.тоже КС- язык. Однако мы знаем, что язык Ь (Е„П)т) не контекстно-свободен, н поэтому заключаем, что множество Ел всех правильных программ Алгола не является КС-языком. г) Пример 2.43 показывает, что язык программирования, требующий описания идентификаторов, длина которых может быть произволыго большой, не контекстно-свободен.
Однако в компиляторе идентификаторы обычно обрабатываются лексическим анализатором н свертываются в лексемы прежде, чем достигают синтаксического анализатора, Поэтолгу язык, который должен распозиаваться синтаксгическим анализатором, обычно можно считать контекстно-свободным. В Алголе и многих других языках встречаются и другие явления, характерные для не контекстно-свободных языков, Например, каждая процедура имеет одно и то же число аргументов в каждом месте, где она упоминается. Поэтому можно показать, что подаваемый на вход синтаксического анализатора язык ие контекстно-свободен, о~образин множество программ с тремя вызовами одной и той же процедуры па не контекстно- свободный язык (О"!О"10")гг) О). Обычно, однако, для проверки того, что число аргументов процедуры не противоречит ее определению, использустсн некоторый процесс, нс входящий в собственно синтаксический анализ.
2.6.3. Результаты о разрешимости Мы уже видели, что для КС-грамматик проблема пустоты разрешима. Алгоритм 2.7 получает на входе КС-грамматнку 6 н выясняет, пуст илн нет язык Е(6). Рассмотрим проблему принадлежности для КС-грамматик. Нам надо найти алгоритм, который по данной КС-грамматике 6=(14, Х, Р, 3) н цепочке в~ 2* выясняет, принадлежит ли в языку Е(6).
Получение эффективного алгоритма, решаюгцего эту проблему, внесло бы существенный вклад в содержание гл. 4 — 7. С чисто теоретической точки зрения можно сразу сказать, что проблема принадлежности для КС-грамматик разрешима: с помощью преобразований, указанных в равд. 2.4.2, всегда можно превратить 6 в эквивалентную приведенную КС-грамматику 6', а приведенные КС-грамматики (без учета пустой цепочки) контекстно-зази - анисимы, так что можно применить общий грубый алгоритм, решающий проблему принадлежнортн (см. упр. 2.1.18). Рассмот ил К сожалению грим проблему эквивалентности для КС-грамматик. ению, эта проблема неразрешилга. Мы докажем, что не в" ггг ГЛ, 2 ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ существует алгоритма, который по двум данным КС-грамматикам 6, и 6, мог бы определить, совпадают ли языки Е(6,) и Е(6,).
Нд самом деле будет доказано, что не существует даже алгоритма, который по КС-грамматике О„и праволинейиой грамматике 6, выяснял бы, выполняется ли равенство Е(6,) =Е(6,). Как и для большинства других неразрешимых проблем, мы пакзжем, что если бы проблема эквивалентности для КС-грамматик была разрешима, то была бы разрешима и проблема соответствий Поста. По частному случаю проблемы соответствий мы будем строить два естественно связанных с ним КС-языка.
Определение. Пусть С=(х„у,), ..., (х„, у„) — частный случай проблемы соответствий над алфавитом Х и 1=(1, 2, ..., п), 1()Х=З. Положим Ес=(х! хч ...х; ! 1„!...12!Е„..., 2„Е1. т)» 1) и Мс —— (у, у,...у! 1 2„,... !', / 2„..., („Е 1, т ~» 1). Лемма 2.29.
Пусть С=(х„у,), ..., (х„, у„) — частный случай проблемы соответствий над алфавитом Х, где Х() (1, 2, ..., и)= — (о'. Тогда (1) можно найти растииренные ДМП-автоматы, допускаюи(ие 1.с и Мс (2) Ес() Мс= З тогда и только тогда, когда С не имеет решения. Д о к а'з а т е л ь с т в о. (1) Легка построить расширенный ДМП- автомат (верхняя часть его магазина расположена справа), который все входные символы, принадлежащие Х, переносит в магазин, а когда на входе появляются символы из (1, 2, ..., и), он удаляет из магазина х2, если на входе появилось число !. Если на верху магазина в этот момент не хо то ДМП-автомат Останавливается.
Кроме того, с помощью управляющего устройства с конечнои памятью он проверяет, принадлежит ли входная цепочка множеству 22(1, ..., и)+, и допускает ее, если все символы множества Х удалены из магазина. Таким образом допускается 1.. Аналогично можно найти расширенный ДМП-автомат, допускающий Мс. (2) Если язык ЕСПМ содержит цепочку Ео( ...!„где ЕоЕХ+, то ясно, что и! — решающая последовательность, Если х!,х; = у,,...у; =ю, то Ео! ...!! СЕС()МС (Л Вернемся к проблеме эквивалентности для КС-грамматик.
Нам понадобятся еще два языка, связанные с частным случаем проблемы соответствий. Определение. Пусть С=(х„у,), ..., (х„у„) — частный слу чай проблемы соответствий над алфавитом Х и 1=(1, ..., и), 2л свойстВА контвкстна-свовадных языков пРичем Е () 1= 8, Положим 11с= (и!У~!си(!с ЕЕ! 1~!ь где ~~!~В ! ! 1 Рс — — ЕЕФ Мс. Лемма 2.30. Пусть С вЂ” определенная выше последовательность.
Тогда (1) можно найти расширенные ДМП-автоматы, допускаюи1ие 6 Р, (2) (гс(! Рс= !с! тогда и талы!о тогда, когда С не имеет ре- Д О к а з а т е л ь с т в а, (1) ДМП-автомат, допускающий построить легко. Что касается Р, то в силу леммы 2,29 существует ДМП-автомат, скажем М„допускающий 1.. Найти ДМП- автомат М„допускающий Мс, не намного труднее; он переносит я со входа в магазин символы из 1 и затем сравнивает их с той частью входной цепочки, которая принадлежит Х+. Поэтому можно построить ДМП-автомат М„моделирующий М„потом проверяющий, есть ли .ф, и, наконец, моделирующий М,. (2) Если ио4е!охЕ(1с()Рс, где и, хЕХ+ и о, юЕ1+, то и=хи и О=-Еол, поскольку ио422схе 6 .
с другой стороны, и — решающая последовательность, так как иофшхЕР . Таким образом, С имеет решение. Обратно, если х!...х! =у!...у;, то х;,... Лемма 2.31. Пусть С вЂ” определенная выше последовательность. Тогда (1) можно найти КС-грамматику для языка с(с У Рс, (2) !'!с(1Р =(ХО 1)' тогда и только тогда, когда С не имеет решения.
Доказательство. (1) В силу замкнутости класса детерминированных КС-языков относительно дополнения (теорема 2.23) можно найти ДМП-автоматы для языков 9 и Р . В силу эквивалентности КС-грамматик и МП-автоматов (лемма 2.26) можно найти для этих языков КС-грамматики. В силу замкнутости класса КС-языков относительно обьединения можно найти КС- грамматику для О О Р . (2) Непосредственное следствие леммы 2,30(2) и закона де Моргана. еперь докажем, что проблема, порождают ли две КС-грамтики Один н тот же язык неразрешима Фактически будет олее сильное утверждение.
эта проблема неразрешима, даже соли Одна из грамматик праволинейная. ГЛ. 3. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ 2.В, СВОЙСТВА КОНТЕКСТНО СВОБОДНЫХ ЯЗЫКОВ Теорема 2.23. Ое существует алгоритма, который для КС- грамматики 6, и праволинейной грамматики 6, отвечал бы на вопрос: „Е(6,) — Е(6,)2" Доказательство. Если бы такой алгоритм существовал, то можно было бы следующим образом решать проблему соответствий Поста: (1) По данному частному случаю С построить КС-грамматику б„поРождающУю бсЦРС (по лемме 2.31), и пРаволинейнУю грамматику б„порождающую регулярное множество (Е () 1)', где Х вЂ” алфавит последовательности С, и — ее длина и Е ==(1, ..., и).
Возможно, придется сначала переименовать некоторые символы, но это не повлияет на наличие или отсутствие решения. (2) С помощью гипотетического алгоритма получить ответ на вопрос: „Е(6,) — Е(6,)?" По лемме 2.31(2) это равснство выполняется тогда и только тогда, когда С не имеет решения. Так кзк существуют алгоритмы, преобразующие КС-грамматику в эквивалентный МП-автомат и обратно, то из теоремы 2.28 следует также неразрешимость таких проблем: распознают ли два МП-автомата (или МП-автомат и конечный автомат) один и тот же язык; распознает ли данный МП-автомат множество, обозначаемое данным регулярным выражением, и т. д.
2.6.4. Свойства детерелнннроввнных КС-языков Класс детерминированных КС-языков замкнут лишь относительно малого числа из тех операций, относительно которых замкнут класс всех КС-языков, Мы уже знаем, что класс детерминирова2шых Кс-языков замкнут относительно дополнения. так как Ет=(а2Ьгс~1Е !~))) и Е,=(аМст~б 1~1) — детерминированцые КС-языки, а 1.,()Е,=(аБЬ"с"!и) 1~ не КС-яйык (пример 2.39), то Отсюда вытекают сразу два свойства иезамкнутости: Теорема 2.29. Класс детерминированных КС-языков не замкнут стнссительно пересечения и объединения.
До к а з а т е л ь с т в о. Незамкиутость относительно пересечения непосредственно следует из сказанного перед формулировкой теоремы. Незамкнутость относительного объединения следует из закона де Моргана и замкнутости относительно дополнения. Е) Приведем пример, показывающий, что детерминированные КС-языки образуют собственный подкласс КС-языков. Пример 2.44. Легко показать, что дополнение языка Е— (а"Ь"с" ! и ~ 1) — КС-язык. Цепочка в принадлежит Е тогда 230 и только тогда, когда выполняются одно или несколько-цз сле- дующих условий: (1) ш(а-'Ь'с'", (2) и2 = атЬтсе и ! Ф. !', (3) и2=.а'Ьтсл и 1Ф-Ь.
Множество, удовлетворяющее условию (1), регулярно, каждое из множеств, удовлетворяющих условиям (2) или (3)- КС-язык, в чем легко убедиться, построив распознающие их недетерминированные МП-автоматы. Так как класс КС-языков замкнут относительно объединения, то Š— КС-язык. Но если бы Е был детерминированным КС-языком, то по теореме 2.23 и Е был бы таким же. Но Е даже не КС-язык.
Для детерминированных КС-языков справедливы те же поло. жительные результаты о разрешимости, что и для КС-языков, т. е. по данному ДМП-автомату Р можно определить, пуст лн язык Е(Р), и по данной входной цепочке ш можно легко определить, принадлежит ли в языку Е(Р). Кроме того, по данному детерминированномуМП-автомату Р и регулярному множеству Р можно определить, совпадают ли множества Е(Р) и )', так как Е(Р)=)2 тогда и только тогда, когда (Е (Р) б Р) 0 (Е (Р) () Р) —.= О.
Легко видеть, что язык (Е (Р) б Р) 6 (Е (Р) б Л,') контекстно-свободен. Другие результаты, касающиеся разрешимости, приведены в упражнениях. " 2.6.$. Неодиозивчность Напомним, что КС-грамматика 6 =-(Ь), 2", Р, о) неоднозначна, если существует цепочка и2ЕЕ(6), имеющая два илн более различных деревьев выводов, или, что эквивалентно, если цепочка в имеет два различных левых или правых вывода.
Если ли грамматика цспользуется для определения языка п ограммировапия, желательно, чтобы она была однозначной. В противном случае программист и компилятор могут по-разному понять смысл некоторых программ. Пример 2.45. Самый известный пример неоднозначности в языках п ог рограммирования — это, по-видимому, „кочующее е!зе". Рассмотрим грамматику б с правилами В- НЬ(йеп5е!зео!11Ь1йеп51а Эта граммат р матика'неоднозначна, так как предложение П Ь йеп П Ь 1(теп а е(зе а 2З! . ГЛ. 2.
ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ 2.6, СВОИСТЕД КОНТЕКСТНО. СВОБОДНЫХ ЯЗЫКОВ имеет два дерева вывода, показанные на рис. 2.18. Дерево а предполагает интерпретацию И Ь 112еп (ИЬ 11теп а) е1зеа тогда как дерево б дает И Ь 1)теп (И Ь Нтеп а е1зе а) Г') Нам хотелось бы иметь алгоритм, хоторый по произвольной КС-грамматике выясняет, однозначна ли она, но, к сожалению, такого алгоритма не существует.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
