Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 30
Текст из файла (страница 30)
Покажем теперь, что если язык Е порождается Щй)-грам- матикой без е-правил, то он начнется ЕЕ(й — 1) языком. Теорема 8,7. Если язык !. порождается ЕЕ(й)-грамматикой беэ е-прилил, й»в2, то он пирожджтся Щй — 1)-гра.нматикай, Доказательство. В соответствии с п!агом (3) алгоритна 8.3 для Е можно найти ! 1.(Ь)-грамматику в нормааьной форме Грейбах. Пусть 0=(Х, 2, Р, 5) — такая грамматика. По ней можно построить ЕЕ(Ь вЂ” 1)-грамматику 6, = (Х„Е, Р„5), где (1) Х».—.ХВ([А,а))АЕХ, аЕЕ и А ааЕР для некоторой цепочки и), (2) Р,=.(А а[А, а>(А паб Р) 0 ([А,а) а(А ааЕ Р).
В качестве уира»кнепия предлагаем доказать, что 6, — Щй — 1). грамматика, Заметим, »то приведенное здесь построение сл>жит примером левой факторизации. С) Пример 8Л. Рассмотрим естественную Щй+ 1)-трам»»атнку 6» для языка Е из леммы 8.7: 5 а5А 1аА А Ь»й)Ь)с Построим для Е» Щй)-грамматику 6», добавив новые сим- волы [5, а), [А, Ь) и [А, с). Правила грамматики 6» таковы: В-а[5, а! Л . Ь[Л, Ь))с[А, с) [5, а) 5А)А [Л, Ь)-Ь- д(с [А,с) е В качестве упражнения предлагаем доказать, что 6»вЂ” ЕЕ!й '; 1)-грамматика, а 6» — 1.1.(й)-грамматика.
Теорема 8.8. Для всех й:. 1 клагс Щй — 1)-яэыкое содержится строго внутри класса ЕЕ(й)-лютое. »ы Ь»» л у.»и» г. г гл э тяория детерминированного рхзворх зхмичдния по литярдтгри Доказательство. Ясно, что ЩО)-языки образуют собственное подмногкество множества 11(1)-языков. По лемые 8.7 язык Е„для Ь >! не порождаетсп никакой СЦЙ).грамматсской без е-правил. Следовательно, по теорелсе 8.4 оп не порождается аикакой )-С(Ь вЂ” 1)-грамматикой. Однако, как мы видели, он порождается ) 1,(Ь)-грамматсской (с е-правилами). Г9 зпрджнення 8.1.1. Приведите дополнительные примеры грамматик, являю- щихся (а) СД и левоанализируемыми (детерминированно), ио нс П., (б) правоапализируемыми и левоаналиэируемыми, но не СЯ, (в) Е)(, но не левоаналнзируемыми. 6.1,2. Преобразуйте Щ1)-грамматику Š— ТЕ' Е' + ТЕ')е Т ЕТ' Т' э ГТ'(е Е п((Е) в С1(2)-грамматику без е-правил. 8.1.3, Преобразуйте грамматику из упр 8.1.2 в Щ2)-грам- матику в нормальной форме Грейбах.
8.1.4, Докажите утверждение (1) теоремы 8,3, 8.1,5, Дополните доказательство леммы 8.4, 8.1.6. Дополните доказательство теоремы В 5. 8.1.7. Покажите, что грамматика б„построепввя в доказа- тельстве теоремы 8.7, является С)-(й — 1)-грамматикой. 8,1.8. Покажите, что нзык ивляется Ы1(0)-языком тогда и только тогда, когда он либо пуст, либо состоит нз одного эле- мента.
8.1.9. Покажите, что грамматики 6» и 6„' из примера 8.3 являются Щй + 1). и ! 5(й)-грамматикой соответственно. э6.1,10, До!!аж!!те, что каждая из грамс!этик в теореме 8.2 обладает приписанными ей там свойствами. э8.1.11. Покажите, что язык Е= (л Ь")п) 1) б (и с")л) 1) детерминированный, но не (.1. Указание! Предположите, что Е порождается С1(Ь).грамматикой б в нормальнои форме Грейбах, Покажите, что язык !.(6) должен содержать кепочки, нс входя- сэз и!ие в Е, рассмотрев для этого левовыводимые с!елочки вида пса для с) 1.
8.1.12. Покажите, что язык Е="(и"Ь")1с т(сс) детерминированный, но не СС. Обратите внимание на то, что Ь представ. ляет собой конквтенаиию двух Щ1)-языковс и* и (паЬ" (и: !), *8.1.13. Покажете, что каждый П,(Ь)-язв!к порождаетсн С!(74+1)-грамматикой в нормальной форме Хамского. *"8.1.14. ПУсть 1.= 1., П Е, б... П Е, где Ьс дла каждого 1 ..
с < т является 11-папском. Покажите,, что если язык регулярен, то регулярны все Ег "*8.1.15. Покажите, что если Š— С1-язык, но не регулярный, то 1 — не 1Л.-язык. *8.1.16, Покажите, что множество 1)--языссов не замкнуто относительно объединения, пересечения, дополнения, конкатенации, обращения и е.свободного гомоморфизма. Укпэпяиег См унр. 8.1,11, 8.1.12 н 8.1.15. 8.1.17, Докажите, что ТНа(шб) =-ТНо(а)+ТНо(5), и если ш ю*)), то ТНо(ш) ( ТНо(5).
8.1.18. Лайте алгоритмы вычисления ТНа(а) н ТНп(ш, г). 8.1.19. Покажите, что грамматика б, из алгоритма 8.1 лево- покрывает грамматику б иэ этого же алгоритма. 8.1.20. Покажите, что каждая ЕЕ(й)-грамматика б левопокры. вается некоторой 11(2+1)-грамматикой в нормальной форме Грейбак. 8.1.2!. Покажите, что для ЙЪ 2 ссаждан 1).(Ь)-грамматика без е-правил левопокрывается яекоторой 1С(Ь вЂ” 1)-грамматикой.
"*8.1.22. Пока!ките, что проблема существования для данной СЯ(й).грзмматссксс 6 такогю числа й', что б является 1.1.(Ь'). грамматикой, разрешима. Замечания по литературе Таороыа 8.! прадложоээ Кнутам !19671. Разгэьтюы рэзд. 8.!.2 а 8.!.3 опорные паяззлясь а работе Роэсэхрэапа и Ссэршэ !Щ761, Тэм жа прэводаэыреасэапхээдэх,сфарнухяраваааых з упр 8.!.!4 — 8.1,!б я 8.!.22. Иэрэр. «ях Щй)-ссзыхоз осжаохэ впервые Курхп-г.уопяо !!969). Раогльтэсы а рэзрешзмасгп. сзхэаэхые с теоремой 8.6, садэржэтса з бо. хоо раппах шэсъах. Коровьях и Хоахрофт (!9661 дахээазэ рэзрашпыос.ь проедены экзхзглссшяаста двух простых С!(!1-грхыыэсах.
Мэк-Нотон [!9671 показах, что пробхамэ эхзявээеп хасса разрешима зля схабоассых ераммашмх, прадссэздхюшхх собой грамыатаха, э катарах правые часса всех правил ээхэюаеаы э «ругэыо схабха, пс астрочшошхосх аагдэ эхугрх арэзнл. Пээээхсаыа ат него Паул п дагер 1!968э) похавала, чта раэрсшача проблема сйэ ГЛ.
Э ТСОРИЯ ДЕТЕРМИНИРОВАННОГО РЛЗКОРД ь э ге дммдтнки, погождьющие дкткэминнговдннык языки Ру уРкьо к г лгкюк д ук гр ккьт»к, кь киак кьд этки, чть ьлэквэлекткие грэкмалккк кьрьжкают один к те жг цепочки, а солтэгтстэуюклкь дгэгкьк рагеьрэ совпадают эь веем, кроме кгю». (дье гэаккагккк сгруктурко экэкээтекткы Гьгда в татка тогда, «ьгда оьгтрьгккыг оа ккк скэоьчкне Грьмкдлккн экэавакекткы.) 8.2.
КЛАССЫ ГРАММАТИК, ПОРОЖДАЮЩИЕ ДЕТЕРМИНИРОВАННЫЕ ЯЗЫКИ В настоящем разделе мы увидим, канне классы грамматик порождают в точности детерминированные языки. Среди них— кяассы Е)((1)-грал!матин, (1,!)-ОПК-грамматик, простых ССП. грамматик и обрэтимык грамматик (2,1)-предшествования. Кроме того, если детерминированный язык обладает префиксным свойством, то он порождается Е(((0).
или (1,0)-ОПК-грамматикой. Заметим, что для любога языка можно сделать так, чтобы он обладал префиксным свойствам.' достаточно добавить к каждому слову данного языка концевой маркер. 8.2.1. ДМП-ввтомвты в нормальной форме н канонические граммвтмкн Общая стратегия равд. 8.2 заключается в построении грамматик по ДМП-автоматам, обладающим специальными свойствамв. Эти грамматики или простые их модификации принадлежат упомянутым вып~е классам.
Определим вначале специальные свойства, наличие которых у ДМП-автомата для нас желателыю. Определение. ДМП-автомат Р=(О, Х, Г, 6, ц„, 7ю Р) называется ДМП-агтииотом г нормальной форме, если он обладает следующими свойствами; (1) Р— автомат без циклов. Это означает, что при любой входной цепочке Р делает тольно ограниченное число шагов. (2) Р состоит из единственного состаяпин цю н если (цю ю, Ел],'— '(цг, е, Т), то уу-Еь. Другими словами, когда Р допускает входную цепочку, он находится в эакдючитепьном состоянии цу, а в магазине содержится только начальный символ, (3) О можно представить в виде ч'=О.ВИ' 0'И,О (цу), где гг„гг и Ц,— попарно непересекающиеся множества, называемые множествами состояний чтения, записи и стирания соответственно, н цу не принадлежит ни одному из них.
Состояния обладают такими свойствамн: (а) Если цб О„то для каждого або существует такое состояние р., что 6(ц, о, 2) =(рю Е) для всех 7. Таким образом, если Р находится в состоянии чтения, то следующий такт состоит в чтении входного символа. Кроме того, этот такт никогда не зависит от символа, записанного в верхушке магазина. (б) Если ц Е ()т то 6 (ц, г, Я) =(р, УЕ) для некоторых р и У и для всех 7. В состоянии записи автомат всегда пишет в верхушку магазина новый символ, причем этот такт не зависит от текущего входного символа н от символа, содержавшегося в верхушке магазина.
(в) Если ц 6 О„то для каждого 7Е Г слчцествует такое состояние рг, что 6 (ц, е, 7) =(рг, е), В состоянии стирания автомат всегда убирает из магазина самый верхний символ, не считывая нового входного символа. (г) 6(цу, о, 2) = Я для всех а нз Е О (е) н 2 6 Г. В заключительйом состоянии никакие переходы невозмогкны. (4) Если (ц, Гг, 2) у-ь (р, е, 2), то ттьг. другими словами, последовательность тактов, в результате которой длика цепочки, содержагпейся в магазине, (возможно) увеличивается, а затем вновь становится прежней, не может реализаватьсн при пустой входной цепочке. Последовательность тактов (ц, Го, 2) 1- " (р, е, 2) называется трагерсом, Заметим, что возможность или невозможность траверса для данных ц, р и ю не зависит от символа Е, записанного в верхушке магазина. Короче говоря, в состоянии чтения автомат считывает еле.
дующий входной символ, в состоянии записи пишет новый символ в магазин, а в состоннии стирания исследует верхний магазинный символ и затем стирает его, Входная головка сдвигаетсн только тогда, когда автомат находится в состоянии чтения. Теорема 8.9. Если 6 од Е' — детгрмииироганнмй яякк и гимгог Ь иг принадлежит В, то 644-Е(Р) ддя некоторого ДМП- агтомато Р а нормальной форме. Д а к а з а т е л ь с т в о, Построим последовательность нз шести ДМП-автоматов Р,— Рю получая Р, Г по Р, так, чтобы у Р„, было больше свойств ДМП-автомата в нормальной форме, чем у Рг В результате Р„будет нужным ДМП-автоматам в нормальнои форме. Сначала с помощью леммы 2.28 построим дочитывающий, а значит, н бесцнкловый ДМП-автомат Р„ для «отарого Е --.I.(Р,).
Затем преобразуем Р, в Рю воспользоваюпись конструкциеи из яеммы 2.21 и слитая Р, расширенным ДМП.автоматолл. ДМП- автомат Р, будет дочитывающим н в каждом состоянии либо будет действовать яак в состоянии стирания или записи, либо не будет изменять магазин, но в любом состоянии автомата Р, будет аозмажен сдвиг входной цепочки (т. е. чтение). Далее по теореме 2.23 получим Р, нз Рю Новый автомат будет обладать всеми свойствами автомата Р, и, кроме того, не будет делать е-тактов в заключительном состоянии. !ьз ГЛ. З ТЕОРИЯ ДЕТЕРМИНИРОВАННОГО РАЗБОРА Затем построим по Р, автомат Р, так, чтобы у него были все упомянутые свойства автомата Р„ по чтобы он допускал изык ьщ где 4 не принадлежит алфавиту языка ь'. У автомата Р, будет единственное заключительное состояние дг, и оп будет допускать входную цепочку только тогда, когда в магазине находится лишь начальный символ. Р, имеет два нижних маркера: 2л и 7Р 7, служит начальным символом и за первые два такта Р, запйсывает иад 7, символ 7, и над 7, начальный сим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
