Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 93
Текст из файла (страница 93)
5.3А. Формальное определение алгоритма типа „перенос — свертка" Определение. Пусть 6 —.-([з[, Х, Р, 8)--КС.грамматика, правила которой занумерованы числами от 1 до р. Алгоритмом типа „перенос — свертка" для грамматики 6 назовем пару функций л=(1, д)'), где 7' называется функцией переноса, а Р— функцией свертки. Функции 1 и Е определяются так: (1) 7" отображает Уах(ХО(5))" в множество (перенос, свертка, ошибка, допуск), где )г =- [з[ О Х О (8), а 3 — новый символ, ко~- цевой маркер.
т) В этой связи см, также работы Гоачзроаой [1975! и Шумел и Зоннса [1975!.-Приап перев, а) Сложность проверки [.К(й)-условия изучается в интересной работе Ханта и др. [1975[.— Прим. пери. з) Это це те функции, которые ассоциируются с 19 (й)-таблицей. 452 (2) о отображает рах(ХО(Ц)' в множество (1, 2, р ошибка) при условии, что если а(гх, ш) =[, то правая часть 1' го правила является суффиксом цепочки а. Алгоритм типа „перенос — свертка" использует входную ленту, читаемую слева направо, и магазин, На основе того, чтб наход т ится в магаанне н осталось не обработанным на входе, функция ) решает, перенести ли текущий входной символ в магазин нли вызвать процедуру свертки.
Если принимается последнее из этих решений, то функция д решает, какую сделать свертку, Работу алгоритма типа „перенос — свертка" можно рассматривать в терминах конфигурацией, т. е. троек вида (3Х,... Х, а„... а„$, р,... р,) где (1) $Х1...Х вЂ” содержимое магазина, причем Х вЂ” верхний символ, Х;Е[ь[ОХ и 8 служит маркером дпа магазина, (2) а,...а„— оставшаяся необработанной часть первоначальной входной цепочки, а, †текущ входной символ, $ служит правым концевым маркером для входа, (3) р,...р„ †цепоч номеров правил, примененных при свертке йервоначальной входной цепочки к цепочке Х,...
Х„ ат...а„. Один шаг алгоритма Л можно описать с помощью двух от- ношений» вЂ” Л и [ —,'Т, определенных на конфигурациях(индекс Л в этих обозначениях будем опускать всюду, где можно): (1) если ) (а, аш) = перенос, то (а, аш, л) [- з (аа, пз, и) для сс Е )г", ш Е (Х О Щ" и п Е (1...,, р) *, (2) если 7" (а[з, пз) =-свертка, д(а(), пг) =-Л и А — [1 — правило с номером г, то (а[), ш, и) ',— г(ссА, гэ, п(), (3) если 7(а, гс) =-допуск, то (сс, ш, и) [ — ' допуск, (4) в остальных случаях (сс, ш, и)» — ' ошибка. Определим отношение г — как объединсние Отношений ! — ' и )-'. Отношения [ — + и [ — * определяются, как обычно. Для гсЕ Х* положим Л(ш) =-и, если ($, ш$, е)',,— ' ($З, 8, и)[-- допуск, и Л(гс) =ошибка, если такого и нет.
Будем называть алгоритм Л корректным для грамматики 6, если (1) Е (6) =- (гс [ Л (ю) Ф Ошибка), (2) и — правый разбор цепочки гс„если Л(гс) =-и. Пример 5.33. Построим алгоритм типа „перенос — свертка" Л = О, д) для грамматики 6 с правилами (! ) В ЗОВ[1 (2) 5 — е Я53 ГЛ. 5, ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ 5.3. ГРАммАтики НРГда»естВОВАния Функцию переноса 1 зададим так; для всех аЕ)»* и хЕ(з 1) ($))". (1) ) (а5, сх) = перенос, если сЕ (а, Ь), (2) ((ас, »(х) =свертка, если сЕ(а, Ь) и»(Е (а, Ь), (3) 7 ($, ах) = свертка, (4) (($, Ьх) = ошибка, (5) Г" (»хХ, $) =ошибка для Х Е(5, а), (6) Г(аЬ, $) =-свертка, (7) » ($5, $) = допуск, (8) 1(Ъ,$) =ошибка.
Функцию свертки я зададим так: для всех аЕ)'* н х~(Х() ($))» (1) а (», ах) = 2, (2) д(аа, сх) =-2 для СЕ (а, Ь), (3) а($5а5Ь, сх) =-1 для се (а, $), (4) д(аа5а»ГЬ, сх) =1 для сЕ (а, Ь), (5) а(а, х) =ошибка в остальных случаях, Разберем с помощью алгоритма А входную цепочку ааЬЬ, Ои приступает к работе в начальной конфигурации ($, ааЬЬ$, е) Первый шаг определяется значением 7"($, ааЬЬ$), которое, как видно из определения функции ), равно свертке. О том, какую делать свертку, говорит значение и ($, ааЬЬ$), равное, очевидно, 2. Поэтому первым шагом будет свертка ($, ааЬЬ$, е) ) — "($5, ааЬЬ$, 2) Следующий шаг определяется значением (($5, ааЬЬ$)=перенос. Таким образом, это шаг переноса ($5, ааЬЬ$, 2) 1 — '($5а, аЬЬ$, 2) Продолжая в том же духе, алгоритм 4 сделает такую после- довательность шагов: ($, ааЬЬ$, е)', †'($5, ааЬЬ$, 2) ) — '($5а, аЬЬ$, 2) ) — '($5а5, аЬЬ$, 22) 1 — '($5а5а, ЬЬ$, 22) )-."($5а5а5, ЬЬ$, 222) '($5а5а5Ь, Ь$, 222) '($5а5, Ь$, 2221) »($5а5Ь, $, 2221) г ($5 $22211) ' допуск Таким образом, 4(ааЬЬ) =-22211.
Ясно, что 2221! — правый раз бор цепочки ааЬЬ. Е) На практике мы не хотим иа каждом шаге рассматривать всю цеп<жку в магазине и всю необработанную часть входной цепочки, чтобы выяснить, каким должен быть очередной шаг алгоритма разбора, Обычно нам хочется, чтобы функция переноса зависела только от небольшого числа верхних символов магазина и от небольшого числа следующих входных символов. Аналогично хотелось бы, чтобы функция свертки зависела только от символов магазина, распопожсниых В нем не нижЕ, ЧЕМ на один или два символа От сворачиваемой основы, и от одного или двух следующих входных символов. Заметим, чго в предыдущем примере функция»Г зависит фактически только от верхнего символа магазипа и следующего входного символа, а функции д требуется только Один символ нигке основы и один следующий входной символ.
ЕК(й)-анализатор, построенный в предыдущем разделе„можно рассматривать как алгоритм типа „перенос — свертка", в котором магазинный алфавит дополнен ЕК(й)-таблицами. Если трактовать его так, то можно заметить, что его функция переноса зависит только от верхнего символа магазина (текущей )К(й)- таблицы) и следующих я входных символов. Функция свертки зависит только от таблицы, расположенной в магазине непосредственно ниже основы, и ие зависит от следующих входных символов. Однако, согласно данному нами формальному определению, надо исследовать все содержимое магазина, чтобы выяснить, какова верхняя таблица. Алгоритмам, излагаемым в этом разделе, требуется только та информация, которая хранится „почти" иа самом верху магазина. Поэтому мы принимаем такое соглашение: Соглашение. Если 7" и д — функции алгоритма разбора типа „перенос — свертка" и значение ) (и, и») опрсделено, то Г (ба, шх) =- Г" (»х, и») для всех 1з и х, если не оговореяо противное.
Аналогичное утверждение касается функции д. Р.3.2. Грамматики простого предшествовання Простейший класс алгоритмов типа „перенос — свертка" Основан па так называемых „отношениях предшествованпя", Для грамматики предшествования границы основы правовыводимой цепочки можно определить с помощью некоторых отношений (предшествования) между символами, Входящими в эту цепочку. Техника разбора, ориентированная на отношения предшествовапия, использовалась при построении анализаторов для языков программирования одной из первых, и с тех пор в литературе появилось несколько вариантов грамматик предшествоваиия.
Мы рассмотрим основанный на Отношениях предшествования детерминированный анализ слева направо, производящий правый гл. з, однопроходнын синтлкснчгскин лнллиз ввз возвзлтов з.з. грлммлтики ппвдшествовлния разбор. При этом будут введены грамматики предшествования следующих типов: (1) простого предшествования, (2) расширенного предшествования, (3) слабого предшествования, (4) смешанной стратегии предшествования, (5) операторного предшествовапия.
Ключ к пониманию метода разбора по отношениям предшествовапия дает определение отношения ) между символами грамматики, которое при просмотре слева направо правовыводимой цепочки ари», где р †осно, впервые оказывается выполненным для последнего символа цепочки р и первого символа цепочки и», Если для разбора применяется алгоритм типа „перенос— свертка", то всякий раз, когда между верхним символом магазина и первым из необработанных входных символов выполняется отис»пенне >, принимается решение о свертке; в противном случае делается перенос. Таким образом, с помощью отношения ) локализуется правый конец основы правовыводимой цепочки.
Локализация левого конца основы и определение нужной свертки осуществляетсн разными способами в зависимости от используемого типа пред- шествования. Техника анализа, основанная на так называемом „простом предшествовании*', использует для выделения основы правовыводимой цепочки арпа трн отношения предшествования: (, и ). Если () — основа, то между всеми смежными символами цепочки а выполняется либо отношение (, либо, между последним символом цепочки сс и первым символом цепочки 3 выполняется (е, между смежными символами основы — отношение ' н между последним символом цепочки (1 и первым символом цепочки и» вЂ отношен >.
Итак, основу правовыводимой цепочки грамматики простого предшествования можно выделить, просматривая эту цепочку слева направо до тех пор, пока впервые не встретится отношение >. Для нахождения левого конца основы надо возвращаться назад, пока не встретится отношение (е. Цепочка, заключенная между ( и ), будет основой. Если грамматика предполагается обратимой, то основу можно однозначно свернуть. Этот процесс продолжается до тех пор, пока входная цепочка не свернется к начальному символу (либо пока дальнейшие свертки окажутся невозможными). Определение.
Отношения прада»еетвования Вирта — Вебера (а, и > для КС-грамматики 6 =-((ч', г., Р, 5) определяются на множестве ЖОг следующим образом: (1) Х< )', если в Р есть такое правило А — аХВр, что В =о 1'у; (2) Х ° г', если в Р есть правило А — аХЩ (3) отношение ) определяется на (гчгОХ)мХ, так как непосредственно справа от основы в правовыводимой цепочке может быть только терминальный символ; полагаем Х >а, если в Р есть правило А — аВУ)1, В=ах еуХ и У=;>*ад (заметим, что У'=-а, если У=~зад). Анализируя входную цепочку методом предшествования, удобно добавлять к ней левый и правый концевые маркеры. В качестве такого концевого маркера возьмем символ $ и будем считать, что 3<а Х для всех Х, для которых 5 =;>' Ха, и К) для всех 1', для которых 5 =;>+ а)'. Вычислять отношения предшествования Вирта — Вебера нетрудно.
Предоставляем читателю самому разработать соответствующий алгоритм или воспользоваться приведенным в равд, 5.3.3 алгоритмом, вычисляющим расширенные отношения предшествования. Определение. КС-грамматика 6 = (М, Е, Р, 5) называется грамматикой предшеетвования, если она приведенная '), не содержит е-правил и для любой пары символов из 5111», выполняется не более одного отношения предшествования Вирта — Вебера. Обратимая грамматика предшествоваиия называется грамматикой простого предшеетеования, Как обычно, язык, порождаемый грамматикой (простого) предшествования, назовем языком (просп»ого) предшествования. Пример 5.34. Пусть 6 состоит из правил 5 - а55Ь!с Отношения предшествования для грамматики 6 вместе с дополнительными отношениями для концевых маркеров показаны в виде матрицы предшествования на рис.
5.11. Каждая ячейка матрицы содержит отношение предшествования между символом, помечающим соответствующую строку, и символом, помечающим столбец. Пустая ячейка интерпретируется как ошибка. Опишем теперь систематический подход к построению отношений предшествования. Отношение ° вычисляется легко: просматриваются правые части правил и обнаруживается, что а ' 5, 5 ' 5 и 5 ' Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
