Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 52
Текст из файла (страница 52)
Нетрудно показать, что конечные преобразования (прямые и обратные) сохраняют свойства регулярности и контекстной свобод- ности. Иными словами, если 1.— регулярное множество (КС-язык) и М вЂ”.конечный преобразователь, то М(~) и М '(6) — регулярные множества (КС-языки). Доказательства этих фактов оставляем в качестве упражнений. С их помощью можно доказать, что некоторые языки не регулярны (или не контекстно-свободны).
Пример 3.10. Язык, порождаемый грамматикой 6 с правилами Я 1131иецо')а не регулярен. Обозначим 6 =. 7„(47) () (П)' а (1)1еп а)' = ((11)" а (1(теп а) л ( л Ъ О) Рассмотрим конечный преобразователь М= Я Х 6 6 да г), где (1) 14 = (де ! О: 1 ~ 6), (2) Х=(а,1,1,1,6, "е", а), (3) Л=(О,1), (4) 6 определяется диаграммой, изображенной на рис.
3.5, (6) У=(у,). 9 А, Ало, Дас Ульиаи, е. ! ла7 Гл. э. Теория переВОЯА Здесь "е«означает букву е в отличие от пустой цепочки. Таким образом, М (~,) = (ОЯ! А (й = 0), а это, как мы знаем, не регулярное множество. Так как класс регулярных мно замки нут относительно пересечения и конечных преобразований, то Е(6) не регулярное множество. () мы ФОРМ РМАЛИЗМЫ, ИСПОЛЪЗМЕМЫЕ ДЛЯ ОПРЕДЕЛЕНИЯ ПЕРЕВОДА назовем множество ) ) «(, е е у) для некоторого у Е 1з«)) Аналогично расширенным МП-автоматам можно определить расширенны ные МП-преобразователи (у них верх магазина расположен справа).
1)ример 3.11. Рассмотрим МП-преобразователь Р=.((д), (а, +, я), (+,, Е), (а, +, я), б,о„Е, (а)) Рис. З.з. Диаграмма преоврвзеввтеля М, 3.1.4. Преобразоаатапи с магазиииои памятью Т еперь введем другой важный класс трансляторов, называемых преобразователями с магазинной памятью. Эти преобразователи получаются из автоматов с магазинной памятью, если их снабдить выходом и разрешить на каждом такте выдавать выходную цепочку конечной длины, Определение.
Преобразова»лелем с магазинной памятью (МП- преобразователем) называется восьмерка Р = ((), Х, Г, Л, 6, д«, Е„Р), где все символы имеют тот же смысл, что в определении МП-автомата, за исключением того, что Л вЂ” конечный выходной алфавит, а 6 — отображение множества (сх(Х(1(е)) хГ в множество конечных подмножеств множества с» х Г'х Л'.
Определим конфигурацию преобразователя Р как четверку (д, х, и, у), где а, х и а те же, что у МП-автомата, а у — выходная цепочка, выданная вплоть до настоящего момента. Если 6(а, а, Е) содержит (», се, г), то будем писать (а, ах, Еу, у))— (», х, сеу, уг) для любых хЕХ«, убГ' и убЛ«. Цепочку у назовем выходом для х, если (д„х, Е„е)! — '(й, е, х, у) для'некоторых дар и яЕГ". Переводом (или преобразованием), о»еределяемым МП-преобразователем Р (обозначается т (Р)), назовем множество ((х, у))(ае, х, Я„е)) —" (а, е, се, у) для некоторых АТЕЕ и асГ") Аналогично МП-автоматам можно говорить о преобразовании входа х в выход у опустошением магазина, если (ае, х, Яе, е), '-* (д, е, е, у) для некоторого д б 9.
Переводом, определяемым преобразователем Р опустошением магазина (обозначается т, (Р)), 25$ где 6 определяется равенствами 6 (у, а, Е) = ((д, е, а)) 6(й, + Е) = ((Ч, ЕЕ+, е)) 6 (и, Ф, Е) = ((а, ЕЕ я, е)) 6(д е (-)=((а е +)) 6 (Ч, е, и) — ((д, е, Ф)) Для входа +ваап МП-преобразователь Р сделает такую последовательность тактов; (Ч, + я ааа, Е, е)) — (а,» ааа, ЕЕ -(-, е) ) — (д,ааа,ЕЕ Е+,е) ! — (д,аа,Е Е+,а) ) — (д, а,яЕ+, аа) ) — (д,а,Е+,аая) ) — (д, е, +, аа Ф а) ) — (у,е,е,ааяа+) Таким образом, Р переводит цепочку + я ааа в цепочку аав а +, опустошая магазин. Можно проверить, что т, (Р) =- ((х, у) ~ х префиксное польское арифметическое выражение в алфавите (-», я, а) и у — соответствующая постфиксная польская запись) П Определение. Если Р . Я, Х, Г, Л, 6, а„Е„ Р) — МП-преобразо- Ватель, то МП-автомат ((), Х, Г, 6', д„ Я„ Р), где 6'(а, а, Я) со- держит (», у) тогда и только тогда, когда 6(а, а, Я) содержит (», 7, у) для некоторого у, назовем МП-автоматом, лежа»цим в основе преобразователя Р (или просто основой Р).
Будем говорить, что МП-преобразователь Р— (ег, Х, Г, Л, 6, л«, Р) детерминированный (ДМП-преобразователь), если (1) для всех йЕс», аЕХО (е) и Е~Г множество 6(д, а, 7) ~~держит не более одного элемента, 9« 259 ,. ~ьыиия пкввводд (ь)'е'2)~~ то 6(ч а о)=И для всех аатх) Очевидно, что если Š— область определения отношения т(Р) для некоторого МП-преобразователя Р, то Е=Е(Р'), где Р' МП-автомат, лежащий в основе Р. Многие из результатов, доказанных в равд. 2.5 для МПУавто матов, естественным образом распространяются на МП-п е б зователи. В частности, аналогично леммам 2.22 и 2.23 можно доказать следующую лемму. Лемма 3.!.
Т=т(Р,) для МП-преобразователя Р; тогда и только тогда, когда Т=т,(Р,) для подходящего МП-преобразователя Р,. Доказательство. Упражнение. () МП-преобразователь, в частности детерминированный МП- преобразователь, служит полезной моделью для фазы синтаксического анализа процесса компиляции.Мы используем его в этой роли в равд. 3.4. Докажем теперь, что перевод является простым СУ-пере д м огда н только тогда, когда он определяется МП-преобрао т возователем. Таким образом, МП-преобразователи характеризуют класс простых СУ-переводов так же, как МП-автоматы характеризуют класс КС-языков. Лемма 3.2. Пусто Т=-(Рх, Х, Л, )с, Я вЂ” простая СУ-схема. Существует такой МП-преобразователь Р, что т, (Р)=т(Т). До к а з а тел ьст в о.
Пусть 6г — входная грамматика схемы Т. Построим Р так, чтобы он распознавал Е(6г) сверху вниз, как и лемме 2.24. П ри моделировании правила А — а, р схемы Т преобразователь Р заменит в магазине верхний символ А цепочкой а, в которую вставлены выходные символы из цепочки 3, т. е. если а=-х,А,х, ... А„хл и р=у,А,у, ... Азу„, то символ А будет заменен цепочкой х,у,А,х,у, ...
Азх„у„. Надо уметь, однако, отличать символы алфавита Х от сймволов алфавита Л, чтобы можно было правильно разбивать цепочки хгу; на две части. Если Х н Л не пересекаются, то никакой проблемы нет. В общем случае определим новый алфавит Л', соответствующий Л, но заведомо не пересекающийся с Х. Будем считать, что Л' состоит ')ъ . Р ' ' у з~ что лежащий н основе Л)П-звтомзт дстерминнровзнный.
Последнее может быть и тогда, когда ()) не выполняется нз-зз того, что МП-преобразователь может выдать двз разных выходи нз двух шагах, которые во всем остальном совпздз~от. Ззметим также, ~то нз условия (2) следует, что если б(ч, а, Я)э и для некоторого оЕл, зо б 0), с, 2) = н. вцФОР формялизмы, использквмыв для опввдвлвния пнпкводд ых символов а', соответствующих аЕЛ. Тогда Л'ПХ= йу нз новых и естестве ственно определить такой гомоморфнзм и, что )з (а) =а' для каждого аЕЛ. Пусть Р =- ((о), Х, )х) )) з () Л', Л, 6, а, В, 8), где 6 определяется так: (1) если А — х,В,х,...
Вьх„, узВздг ... В,у,— правило из Р ля )з)0, то 6(с), е, А) содержит (о, х,у,'В,х,у, '... Вьхьу;, е), „де у) =п(уг) для 0~()я=)з; (2) 6 (д, а, а) — ((д, е, е)) для всех а Е л; (3) 6(д, е, а') =-((д, е, а)) для всех аЕ Л. Индукцией по т и и можно показать, что для А Е)х) н т, я~~1 справедливо следующее утверждение: (3.1.3) (А, А)=р (х, у) для некоторого т тогда и только тогда, когда (о, х, А, е) « —" (д, е, е, у) для некоторого и.
Необходимость. Базис, т=1, выполняется тривиально, так как правило А — х, у должно принадлежать Р. Тогда (д, х, А, е) « — (д, х, хй (у), е) ,'— * (д, е, й (у), е) « — ' (д, е, е, у). Для доказательства шага индукции допустим, что (3,1.3) справедливо для значений, меньших т, и пусть (А, А) =р (х,В,х, ... Вьхь, д„В„д,, Вьдь)=~ '(х, у). Так как в простой СУ-схеме порядок вхождений нетермнналов не меняется, можно писать х=-х,и,х,...и,хь и у=два,д,...оьуь, причем (Во Вз)=у"г (ио ог) для 1()(й, где тз <т для каждого 1.
Таким образом, по предположению индукции (д, ио Во е) « — '(у, е, е, о;). Объединяя эти последовательности тактов, получаем (д,х, А,е) « — (д, х, х,й(у,) В, ... Вьхь)г (уь), е) « — *(з), и,х, ... и,х,, )) (у,) В, ... Вьхь )з(у„), е) (и и хг, иьхь В, Вьхзй(уз) у ) « — *(4, х, и,х,, х,й(у,) ... Взхзй(у„), дзот) ) — '..., *(д,е,е,у) Достаточность. Опять базис, и= — 1, тривиален, так как правило А — е, е должно принадлежать )х'. Для доказательства шага индукции допустим, что первый такт преобразователя Р имеет вид (ь), х, А, е) ) — (ь), х, хзй (у,) Взхз)ь (у,) ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
