|
LL(k)-грамматики
Для начала предположим, что
). Тогда
существует единственная последовательность левовыводимых цепочек b S - левый разбор
цепочки w. Допустим, что мы хотим найти этот левый разбор, просматривая w
один раз слева направо. Можно попытаться сделать это, строя последовательность
левовыводимых цепочек b ajAB, то к данному моменту анализа мы уже
прочли первые j входных символов и сравнили их с первыми j символами цепочки bi.
Было бы желательно определить bi+1 aj (часть входной цепочки, считанную к
данному моменту), несколько следующих входных символов (aj+1 Если эти три фактора
однозначно определяют, какое правило надо применить для развертки нетерминала A,
то ai+1 (k)-
грамматикой. Мы увидим, что для каждой (k)- грамматики можно построить
детерминированный левый анализатор, работающий линейное время. Дадим несколько
определений : ), что x E*, а b либо начинается нетерминалом, либо пустая
цепочка. Будем называть x законченной частью цепочки a, а b - незаконченной
частью частью. Границу между x и b будем называть рубежом. Пусть
x=abacAaB, тогда abac - законченная часть цепочки x, AaB - незаконченная часть
цепочки. Если x=abc, то abc - законченная часть и (k) - грамматики
можно объяснить так: если имеется уже разобранная часть цепочки, то на основании
этого и еще нескольких неразобранных символов мы можем сделать вывод о том,
какое правило неоюходимо применить. Таким образом грамматика посуществу не
зависит (не считая k последующих символов) от того, что выводится из
незаконченной части цепочки. В терминах деревьев этот процесс выглядит следующим
образом: дерево вывода цепочки строится начиная с корня и детерминировано сверху
вниз. - количество символов и грамматика
соответственно, но их возможно опускать, если это не вызовет
недоразумений. (k)-
грамматикой для некоторого фиксированного k, если из существования двух левых
выводов wb`a` Aa` для которых
FIRST( Иначе это
определение выражает то, что для имеющейся цепочки и зная следующие k символов
можно применить не более одного правила вывода. Грамматика называется состоит из правил (1)- грамматикой, потому что, коль скоро дан самый левый нетерминал
, существует
не более одного правила, применимого к (1)-
грамматики, мы видим, что если и цепочки x , то должно применяться правило
= Когда рассматриваются два вывода служит примером так называемой простой P (k) - грамматикой ( или разделенной грамматикой ), если для
каждого все его
альтернативы начинаются различными терминальными символами.
(k)-
грамматики очень удобно осуществлять с помощью так называемого алгоритма разбора. k-предсказывающий алгоритм использует
входную ленту, магазин и выходную ленту. Алгоритм пытается проследить вывод
цепочки, записанной на его входной ленте. При чтении анализируемой цепочки
входная головка может заглядывать вперед на очередные k символа. Эти
символы называют ), где Работой k- предсказывающего алгоритма руководит управляющая таблица,
которая задает соответствие между множеством {(правая часть правила и его
номер)ошибкавыбросдопуск}. Алгоритм является корректным для грамматики, если
для любой цепочки из этой грамматики алгоритм позволяет получить упорядоченный
список правил для ее разбора. Если работой некоего алгоритма руководит какая-то
таблица и этот алгоритм оказывается корректным для рассматриваемой грамматики,
то таблицу называют корректной. b ошибка ошибка , , AS$,142
можно моделировать на детерминированном МП-
преобразователе с концевым маркером на входной ленте. Так как входная головка
МП- преобразователя может обозреть только один входной символ, аванцепочка
должна храниться в конечной памяти управляющего устройства. Остальные детали
моделирования очевидны. . Тогда существует такой
детерминированный МП- преобразователь, который позволяет разобрать любую цепочку
из этой грамматики. Иначе говоря можно промоделировать любой алгоритм на
указанном преобразователе. существует
детерминированный левый анализатор. грамматики можно
механически построить корректный k- предсказывающий алгоритм разбора. Так как
ядром алгоритма является управляющая таблица, надо показать, как строить по
грамматике такую таблицу. Для этого выведем некоторые следствия определения
a цепочка w и
непосредственно следующие за ней k входных символов однозначно определяют, какое
применить правило для развертки нетерминала A. Поэтому на первый взгляд может
показаться, что для определения нужного правила надо помнить всю цепочку w.
Однако это не так. Докажем теорему, очень важную для понимания (k)-грамматикой
тогда и только тогда, когда для двух различных правил из )
пусто для всех таких wA Необходимость.
Допустим, что w, A, wxz. (Заметим, что здесь
мы использовали тот факт, что не содержит бесполезных терминалов, как
это предполагается для всех рассматриваемых грамматик.) Если x < k то y = z
= (k)- грамматика. wy, что цепочки x и y
совпадают в первых k позициях, но b` b`a` G (1)- грамматикой, так как FIRST (a)=a.
Это можно объяснить так - видя только первый символ цепочки мы не можем
определить какое правило необходимо применить (левое или правое). С другой
стороны эта грамматика является LL N b` ) как множество
терминальных символов, которые могут встречаться после нетеминала, являющегося
аргументом функции. (1)-грамматикой
тогда и только тогда, когда для двух различных правил c` c` Теорему можно
выразить следующим : по первому символу после нетерминала необходимо выбрать
применимое правило - следовательно эти символы различны и пересечение пусто. Эта
теорема может применяться к (k)- грамматикам, но не всегда выполняться.
Грамматики для которых выполняется теорема называются сильными, таким образом
все (k)- грамматика однозначна, поэтому если имеется неоднозначная
грамматика - то она не , не являющейся
(k)- грамматика. Однако в ряде случаев
такое преобразование возможно. Применяется два способа: S ).
Иными словами, мы считаем что операция конкатенации дистрибутивна относительно
операции выбора альтернативы (обозначаемой вертикальной чертой). Заменим эти
правила на : Ядром предсказывающего алгоритма является управляющая таблица.
В этом и следующих разделах будет показано как построить корректную управляющую
таблицу. Выход : Будем считать, что $-маркер
дна магазина. Таблица определяется следующим образом: a` ,i) для всех b M[a,a]=выброс для всех a В
остальных случаях M[X,a]=ошибка для X И Построим
управляющую таблицу для произвольной грамматики. Если грамматика сильная, то
можно применить предыдущий алгоритм с аванцепочками расширенными до k символов.
В противном случае возникает несколько проблем. В 1-м предсказывающем алгоритме
разбора в магазин помещались только символы из и оказывалось, что для однозначного
определения очередного применяемого правила достаточно знать нетерминальный
символ наверху магазина и текущий входной символ. Для не сильных грамматик этого
может оказаться недостаточно. Если
даны нетерминал A и аванцепочка ba, то не известно, какое из правил надо
применить. Неопределенности такого рода однако можно разрешить, связав с
каждым нетерминалом и частью левовыводимой цепочки (которая может оказаться
справа), специальный символ, называемый (k)- таблицабудет однозначно определять какое правило надо
применить на очередном шаге вывода. L 1 2 1 либо w состоит из первых k символов цепочки
xy b` ( k ) - КС- грамматика. Для каждых
A LL , соответствующую A и L, как
функцию T(u), значением которой служит : , что
FIRST k L содержит
u; не определено, если в множестве найдутся два и более правила (эту
ситуацию называют конфликтом между правилами) На нормальном языке это
означает что вырабатывается значение ошибка, если u вообще не является цепочкой
грамматики, возвращается правило если оно существует и только одно и если
несколько правил - то значение не определяется. E (k)- таблиц, необходимых
для построения управляющей таблицы для ,
соответствующую 0 (k)- таблицу T для
1 ПРМ: } . Так как
T надо включить T . Аналогично, так как T bAba,{ba}), то
в T A , отличные от значения ошибка, приведены в таблице ниже). Сейчас
T }, и алгоритм уже
не может включить в T (2)- таблицы образуют множество соответствующее
грамматике. A,{aa} u ba Теперь дадим алгоритм, которым можно
построить корректную управляющую таблицу по соответствующему множеству
(k)- таблиц. Управляемый этой таблицей k- предсказывающий алгоритм
будет в качестве магазинных символов употреблять вместо нетерминалов
{$}) , то для всех u, для которых T 0 ...Bmxm,<Y ,u]=(x Построим управляющую таблицу
для (2)-таблиц, найденное в предыдущем примере. Алгоритм должен
выдать таблицу: ba aT выброс =T . Подразумевается,
что в пустых ячейках - ошибка. Допуск* находится в последней колонке. Для
входной цепочки bba 2-предсказывающий алгоритм выдаст такую последовательность
тактов: (ba,ba$,24) (k)- грамматики
) корректную таблицу, управляющую
работой соответствующего k- предсказывающего алгоритма. ® (2)-
таблицы. Начнем с T . Затем по T0 найдем T , далее T T S A aa По этим таблицам построим
управляющую таблицу: bb ,1
-
(aa,T Число шагов, выполняемых k- предсказывающим
алгоритмом с управляющей таблицей, построенной предыдущим алгоритмом по
G (k)- грамматика? (1)- грамматика,
то существует ли эквивалентная ей К сожалению, только для первого
вопроса есть отвечающий на него алгоритм. Можно показать, что вторая и третья
проблемы алгоритмически не разрешимы, но это доказательство не приводится.
Приведем алгоритм проверки N (k)- грамматика и Нет в
противном случае. Суть алгоритма сводится к следующему: Для
каждого нетерминала, имеющего два или более правила раскрутки вычисляется
пересечение первых k- символов всех возможных цепочек раскрутки. Если это
множество пусто, то переходят к следующему терминалу, иначе заканчивают со
значением Нет . Если все пересечения пусты - заканчивают со значением
Да . Для получения пересечения двух правил можно воспользоваться
записью: (FIRSTk( ) -
цепочка символов после терминала.
| |
