Ll(1) - грамматики

Наиболее просто данный анализатор строится для LL(1) грамматики. Таблица анализа для данной грамматики не имеет множественных записей. L – просмотр входного потока слева направо, L – левое порождение (вывод), (1) – просмотр одного символа из входного потока на каждом шаге для принятия решения о дальнейшем действие.

Примечание: имеются грамматики, которые нельзя привести к LL(1).

Пример:

Построим анализатор, работающий с грамматикой LL(1).

Имеется грамматика

и цепочка: .

Конфигурация, описывающая состояние анализатора в общем виде: , где - содержимое магазина; - необработанная часть цепочки (a - текущий символ); - построенный к данному моменту разбор.

1. Из S порождаем цепочку. Так как первым в является символ a, то используем продукцию 1). Получаем: .

2. В вершине магазина находится терменальный символ a. Так как он совпадает с первым символом , можно его вычеркнуть и продолжить анализ ().

3. Текущий символ входной цепочки – c. В вершине магазина - A, поэтому выбираем правило 3). Таким образом получим: .

Дальнейший анализ заполнен в таблице:

№ шага	Входная цепочка		Магазин	Действие
	вычеркнутое	оставшееся
1		accedd	S	правило 1).
2		accedd	aA	вычеркнуть a
3	a	ccedd	A	правило 3).
4	a	ccedd	cAd	вычеркнуть c
5	ac	cedd	Ad	правило 3).
6	ac	cedd	cAdd	вычеркнуть c
7	acc	edd	Add	правило 4).
8	acc	edd	edd	вычеркнуть e
9	acce	dd	dd	вычеркнуть d
10	acced	d	d	вычеркнуть d
11	accedd			цепочка допускается

КС – грамматика без – правил называется простой LL(1) (или S – грамматикой или разделенной грамматикой), если все его альтернативы начинаются различными терминальными символами.

Введем ряд определений:

FIRST (A) – это множество терменальных символов, которыми начинаются цепочки, выводимые из терминала A:

FOLLOW (A) – это множество терменальных символов, которые могут встретиться непосредственно справа от нетерменала A в некоторой цепочке:

и

Пример:

SELECT – это множество выбора правил. Оно определяется:

1. eсли , то;

2. если , то.

LL(k) – грамматика.

КС – грамматика является LL(1), тогда и только тогда, когда для двух различных правил A→β, А→γ Р пересечение при всех таких wАα, что S * wАα.

Мощности LL(1)-грамматик недостаточно, чтобы описать синтаксис любых языков программы. Естественным обобщением LL(1)-грамматик является LL(k) – грамматика. Для этого введем обобщение множеств FIRST(α) множество Оно представляет собой множество терминальных префиксов длины k терминальных цепочек, выводимых из α (или меньшей длины, если выводимые цепочки меньше k). Аналогично определяем FOLLOW_k(A).

LL(k) применяются на практике редко из-за сложности.

1-предсказывающий алгоритм разбора.

Работой алгоритма управляет управляющая таблица M, которая задает отображение множества множество, состоящее из следующих элементов:

1) (β,i), βV_p*, (V_p – это алфавит магазинных символов без символа дна ⊥); β – правая часть правила вывода с номером i;

2) “Выброс”. В этом случае удаляется верхний символ магазина, читающая головка сдвигается на один символ вправо, выходная лента не изменяется.

3) Может быть слово “Допуск” . В этом случае значение в таблице должно иметь вид: пустой магазин, пустая строка M(⊥,ε).

4) Ошибка – в таблице ячейка ничем не заполняется.

Пример:

Есть грамматики :

1. E→TE’

2. E’→+TE’

3. E’→ε

4. T→PT’

5. T’→*PT’

6. T’→ε

7. P→(E)

8. P→i

Таблица строится так:

Имеется 11 строк: {N}={E,E’,T,T’,P,+,*,i,(,),⊥};

Имеется 6 столбцов: {i,(,),+,*,ε}=Σε

	i	(	)	+	*	ε
E	TE’,1	TE’,1
E’			ε,3	+TE’,2		ε ,3
T	PT’,4	PT’,4
T’			ε,6	ε,6	*PT’,5	ε,6
P	i,8	(E),7
i	Выброс
(		В
)			В
+				В
*					В
						Допуск

1. E→TE’

Последовательно расссмотрим все нетерминалы, т.к. FIRST(TE’)={(,i}

M(E,()=M(E,i)=(TE’,1)

2. E’→+TE’; FIRST(+TE’)={+}

M(E’,+)=(+TE’,2)

3. E’→ε, в этом случае пустая правая часть, нужно вычислить множество символов, следующих за нетерминалом E’ в выражениях, построив левый вывод, т.е.:

ETE’PT’E’→(E)T’E’→(TE’)TE’…

FOLLOW (E’)={),ε}

M(E’,))=M[E’,3]=(ε,3)

и т. д.

M(⊥,E) – допуск.

По данной таблице необходимо провести пошаговую проверку работы:

Будем проверять цепочку: i+i*i

Начальная конфигурация (i+i*i, E, ε )

Первая конфигурация: (i+i*i, TE’, 1 )

Получаем: (i+i*i, PT’E’,14 )

Проанализировать таблицу и получить допуск.