Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 53
Текст из файла (страница 53)
Вьхьй (уз), е) х;с2:е, у,ЕЛ", й(у;)ЕЛ'". Тогда цепочка х, должна быть "Рефиксом цепочки х и на следующих тактах работы преобразователя Р цепочка х, будет прочитана на входе и устранена из магазина, а затем на выходе будет выдана цепочка у,. Пусть оставшаяся часть входной цепочки, Тогда цепочка х' должна и"еть префикс и„который приводит к тому, что магазинные 261. Гл. 9.
ТеОРия переВОдА символы, расположенные на уровне символа В, н выше, устра няются из мзгазина. Прн этом к моменту, когда длина магазина становится меньше (В, ... В,хьй(уь) ~, на выходе выдается цепочка о,. Тогдз (Ч, и„В„е)~ — '(Ч, е, е, О,), и соответствующая последовательность состоит менее чем из и тактов. По предпо. ложению индукции (В„В,)=;>'(и„о1). Рассуждая таким образом, мы приходим к тому, что х можно записать в виде х„и,х, ... и,х„, а у — в виде у,о,у, ... О«уь, причем (Во ВТ) ~'(и;, о;) для 1 «: 1'(й.
Так как правило А — х„В,х, ... Вьхь, у,В,у, ... Ввуг, очевидно, принадлежит ~>, то А, А)О*(х У). качестве частного случая утверждения (3.1.3) имеем (5, 5) =>* (х, у) тогда и только тогда, когда (Ч, х, 5, е) ', †* (Ч, е, е, у), так что т,(Р) = т(Т). Пример 3.12, От простой СУ-схемы с правилами Š— +ЕЕ, ЕЕ+ Š— «ЕЕ, ЕЕ« Š— а, а можно перейти к эквивалентному МП-преобразователю Р=((Ч), (а, +,«), (Е,а, +,«,а.', +',«'),(а, +,«),6,Ч,Е,8) где 6 определяется равенствами (1) 6 (Ч, е, Е) = ((Ч, +ЕЕ +', е), (Ч, «ЕЕ «', е), (Ч, аа', е)), (2) 6(ч, Ь, Ь) =((ч, е, е)) длн всех Ь~(а, +, «), (3) 6(Ч, е, Ь')=((Ч, е, Ь)) для всех ЬЕ(а, +, Это недетермннированпый МП-преобразователь. Эквивалент- ный ему детерминированный МП-преобразователь приведен в при- мере 3.11.
Г) Лемма З.З. Пусть Р = (1г, г, Г, Л, 6, Ч„о„, Р) — МГ1-преобра- эоватпель. Суи(ествует т хая простая СУ-схема, что т (Т) == =-- т, (Р). Доказательство. Построение схемы аналогично построе- нию КС-грамматики по МП-автомату, Пусть Т=(1«, л, Л, ~, 5), где (1) «ч= ([рАч]( р, ч еД, А еГ) («(5), (2) )с определяется так; (а) если 6(р, а, А) содержит (г, Х, Х, ... ХА, у), то при й > О в В входят правила [рАч,] а[гх,ч,][ч,х,ч,]... [чь,х,ч«1, у[гХТЧ11[ЧТХ9Ч91 ...
[Чь 1ХАЧА] 262 ФОРМАЛИЗМЫ. Ис ПОЛЬЗ1'ЕМЫЕ ДЛЯ ОПРЕДЕЛЕНИЯ ПЕРЕВОДА всех последовательностей Ч„ Ч, . ЧА сОСтОЯНИИ О в р входит одно прав~~о [рАг] — а у' 2' (б) для каж каждо1О Ч ~ («В Я Входит пушило 5 [ЧО «Ч]~ (Ч9ЛРЧ]. ясно, что Т вЂ” „остая СУ-схема. Снова индукцией по т н по п легко доказать, что (З.«А) («Чь [ А ', [ А 1)=Р'"(х у) тогда и только тогда, когда (р, х, А, е),'—" (Ч, е, е, у) для всех р, ЧЕ 9 и А ~ Г. доказательство утверждения (3.1 А) оставляем в качестве упражТаким образом, (5, 5) =О ([Ч,Е,Ч], [Ч,З,Ч])-.=.>+ (х, у) тогда и только тогда, когда (Ч„ х,о„ е)« †« (Ч, е, е, у). Следовательно, Пример 3.13. С помощью конструкции предыдущей леммы н ем - - Т.= «х ' « МП-преобразователю нз примера 3.11 эквивалентную ему простую СУ-схему.
Получим СУ-схему ' = (, (а, -,-, «), (а,+,«), В, 5), где «т'=-([чхч]~х ~(+, «-, е)) 0(5), а тг состоит нз правил 5- [чеч], [чеч] [чЕч] — а, а [чеч]- + [чеч] [чеч] [ч+ ч] [чеч] [чеч] [ч+ ч] [чеч] —:[чеч][чеч][ч«ч] [чеч1 [чеч][ч«ч] [ч+ч]-е, + [ч«ч] е, « Заметим, что преобразования, аналогичные тем, которые применялись для устранения из КС-грамматики цепных правил и е-правил, позволяют упростить эту схему н получить правила 5 — а,а 5 — -1-55, 55+ 5 — «55, 55«П Теорема 3.2. Т вЂ” простой СУ-перевод тогда и только тогда, иногда Т =т(Р) для. некоторого МП-преобразователя Р.
Йока з а тел ьст в о. Теорема непосредственно следует из тамм З« ЗЗ и гл. 9 мы введем машины, называемые процессорами с магазинной памятью, способные определять любые синтаксически «'"Равляемыс переводы. 2аз ГЛ. 3. ТЕОРИЯ ПЕРЕВОДА УПРАЖНЕНИЯ 3.1.!. О ... Операция ) с одним аргументом называется унарной, вается с двумя — бинарной, и вообще операция с и аргумента я п-арной (нли ~-местной), Например, операция — может быть унарной (как в — а) и бинарной (как в а — Ь).
Число а г . ментов опе алии з рапии иногда называют ее арностью (илй местностью) Пусть 9 — мпожество операций с заданными арностями и Х— множество операндов. Постройте КС-грамматики 6 и б и, и „порожд щ прсфиксные и постфиксные польские записи выражений, ства л. составленных из операций множества О н оп .. ерандов множе- «3.!.2.
«П е р дшествование" (приоритет) инфиксных операций опе апия 8 „п е определяет порядок, в котором они выполняются. Е ли б с инарная операция , „предшествует" операции О„ то аО 6 О с вычисляетс ,.(,с). Например, и предшествует -)-, и потому а+б:с означает а+(Ьи с), а пе (а+6) ис. Рассмотрим булевы операции ) (не), /~ (и), '/ (нли), — (нмпликация) и = (эквивалепция). Эти операции перечислены в том порядке, в каком они предшествуют друг другу. Операция ! — упарная, а остальные— бинарные. Например, в выражении )(а '/ Ь) †. — ! а Л ! Ь подразумевается такая расстановка скобок: ( ! (а~/6))==(( ) а) Л( ) 6)).
Постройте КС-грамматику, порожда|ощую все правильные булез р жения, составленные из этих операций и операндов а, Ь, с ы и не содержащие избыточных скобок, *3.1.3. ... Постройте простую СУ-схему, отображающую инфиксные булевы выражения в префиксные. *3.1.4. В А, Алголе выражения строятся с помощью операций, перечисленных ниже в порядке их приоритетов. Если операций с одного приоритета более одной, то они выполняются в по ядке лева направо.
Например, а — Ь+с означает (а — 6)+с. Р (!) ! (2) х / †: (3) +— (4) < < =- ~ ) ~ (б) ) (б) Л (7) ч' (8) -ь (9) Постройте простую СУ-схему, которая отображает иыфиксные выражения, содержащие эти операции, в нх постфиксные поль- ские записи, з) Здесь и в дальиейшеи мы будем называть оп Чии (например, арифметические), тзк н зинки опзрия перациями вызовет недоразумений. †Пр. зд. ° р опариииа. Надеемся, что это не лба УПРАЖНЕНИЯ следузоп!ую СУ-схемУ, в кОтОРО ! ' ' > о ачает один нетерминал: <е )со ьч!1Ь (чаг) +-(ехр)"' 10(ехр) ) Ьеа!п 1оса1 1; 1-: — О; 1ог <чаг> ч-<ехр><з1 1о <ехр>он йо 1 1- <ехр>а'! гезп!11 епд <чаг> <Ы> <'й> < р> <б> <й> <Ы>- а<Ы>, а<Ы> <Ы> Ь<Ы>, Ь<Ы> <)й> а, а <Ы> б б Постройте переводы предложений а) зшп пази!1Ьૠ— 6 1обб б) мпп апгп а Ав ! 1Ь аа и — ааа 1о аааа еПЬ 6 ч- 66 1о ббб «3.1.6.
Рассмотрим такую схему трансляции; <з(а1егпеп1> — Ьзг <чаг> ~ — (ехр)ол 1о <ехр)п' йо <з1а1ешеп1>, Ьей!и <чаг> ч- <ехр)"', уе !1<чаг) и (ехр>"'1Ьеп Ьей!и <з(а1ешеп1>; <чаг> ч- <чаг>+1 до1о 1, епд епд (чаг) — (Ы), (Ы) <ехр>-- <Ы>, <Ы> <з1а1ешеп1> — <чаг> ~- (ехр>, (чаг) и — <ехр> <Ы> — а<!й), а<Ы) (Ы) — Ь <!й>, б (Ы) <Ы> а,а <Ы> — Ь, Ь Почему эта схема не является СУ-схемой? Каким должен быть выход для входного предложения !ог а «- Ь 1о аа до баа и — Ьба ') Обратите внимание, что эта запязая отделяет две части правила.
Гл. 3. ТРОРия пеРЕИОДА УПРАЖНЕНИЯ Указание: Примените алгоритм 3.1, дублируя в выходном дереве вершины, помеченные <айаг>. Упражнения 3.1.5 и 3.1.6 дают примеры того, как с помощью синтаксических макросов можно расширять язык. В приложении П1 подробно показано, как включить в язык такой механизм расширения. 3.1.7. Докажите, что область определения и множество значений любого СУ-перевода являются КС-языками.
3.1.8. Пусть !.с=Х' — КС-язык и 2г> ~Х* — регулярное множество. Постройте такую СУ-схему Т, что т(Т) =((х, у) ) если хЕ!.— )7, то у=-О, если х Е !. В )7, то у = Ц "'3.1.9. Постройте такую СУ-схему Т, что т(Т) — ((х, у) (хЕ (а, Ь)' и у= с', где г'=) ~„(х) — 4~ь(х)) и 4Ь (х) — число символов й в цепочке х) "3.1.10. Покажите, что если Š†регулярн множество и М вЂ конечн преобразователь, то М (!.) и М г(!.) †регулярные множества. *3.1.11.
Покажите, что если !.— КС-язык и М вЂ” конечный преобразователь, то М (!.) и М '(!) — КС-языки. ь3.1.12. Пусть )7 — регулярное множество. Постройте такой конечный преобразователь М, что М (! ) = !.7)7 для любого языка !.. Учитывая упр. 3.1.10 и 3.1.11, заключаем отсюда, что классы регулярных множеств и КС-языков замкнуты относительно операции 7)7 (деление справа на регулярное множество).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
