Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 111
Текст из файла (страница 111)
Для этого надо предположить, что существуют три непересекающихся отношения <т, и ), заданные иа символах грамматики, из которых ) означает, что надо сделать свертку, а < н †перен. Когда делается свертка, ( указывает левый конец некоторой составляющей (не обязательно основы). Следует подчеркнуть, что отношения (, " и > по крайней мере временно не предполагаются связанными с правилами грамматики. Поэтому, например, может быть Х У., даже если Х н У пе стоят рядом ни в какой правой части правила. Определение. Пусть 6=-(Я, Х, Р, 5) — КС-грамматика и <, , ) — трн непересекающихся отношения на 61() г'() ($), где $— новый символ (концевой маркер). Двухмагазииный анализатор, индуцированныйотвошеииями (, ' и, определяется правилами (1) (Х, 1') — (Х1', е) тогда и только тогда, когда Х< 1' или' Х '.
1', (2) (ХЯ,...ЯА, 1') — (Х, А1') тогда и только тогда, когда У~)У, Яг 2,, для 1: 1<6, Х< 2, и А 2,...2А — правило грамматикй 6. Заметим, что если 6 †обратим грамматика, то индуцированный двухмагазинный анализатор будет детерминированным,. н обратно. Пример б.!2. Пусть 6 †граммати с правилами , (1) 5 а5А (2) 5 — Ь5А (3) 5 Ь (4) А — а как в примере 6.10. Зададим отношения <4, ' н ) таблицей на рис. 6.3.
Гл, а АлГОРитмы РАВБОРА с ОГРАниченными ВОЗВРАтАми ЕД. ВОСХОДЯЩИИ РАЗВОРС а »»»»» Зти отношения индуцируют двухмагазиниый преобразователь, правила которого определяются так: (Х, У) (ХУ, е) для всех ХЕ($, а, Ь), )'Е(а, Ь) (Ха, )') — (Х, А)') для всех Х6 ($, а, Ь), УЕ ($, А) (ХЬ, 1')- (Х, 5К) для всех Х6 ~$, а, Ь), )'Е ($, А) (Х, 5) — (Х5, е) для всех Хр а, Ь) (5, А) (5А, е) (Ха5А, )') — (Х, 5)") для всех ХЕ($, а, Ь) н )'Е(А, $) (ХЬ5А, 1') (Х, 51') для всех ХЕ ($, а, Ь) и )'Е(А, $) ф Т допускает цепочку юЬа», у которой 1ш) =и, проделав последовательность тактов ($, иЬа»$, е) ) в»+2 ($ГВЬа» $ е) — ($шЬ, А"$, (4, 2и)...(4, и+1)) ($2э, 5А»$, (4, 2и)...
(4, и+ 1) (3, и)) ( — '" ($, 5$, (4, 2п)...(4, и+1)(3, и)(е'„п — !)... (2„0)) где Гх Е (1, 2) для 1 «1«и. Заметим, что на последних Зп тактах чередуются переносы 5 н А со свертками а5А либо,Ь5А к 5. Легко проверить, что преобразователь Т детерминированный. Поэтому для каждой цепочки из Ь (6) возможна только оди» а д а 'л Ф Рве. 6.$. Отво2вевив „преашесгвоваввя». 1 последовательность 'тактов.
Так каи все сверки преобразователя Т соответствуют правилам грамматики 6, то Т вЂ” двухмагазинный анализатор для 6. П В некоторых грамматиках можно так задать отношения "пред- шествования", что нндуцируемые ими двухмагазинные анализаторы будут одновременно детерминированными н корректными; Сейчас мы дадим соответствующее определение, а в следующем разделе опишем простой тест, позволяющий установить, обладает ли грамматика нужным анализатором. , Определение. Пусть 6=(Ь), г,, Р, 5) — КС-грамматика. Назовем 6 грамматикой Холмерауэра, если (1) она'однозначная, (2) приведенная, (3) существуют непересекающиеся отношения (, ' и ) на Г(0 Х 0 ($), индуцирующне двухмагазинный анализатор, коррентный для 6.
Эти отношения назовем отношениями иредшестеования Колмерауэра. Заметим, что из условия (3) слепует, что грамматика Колмерауэра должна быть обратимой. Пример 6.13. Отношения иа рис. 6.3 являются отношениями предшествования Колмерауэра, и, значит, грамматики нз примеров 6.10 и 6.12 — грамматики Колмерауэра. Е) Пример 6.14. Каждая грамматика простого предшествования является грамматикой Колмсрауэра. Пусть (», . ° и ) — отношения предшествования Вирта — Вебера для грамматики 6 =- =(1», 2, Р, 5). Если 6 — грамматика простого предшествования, то она по определению приведенная и однозначная. Индуцируемый ею дзухмагазинный анализатор действует почти как анализатор типа „перенос — свертка" для грамматик предшествования. Однако, когда делается свертка правовыводимой цепочки а()ш к цепочке кА2а, мы заталкиваем $а в'первый магазин, а Аю$— во второй,'тогда как при разборе методом предшествования $ссА находится в магазине, а гэ$ — на входе.
Если Х вЂ последн символ цепочки $а, то по теореме 6.14 либо Х ( А, либо Х ° А. Поэтому на очередном шаге двухмагазинный анализатор должен перенести А в первый магазин. Затем до следующей свертки двухмагазииный анализатор работает каи анализатор простого предшествовання. Заметим, что если отношения предшествования Колмерауэра являются отношениями Вирта — Вебера, то нндуцированный двух- магазинный анализатор дает правые разборы. Однако в общем случае этого ожидать нельзя. 6.2.4. Проворна условий првдшествоааиия Колмараувра Дадим теперь условие, необходимое и достаточное для того, чтобы однозначная приведенная грамматика была грамматикой Колмерауэра. Оно включает три отношения, определяемые ниже.
Следует напомнить, что проблема выяснения однозначности КС-грамматики неразрешима и что, как мы видели в примере 6.12, существуют иеодпозначные грамматики, обладающие детерминированными двухмагазинными анализаторами. Таким образом, 5Я9 . е. ишимовы ялзиогл с огилничинными возиядтлми нельзя установить, является ли произвольная КС-грамматика грамматикой Колмерауэра, не зная заранее, что она однозначная. ели Определение. Пусть 6 =(Рч, 2, Р, 5) — КС-грамматика. О д м трн новых отношения 1. („ слева" ), р („смежность") и р — — пре(„справа") на Ь(() 2.
Для всех Х, УЕ Ь) ОВ и А ЕЬ) положим (!) АХУ, если в Р есть правило А' -Уа, (2) Хф', если в Р есть правило А — аХЩ (3) ХРА, если и Р есть правило А саХ. Как обычно, для каждого отношения )с обозначим й)+= 11 )сг Ю Е=! и гс'= 0 )с'. Напомним, что К+ и )с* удобно вычислять с по- мощью алгоритма 0.2. Заметим, что отношения предшествовання Вирта — Вебера (, и > на Ь)()2 можно определить через Х, р и р: (1) <=рЛ, '(2) — '=рй (3) ) = р~Р)л П (Ь) О 2) х 2.
Остальную часть этого раздела посвятим доказательству того, что однозначная приведенная КС-грамматика 6 облздает отно- шениями предшествования Колмерауэра тогда и только тогда, (1) р')з П )аь* = а „ (2) РПр рХ.=~.' Пример О.И. Рассмотрим предыдущую грамматику 5- а5А)ЬВА(Ь Л вЂ” ьа Для нее к = ((5, а), (5, Ь), (А, а)) р = ((а, 5), (5, А), (Ь, 5)1 р=- (А, 5), (Ь, 5), (а, А)) р+р= (А, А), (Ь, А), (а, А)) рй'= (а 5), (5.
Л), (Ь, 5) (а. а), (а, Ь), (5, а), (Ь, а), (Ь, Ь)) р'мХ+ = ((а, а), (а, Ь), (Ь, а), (Ь, Ь), (5, а), (А, а)) Так как р+рсПрь'= я н рерь+ () (ь=- я, эта грамматика обладает отношениями предшествовання Колмерауэра м на рис. 4.3. сз ы их уже виделн Покажем теперь, что если грамматика 6 содержит такие символы Х и 1, что ЛРУ и Хр'~й+У, то она не может быть 55В ел. восходящия рлзвои с огглиичвннымн возвидтлми грамматикой Колмерауэра. Здесь Х и 1' не обязаны быть различными.
Лемма 6.7. Пусть 6 = (Ь), Х, Р, 5) — грамматика Колмерауэро с отношениями предшествования Колмераувра (, '. и ). Если ХРУ, то Х=У Доказательство. Так как грамматика 6 приведенная, существует вывод, в котором применяется правило А аХУ)), При разборе цепочки АТЕЕ(6), в выводе которой встречается это правило, цепочка аХУ)) в какой-то момент окажется на верху первого магазина и свернется к А.
Это может произойти, только если Х ' 1'. 1) Лемма 6.8. Пусть 6=(Ь), Х, Р, 5) — такая КС-грамматика, что Хр'р).еУ и ХРУ для некоторых Х и У из ь(()2 Тогда 6 не является грамматикой Колмерауэра. До к аз ательсто. Предположим, что 6 — грамматика Кол.
мерауэра. Пусть (е, ' и ) — отношения Колмерауэра для этой грамматики и Т вЂ” индуцированный ими двухмагазннный анализатор. Так как 6 предполагается приведенной, найдутся такие х и у из Е*, что Х~*х и У=Ф*у. Так как ХрУ, существуют правило А — аХУО и такие цепочки ш„, ш„со, и ш, из Х", что 5 ==;>* в,Лсо, =чь из,аХУ(иоа =Л* ш,ю,ХУюаю, =>* в,со,хУюзсо4.
Так как Хр*рк+У, существует такое правнло  — уЯС6, что Я=реу'Х, С==>е УЬ', и для некоторых г„г„г, н г, 5 ~е г,Вг, =~ г,у2СЬг, =!>" г,уу'ХУЬ'бг, =:з' г,г,ХУг,г, =->' г,г,хуг,г, По лемме 6.7 можно считать, что Х ' 1'. Посмотрим, как анализатор Т обрабатывает две пеночки и =со,шзхусоагое 'и о=г,г,хуг,г,. В частности, проследим за цепочками, к которым свертываются х и у в каждом разборе, н выясним, появляются эти цепочки в первом магазине, во втором илн же они как-то разделены по магазинам. Пусть О„ О„ ...
†последовательнос цепочек, к которым свертывается ху в цепочке и, зры зр„... †аналогичная последовательность для цепочки о. Мы знаем, что найдется такое число ), что О;= ХУ, так как в силу предположенной однозначности грамматнкй Х и 1' при свертке цепочки и должны свертываться одновременно. Если зР, =О, для 1 ~ з ( 1, то в тот момент, когда У подвергается свертке прн обработке цепочки и, стоящий слева Х тоже будет свернут, так как Х ' У. Но этого не может быть, так как С=->' 1'6' для некоторого 6' в выводе цепочки и'). ') Заметим, что здесь Х и г' обозначают определенные вхождения атнх символов в выводы, т. е.
конкретные вершины дерева вывода. Мы надеемся, будет ясно, чть именно имеется в виду. 55з 553 1В А. Амо, дм. ульммм, т. ! Гл. б. АлГОРитмы РАВВОРА с ОГРАниченными ВОВВРАтАми Поэтому предположим, что для какого-то наименьшего . 1 с, б(1 либо 0;Ффо либо фс не существует (потому что следующая свертка символа из 1Г; затрагивает также символ вне ф). Мы знаем, что если 1> 2, то точка, делящая цепочку на две части, расположенные в разных магазинах (назовем ее точкой разделения по магазинам), занимает одну и ту же позицию в 0;, и в фс, после того, как О,, н ф;, построены в результате свертки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
