Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 42
Текст из файла (страница 42)
(5) Та же, что н (1), но вместо Тт стоит Те. (01 То же, «то н П), мо еиесто 79 стоит Те. (7) Меглтнн шперк содержит ХПТ, рй, где р — укэзэтель нл нскоторуюэершнну л. Зэнжшп, ВТ, л!) ш (Т', р), где Т =перекок(Х). Рис. В.Е. действии процессоре по построению еыкодэ. Проследим за поведением процессора Р, на вход которого поступает пеночка а,е(а, ! а )5. Для ясности буквы а снабжены (1) (2) (З) (4) (8) (8) (7) (8) (9) ((О) (1!) зд.
синтАкснчески упРАВлпемыз пеРРВОды Р выполняет такую последовательность тактов: т, Пт е (аэ+ пх) 3 т,(тп р,] е (а,.(- ае) 3 т,]т„р,]» (о, 9 114) 8 т,!Т„р,]»( лэ4-о,) Э т,(т„р,]. ((Тю р,] +а,) 8 т,(т„р,]и (]т„р*]+ а,)8 г. (Т„р,]. (]Т„р,]+«тю р,] )8 т„!Т„р,]»(!Т„р,] )8 т. ! т„р,]» ((т„р,]) 8 Т тт 111] н ] те Ре] 8 т„(т„р,] 8 ГЛ 9, ПЕРЕВОД И ГЕИЕРА!ГИЯ КОЛЛ Рис. В.В. Окоячьтольома ьмхоа.
жв зю входе 5 служит допуск, и, следовательно, дерево, изображенное на рис. 9.6, является окончательным выходом. Этосинтаксичесиое дерево дла выражении а,ь(а,-,'-а„). Д 9.2.3. Детерминированный однопрокодный восходящий перевод Зто первый из трех разделов, в которых показывается, как можно обобщить различные алгоритмы анализа дли реализации СУ-схемы с помощью детерминированного МП.процессора вместо Л!П.преобразователя. Начнем с того, что дадим алгоритм реали. ванин произвольной СУ-схемы с входной ЕК-грамматикой. Алгоритм 9.1. Реализация СУсхе мы над ЕК.г р амматикой.
Вха). Семантически одноаяачиая СУ.схема Т вЂ - (Уп В, Л, Р, 5) с входной !.к(л)-грамматикой 0 = ()Е В, Р, 5) и входная цепочка юб В'. Вьгход. Выходное дерева, крона которого служит переводом ю. Метод. )(ерево строится МП-процессором М, моделирующим 1.К(й)-аналиаатор А лля грамматики О. Как и у(. М запоминает в магазине (верхушка которого расположена сираев) символы из Л)ВЕ н ЕК(Ь)-таблицы. Кроме того, М ааписывает под ииждым нетермивалом указатель на порождаемый выходной граф. Лействии перенос, свертка и допуск процессора М описываются так'. 9 9 синтлксическн упРАВ зяемые пеРеВоды (1) Когда А переносит символ а в магазин, М делает то же самое.
(2) Если Ай свертывает Х,, Х в нетермипал Л, то М делает следующее: (а) Пусть Л 'Х, . ° . Х,„, юьВ,ю, ... В,ю, — правило СУ-схемы, где символы В взаимно ол 'Отначка соответствуют тем символам Х, которые ивляются нетермнналами. (б) М удаляет из магазина Х, Х Вместе с промеж!. точными указатслямн 1.К(Ь)-таблиц н, если Х,Е)Ч, указателгь расположенный непосредстяеяно под ХР (в) М создаст новую вершину л, поь.ечает ее символом Л и помещает указа~ель на пес а магазин непосредственно под А. (г) Метки прямых потомков вершины л читаются слева направо: ю„В„ю, ... В,ш, Для всех символов цепочек ш создаются вершины.
Вершива длн ВО 1:-гщ.г, пред. стааляет собой вершину, на которую указывает указа. тель, расположенный в магазине процессора М непосредственно под Х, тле Х ".Ретермипал, соответствующий В, в данном конкретном правиле СУ-схемы. (3) Если входная цепочка исчерпана [достигнут правый капиевой марнер) и в магазине процессора М содержатся только р5 и лве ЕК(Ь)-таблицы, то М попускает тогда, когда допускает А; р указывает на корень выходного дерева процессора М. С) Пример 9.6.
Пусть алгоритм 9.1 применяется н СУ-схеме 5 а5А, ОА5 5 Ь, А — ЬА5, 15А А а, О а входной цепочкой служит аЬЬаЬ. Входная грамматика яв. ляется БЕК(!).грамматикой. Мы не будем рассматривать ЕК(1)- таблицы, считая, что они правильно управляют разбором. Будем последовательно выписывать цепочки, содержащиеся в магааине МП-процессора, а затем привелем древовидную структуру, на которую указывает каждый из указателей. ЕК(1)-табл9гцы, содержапгиеся в магазине, опускаем.
(е, аввав5) ! — "(ВЬ, Ьабб) !†(ар,5, Ьайй) ! †'(Вр,5Ьа, Ьй) ! — (ар,ВЬР,А, Ь5) !†(ар,5ЬР,АЬ, 5) ) — (ар,5ЬР,АР,5, 5) 1 — (ар,5Р„А, 9) ГЛ 9 ПЕРЕВОД Н ГЕНЕРАПИЯ КОДА зж Деревья, построенные к моментам, когда процессор прошел третью, пятую, седьлгую, восьмую и девятую конфигурации, изображены иа рис. 9.9. Ю Рзс. в.я. перезчл с изножью мп-процессрра Заметим, что когда ЬрлАр95 свертывается в Л, поддерево, на которое вначале указывал указатель р„ появляется слева ог поддерева, на которое ! казызает рю тан как элемент перевода, связанный с А ЬЗА, переставляет справа символы 5 и А. Аналогичная перестановна происходит при последней свертке.
Можно видеть, что результатом работы процессора на рнс. 9.9, д будет ОПО!. С! Теорема 9А. Алгоритм 9.1 правильно змполпяет лгрезад входной кепочки а соответствии с данной СУ-гхгмай. 9.9. СИПТАКСИЧЕСКИ УПРАВЛЯЕМЫЕ ПЕРЕЗОДЫ Доказательство. Элеме99тарная нндукция по порндку, в кагором образуются указатези в алгоритме 9.1. С] Добавим, что если мы „реализуем"МП.процессор на обычной вычислительной машине с прямыл9 доступом, то один такт МП- процессора осуществляется за конечное число шагов такой машины. Следовательно, время, затрачиваемое алгоритмом 9.1, является линейной функцией длины входной цепочки.
9.2.4. Детерминированный однопроходный нисходящий перевод Предположим, чта перед нами предсназывающий (нисходящий! анализатор, Превращение такого анализатора в транслятор требует подхода, несколько отличного от того, который применялся в случае восходяпгего анализатора. Допустим, чта у иас есть СУ-схема с входной ЕЕ-грамматикой. В пронессе разбора дерево строится сверху вниз, и на каждом этапе можно с 9итать, что построено частичное дерево. Листья этого часгична9о дерева, помеченные нетерминалами, соответствуют нетермииалал9, содержащимся в магазине предсказывающего анализатора, построенного алгоритмом 6.3.
Развертка нетерминала эквивалентна созданию потомков для соответствуюплего листа дерева. Стратегия при переводе состоит в том, чтобы хранить ука. ватель нв каждый лист „теку9цего" дерева с нетерминальной меткой. При обычном ЕЕ.разборе этот указатель хранится в мз. газине непосредственно под нетерминалом, соответствующим вершине, иа которую указывает указатель. При развертке нетерминала по некоторому правплу для соответствующего элемелпа перевода создаются новые листья я на верп9ияы с нетермииальными меткамн устанавливаются вновь соаданные укааатели, записанные в магазине.
Указатель, записанный непосредственно под развертываемым петерминалом, нсчеаает. Поэтому необходимо хранить где-то вне МП-процессора указатель на корень образующегося дерева. Например, если магазин содержит Ар и для развертки А применяется правило Л ПВЬСс с элементом перезода ОС1В2, то МП-процессор заменит Лр на аВр,бСр,с.
Если уназатель р до развертки указывал иа лист с меткой А, то после развертки А будет корнем поддерева где р, уиазывает на вершину В, а р,— на вершину С, (слово) <слово) (согласные> <согласные> (буквы) <буквы> <гласная> <гласная> <гласная> '11', '1)' (согласная> 'В', 'В' <согласнаи> 'С', 'С' В орнгннн ~н Г!К !.нцп.— Прн рнд, 222 гл г пю наод и ганге лция када Алгоритм 92. Нисходящая реализация СУ-схемы над !1.-грамматикой.
Вход. Семантически аднозначпан СУ-схема Т=[Б, Е, д, )), 5) с входной С1(Д) грамматикой 6 —. (П, 2, А, Р, 5). Выход. МП-процессор, порождающий дерево, крона которого служит переводам для ы, где ю — любая цепочка иэ !.[6). Межод. Построим МП-процессор М, моделирующий 1Л.(Д). анализатор А для грамматики 6. М моделирует н( следующим образом Как и в алгоритме 9.1, мы опускаем операции работы с таблицами Для М они ге же, что и длн ий (!) Первоначально в магазине процессора М [верхушка на ходится слева) записана цепочка др„ где р, — указатель на корневую вершин> н„.
(2) Если в верхушке магазина анализатора н( содержится терминал и он сравнивается с текущим входным символом, после чего н тот и другой стираются, то в М происходит то же самое, (3) Предположим, что н! развертывает нетерминал А (воз- можно, вместе с соответствующей 1.1.(й)-таблицей) по правилу А Х, ..
Х с элементом перевода у„д,у, ... В,у, н указа!ель, расположенный непосредственно под А (легко показать, что оп всегда существует), указывает на вершину л. Тогда М делает следующее: (а) Для и оп образует прямых потомков, помеченных слева направо символами цепочки у,В,у,... В,у,. (б) В хна[азине он заменяет А и расположенный под ним уиазатель на Х, Х , причем под теми из символов Х,... Х , которые являются негерминалами, записываются указатели. Указательч расположенный под ХР указывает на' веригину, образованную для Во если Хг и В, соответствуют друг другу в правиле А Х,..лХ,УВУ,...Ву, (4) Если магазин процессора гИ становится пустым к моменту достижении конца входной цепочки, то процессор допу.
скает; выходом служит построенное к этому моменту дерево с корнем л,. Г Пример 96. Рассмотрим приыер из области перевода естест. венного языка. Известно, что СУ-схема дает точную модель перевода с английского изыка на другой естественный язык— распространенный жаргон „пиг латин"'). Перечислим правила, г г. синтаксически гпгхвляамыа пенсаоды которые неформально определяют перевод английского слова в соответствующее слово на „пиг латин": (1) Если слово начинается с гласной, добавляем к нему суффикс УАУ'. (2) Если слово начинается с непустой цепочки согласных, помещаем все согласные до первой гласной в конец слова и добавляем суффикс АУ. (3) Однобуивениые слова ие изменяем. (4) Букна (). стоящая после Я, считается согласной. (5) Буква У в начале слона считается гласной, если за ней пе следует гласная.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
