Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 44
Текст из файла (страница 44)
Т да нож>го по лемме 6.6 посгроить Р' в смысле равд... Огда и анализирующую мапшну М', распозн, )' ( ). акнц) ю которые нужно внести Опишем ны)юрмальпо> изменения М' .гн пол че пня чодшршгированной анализируюц<е>г аМ ое М машины М. Модифицировгаппая магггиг ° г ° РУ помещая в магазин укн образусг вер линь< в ныхс>дном дереве начинает работу в конфи. затели нв эти вершины. Пал чив на вход цен<очку ы, М Гураинн (НаЧаЛО, > цн (5„ 0)Р,). ЗдЕС ПолУшш,д . ' Р Р, >на>атель на корне.
вую вершину и„ (!) (а) Пусть А В[С;, Е>] у Еу Ед„У<Од> — пРавило длЯ А. М полц.Яет следУющУю послеловаПредположим, чтю выполи те.тьность гактов, реализующ, ' Ов реа. изующдгб вызов пйоцедУРы А по правилу Л В[С:,()[.' (начало, и, ) и,н„(А, г) уу,'— (начале> пг ! <ггн„(В, !) (Л, !) у) (начвлд иги ) иг (С ') у) Затем М выполпягет такуго гуосггедонательность тактов, соответствующуго послсдоватег послсдоватегтьпости тактов, выполнен.
пых ранее машиншй М'. (9.2.!) (начало„п, [ и,и„, (. 4 <) Рлэ') (9.2.2) (9.2.3) ! — *(успех, шгпг ) п„(А ° '! Рнр<У ) (9.2.4) г — (начало„и,и,! и,, ((- г) Рср ) а в <9 2 )> указдтель Рл на лист пл Расположен негюсред<ственно под о с>каем.) При переходе в коифигурациго (9.2.2) М об азукт новую ве'Рпгнну гг„, которая та вится прггмыч поиочком нерп ганы и, и почещает указатель на н нгепосредстнш<ио под Л к над . атем ватель рн ' гг а,азина.
В конфиг) ран><и М помещает В в верхушку чаг СОСГОЯНИН УСПЕХ. (9.2.3) М возврлшасгся к ехо е н жоп иг ацию (гк2,4) М создает пРЯ- тн всех символов сепо шн мых потомков веривины гг„д. " ис ,Е,Р ., и уцо я.дочивает нх слева направо Вершина Пн Стаибаптеа ВЕ)РШ>гггой ДЛН тств дт В). Ооозначим вершину символа, когорый соощетству ) Р через лс. В конфигтрадля лругога из сн мво гов Е и Р О с В ! и па шш (92.4) М зашеинег .
Рнр г ° с, < ', если Е=-С и =, то тель иа ггс. Тащим образом; 22Э Гл Р паРавод и ГанаРАция кодА твв ча в.з с, в конфигурации (9.2.4) вершина лк является корнем поддерева ш (6) Если, с другой стороны, В вырабатывает неудачу в правиле А В[С, 0], то М выполняет такую последовательность тактов: (9.2.1] (начало, и, ) и,иг (Л, 1) Р,эу') (9,2.2) '„- (начало, и,",и,и„(В,))Рв(4 ')РвРА]К) (9,2.6) , ''(иеУДача, и,г и,ит (А, ()РРРгр ) (9 2.6) ) — (иачало, и, ( и„и„(В, (] Роу ) При переходе иа (9.2.5) в (9.2.6) М сначала удал ет из выходного дерева вершину л„и всех ее прямых потоьгков, исионьзУЯ дла запоминаниЯ лв Указатель Рв, записанный под А. Затем для всех символов цепочки у,0у,, в порядке слева направо М образует прямых потомков вершины лд и заменяет в верхушке магазина Лрврк иа г'Ро, гДе Ро — Указатель иа веРшииУ, постРоеннУюДла ().
(2) Если Л а, у — правило а ЕЕ()(г), то М выполняет один нз след)ющнх тактов: (а) (начало, и ] ао, (А, г) рлу] с — (успех, иа ] о, у). На этом шаге для каждого символа цепочки у создается прямой потомок вершины лк (вершина, иа иоторую указывае~ Р„). Если у —.е, то прямым потомком станет одна вершина, помеченная символом е. (б) (начало, и ) о, (А, Пуку) г-(неудача, и' А о', у), где ) и')=- Г и о ие начинается с а. (3) Если А --[, е--правило, то М выполииет такт (26). (4) Если М' прочитывает всю входную цепочиу ш и стирает вге сичволы в ма~ азине, эо переводом пеночки ш будет построенное к этому момепту дерево с корнем л,.
ь] Теорема 9.6. Алгоритм 9.3 определяет модифицированную аналггзггруюи)ую могилку, яоролгдигоигую для вхсдной цепочки ш дгото, крона которого является лергвооом цвлогки ш. В о к а за тел ь от в о Доказательство представляет собой простую индукцию по числу тактов, совершаемых машиной М. вг гинткксичгски РпРАвляьмыг пгтеводы Предположение индукции состоит в том, что если М, начав работу в состоянии начало и имея в верхушке магазина сим.
вол А и указатель Р иа вершину в п цепочку ио справа от входной головки, исчерпывает вхол и, в результате удаляв из магазина А и р, и ааканчивает работу в состоянии успех, то веригина, иа которую указывает Р, будет корнем поддерева с такой кроной у, что А ю"(и ) о, у, з). Пример 9.9. Посмотрим, как аиализируюшаи машина осуществляет перевод, описанный в примере 9.8. Мы примем следуюгцую форму записи (табл. 9.2). За копфигурацннми будет гл. в пвравод и гвикрлния кадя следовать построенное к эгону моменту дерево. Такты, представлиющие опознание согласных, гласных и букв (нстсрминалы С„ !' и 1,), опускаем.
Выхолное дерево после каждой четвертой коифигурапви показано па рис. 9.11. Не вдаваясь в подробности, отмеюпг только, что мегоды, представленные в алгоритме 9.3, применимы и к другим алгоритлтам нисходящего разбора,таням, как алгоритм 4.! и построение перевода в виде ОЯНРОВ-программы. упражнения 9.2.1. Постронге МП-преобразователгь реализующий простую СУ-схеьгу Е Е-(-Т, ЕТ 'А00", Е Т, Т Т Тер, ТР 'МР)"; Т вЂ” Т, Р— Р 1 Р, РР 'ЕХР', Р— Р, Р Р (Е), ŠР— а, 'СОАО ау Преобразователь должеп опираться на БЕЙ(1)-алгоритьт разбора.
Напишите последовательности выходных пепочеи, возникающих при обработке выражений (а) а й а э(а р а), (б) а+а па) а. 9.2.2. Сделайте упр. 9.2. ! для случая М)1-пропессора, использующего ЕЕ(1)-алгоритм разбора. Если понадобится, видоизмените входную грамматику. 9.2,3. Покажите, каким образом МП-преобразователь, работающий как 1.С(1)-анализатор, будет выполнять перевод следующих пепочек в соответствии с простой СУ.схемой; Е ТЕ', ТЕ' Е' +ТЕ', Т 'А00", Е' Е' е, е Т РТ', РТ' Т' нРТ', Р 'МРУ Т' Т' е, е Р (Е), Е Т вЂ” а, 'СОА0ар Рве 9.г! Перевод с «пнг дагни с помощью енвлнэнрующей нвшвнн.
(Здесь с — пустая неповвв, перевод сннвоне 5.) Гл. э. нзгвзо г и Гснсгхпия кОдА упэгжненпя (а) аь(а+а), (б) Ва-1-п)ьа) фа. 9.2.4. Покажите, как МП-процессор будет выпочнять перевод цепочка пЬЬЬаааа в соответствии с СУ схемой 5 аАц"А", Олпь4п'1 А - 85"'5пй !Ело5'"'О А — а, г если разбор проводится с помощью (а) Щ !)-алгоритма, (6) ЕЯ(1).алгоритма. 9.2.5. Покажите, что не существует СУ-схемы для перевода, описанного в примере 9.1, есчи язык порождается гралгматикой Š— а-(-Е(аь Е)а.
9.2.6. Опишите формалыю построение МП-преойразоиателя М из теоремы 9.1. *9.2.7. Докажите, что каждый ДМП-преобразователь определяю постфнксный простой синтаксически управляемый перевод языка, порождаемого СЯ(1)-грамматикой, Указагшгг Покажите, что каждый ДМП-преойразователь можно преобразовать к нормальной форме, аналогиюгой той, которая была определена в разд. 8.2.1 *9.2.8. Покажите, что существугот такие переводы Т.—. =((хт;,у)), по Т можно определить ДМП-преобразователем, ао ((х, у) ((хй, у) б Т) нельзя определить никаквм ДМ!1 преобразователем.
Сопоставые этот результат с упр. 2.6.20(6) 9.2.9. Проведи ге формальное показательство теоремы 9.3. 9.2,10. Докажите теорему 9.4. 9.2.11. Расширьте СУ-схему из примера 9.7 так, чтобы вклю. чить в нее правила (3) — (5) из определения перевода на „пиг латин . 9,2.12. Можно ли заменить СУ-схему из примера 9.7 простой СУ схемой, если принять, гго в английском языке нет слов, начинающихся более чем с четырех согласныху Изменится ли число правил СУ схемыу 9.2.13.
Покажите, как аналиаирукипая мащпиа с указателями будет выполнять перевод пеночки аЬЬ согласно ОЯНРОВ про- грамме с выходом 5-А(в,с(, Овл, !!с Л а, О В 5(с, А], ОС5, )л С Ь, ! ""9.2.14. Нзпипги~е такую ОЯИРОВ программу с выходом, что г(Р) - ((х, у) !» пеночка, содержащая л символов а н и символов Ь, л.лО и у=а"Ь"). Постройте по Р моднфиггирован- ную анализирующую машину М, для которой т(М) -— -т(Р).
Сущее снует ли (а) ЯНРОВ-программа с выходом, (б) СУ-схема, определяющая тот же перевод? 9.2.15. Докажите теорему 9.5. 9.2.16. Докажите теорему 9.6 "9.2.17. Обобщите пояягпе процессора с указателямн на граф и данте алгоритмы перевода для СУ-схем, основанные на сле- дуюшвх алгоритмах: (а) алгоритм 4.1, (б) алгоритм 1.2, (з) алгоритм Кока — Янгера — Касами, (г! алгоритм Эрли, (д) дв)хьгагазианый анализатор (равд. 6.2), (е) анализатор Флойда †Эван. Проблглга длл лсслгдозанил 9.2.18.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
