 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Пример 5.8
Рассмотрим в качестве примера грамматику G5 со следующим множеством продукций:
S ® bMb M ® (L ï a L ® Ma)
Языку L, порождаемому грамматикой G5, принадлежат цепочки: bab, b(aa)b, b((aa)a)b, b(((aa)a)a)b и т.д.
Попробуем определить отношения предшествования между символами данной грамматики. На рис. 5.8 представлены различные сентенциальные формы, их синтаксические деревья, основы и те отношения, которые можно получить с их помощью.
На первый взгляд может показаться, что трудно найти все отношения предшествования между символами грамматики. Создается впечатление, что для этого необходимо построить массу синтаксических деревьев. Да и где гарантия, что все отношения уже найдены?
Дадим более строгие определения отношениям предшествования с тем, чтобы формализовать алгоритм их выявления. Прежде всего определим множество самых левых L(U) и самых правых R(U) символов грамматики для нетерминала U:
L(U) = {x | x Î N È S & ($ (U ® xj) or $ (U ® U1j) & (x Î L(U1))},
где здесь и далее U, U1, U2 Î N (нетерминалы), а j, y Î (N È S)* (любые цепочки из терминалов и нетерминалов, возможно пустые).
R(U) = {x | x Î N È S & ($ (U ® jx) or $ (U ® j U1) & (x Î R(U1))},
Иными словами, символы, которые записаны слева во всех правых частях правил (альтернативах) нетерминала U и составляют множество самых левых символов U – L(U). И далее, если левым символом U является нетерминал U1, то левыми для U будут и все самые левые символы U1 (L(U1)ÎL(U)). Множество R(U) определяется аналогично.
Пример 5.9. На рис. 5.9 а представлена таблица самых левых и самых правых символов для нетерминалов грамматики, рассматриваемой в качестве примера 5.8 в данном разделе. На рис. 5.9 б приведена матрица предшествования – наиболее удобная форма представления отношений предшествования между символами грамматики.
Матрица предшествования с рис. 5.9 б формировалась на основании следующих определений отношений предшествования:
x 
y, если $ (U ® jxyy)
То есть x y, если они стоят рядом в правой части какой-либо продукции именно в отмеченном порядке (x, а сразу следом за ним y).
x <· y, если $ (U ® jxU1y) & (y Î L(U1))
Если в правой части продукции стоит символ x (терминал или нетерминал), а следом за ним нетерминал U1, то x будет <· всех левых U1 (L(U1)).
x ·> y, если $ (U ® jU1yy) & (x Î R(U1)) or
$ (U ®jU1U2y) & (x Î R(U1)) & (y Î L(U2))
Если в правой части какой–либо продукции указан нетерминал U1, а следом за ним терминал x (напомним, что разбор канонический), то все правые символы U1 (R(U1)) будут ·> x. И далее, если в правой части продукции два нетерминала U1 и U2 стоят рядом, то все самые правые символы U1 (R(U1)) будут ·> левых символов U2 (L(U2)).
|
Как использовать полученные отношения? Если между парой символов более одного отношения предшествования, то они бесполезны. Если же не более одного, то они позволяют достаточно просто найти основу.
Для любой сентенциальной формы x1...x n основой является самая левая подцепочка x j ... x i , такая что
x j – 1<· x j, x j x j + 1 ,..., x i -1 x i, x i ·> x i + 1. €
Пример 5.10. На рис. 5.10 представлены шаги свертки цепочки b(aa)b к начальному символу грамматики S. Основы, получаемые на каждом шаге свертки, выделены здесь курсивом и подчеркнуты. Для осуществления последней свертки к цепочке добавляется ограничитель слева и справа (x0 и x n). В качестве символа ограничителя здесь взят символ # и предполагается, что # <· x и x ·> # для любого x Î N È S из G. €
Контекстно–свободная грамматика G называется грамматикой простого предшествования, или грамматикой (1,1) предшествования или грамматикой предшествования Вирта если:
1) грамматика G однозначно обратима, то есть никакие два правила грамматики не имеют одинаковых правых частей;
2) между любыми двумя символами грамматики существует не более одного отношения предшествования. €
5.2.1. Алгоритм Вирта–Вебера для анализа языков простого предшествования
При практическом применении отношений предшествования для распознавания предложений языка потребуется способ компактного представления отношений. Обычно этой цели служит матрица P, элементы которой принимают значения:
P[i,j] = 0, если x i и x j несравнимы (x i 
y j);
P[i,j] = 1, если x i <· x j;
P[i,j] = 2, если x i x j;
P[i,j] = 3, если x i ·> x j.
Для грамматики предшествования такое представление возможно, так как известно что между любыми двумя символами грамматики определено не более одного отношения. Таким образом, под каждый элемент матрицы можно отвести всего два разряда, но для того чтобы не выполнять лишних действий на выделение разрядов следует, видимо, использовать байтовый массив.
Сами правила грамматики должны располагаться в таблице, имеющей такую структуру, которая позволяет по полученной основе найти правило, содержащее данную основу в качестве правой части продукции, а затем указать соответствующую левую часть.
Неформально работу алгоритма Вирта–Вебера, а именно Н. Виртом и Х. Вебером были определены отношения простого предшествования и данный алгоритм в 1966 году, можно представить следующим образом. Символы входной цепочки просматриваются слева направо и заносятся в магазин (стек) до тех пор, пока не окажется, что верхний символ стека находится в отношении ·> к следующему входному символу. Это означает, что верхний символ стека является хвостом основы и, следовательно, вся основа уже в стеке. Затем полученную основу находят в списке правил грамматики и заменяют тем нетерминалом, из которого она выводится. Процесс повторяется до тех пор, пока в стеке не окажется символ S (начальный символ грамматики) и следующим входным символом станет ограничитель цепочки (в нашем случае – #).
На рис. 5.11 представлена функциональная схема данного алгоритма. Здесь C – стек, Т – входная цепочка, i – номер (позиция) верхнего символа в стеке, k – текущая позиция входной цепочки. Ограничимся небольшими комментариями к отдельным блокам или их группе, используя номера блоков из схемы:
1). В стек заносится ограничитель цепочки – # и индексам по стеку и входной строке присваиваются начальные (0–ые) значения.
2) – 3). Если между символом из вершины стека – C[i] и очередным входным символом – T[k] отношения не определены, то сообщить об ошибке и завершить работу. В противном случае перейти к блоку 4.
4) – 5). Ищется хвост основы. До тех пор, пока между C[i] и T[k] не обнаружится отношения ·>, текущий входной символ помещается в стек, извлекается следующий входной символ и осуществляется переход к блоку 2. Если хвост основы найден (C[i] ·> T[k]), то переходим к блоку 6.
6) – 8). Осуществляется поиск головы основы в стеке. На нее будет указывать индекс j.
9). Найденная основа ищется среди правых частей продукций заданной грамматики. Если поиск успешен, то осуществляется переход к блоку 10, иначе – к блоку 12.
10) – 11). Основа в стеке заменяется нетерминалом U – левой частью правила, обнаруженного в блоке 9. Затем выполняется семантическая подпрограмма, связанная с данным правилом грамматики и осуществляется переход к блоку 2.
12)–14). Сюда мы попадаем, когда обнаруженная основа ни к чему не приводится. Это может случиться тогда, когда в стеке кроме левого ограничителя цепочки записан начальный символ грамматики и очередной входной символ – правый ограничитель. В этом случае вся цепочка была свернута к начальному символу грамматики, исходная цепочка принадлежит рассматриваемому языку и алгоритм завершает работу сообщив об успешном окончании. В противном случае, для найденной основы просто не обнаружено соответствующего правила грамматики, и алгоритм также завершит работу, сообщив об ошибке.
Пример 5.11. На рис. 5.12 разобрана по шагам работа изложенного алгоритма для правильной цепочки b(aa)b языка из примера 5.8 с матрицей предшествования с рис. 5.9 б.
| Шаги | С0 | С1 | С2 | С3 | С4 | С5 | Отношение | Т k | ||||||
| # | <· | b | ( | a | a | ) | b | # | ||||||
| # | b | <· | ( | a | a | ) | b | # | ||||||
| # | b | ( | <· | a | a | ) | b | # | ||||||
| # | b | ( | a | ·> | a | ) | b | # | ||||||
| # | b | ( | M |
| a | ) | b | # | ||||||
| # | b | ( | M | a |
| ) | b | # | ||||||
| # | b | ( | M | a | ) | ·> | b | # | ||||||
| # | b | ( | L | ·> | b | # | ||||||||
| # | b | M |
| b | # | |||||||||
| # | b | M | b | ·> | # | |||||||||
| # | S | # |
Рис. 5.12
На рис. 5.13 а представлен пример разбора ошибочной цепочки babb, где причиной ошибки является отсутствие отношений между символами b и b, а на рис. 5.13 б показан пример цепочки ba, где ошибка возникает из–за отсутствия обнаруженной основы bM среди правых частей правил грамматики. ‡
Завершая обсуждение алгоритма Вирта–Вебера, заметим, что в нем и других подобных распознавателях есть одно очень привлекательное свойство: нет необходимости хранить в памяти одновременно всю цепочку входных символов (если только грамматика не из ряда вон выходящая). Символы считываются с входного носителя по одному и заносятся в стек, но после редукции основы те символы, что входили в нее исчезают. Всю цепочку приходится хранить в памяти только в том случае, когда основа находится в правом конце цепочки, но грамматики языков программирования никогда не строятся подобным образом.
Поиск по сайту: