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

Иначе это определение выражает то, что для имеющейся цепочки и зная следующие 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- предсказывающего алгоритма руководит управляющая таблица, которая задает соответствие между множеством {(верхний символ магазина) Х (аванцепочка) } и множеством {(правая часть правила и его номер) |ошибка|выброс|допуск}.

Алгоритм является корректным для грамматики, если для любой цепочки из этой грамматики алгоритм позволяет получить упорядоченный список правил для ее разбора. Если работой некоего алгоритма руководит какая-то таблица и этот алгоритм оказывается корректным для рассматриваемой грамматики, то таблицу называют корректной.

ПРМ: Пусть дана грамматика с правилами: (1) (1) ®aAS (2) (2) ®b (3) (3) ®a (4) (4) ®bSA Для такой грамматики будет построена таблица: аванцепочка a b e верхний S aAS, 1 b, 2 ошибка символ A a, 3 bSA, 4 ошибка магазина a выброс ошибка ошибка b ошибка выброс ошибка $ ошибка ошибка допуск По такой таблице будет проведен анализ: (abbab, S$, e) |-(abbab, aAS$, 1) |-(bbab, AS$, 1) |-(bbab, bSAS$, 14) |-(bab, SAS$, 14) |-(bab, bAS$, 142) |-(ab, AS$, 142) |-(ab, aS$, 1423) |-(b, S$, 1423) |-(b, b$, 14 232) |-(e, $, 14 232) k предсказывающий алгоритм разбора КС-грамматики G можно моделировать на детерминированном МП-преобразователе с концевым маркером на входной ленте. Так как входная головка МП-преобразователя может обозреть только один входной символ, аванцепочка должна храниться в конечной памяти управляющего устройства. Остальные детали моделирования очевидны.