Готовые Домашние Задания

Рефераты по теме Маркетинг

Реферат LL(k)-грамматики

Скачать реферат↓ [12.25 KB]



Текст реферата 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 левый разбор цепочки 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ЮwAa`Юwb`a`Юwx (2) (2) SЮwAa`Юwc`a`Юwy для которых FIRST(x)
=FIRST(y) , вытекает что b`=c`.
Иначе это определение выражает то, что для имеющейся цепочки и зная
следующие k символов можно применить не более одного правила вывода.
Грамматика называется LL-грамматикой, если она LL(k) -грамматика для
некоторого k.
ПРМ: Пусть G состоит из правил S®aAS|b, A®a|bSA. Интуитивно G