АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

ВОСХОДЯЩИЙ РАЗБОР С ВОЗВРАТАМИ

Читайте также:
  1. I. Разбор основных вопросов темы.
  2. I. Разбор основных вопросов темы.
  3. Клинический разбор 1.
  4. Клинический разбор №5.
  5. НИСХОДЯЩИЙ РАЗБОР С ВОЗВРАТАМИ
  6. Понятие грамматического разбора
  7. Порядок морфологического разбора
  8. Практическое применение магнитной обработки в теплосетях с непосредственным водоразбором
  9. Предсказывающие алгоритмы разбора и разбор для LL(1)-грамматик
  10. Приложение 1. Правила проведения водных туристских спортивных походов на разборных парусных судах
  11. Разбор конкретных ситуаций

 

Существует общий подход, противоположный тому, который применяется при нисходящем разборе. Алгоритм нисходящего разбора можно представить себе как построение дерева разбора методом проб и ошибок, которое начинается сверху в корне и продолжается вниз к листьям. В противоположность этому, алгоритм восходящего разбора начинается с листьев, (то есть с входных символов), и пытается построить дерево разбора, восходя от листьев к корню.

Опишем восходящий разбор в виде алгоритма синтаксического анализа, который называют алгоритмом типа “перенос-свертка”. Он представляет собой по существу правый анализатор, который перебирает всевозможные обращенные правые выводы, совместимые с входной цепочкой. Один шаг алгоритма состоит в считывании цепочки, располагаемой в верхней части магазина, чтобы выяснить, образуют ли верхние символы правую часть какого-нибудь правила. Если да, то производится свертка, замещающая эти символы левой частью того самого правила. Если возможна более чем одна свертка, то эти свертки упорядочиваются произвольным образом и выбирается первая из них.

Если свертка невозможна, то в магазин переносится следующий символ и процесс продолжается, как и прежде. Всегда перед переносом делается попытка свертки. Если мы дошли до конца цепочки, а свертка все еще невозможна, то надо вернуться к последнему шагу, на котором была сделана свертка. Если здесь возможна другая свертка, то надо испытать ее.

Рассмотрим грамматику с правилами S ® AB, A ® ab и B® aba. Пусть ababa - входная цепочка. Сначала перенесем в магазин a. Так как свертка пока невозможна, перенесем b. Затем цепочку ab, расположенную наверху магазина, заменим нетерминалом А. Получим частичное дерево, показанное на рис. 4.4 а.

 

Так как А не допускает другой свертки, переносим в магазин а, а потом b. Затем можно опять свернуть ab к A (см. рис. 4.4 б).

Перенеся в магазин а, мы обнаруживаем, что свертка невозможна. Возвращаемся к последней позиции, в которой была сделана свертка, а именно, когда в магазине была цепочка Aab, то есть дерево было таким, как на рисунке 4.4 а. Так как другая свертка здесь невозможна, то делаем перенос вместо свертки. В магазине окажется Aaba. Тогда aba можно свернуть к B. Получим дерево с рис. 4.4 в. Далее заменим AB на S и получим завершенное дерево с рис. 4.4 г.

Этот метод можно рассматривать как процедуру прослеживания всевозможных последовательностей тестов недетерминированного правого анализатора для данной грамматики. Однако, так же как и в случае нисходящего разбора, надо избегать ситуаций, в которых число возможных последовательностей тактов бесконечно.

Одна из ловушек имеет место для грамматик с циклами, т.е. грамматик порождающих выводы A Þ+A для некоторого нетерминала A. Число частичных деревьев при этом может быть бесконечным, и мы исключим такие грамматики из рассмотрения. Трудности создаются и аннулирующими правилами, так как они приводят к произвольному числу “сверток” пустой цепочки к нетерминал.

 

Алгоритм 4.2. Алгоритм восходящего разбора с возвратами.

 

Вход. КС-грамматика G = (N, S, P, S) без циклов и аннулирующих правил (все правила занумерованы от 1 до p) и входная цепочка w = a1, a2, ¼, an (n ³ 1).

 

