Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 35
Текст из файла (страница 35)
Закончите доказательство теоремы 8.12. *8.2.20. Покажите, что каждая ЕЙ(й)-грамматика прааопокрывается некоторой (1, й)-ОПК грамматикой. Указание: Видонзмените ЕЙ(й)-граыыат11ку, заменив в правых частях правил все терминалы и новыми петерминалами Х, и добавив новые правила вида Х. а. Затем измените нетермппалы грамматики, чтобы запомнить множество допустимых ситуаций для активных префиксов, расположенных справа от них.
**8.2.21. Покажите, что каждая 1 Й(й)-грамматика правопокрывается (.Й(й)-грамматикои, которая является з то же время грамматикой (1,1)-предшествования (не обязательна обратимой). *8.2.22. Покажите, чго грамматика Сь из алгоритма 8.5 право. покрывает граьягатику С из этого алгоритма. Спи!ритме проблемы 8.2.23. Верно ли, что каждая ЕЙ(й)-грамматика покрывается некоторой 1.Й(!)-грамматнкои? 8,2.24.
Верпо ли, что каждан ЕЙ(й)-грамматика покрывае1ся обратимой грамматикой (2,!)-прелшествования? Утвердительнь!й !пмег на этот вопрос означал бы также утвердительный ответ иа вопрос, сформулироваяный в упр. 8.2.23. 8.2.25. Эта проблема уже была поставлена в гл 2, но решение ее пока ие получено, поэтому сформулируем ее еще раз. Ргырешима ли проблема эквизалецтпосю! лля Д?4П-автоматов? Поскольку все конструкции этого раздела эффективно реалнзуются, мы получаем много эквивалентных формулировок этой задачи. Например, можно было бы доказывать, что разрешима проблема эквивалентности для простых ССП-грамиатнк или для обратимых грамматик (2,1)-предшествозания.
Замечания по литературе Теорема 8 1! эаерзые была аькэээьэ Л о «хр 11972). Теэ?еии 8.15 э 8.Щ зерэоиачэльмп появились э рабате Кнута 119551. Теореме 8.18 заэисгзаеэиа 7 Грэ еиг 119791. Упр. 8.2.21 зшто эз работы Грэя и Хэрргсеяэ (19691. 3.3. ТЕОРИЯ ЯЗЫКОВ ПРОСТОГО ПРЕДШЕСТВОВДИИЯ Гйы уже видели, что многие классы грамматик порождают в точности множество детерминированных языков. Однако сущсст. вует несколько важных классов грамматик, не порождающих всех детерминнрованных языков. Один из таких классов образуют ЕЕ-грамматики. В настоящем разделе мы изучим другой такой класс, а именно класс грамматяк простого предшествования.
?Аы покажем, что множество языков простого предшсстаования является собственным подмножеством множества детерминированных нзыков н несравнимо с множеством 1 Е-языков. Ьудет показано также, что множество языков операторного пред- шествования является собственным подмножеством маожестза языков простого предшествоааиия. 8.3.1. Квасе языков простого ярвдшестввввння Как отмечалось в гл. б, каждый КС-язык имеет обратимую грамматику и грамматику предшествоаания. Если грамматика обладает обоими этими свойствал1и, то у нас — грамматика и язык простого предшествования, Интересно изучить порождающую спо. собность грамматик простого предшествования. Онн могут порождать только детерминированные языки, поскольку всякая грамматика простого предшествования имеет детерминированный анализатор. Докажем два основных результата, относящихся к языкам простого предшествовапия.Сначала покажем, что язык Ег=(об" 1 ) в ~1) С (бб"1-) л ~1) пе являетсз языком простого предшествования.
Теорема 8.19. Языки простого предшестеованил образу!от гобопггнниг подмножество мноэ!сгстги дггпгрминироэииимх г!мхкоэ. До кааа тель ства. Ясно, что каждая грамматика простого цредгпсстзования является ЕЙ(!)-грамматикой. Длп того чтобы доказать, что включение собственное, покажем, что не существует гралгматики простого предшествованкя, порождающей детерминнрованный язык 1, Интуитивно причина этого состоит в том, что никакой анализатор простого предшествования для Е, не может содержать счетчнка нулей, встретившихся во входной цепочке, а в то же Время помнить, Встретился еиу в начале входной пеночки сим- 185 ГЛ Б.
ТЕОРИЯ ДЕТСРМИПИРОВАПИОГО РАЗБОРА аол а или Ь. Если анализатор запоминает в магазине первый входной символ, за которым следует строка нулей, то, как только во входной цепочке встретится цепочка единиц, анализатор ие сможет определить, одна нли две единицы соответствуют каждому записанному в ыагвзиие иушо, нв стерев предварительно вес нули, содержащиеся я магазине С дру~ой стороны, если анализатор попытается поместить в всрхуп|ку магазина указание на то, какой символ — и или Ь вЂ” встретился раиыпе, то он должен будет в процессе чзения нулей выполнить последоватетшность сверток, разрушаювгую счетчик нулей, встретившихся во входной депочке. Приведем теперь формальное доказательство, основанное иа этом интуитввцом рассуждвнии.
Предположам, что С = (Ы, Х, Р, 5) — грамматика простопг предп|ествования я 6(0) —.: 6Р Покажем, что этого не может быль, т. е. что всякая грамматика простого прещцествования должна порождать цепочки, не принадлежащее 1, Допустим, что входную цепочку аО'ю, ыб)", надо проанализировать с помощью анализатора простого предшествования, построенного для С алгоритмом 6.12. Так как иО" для любого и является префиксом некоторой цепочки из 6О каждый пуль должен в конце концов оказатьси и магазине. Обозначям череа аг содержимое магазина после переноса ого нуля.
Если а, †.-а для некоторого 1 < Д то цепочки а0'17 и а0717 либо обе допускаются, либо обе отвергаются анализатором, и потону если (щ.(Т то а, чеа . Таким образом, для любой константы с можно найти такую цепочку аг, что )а,) ) г и аг — префикс любой цепочки а при 1 ) 1 (если зго не так, можно построить такую последовательность аг, а,, ... произвольной длины, что (а, ( =-)а, ) для 1 ) 2, и тем самым найти две совпадающие цепочки а). Выберем наименьшее 6 Тогда должна найтись такая кратчайшая цепочка рчлг, что для каждого й а,рг=аю „для некоторого ш ) О. Это следует из того, что поскольку аг не гтираегся, пока ня иходе появляются нули, символы, записываемые анализатором в магазин, ие зависят от ас Поведение анализатора при входной цепочке иО" должно быть пикличным, и он должен либо увеличивать длину цепочки, содержащейся в магазине, либо повторно приходить к ситуации с одной и той же магазинной це.
почкой (последнее, как мы уже доказали, невозможно). Рассмотрим теперь поведение анализатора при входной цепочке вида ЬО"х. Обозначим содержимое магазина после чтения подцепочки ЬОА через у„. Как и раныце, можно доказать, что для некоторой цепочвн у, где 1 выбрано наименьшим, найдется такая кратгайшая Цепочка 6 ~ г, что длв каждого й у 6' =у, РР газ зг тьогия языков пгостого пеедшествовгция для некоторого д ) О. На самом де.че, поскольку у никогда не стирается, должно быть 6 =.6 и д =ш. Другими словами, прас.
той ицдукцисй ио г )О можно показать, что если после чтения ОО' ' магазин содержит а,е„ то после чтения Ы)7 ' он будет содержать ТТР . Изучим поведение анализатора, обрабатывающего входную цепочку аО'+ '! ""'. После чтения иО' ' магазин будет содержать а,РА. Пусть з — наибольшее из чисел, обладаю~них гемсвоиством, что после чтения 1'+"""* в магазине остается аА для некоторой цепочки 6 из (!ч ОХ)Р (т.
е. если после эзого иа входе появляется 1, то олин из символов цепочки а, участвует в свертке). Ясно, что з существует; в противном случае анализазор допустил бы цепочку, це принадлежащую ЬР Аналогично пусть г †наибольш из чисел, таких, что анализатор, начав работать с цепочкой у,йг в магазине и пол)чив на вход !ВА' " ', придет к ситуапии с цепочкой у Р в магазине. Как и раньше, ясно, что г существует.
Таким образам, для любого й входнап цепочка ЬО™А! ""г ' " должна допускаться, поскольку после чтения 607 А в магазине содержится цепочка агйг, а после чтения 1 " " " †цепоч а ь. Цепочки 6 стираются независимо от ~ого, что находится ниже: сгг нли аг, а 1' приводит к доп>ску. Но так как ш~О, то для всех й не может выполняться равенство г А шй- -зтр г =.2 (/шшй), Отсюда заключаем, что 67 не является языком простого пред- шествования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
