Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 31
Текст из файла (страница 31)
вол автомата Рл. Потом Р, моделирует Р„, Гела Р, допускает входную цепочку, то при входном символе 4 автомат Р, переходит в новое состояние д, и стирает все содержимое магазина вплоть до 7О Затем Р, стирает 2и переходит в состояние дг и останавливается. Для того чтобы сделать Р, автоматом в нормальной форме, осталось (1) отделить операции чтения входной цепочки от операций с магази~!Ом, (2) иснлючить травгрсы для пустой входной цепочки. Чтобы удовлетворить требованию (1), образуем из Р, автомат Р,.
Для каждого состояния д автомата Р„в котором невизможен е-такт, кроме д =до построим новые состояния д, дли всех а нз Х. Из состояния д при входном символе а происходит переход в состояние д„ после чего Р, в состоянии д, при входе г выполняет тот шаг, который автомат Р, выполнял в состоянии д прн входе а.
Наконец, видим, что проблема, верно ли, что (д,е, 7)! — + (Р,е, 2), разрешнлга для всех д и р. Из конструкции автомата Р, вытекает, что разретнимость втой проблемы не зависит от 7. Построение ал!.орнтма, решающего такую задачу, оставляем в качестве упражнения. Отметим, что все построенные ДМП-автоматы, вклю.
чая и Р„не имеют цвклоа Следовательно, для каждого состояния д существует такое единственное состояние д' (возможна, д'=:д), что (д, е,2),'— *(д',е,7), но ии для какого д" неверио, что (д', е, 2) т — (д", е, 7). Последний ДМП-автомат Р, в на~пей последовательности построим нз автомата Р„приписывая со. стоянию д все перехОды, которые можно сделать из д' в таких ситуациях. Р, и будет нужным ДМП-автоматом Р.
Детальное построение, опирающееся на зги интуитивные соображения, оставляем в качестве упражнении. Иаложим теперь метод построения по ДМП-автомату в нор. мальной форме грамматики, которую мы назовем канонической. Этот метод отличается от метода, использованного в лемме 2.26, тем, что алесь мы опираемся на специальные свойства у!К!П- автомата в нормальной форме. Зт.
ГРАММАТИКИ, ПОРОЖДЛЮ1ЦИЕ ЛЕТРРМИНИРОВАННЫЕ ЯЗЫК!! Определение. Пусть М=(О,З Г б, дл 7 (д!)) ДМГ) авто ыат в нормальной форме, )' которого верхушка магазина распо- ложена слева. Канонической грамматикой дл» Р называется грамматика Π— (М, Х, Р, [д, дг!), где (1) Н' — множество таких пар [др! из Ох(), что д — состояние чтения или записи, а р протщвольное состояние. Из нетерми- нала [др! выводятся в точности такие терминальные цепочки ю, что, получая нх на вход, автомат М делает гравере из состоя- ния д в состояние р. другини словами, [др]=.>'ю тогда и только тогда, когда (д, ю, 7) ) — ' (р, е, 2) для всех 2 Р Г. (2) Множество правил Р' строится так: (а) Если б (д, а, 2) == (д', 7), вялючим в Р' правило [дд'] — а Кроме того, длп всех гЕО,О!) включим в Р' правила [гд'] — [гд! о Заметим, что адесь д — состояние чтения.
(б) Если б (д, е, 7) = (з, 77) и б (р, е, У) = (д', е), вклю. шм в Р' правило [дд'] - [Ар! и для всех г бОТ О О вЂ” правила [гд']-[гд][з ] Здесь д †состоян записи, а р †состоян стирания. (3) Множества М и Р образуются в результате исключения из Рр и Р' соответственно бесполезных нетерлгиналов и правил. Правила в Р будут иметь вид (!) [дд'] и (2) [дд'! [Рр']а (3) [дд'] — [рр'! (4) [г)д'! [Рр'][гг'] Назовем правило, имеющее в зюм списке номер (!), правилом шила (, 1 ..г ц.
4. Заметим, что в канонических грамматнках правила обладают такими свойствами: (!) если [дд') ай Р, то д — состояние чтения, (2) если (дд'! [Рр']ай Р, то р' — состояние чтения, (3) если [дд'! — [Рр']ЕР, то д — состояние записи, а р'— состояние стирания, (4) если [дд! -. [Рр] [гг! Е Р, то р' — состояние записи, а г'— состояние стирания.
!ен Гл з теОРия детеРминнРОЕЕННОГО РЕЗЕОРЕ ч.т. гглмматики, погождлющиг. детаоминиговянные языки Полезно также заметить следующее. Пусть д--произвольное состояаие занеси автомата М. В состоянии д автомат М, прежде чем считать с.чедующий входной символ, записывает в магазин только фиксированное ~исло символов. Другими словами, существует такая конечная последовательность состояний д„ ., д, что д,=д, Ь(до с,7)= — (дггм У,Е) Дла 1((<й и всех 7., пРичем д †состоян чтения.
Последовательность не содержит повюряюпгихся элементои, и, возможно, й = 1. Основанием для такого утверждения служит тот факт, что если бы в последовательности были повторяющееся элементы, то автомат М не был бы бесцикловым; если длина последовательности больше ду 6, то последовательность должна содержать повторения. Наюзем эту последовательность состояний пиюущсй лосягдоаатсгюностью для состояния д. Теорема 8.10. Есга 6=()д, 2, Р, 5) — каноническая грамматика, постросняая по ДМП.азтомату о нормичьной форма М вЂ”....
(6, 2, Г, б, д„2„(дг)), ° Е(6) = Е(М) — (е). Доказательство. Покажем, что символ [дд') порождает точно такие входные цепочки, для которых возможен гравере из д в дС Для этого докагкеьг индукпией, что (82,1) [дд')ю" ю для некоторого л н ю~г тогда и только тогда, когда (д, ю, 7) с- (д', е, 7) для некоторого т ) О и любого 2. Достаточность. Базис, т= 1, проверяется тривиально. В этом случае цепочка ю должна быть символом из Е, а в Р должно быть правило [дд'] ю. Для проведения шага индукции предполотким, что (8.2.1) истинно для значений, меньшйх т, н что (д, ю, 2) )- (д', е, Е). Тогда конфигурация, непосредственно предтпествующаи (д, г, 7), должна иметь вид (р, а, 2) нли (Р, г, 1'2).
В первом случае р — состояние чтения и (д, ю, l) '-"-' (Р а 2). Следовательно, (д, ю', Е))- -'(Р, г, 2), если ю'а =ю. Согласно предположению индукции, [др) ю*ю'. По определению грамматики Г правило [дд') [дР)а принадлежит Р, и потому [дд') =Я* ю. Во втором случае нада цепочку ю представить в виде ю,ю, и найти такиЕ состояния г и з, что (д, ю,юм 7) ';" (г, юм 2) 1 — (з, юм УЕ) ,' —" (Р, г, 72) 'г (д', е, 2) где т, ( т, т, с т и последовательностьпереходов (з, юа У7] ) — ° (р, г, ГЕ) никогда ие стирает выделенный символ У. Если гьв т, =О, то г = д и ю, =- сс. Таким образом, правила [дд') [зр) принадлежит Р.
Из вида шагов автомата заключаем, что (з, ю„ У)г — *(Р, г, У) и, значит, [зр).=о*ма Итак, [дд') ~*ю. Если т, > О, то (д, юо 2)) †"' (г, г, 2) и, значит, согласно предпалоисению, [дг)=~"ю,, как и раньше, [зр)=Р'ю„. Грамматика 6 устроена так, что правило [дд ) [дг)[зр] принадлежит Р; следовательно, [дд') =ь'ю.
Вюбхсдимосяю. Эту часть легко доказать индукцией; мы предоставляем то читателю Наша теорема †частн случай утверждения (8.2.1) при д=у„и д -. дг. Стдствие 1. Если Š— детгрмаяирозанный язык, обладаюи(ай префиксами сяойсглоом, и гць'), то 1. порождается канонической граиматокоп. До к а за тел ь от в о. Метод построения дяя такого языка ДМП.автомата в нормальной форме аналогичен методу, описанном) в теореме 8.9.
Следствие 2. Если Е:-2' — дстергюнарозоииый язьж и д ц Е, то Еу нарождается канонической грамматикой. () 3.2.2. Простые ССП-грвммвтмни и детермниираввнные языки Приступим теперь к доказательству того, что каждая каноническая грамматика является простой ССП-грамматикой. Напомним, что простая ССП-грамматиха — это такая грамматияа (пе обязательно обрат~чная) слабого предшсствованин 6 = (К, Е, Р, 5), что если А — а и В а принадлежат Р, то 1(А)61(В)=-(д, где 1(С) — множество нетерминальпых или терминальных сгцюолов, которые могут появиться непосредственно слева от С в правовыводимой цепочке, т.
е. 1(С) = (Х ) ХЕТС или Х'С). Начнем с того, что покажем, что ианоничсская граыматика является грамматикой (не обязательно обратимой) (1, 1)-предптествовання. Лемма 8.8. Кияоначгская грамматика яаляется пригедсняой грамматикой (т. е. яг имеет бесполезных санга.юа, г.праоил и циклов). Доказательство. Метод постросния канонической грамматики исключает бесполезные символы и г-правила. Достзтачно показать, что в ней нет циклов. Цггкл может быть только тогда, ') Заметем, что чсля Ь обладает сро)акснмм сзоастзси е г дш тс Ь= (е) 1бэ гл.
в теооия деткгминнвовлнного вьзьовь ь е гкаммлтики, поеождьющик дгтегминивовьниыя языКи когда есть последовательность правил типа 3, скажем [дЛД- [й)„д)ь,], 1 -) (/, где [д,д,')=[4 йД. Но тогда из правил по. Строения канонической грамматики вьшекает, что пишущая последовательность для состояния дь начинается с до й„..., йг н, значит, содержит пов~ориющиеся элементы. Эго в свою очередь ознлчаст, что соответствующий ДМП-автомат в нормальной форме имеет пикл. Отсюда заключаем, что не самом деле аиклои в граммлтвке нет. Лемма 8.9. Каноническая грамматика яоллетгл (не обязательно обрапшмоо) грамматикой (1, 1)-лредаггство)алия'). доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
