по правилу FILO (first in, last out), чтение исходного текста
производится слева направо, а дерево сворачивания строится снизу
вверх.
Алгоритм в каждом текущем предложении Si выделяет самую ле-
вую строку, заключенную между отношениями > и <, и заменяет ее по
соответствующему правилу грамматики. Если грамматика предшество-
вания не имеет двух правил с одинаковыми строками y i, то данный
алгоритм для каждого предложения S L(G) всегда порождает одну и
ту же последовательность правил сворачивания. Для того, чтобы
строки сворачивания всегда были заключены между отношениями > и
<, в грамматиках анализируемых языков, как и в случае КС-грамма-
тик, вводятся ограничители начала и конца текста @.
В начале анализа строки в верхнюю ячейку стека R записыва-
ется первый символ программы, т. е. символ @. Индексам i (номер
символов стека R) и k (номер смвола входного текста) присваива-
ются начальные значения 1.
Блок 2. Проверяется отношение предшествования между верхним
символом стека Ri и очередным символом входного текста Lk . Если
между ними отношение вида _ (пусто), значит во входном тексте до-
пущена ошибка.
Блок 3 записывает в стек R очередной символ входного текста.
Блок 4 выделяет признак окончания текста Ri = @.
Блоки 5 и 6 определяют левую границу сворачиваемой строки.
Для этого проверяется отношение предшествования между каждой па-
рой символов R и R до выполнения условия R < R . В блоке
j-1 j j-1 j
5 не предусмотрен выход при выполнении условия R > R , так как
j-1 j
такое условие не может иметь место; вообще в процессе работы ал-
горитма в стеке R не может появиться пара символов с отношением
>, так как это исключает сам алгоритм.
Блок 7 производит поиск правила y=Rj,...,Ri по таблице грам-
матических правил и запоминает номер правила n, если оно найдено.
Блок 8 записывает в счетчик q число символов строки
Xn (q:=│Xn│).
Блок 9 производит переход на генерирующую подпрограмму.
Блок 10 проверяет длину строки Xn.
Блок 11 "выталкивает" символы Rj,..., Ri из стека R и запи-
сывает в него первый символ строки Xn, обозначенный на блок-схе-
ме Xn(1).
Блок 12 записывает все символы строки Xn, кроме первого, пе-
ред первым непрочитанным символом входного текста. Это не вы-
зовет переполнения массива L, так как по условию │Xn│ <= │Yn│.
Следовательно, число символов строки x не может быть больше чис-
ла символов строки y.
Блок 13 проверяет, выполняется ли правило R1,...,Ri. Если
такое правило выполняется, то алгоритм анализа и свертывания
входного текста закончен. Если такое правило не выполняется, зна-
чит данный текст из-за допущенной ошибки не может быть свернут.
Описания языков программирования КС- и даже неукорачивающи-
ми грамматиками вынуждает переносить определение части формаль-
ных условий из синтаксиса в семантику. Например, в ФОРТРАНе при
анализе каждого идентификатора необходимо определить, является
ли его описание явным или неявным. Если описание явное, то опре-
деляется тип идентификатора.
Пример:
Имеется грамматика:
Vт = { А, B }, Vn = { S, D, H, B`, A` }
1: S -> A`SD
2: S -> A`B`A
3: AD -> HA
4: H -> D
5: B` -> B
6: BD -> BB`A
7: A` -> A
Эта грамматика порождает язык следующего вида:
(А**n)(B**n)(А**n) ; n - степень
L(S) =A`,A,H,D R(S)=A, D
L(B`)=B R(B`)=B
L(A`)=A,H,D R(A`)=A
L(H) =D R(H)=D, A
L(D) =" R(D)=A
L(B) =B R(B)=" (неопределено)
L(A) =H,D R(A)="
Матрица предшествования:
│
S │ = =
B`│ < < =
A`│ = = < < < <
H │ < < =
D │ > > > >
A │ > > > > > > >
B │ = > > > <
@ │ = < < < <
───┼────────────────────────
│ S B` A` H D A B @
Дерево вывода на основе матрицы и правил:
┌──────────────────────────┐
S+──┐ ┌─────────────А+ +D
│ │ │ \ /
│ S+─── +─────+B` H +────+3
│ │ │ │ │
│ │ +5 4+ │
│ │ │ │ │
│ │ +B D+ │
│ │ │ │ │
+А` +А` └──+──┘ │
│ │ ┌──/│\──┐ │
│ │ │ │ │ │
+1 +1 │ +B` │ │
│ │ │ │ │ │
│ │ │ +5 │ │
│ │ │ │ │ │
А А B В А А
Ф : BA ─> BDA B. .A
\./
./│\.
B D A
ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ ПОРОЖДАЮЩИХ ГРАММАТИК
В ГРАММАТИКИ ПРЕДШЕСТВОВАНИЯ
Грамматики называются эквивалентными, если порождающие их
языки совпадают.
Теорема 1. Пусть в порожденной грамматике имеется одно или
несколько вхождений строки y в правые части порождающих правил.
Преобразование грамматики путем введения нового нетерминала Ф,
нового правила вывода Ф::=y и замена всех или части вхождений
строк y на вхождения нового символа порождает новую грамматику,
эквивалентную исходной.
G - грамматика.
Строка АВ, которая входит хотя бы в одну часть грамматичес-
кого правила, называется парой. Если А С R(А), В С L(В), то пара
рекурсивно-неоднозначна.
Грамматика, не содержащая рекурсивно-неоднозначных пар сим-
волов, называется рекурсивно-приведенной. Любая приведенная грам-
матика - рекурсивно-приведенная.
АЛГОРИТМ ПРЕОБРАЗОВАНИЯ РЕКУРСИВНО-НЕОДНОЗНАЧНОЙ ГРАММАТИКИ
В ГРАММАТИКУ ПРЕДШЕСТВОВАНИЯ
1. Находим множество правых символов. Выбираем все рекурсив-
ные символы грамматики (А R(А)). Грамматические правила имеют
вид: Ф::=(psi). Выделяем все вхождения этих символов в строки
psi, при условии, что они являются левыми частями пар. Для каждо-
го выбранного символа, имеющего такое вхождение, введем новый не-
терминальный символ А, новое правило вывода и заменим все выде-
ленные вхождения А на вхождения А`.
2. Для каждого нового правила А`::= А ищем другое правило
вида Ф ::= А, и если R(А) не содержит последнего символа строки,
то заменяем правило Ф ::= А на Ф ::= А`.
3. Находим множество левых символов. Выбираем все леворекур-
сивные символы В L(B), при условии, что В - правый член некото-
рой пары. Выделим все вхождения этих символов в строку (psi), при
условии, что эти вхождения являются правыми членами пар. Для каж-
дого В, имеющего такое вхождение, вводим В`, В`::= В и заменим
все вхождения В на вхождения В`.
4. Для каждого нового правила В` ::= В ищем в G другие пра-
вила вида Ф ::= В, при условии, что правые части этих правил сов-
падают. Если L(B) не содержит первого символа строки Ф, то заме-
няем правило Ф ::= В на Ф ::= В`.
5. Находим множество левых и правых символов для полученной
грамматики, находим матрицу отношений предшествования, если мат-
рица однозначна выход.
6. Перебирая все вхождения пар во всех строках (psi), отли-
чаем вхождения таких пар АiDi, где неоднозначность типа >< или >=
имеется либо между Аi и В L(Di). Для каждого отличного вхождения
пары АiDi в строку (psi)m выделяем подстроку хАi, для нее вводим
нетерминал Nj и новое грамматическое правило вида Nj ::= xАi. В
правых строках грамматических правил выделенные вхождения цепоч-
ки xАi заменяем новым символом Nj. Если в одной строке в правой
части выделено несколько вхождений таких цепочек, то надо после-
довательно заменять сначала более длинные, а потом короткие. Если
в правых частях грамматического правила выделено несколько строк,
то замена выполняется сначала для самых длинных строк, потом для
самых коротких.
7. Потом повторяется п. 5.
8. Перебирая все вхождения пар в правых частях грамматичес-
ких правил, выбираем (отмечаем) пары АiDi, где имеется неодноз-
начность. Для каждого отмеченного вхождения вычисляем строку Di y.
Для каждой выделенной подстроки, отличной от других, вводит-
ся новый нетерминал вида Nj ::= Di y. Для всех выделенных под-
строк грамматика будет однозначной.
Грамматики предшествования.
L(U)={S/Эz(U=>Sz)}
R(U)={S/Эz(U=>zS)}
Si = Sj ::= Э F (F: U::=xSiSjy)
Si < Sj ::= Э F ((F: U::=xSiUly) & Si{-L(Ul))
Si > Sj ::= Э F ((F: U::=xUkSjy) & Si{-R(Uk)) v
Э F ((F: U::=xUkUly) & Si{-R(Uk) & Sj {- L(Ul))
Алгоритм.
Обозначения:
L - строка анализируемого текста;
L(k) - к-й символ L;
S - стек реализации процесса свертывания;
S(i) - i-й элемент стека S
u(l),w(l),fi(l),psi(l) - соответственно цепочки u,w,fi,psi
правила P(l);
│u(l)│,│w(l)│,│fi(l)│,│psi(l)│ - длины цепочек u,w,fi,psi;
n - индекс самого нижнего символа S(n), такого что
S(n).x.S(n+1);
m - указатель существования в S пропущенной основы;
│p│ - число правил в грамматике.
Блок 1. Инициирует работу алгоритма.
i=k=1; n=max; m=0; Si=1;
Блок 2. Обработка ошибок.
Блоки 3,4. Нахождение правой границы основы свертывания.
3: S(i) ? L(k) =< - 4, >,>< - 6
4: j=i=i+1;
S(i)=L(k);
k=k+1;
Блоки 5,6. Запоминают n.
5: n=i;
6: S(i).><. L(k) & n>i да - 5, нет - 8.
Блоки 8,9. Нахождение левой границы основы свертывания.
8: S(j-1) >< S(j), < - 7, = - 9
9: j=j-1;
Блок 7. Начальное значение номеру грамматического правила Р
l=0
Блок 10. Анализ завершения просмотра всех правил.
l=│p│ да - 12, нет - 11.
Блок 11. Переход на просмотр следующего правила.
l=l+1;
Блок 12 проверяет возможность анализа при отсутствии правил
вида (u fi, u psi) для свертывания выделенной основы.
m=0;
Блок 14 проверяет возможность запоминания выделенной основы
в S.
n=i;
Блок 16 - возврат на первую из пропущенных основ.
L(k-n+j)...L(k+1)=S(n)...S(i)
i=j=n;
m=0;
k=k-n+1;
Блоки 13,15,17 проверяют соответствие строк u(l), w(l), fi
(l) выделенной основе и контекстным строкам, ее окружающим.
ЛЕКЦИЯ 6
LR(k)-ГРАММАТИКИ И СООТВЕТСТВУЮЩИЙ АНАЛИЗАТОР
Анализ для LR(k) - грамматики называется методом Кнута.
LR(k)-анализатор - устройство из неограниченных вправо вход-
ной ленты, верхнего и нижнего магазинов.