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

ТРМ: Пусть, А — k- предсказывающий алгоритм разбора для КС-грамматики G. Тогда существует такой детерминированный МП- преобразователь, который позволяет разобрать любую цепочку из этой грамматики. Иначе говоря, можно промоделировать любой алгоритм на указанном преобразователе.

СЛВ: Пусть, А — k- предсказывающий алгоритм разбора для КС-грамматики G. Тогда для G существует детерминированный левый анализатор.

Следствия определения LL (k) -грамматики.

Покажем что для каждой LL (k) -грамматики можно механически построить корректный k- предсказывающий алгоритм разбора. Так как ядром алгоритма является управляющая таблица, надо показать, как строить по грамматике такую таблицу. Для этого выведем некоторые следствия определения LL (k) -грамматики.

В определении LL (k) -грамматики утверждается, что для данной выводимой цепочки wAa цепочка w и непосредственно следующие за ней k входных символов однозначно определяют, какое применить правило для развертки нетерминала A. Поэтому на первый взгляд может показаться, что для определения нужного правила надо помнить всю цепочку w. Однако это не так. Докажем теорему, очень важную для понимания LL (k) -грамматик: ТРМ: КС-грамматика G=(N, E, P, S) является LL (k) -грамматикой тогда и только тогда, когда для двух различных правил A®b` и A®c` из P пересечение FIRST (b`a`) ЗFIRST (c`a`) пусто для всех таких wAa`, что SЮwAa`.

ДКВ: Необходимость. Допустим, что w, A, a`, b` и c` удовлетворяют условиям теоремы, а FIRST (b`a`) ЗFIRST (c`a`) содержит x. Тогда по определению FIRST для некоторых y и z найдутся выводы SЮwAa`Юwb`a`Юwxy и SЮwAa`Юwc`a`Юwxz. (Заметим, что здесь мы использовали тот факт, что N не содержит бесполезных терминалов, как это предполагается для всех рассматриваемых грамматик.) Если |x| < k то y = z = e. Так как b` ¹ c`, то G не LL (k) — грамматика.

Достаточность. Допустим, что G не LL (k) грамматика. Тогда найдутся такие два вывода SЮwAa`Юwb`a`Юwx и SЮwAa`Юwc`a`Юwy, что цепочки x и y совпадают в первых k позициях, но b`¹c`. Поэтому A®b` и A®c` - различные правила из P и каждое из множеств FIRST (b`a`) и FIRST (c`a`) содержит цепочку FIRST (x) совпадающую с FIRST (y). ЧТД.

ПРМ: Грамматика G из правила S®aS|a, не будет LL (1) -грамматикой, так как FIRST1(aS) =FIRST1(a) =a. Это можно объяснить так — видя только первый символ цепочки мы не можем определить какое правило необходимо применить (левое или правое). С другой стороны эта грамматика является LL2(k) грамматикой — что вполне очевидно.