Выход. Один обращенный правый разбор цепочки w, если он существует, или слово “ошибка” в противном случае.

 

Метод.

(1) Произвольным образом упорядочить правила грамматики.

(2) Анализатор будет изложен в терминах 4-х компонентных конфигураций, подобных конфигурациям из алгоритма 4.1. В конфигурации (q, i, a, b):

(а) q - состояние алгоритма (их всего три: q - нормальной работы, b - возврата, t - завершения).

(б) i - текущая позиция входного указателя (предполагается, что (n+1) -м символом служит правый концевой маркер $).

(в) a - содержимое магазина L1, где хранится цепочка терминалов и нетерминалов, из которой выводится часть входной цепочки, расположенная слева от входного указателя. (Верх магазина L1 справа.)

(г) b - содержимое магазина L2, верх которого расположен слева. В магазине хранится история переносов и сверток, необходимых для получения из входной цепочки содержимого магазина L1.

(3) Начальная конфигурация алгоритма - (q, 1, $, e).

(4) Сам алгоритм начинает работу с попытки применить шаг 1.

Шаг 1. Попытки свертки

(q, i, ab, g)÷¾ (q, i, aA, j g), при условии, что A®b правило из P с номером j в линейном упорядочивании, определенном в (1). Номер этого правила (j) записывается в L2. Если шаг 1 применим, то повторить его еще раз. В противном случае перейти у шагу 2.

Шаг 2. Перенос

(q, i, a, g)÷¾ (q, i+1, aa i , m g), при условии, что i ¹ n+1. Затем перейти к шагу 1. Если i = n+1 перейти к шагу 3.

При выполнении шага 2, i-ый входной символ переносится в верхнюю часть магазина L1, позиция указателя увеличивается на единицу и в магазин L2 записывается символ m, чтобы указать, что сделан перенос.

Шаг 3. Допускание

(q, n+1, $S, g)÷¾ (t, n+1, $S, g).

Выдать обращенный разбор цепочки w - h(g), где h - гомоморфизм, определенный равенствами h(m)= e и h(j)= j для всех номеров правил. После этого остановиться.

Если шаг 3 неприменим, то перейти к шагу 4.

Шаг 4. Переход в состояние возврата

(q, n+1, a, g)÷¾ (b, n+1, a, g), при условии, что a ¹ $S. Перейти к шагу 5.

Шаг 5. Возврат

(а) (b, i, aA, j g)÷¾ (q, i, a¢B, k g), если A®b правило из P с номером j, и следующим правилом в упорядочении (1), правая часть которого является суффиксом цепочки ab, является правило A ®b¢ с номером k. (Заметим что ab = a¢b¢). Перейти к циклу 1. (Здесь происходит возврат к предыдущей свертке и делается попытка свертки с помощью следующей альтернативы).

(б) (b, n+1, aA, j g)÷¾ (b, n+1, ab, g), если A®b правило из P с номером j и для цепочки ab не остается никакой другой свертки. Перейти к шагу 5. (Если других сверток не существует, надо “взять назад” данную свертку и продолжать возврат, оставляя входной указатель на n+1).

(в) (b, i, aA, j g)÷¾ (q, i+1, aba, m g), если i ¹n+1, A®b правило из P с номером j и для ab не осталось никакой другой свертки. Здесь символ а = а i переносится в магазин L1, а m поступает в L2. Перейти к 1. (Мы вернулись к предыдущей свертке, и так как других сверток нет, попробуем сделать перенос).

(г) (b, i, aa, m g)÷¾ (q, i -1, a, g), если вверху магазина L2 находится символ переноса m. (Здесь в позиции i исчерпаны все альтернативы и надо “взять назад” операцию переноса. Вход указателя сдвигается влево, терминал устраняется из L1, а символ переноса удаляется из L2). Если этот шаг невозможен, объявить об ошибке.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)