Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 43
Текст из файла (страница 43)
Приведем СУ-схему, вилючающую только правила (1) и (2). В качестве упражнения предлагаем учесть и остальные правнла. Прапила СУ-схемы таиовы: <согласные) <гласная> <буквы>, (гласная> <буквы> (согласные> 'АУ' (гласная) (буквы), <гласная> <буквы> 'УАУ' (согласная) (согласные), <согласная) <согласные) <согласная>, <согласная> <буква> <буквы>, <буква> <буивы> е,е 'А', "А' 'Е', 'Е' (согласная) '2', '7' <буква) <гласная>, (гласная> <буква> <согласная>, <согласная> Легко видеть, что входная грамматика явлнется ЕЕ(2).граггматикой.
Найдем перевод, соответствующий входному слову "ТНЕ". Каи и в предыдущих двух примерах, сначала выпишем конфигурации процессора, а затем покажем, как выглядит дерево иа различных этапах его построения. Верхушка магазина все время находится слева. ПГГЕВОД И Гапяэанин Кпла 7 <ваада» Здесь левый столбец означает входную цепочку, правый— содержимое магааина. Структура дереве после шагов 1, 2, 6 и П представлена соответственно на рнс. 9.10,а — г.
С) Как и в предыд>щем разделе, легко доказать, что рассматриваемый алгоритм выполняет правильный перевод и что па обычной машине с прямым доступом его можно реализовать так, чтобы он работал за время, линейно зависящее от длины входной цепочки. Зафиксируем изложенное в следующей теореме. Теорема 9.5, Алгоритм 9.2 строит МП-праце сор, порождиюн(ии е качестве еажода дереве, крона которого служит переводом входной цепочки. Дои аз а тельство.
Индукцией можно доказать, что вход. ная цспочна ш вызывает стирание нетерминала А и указателя р в магазине тогда и только тогда, когда (А, А) =эг(ш, х), где х †кро поддерева, корнем которого служит вершина, на которую указывает р (после стирания символа А, указателя Р и символов, в которые развертывается А). Детали доказательства оставляем в качестве упражнения. С) Г <ее магмы» <следе» 0.2.5. Перевод при наличны возвратов Центральные цдси МП-процессора можно применить танже и к алгоритмам разбора с возвратом.
Для определенности рас. смотрим, иак можно обобщить анализирующую машину из равд. 6.1, чтобы она строила дерево. Основная новая идея заключается в том, что процессор должен обладать способностью „раарушать" поддеревья, которые оп построил. Иными словами, некоторые поддеревья могут становиться недостижимыми (и, хотя здесь мга пе будем разбирать детали реализации, на практике использованные для представления таких поддеревьев ячейки пачнти возвращаются в общую досту)шую начать). Модифицируем анализнрующу)о машину из разя.
6.1 так, чтобы предоставить ей возможное~в помешать в магазин указа. тели на вершины графа. (Напомним, что в анализирующей ча- 225 Э а канны га, .а 224 (!) ТНЕ5 (2! ТНЕЕ (3! ТНЕЕ (4) ТНЕЕ (5! Ннй (б) НЕЕ (7! НЕ5 (з) е3 бй Ей (10! 5 (19 5 <саааюра <сагласаые>ра<гаасааа>ра<букаы>р <с гаатаа>Р <сагкаскыюе <гаа каа>р <б!'каы>Р4 Т<сагаас ыа)Р,<гааскаа>р,<буквы>Р, <сагаасаыа>р„<гааскак>р <букам>р <соска<как)Р <сакская)еа <букам)Р4 и<глас аа>ра<букаы>ра <гаасааа>ра<букаы>ра 6<буквы>р, <буквы>Р, аз синтакси шоки юшлвлягмыв не»вводы шине уже есть указатели на ее вход, они хранятся в одной ячейке памяти с информационным символом.) Правила работы <саада» <г ге<ига» <глебы.
<еиеееаые» Р 1 ! и е <атеаеала» <сагаеат)е» ! 1 Т <мгаегмы» ! гг Ркс 0.!О Первака на кпкг катка . с этими указателялги те же, что и в случае МП-процессора, поэтому мы пе булем здесь подробно на цих останавливагься. Прежде чем описать алгоритм переводя, связанный с анализируюгцей машиной, посмотрим, как переносится понятие СУ- гл з, пегявод н гснсвлпня кодл перевода на ОЯН!зОВ-программы (программы, написанные на Обобщенноьг Языке Нисходящего Разбора с Ограниченными Возвратами) нз разя. б.1 Рааумно предположить, что перевод связан с „вызоволг" нетерминалз тогда и только тогда, когда этот вывоз успешеп.
Пусть Р=-(Н, т, В, В) — ОЯНРОВ-программа. Будем интер. претировать ОЯНРОВ.оператор А — а, где а Е Е О (е), как попытку применить прзвило Л а в КС-грамматике. Тогда по аналогии с СУ-схемой можно было бы ожядать, что найдется связанная с этим правилом пепочна выходных символов. Иными словами, все правило будет иметь вид А о, ш, где ыЕЛ*; здесь Л вЂ” „выходной алфавит". Единственным другим ОЯНРОВ-оператором, способным порп. дип перевод, будет А —.
В[С, О[, где А,В, Си О принадлежат РК Можно считать, что алесь участвуют два правила КС-грамматики, а имешш А ВС и А О. Если В и С приводят к успеху, то желательно, чтобы неревод для А включал переводы для В и С. Поэтому предстанляется естественным связать с правилом А В[С, О) элемент перевода вида шВхСу илн иСхВу, где ш, х и у принадлежат Л'. (Если В =С, то должно быть точно определена соответствие между нетерминалами правила и нетерминалами элемента перевода.) Однако, сслн В приводит к неудаче, хотелось бы, чтобы перевод для А вызывал перевод для О.
Поэтому второй элемент перевода, иыеющий внд иОо, должен быть связан с правилом А В[С, О). Дадим формальное определение такого метода описания перевода и посмотрим, как можно обобщить анализирующую машину, чгобы она выполняла такие переводы. Определение. ОЯНРОВ.программой с выходом назовеы пятерку Р.= (В, х', Л, )2, В), где Н, Е и В те же, что для нроизвольпой 05!НРОВ-программы, Л вЂ” конечное множество выходльгх кима>лов, а )2 в множество правил вида: (1) А — Д е, (2) Л .
о, у, где оЕЕП(г) н уйЛ", (3) (а) А В[С, О), у,Ву,Су„у,Оу„ (б) А В[С, О[, у,Су Ву„у,Оу„ где д, ЕЛ'. Для каждо~о нетермннала существует не более одного из этих правил Определим отношения ~" между нетсрминалами и тройиами вида (и1о, у, г), где и и о принадпежат Е*, уйЛ' и г — это либо з, либо Д Здесь первая компонента †входн кепочка, в ко~врой отмечено положение входной головки, вторая компо- 22З зл гггнтхксггчяски . пэхвлявмык пегвводы кента — выходная пспочка, а третья --выход, означающий успеХ или неудачу. (1) Если для А есть правило А и, у, та А=>'(а1и, у, з) для всек и ЕЕ*.
Если о принадлежит т', по пе пачннается с а, то А~'(1э е [) (2) Если для А есть правило А В[С, 01, у,Еу,уу,, д,Одз, где Е----В и Р=.С нлн наоборот, го справедливо следующее: (а) Если В=>" (и,1ити„х,, з) н Сжж (и,1и„х„з), то прп Е=В, Р=С и А =>" +"* ''(и,и,( и,, у,х,у,х,у„т) при Е =С н у=В. В случае В.=.С будем предполагать, что соответствие между Е н Р, с одной стороны, и позншгнмн, з которых стоят В и С, с другой стороны, указывается с помощью верхних нндсксоз; например, А -Во[В, О], д,впц Вц„дОд, * (б) Если В=>" (и,(н, х, з) и С=ю" ()из, е, П, то А =>" ""'(1и,и„е, [) (в) Если В~" (', и,и„г, [) и 0=>"*(н, г и„х, з), то А =>" "" (и, 1 и„у,ху„з) (г) Если Вы>" (1 и, е, П и О~ч(1и, е, [), то А =>" '" "'('и, е, П Заметим, что если Л ~" (и1о, у, [), то и=-е и у=е.
Иныьги словами, орн неудаче входной указа~ель не сдвигается н не порыкдается никакого перевода. Следует также подчеркнуть, что з случае (26) перевод символа В „аннулируется", если С приводит к неудаче. Обозначим через =>+ объединение отношений ~" для и ) 1, Переводом т(Р), опраделяемыч программой Р, назовем множество ((ш, х) (В=>+ (ш(, х, з)).
Пример 9.8. Напипгем ОЯНРОВ-программу с выходом, осуществляющую перевод на „пиг латин", описанный в примере 9.7. Выход будем записывать строчным» буквами. При переводе непа ~ьзуются нетерминалы, связь которых с предыдущим примером показана в табл. 9хС Х н С, означают здесь кепочки нетерчнналоз. Кроче гого, мы б)дем по,ггжаваться нетерминалами В и Р с правилами В г и Р Д Наконсп, правила для Со д и (. должны быть такими, ч зобы они соответстзозалн любой согласной, гласной или букве, определяя перевод, который является 227 гл э. Пгнгвод н тансен<гик код* н.г сингнкси гес -иче<>КИ УПГНВЛЯСМЫЕ ПГГГНОЛЫ тана на э г соответствующей буквой.
В эти правила входят дополнительные нетерминалы, и мы их опускаем. Существенными правилвцн будут %' С,[Х, Х], ХС, 'ау', Х 'уау' С,-С,[Сг, Р], С,фРф— С,[СО В], С,См В (., Ег[Е„З], Е>Е„В Х-Р[Е„Р], Рйм Е Например, если рассматривается входная цепочка 'апд', то легко видеть, что Р ~' (а 1пб, а, з) и Егш>' (пб 1, пд, з). Поэтому Х~ (апб 1, апб,з). Так как С, ~Т (! апд, е, [),тоС<ыь (! аш),е, [). Таким образом, )у=э+ (апд 1, апдуау, з).
! Подобный перевод можно осуществить с помощью молифи. цированной ана.тизнрующей машины из равд. 6.!. Действие такой машины основано на следующем паблгодеиии. Если вызывается процед>ра А с правилом А — В[С, Р], то Л порождает перевод, только если В н С приводят к успеху или В приводит к неудаче, а 0 — к успеху. Опишем поведение модифицирован. ной анализирующей машины н виде алгоритма. йлг оритм 93. Реализация ОЯНРОВ-програчмы с о ы ходом.
Вход. ОЯНРОВ-программа Р =(Ч, 2, й, )2, 5) с выходом. Выход. Модифицированная анализирующая машина М, по. рождшощая длн любой входной цепочки ш дерево с кронои к тогда и только тогда, когда (и, х) принадлежит п,Р). <Игшод. Если не учитывать элементов перевода, отвечающих правилам из Р, го можно считать, что у нас ОЯНРОВ-прог рампа м С, с пг ьг Х <Санно> <СОГЛНС н н> <ссгляснме> <с лнснзя> <буква> <букьн> <гггаеннн> <гтнснан> <букам> . 6.!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
