Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7

Вид материала

Конспект

Содержание 11.3. Восходящий анализ LR(k)-грамматик – тот тип грамматик, для которых однозначно восстанавливается правый вывод (R) S, либо дальнейшие свертки окажутся невозможными. Отношения простого предшествования с указанными свойствами могут быть определе Алгоритм разбора для ГПП.

Подобный материал:

• Учебное пособие тверь 2008 удк 519. 876 (075. 8 + 338 (075. 8) Ббк 3817я731-1 + 450., 2962.9kb.
• Тексты лекций Москва 2008 удк 339. 9(075. 8) Ббк 65. 5я73-2, 1528.45kb.
• Программно-технический комплекс Учебное пособие Новочеркасск юргту (нпи) 2010. Удк, 3911.73kb.
• Удк 152. 27 (075. 8) + 157 (075. 8) + 152. 3 (075, 60.12kb.
• Краткий конспект лекций Кемерово 2002 удк: 744 (075), 1231.26kb.
• Методические указания по курсу Новосибирск 2004 ббк ю 937. 4 Удк 152. 26 (075), 802.63kb.
• Москва 2011 ббк 63. 3 (2)я 7 к 90 удк 947 (075) История России, 110.08kb.
• Курс лекций Гродно 2005 удк 631. 1 (075., 1193.16kb.
• Удк 070(075. 8) Ббк 76. 01я73, 5789.66kb.
• Удк 339. 9(470)(075. 8) Ббк, 7329.81kb.

11.3. Восходящий анализ

При восходящем анализе цепочка сворачивается путем применения правил в обратном порядке (дерево вывода строится снизу вверх).

Введенные строки анализируются слева направо, полученные подстроки сопоставляются с правыми частями правил грамматики, и при совпадении заменяются на соответствующий нетерминальный символ в левой части правила (свёртка). Цепочка, заменяемая на этот символ, называется основой.

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

Среди грамматик выделяется класс LR(k)-грамматик – тот тип грамматик, для которых однозначно восстанавливается правый вывод (R) при чтении цепочки слева (L) направо, при подглядывании вперёд не более чем на k символов.

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

Пусть цепочка z получена в грамматике G=< V_N, V_T, S, R> с помощью правого вывода:

S₁₂…._n=x (V_T)*.

Тогда при восходящем анализе будем иметь

z=_n ├ _n-1 …├ ₀ = S.

Выделим i-й шаг вывода S*Ay (=_i-1)   y (=_i)*x y, здесь Ay – текущее состояние правого вывода, A – самый правый нетерминал в выводе. Свёртка состоит в переходе от   y к aAy, (a j y├ aAy) т.е. мы должны выделить подцепочку j, которая сворачивается в нетерминал A применением правила A j в обратном порядке.

Пример разбора цепочки для грамматики G₂₁(курсивом выделена основа): acacbbd├ acacbbB ├ acacbB ├ acacS ├ acS ├ S

Для ГПП техника выделения основы следующая:

строится матрица отношений предшествования между символами V_TV_N. При этом между парой символов х и y может существовать не более одного отношения предшествования, обозначаемого символами <, ≗, >.

Отношения предшествования отражают порядок появления символов в правом выводе.

Если a j y – текущее состояние цепочки, где j – основа, то между:

1. всеми смежными символами цепочки  выполняется отношение < или ≗ .
   
2. последним символом цепочки  и первым символом цепочки  (основы) выполняется отношение < .
   
3. смежными символами основы выполняются отношения ≗.
   
4. последним символом основы и первым символом цепочки у выполняется отношение >.
   

Если такое свойство отношений имеет место и для каждой пары символов определено не более одного отношения, то основу легко выделить, просматривая цепочку y слева направо до тех пор, пока впервые не встретится отношение >. Для нахождения левого конца основы надо возвращаться назад, пока впервые не встретится отношение < . Цепочка, заключенная между < и >, и будет основой. Если в грамматике нет правил с одинаковыми правыми частями, то однозначно находится нетерминал А, такой, что A   , что позволяет свернуть основу, получая цепочку _i-1 .

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

Отношения простого предшествования с указанными свойствами могут быть определены на V_NV_T следующим образом [1]:

X < Y, если в R есть правило A  X B , и при этом B^Y;

X ≗ Y, если в R есть правило A  X Y .

Отношение > определяется на (V_NV_T)  V_T , так как непосредственно справа от основы может быть только терминальный символ.

X > a, если в R есть правило A  B Y , и B ⁺  X, Y* a .

Так как основа может являться правым или левым концом цепочки, то удобно заключить анализируемую цепочку в концевые маркеры $ и $, положив X > $ для всех X V_NV_T, для которых S ^  X и $ < X для всех X V_NV_T, для которых S ^ X .

Грамматика G называется грамматикой простого предшествования, если она не содержит -правил, для любой пары символов из V_NV_T выполняется не более одного отношения простого предшествования и в ней нет правил с одинаковыми правыми частями.

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

Пример. Пусть множество правил грамматики G₂₄: S a S S b, S c. Для заключения цепочки в маркеры вводим новый начальный символ S’и правило S’$S$. Отношения предшествования для этой грамматики приведены в таблице 1.

Таблица 1

	S	a	b	c	$
S	≗	<	≗	<	≗
a	≗	<		<
b		>	>	>	>
c		>	>	>	>
$	≗	<		<

Разбор цепочки $accb$:

$<a<c>cb$├$<a≗S<co>b$├$<a≗S≗S≗bo>$├$S$

Вывод, соответствующий этому разбору:

S’ $ S $  $ a S S b $  $ a S c b $  $ a c c b $
Способ построения свёртки для цепочки связан с использованием стека, куда посимвольно переносится информация из входного буфера, до тех пор, пока не встретится отношение >. Тогда к цепочке от отношения > до ближайшего слева отношения < должна применяться свёртка.

Алгоритм разбора для ГПП.

1. Анализируемая цепочка заключается в маркеры.

2. Берём очередной символ из входного буфера (слева направо). Если между верхним символом стека и первым символом входной цепочки отношение <o или ≗ , то заносим этот символ из входной цепочки в стек и возвращаемся к шагу 2; если же между верхним символом стека и первым символом входной цепочки отношение o>, то переходим к шагу 3. Если между символами нет никакого отношения предшествования, то цепочка не принадлежит языку, порождаемому грамматикой.

3. Обратное движение: из стека вынимаются символы до первого отношения <o между первым символом стека и символом цепочки во входном буфере. Если такой символ появился, то переходим к шагу 4, иначе цепочка не принадлежит языку, порождаемому грамматикой.

4. Применяем свёртку (заменяем выделенный фрагмент на левую часть правила грамматики, правая часть которого совпадает с основой) и возвращаемся к шагу 2. Если свёртка неприменима (нет такой правой части правила), то цепочка не принадлежит языку, порождаемому грамматикой.

Если в результате применения свёртки приходим к цепочке $ S $, то исходная цепочка принадлежит языку, порождаемому грамматикой, в противном случае цепочка не принадлежит языку, порождаемому грамматикой.

Обозначим

Head(A)={X/A⁺X} (First₁(A)=Head(A)V_T),

Tail(A)= {X/A⁺  X},

тогда

X

X  > a  A B C  & X Tail(B) & aFirst₁(C).

Пример разбора цепочки aaccbbcb с использованием построенной таблицы отношений предшествования приведен в табл.2.

Таблица 2

	Отношение	Входная
Стек	предшествования	строка	Операция
$	<	aaccbcb$	сдвиг
$a	<	accbcb$	сдвиг
$aa	<	ccbcb$	сдвиг
$aac	>	cbcb$	«Свертка»
$aaS	<	cbcb$	сдвиг
$aaSc	>	bcb$	«Свертка»
$aaSS	≗	bcb$	сдвиг
$aaSSb	>	cb$	«Свертка»
$aS	<	cb$	сдвиг
$aSc	>	b$	«Свертка»
$aSS	≗	b$	сдвиг
$aSSb	>	$	«Свертка»
$S		$	«Конец»