Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 42
Текст из файла (страница 42)
Пусть 6=(Ы, Ез Р, Б) — КС-грамматика. По 6 можно построить такой Расширенный МП-автомат )т, что ~Ж)=~(6) ). Работу автомата )т „разумно" рассматривать как процесс отсечения основ. Доказательство. Пусть Р=-((д, г), Е, М()Е()(6), 6, Ч~ 3, (г)) — расширенный МП-автомат' ), в котором 6 опредеЯрш бр 'ЗЛ 225 2И 2.2~, евка конструкция. ") По нашему соглашению верх его магазине расположен справа.
207 ГЛ. 2. ЭЛПМВНТЫ ТВОРИИ ЯЗЫКов 2,2, АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ (1) 6(гу, а, е)=((гу, аЦ для всех абХ, (На этих тактах входные символы переносятся в магазин.) (2) Если А — я принадлежит Р, то 6(гу, е, я) содержит (гу, А). (3) 6(гу, е, 53) =((г, еЦ. Покажем, что процесс вычисления в автомате ус заключается в построении правовыводимых цепочек грамматики 6, начиная с терминальной цепочки (на входе уг) и кончая цепочкой 5. Иидукцией по и докажем, что (2.5.3) о =Ос яАу.=>згху влечет (гу, ху, $) 1 — е(гу, у, $яА) Базис, и=О, тривиален: Уу не делает ни одного такта.
Предположим, что (2.5.3) верно для всех значений параметра, меньших и. Можно написать яАу~,а()у=>",-гху. Допустим, что цепочка я() состоит только из терминалов. Тогда яр = х и (гу, ху, $)) — *(гу, у, Ея))))-(гу, у, $яА). Если я)) чХ*, то можно писать яр= уВз, где  — самый правый нетерминал. По (2.5,3) из В =р',уВау =р," 'ху следует (гу, ху,5))-е (гу, зу, $)гВ). Кроме того, (гу, «у, ЗуВ) 'г — * (гу, у, 5ТВ2) )в (гу, у, 5яА) — тоже возможная последовательность тактов.
Мы заключаем, что (2.5.3) верно для всех и. Так как (гу, е, $3) 1 — (г, е, е), то Е(6) с:-Е(Ус). Для того чтобы доказать обратное включение Е (УС) ~Е (6) и, следовательно, равенство 1.(6) =1 (Ус), докажем, что (2.5.4) (гу, ху, $)) — "(гу, у, $яА) влечет яАу=реху Базис, и =- О, выполняется автоматически. Для проверки шага индукции предположим, что (2.5.4) верно для всех и<т. Если верхний символ магазина автомата уг иетерминальный, то последний такт был сделан по правилу (2) определения функции 6. Поэтому можно писать (гу, ху, 6)) — м г(гу, у, $я())) — (гу, у, $яА) где А — 6 принадлежит Р, Если цепочка я() содержит нетерминал, то по предположению индукции и()утеху.
Отсюда яАуо я()утеху, что и утверждалось. В качестве частного случая утверждения (2.5.4) получаем, что (гу, и, $)) — е(гу, е, 55) влечет З.=~ьцг. Так как Ус допускает и только тогда, когда (гу, цг, 6)) — "(гу, е, 55)) — (г, е, е), то Отсюда следует, что 1. (ус) ы 1. (6). Таким образом, Е (уу) =-Е (6).г) Заметим, что сразу после свертки правовыводимая цепочка вида яАх представлена в 11 так, что яА находится в магазине, а х занимает непрочитанную часть входной ленты.
После этого уу может продолжать переносить символы цепочки х в магазин до тех пор, пока в его верхней части не образуется основа. Тогда Уу может сделать следующую свертку. Синтаксический анализ этого типа называют »восходящим анализом" (,„анализом снизу вверх") или „анализом сверткой". Пример 2.36. Построим восходящий анализатор ') УУ для грамматики 6,. Пусть Уг — расширенный МП-автомат ((гу, гу, Х, Г, 6, гу, $, (г)), где 6 определяется так: (1) 6(гу, Ь,е) =4(гу, ЬЦ для всех ЬЕ(аг +, «, (,Ц; (2) 6(гу, е, Е+Т) =~(гу, ЕЦ 6(у, е, Т) =((у, ЕЦ 6(гу, е, Т«Р) =((гу, ТЦ 6(гу, е, Р) = (гу, ТЦ 6(гу, е, (Е)) = (гу, РЦ 6(гу, е, а) = (гу, РЦ; (3) 6(гу, е, 6Е) = (г, еЦ. Для входа а+а»а распознаватель ус может сделать следующую последовательность тактов: (гу, а+а«а, $))-(гу, +а«а, Ва) ) — (гу, +а»а, $Р) ) — (гу, + а «а, йТ) ) — (гу, +а«а, $Е) )-(гу, а»а, 5Е+) ) — (гу, «а, $Е+а) (гу, » а, 6Е+ Р) ) — гу, »а, $Е+Т) ) — (гу, а, $Е+Т») ) — (гу, е, 5Е+Т»а) 1 — (гу, е, $Е+Т «Р) ) — (гу, е, $Е +Т) )-(гу, е, 6Е) )-(», е, е) Заметим, что для входа а+а«а распознаватель Ус может сделать много различных последовательностей тактов.
Однако выписанная последовательность — единственная, которая переводит начальную конфигурацию и заключительную. () Покажем теперь, что язык, определяемый МП-автоматом, контекстно-свободен. Лемма 2.26. Пусть Ус — (4), Х, Г, 6, гу„7„Р) — МП-автомат, Можно ггостроить такую КС-ераммат1гку 6, что Е(6) =Е,(Ус). ') Автомат, который строится в етом примере (зтзкжеи в еримерез.З4),— зто епге не анализатор, з только распознаватель, но его легко превратить в анализатор (см. гл. 4 и о).— Прим.
перез. ГЛ. 2. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ Ьб. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ Д о к а з а т е л ь с т в о. Построим 6 так, чтобы левый вывод цепочки ш в грамматике 6 прямо соответствовал последовательности тактов, которую делает 1с при обработке цепочки ш. Нетерминальныс символы будут иметь вид [ОХЕ], где 4, гЕ1Е' и 2~Г. Потом мы покажем, что [д2г]=О и тогда и только тогда, когда (1), и1, 2) 1 — ' (г, е, е). Формально пусть 6 — --(11; Х, Р, 5), где (1) )А( — ([42г]1 су, г ЕЮ, 76Г) 0(3); (2) правила множества Р строятся так: (а) если 6(д, а, Х) содержит (г, Х,...ХА)') (й:=: 1), добавим к Р все правила вида [с)7зк] — а [гХ,в,][в, Х,з,]... [зА,Х„з„] ДЛЯ КажДОй ПОСЛЕДОВатЕЛЬНОСтИ З„вм ..., ЗА СОСТОЯ- ний из 1е, (б) если 6(4, а, 2) содержит (г, е), добавим к Р правило [ОХг] — а, (в) добавим к Р правила 3 [4„7„4] для каждого с) ЕО.
Индукцией по т и и легко доказать, что для любых д, г и6 и Е~Г [дог] ~"ш тогда и талька тогда, когда (4, ш, 2))-'(г, е, е). Доказательство оставляем в качестве упражнения. Из этого утверждения следует, что 5 ср [4,2 д] ср ' со тогда и только тог- да, когда (д„ ш, 2,)) †'(о, е, е) для 1) Е 9. Таким образом, Т.,Д) = й (6).
Г1) Результаты двух последних разделов можно сформулировать в виде следующей теоремы: Теорема 2,21. Утверждения (1) Г.=.1,(6) для КС-грамматики 6, (2) й =-~. (Р,) для МП-автомата Р,, (3) У,=Е,,(Р,,) для МП-автомата Рл, (4) 1.= 6(Р,) для расширенного МП-автомата Р, зквивалентпны. Доказательство. Из (3) следует (!) по лемме 2.26. Из (1) следует (3) по лемме 2.24. Из (4) следует (2) по лемме 2.21, а (4) тривиально следует из (2). Из (2) следует (3) по лемме 2.22, и из (3) следует (2) по лемме 2.23.
П 1) Верхний символ маглзкна й расположен слева, так как кы ке оговарквалк противное. 210 2.5А. Детерминированные МП-автоматы Мы уже видели, что для каждой КС-грамматики 6 можно построить МП-автомат, распознающий Л (6). Однако построенный МП-автомат был иедетерминированным.
В практических приложениях нас больше интересуют детерминированные МП-автоматы, т. е. такие, которые в каждой конфигурации могут сделать не более одного очередного такта. В этом разделе мы займемся детерминированными МП-автоматами и в дальнейшем увидим, что, к сожалению, детерминированные МП-автоматы не так мощны по своей распазнавательной способности, как недетерминированные МП-автоматы. Существуют КС-языки, которые нельзя определить детерминированными МП-автоматами.
Язык, определяемый детерминированным МП-автоматом, называется детерминированным КС-языком. В гл. 5 мы введем подкласс КС-грамматик, называемых ).К(й)-грамматиками, а в гл. 8 покажем, что каждая (,К(й).грамматика порождает детерминированный КС-язык и каждый детерминированный КС-язык определяется 1 К(1)-грамматикой. Определение. МП-автомат Р.=Я, А, Г, 6, д„7,„Р) называется детерминированным (сокращенно ДМП-автоматом), если для каждых дб9 и 7.е Г либо (1) 6(д, а, 2) содержит не более одного элемента для каж- даГО а~к И 6(д, Е, 2) — АО', ЛИбО (2) 6(д, а, 7)=1с1 для всех аЕт и 6(д, е, с) содержит ие более одного элемента.
В силу этих двух ограничений ДМП-автомат в любой конфигурации может выбрать не более одного такта. Это приводит к таму, чта на практике гораздо легче моделировать детерминированный МП-автомат, чем недетерминированный. По этой причине класс детерминированных КС-языков важен для практических приложений. Соглашение. Так как для ДМП-автомата 6 (д, а, 2) содержит не более одного элемента, мы будем писать 6(д, а, 2)=(г, у) вместо 6 (д, а, 7) ==- ((г, у)). Пример 2.37. Построим ДМП-автомат, распознаю1ций язык Т. = (и1си1я ) и1 С (а, Ь) ). Пусть Р = ((14, 4„1),), (а, Ь, с), (л„а, Ь), 6, о„Х, (о,)), где 6 определяется так: 6(д„Х, 1') =(д„Х)') для всех ХЕ(а, Ь) и 1'ч(2, а, Ь) 6(д„с, р')=(д„)') для всех )'Е(а, Ь) 6(д„Х, Х) =(дм е) для всех Х р'-(а, Ь) 6 (дх, е, 7) = (д„е) 211 гл.
г, элементы тнопии языков З.З. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ До тех пор пока Р не увидит маркер с, отмечающий середину, ои запасаег в магазине символы входной цепочки. Когда Р достигает с, он переходит в состояние о, и далее сравнивает оставшуюся часть входной цепочки с содержимым магазина. Доказательство того, что Е(Р) --Л, оставляем в качестве упражнения. г1 Определение детерминированного МП-автомата можно естественным образом' расширить, чтобы включить в него те расширенные МП-автоматы, которые естественно считать детерминированными. Определение. Расширенный МП-автомат Р=(!е, Х, Г, 6, о„ 7„Р) называется детерминированным, если выполнены следующие условия: (1) 4): 6(д, а, у)(1 для всех дЕ !е, аЕХ 0(е) и у ЕГ*; (2) если 6(д, а, сс)Ф8, 6(д, а,(!)~Р) и сече:!), то ни Одна из цепочек сз и !! пе является суффиксом другой '); (3) если 6(о, а, сс)~ 0 и 6(д, е, )))чьо, то ни одна из цепочек а и )) не является суффиксом другой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
