Нисходящий анализатор без возвратов (ll(1)).

Анализатор с возвратом работает для всех грамматик, которые не являются леворекурсивными.

LL(1) анализатор можно построить для значительного более узкого числа грамматик.

- левая рекурсия.

Вывод из предыдущего примера:

Табл:

Символы

	a	B
S	1)	2)

правила

- если на входе «а», то применим 1-е правило, если на входе «b», то применяем 2-е правило.

T(A,a)=i

T-таблица

- строки помечены терминалами;

- столбцы помечены нетерминалами;

(f,x,б,e)

1. Развертка.

Если T(A,a)=i Если T(A,a)=Ø, то неудача

:

2.

- взаимное уничтожение;

3. - успех.

Неудача будет, если в таблице пустая клетка, т.е. нет i.

Не каждая грамматика является LL(1) грамматикой, иногда грамматику можно преобразовать в LL(1).

Грамматика ml для правила ll(1).

По правилу:

Z→</>/<=/>=/=/<>

Таблица с альтернативными правилами:

	.	;	id	if	while	begin	+	-	)	else	<	>..	Then	do	*	/	c	(
P1	1)	2)
S			1)	2)	3)	4)
E1	1)	1)					2)	3)	1)	1)	1)	1)	1)	1)
T1	1)	1)					1)	1)	1)	1)	1)	1)	1)	1)	2)	3)
M			1)														2)	3)
Z											1)	2)