Главная:
Рефераты
Главная
Финансы деньги и налоги
Философия
Физика и энергетика
Управление
Схемотехника
Стратегический менеджмент
Статистика
Соцобеспечение
Семейное право
Программирование компьютеры и кибернетика
Охрана окружающей среды экология
Основы права
Медицина
Криминалистика и криминология
Коммуникации и связь
Кибернетика
Качество упр-е качеством
КСЕ
Информатика ВТ телекоммуникации
Журналистика
Государство и право
Биографии
Банковское дело
Карта сайта
Рефераты. LL(k)-грамматики
LL(k)-грамматики
LL(k) - Грамматики.
Определение LL(k)-грамматик.
Для начала предположим, что
G
=(
N
,
E
,
P
,
S
) - однозначная грамматика и w=a1,a2...an - цепочка из
L
(
G
). Тогда существует единственная последовательность левовыводимых цепочек b0,b1..bm, для которой
S
=b0,bi,pi Ю bi+1 при 0<=i<m и am=w. Последовательность p0p1..pm-1 - левый разбор цепочки w.
Допустим, что мы хотим найти этот левый разбор, просматривая w один раз слева направо. Можно попытаться сделать это, строя последовательность левовыводимых цепочек b0,b1..bm. Если bi=a1,a2...ajAB, то к данному моменту анализа мы уже прочли первые j входных символов и сравнили их с первыми j символами цепочки bi. Было бы желательно определить bi+1, зная только a1,a2...aj (часть входной цепочки, считанную к данному моменту), несколько следующих входных символов (aj+1aj+2...aj+k для некоторого фиксированного k) и нетерминал A. Если эти три фактора однозначно определяют, какое правило надо применить для развертки нетерминала A, то ai+1 точно определяется по ai и k входным символам aj+1aj+2...aj+k .
Грамматика, в которой каждый левый вывод обладает этим свойством, называется
LL
(k)-грамматикой. Мы увидим, что для каждой
LL
(k)- грамматики можно построить детерминированный левый анализатор, работающий линейное время. Дадим несколько определений :
ОПР:
Пусть a=xb такая левовыводимая цепочка в грамматике
G
=(
N
,
E
,
P
,
S
), что xОE*, а b либо начинается нетерминалом, либо пустая цепочка. Будем называть x законченной частью цепочки a, а b - незаконченной частью частью. Границу между x и b будем называть рубежом.
ПРМ:
Пусть x=abacAaB, тогда abac - законченная часть цепочки x, AaB - незаконченная часть цепочки. Если x=abc, то abc - законченная часть и е - незаконченная и рубежом служит конец цепочки.
Иными словами идею
LL
(k) - грамматики можно объяснить так: если имеется уже разобранная часть цепочки, то на основании этого и еще нескольких неразобранных символов мы можем сделать вывод о том, какое правило неоюходимо применить. Таким образом грамматика посуществу не зависит (не считая k последующих символов) от того, что выводится из незаконченной части цепочки. В терминах деревьев этот процесс выглядит следующим образом: дерево вывода цепочки строится начиная с корня и детерминировано сверху вниз.
Вводят функцию FIRST(x) - возвращающую первых k символов. Обычно приписывают в качестве индексов k и
G
- количество символов и грамматика соответственно, но их возможно опускать, если это не вызовет недоразумений.
ОПР:
KC- грамматика
G
=(
N
,
E
,
P
,
S
) называется
LL
(k)-грамматикой для некоторого фиксированного k, если из существования двух левых выводов
(1)
S
Юw
Aa`
Ю
wb`a`
Юwx
S
Юw
Aa`
Ю
wc`a`
Юwy
для которых FIRST(
x
)=FIRST(
y
), вытекает что
b`
=
c`
.
Иначе это определение выражает то, что для имеющейся цепочки и зная следующие k символов можно применить не более одного правила вывода. Грамматика называется
LL
- грамматикой, если она
LL
(k)- грамматика для некоторого k.
ПРМ:
Пусть
G
состоит из правил
S
®
aAS
|
b
,
A
®
a
|
bSA
. Интуитивно
G
является
LL
(1)- грамматикой, потому что, коль скоро дан самый левый нетерминал
С
в левовыводимой цепочке и следующий входной символ
с
, существует не более одного правила, применимого к
С
и приводящего к терминальной цепочке, начинающейся символом
с
. Переходя к определению
LL
(1)- грамматики, мы видим, что если
S
Ю
wSa`
Ю
wb`a`
Ю
wx
и
S
Ю
wSa`
Ю
wc`a`
Ю
wy
и цепочки
x
и
y
начинаются одним и тем же символом , то должно быть
b`
=
c`
. В данном случае если
x
и
y
начинаются символом
a
, то в выводе участвовало правило
S
®
aAS
и
b`
=
c`
=
aAS
. Альтернатива
S
®
b
здесь невозможна. С другой стороны, если
x
и
y
начинаются с
b
, то должно применяться правило
S
®
b
и
b`
=
c`
=
b
. Заметим, что случай
x
=
y
=e здесь невозможен, так как из
S
в грамматике
G
не выводится e.
Когда рассматриваются два вывода
S
Ю
wAa`
Ю
wc`a`
Ю
wy
рассуждение аналогично. Грамматика
G
служит примером так называемой простой
LL
(1)- грамматики (или разделенной грамматики).
ОПР:
КС-грамматика
G
=(
N
,
E
,
P
,
S
) без e-правил называется простой
LL
(k) - грамматикой ( или разделенной грамматикой ), если для каждого
A
О
N
все его альтернативы начинаются различными терминальными символами.
Предсказывающие алгоритмы разбора.
Разбор для
LL
(k)-грамматики очень удобно осуществлять с помощью так называемого k- предсказывающего алгоритма разбора. k-предсказывающий алгоритм использует входную ленту, магазин и выходную ленту. Алгоритм пытается проследить вывод цепочки, записанной на его входной ленте. При чтении анализируемой цепочки входная головка может "заглядывать" вперед на очередные k символа. Эти символы называют аванцепочкой. Алгоритм имеет конфигурацию представляемую тройкой (x,Xa,
n
), где
x - неиспользованная часть входной цепочки
Xa - цепочка в магазине и Х - верхний символ
n
- цепочка на выходной ленте
Работой k- предсказывающего алгоритма руководит управляющая таблица, которая задает соответствие между множеством
{(верхний символ магазина)Х(аванцепочка)}
и множеством
(правая часть правила и его номер).
Алгоритм является корректным для грамматики, если для любой цепочки из этой грамматики алгоритм позволяет получить упорядоченный список правил для ее разбора. Если работой некоего алгоритма руководит какая-то таблица и этот алгоритм оказывается корректным для рассматриваемой грамматики, то таблицу называют корректной.
ПРМ:
Пусть дана грамматика с правилами :
S
®
aAS
S
®
b
A
®
a
A
®
bSA
Для такой грамматики будет построена таблица:
аванцепочка
Апрель (48)
Март (20)
Февраль (988)
Январь (720)
Январь (21)
2012 © Все права защищены
При использовании материалов активная
ссылка на источник
обязательна.