Нисходящий синтаксический анализатор с возвратом.

Алгоритм:

 

Содержит 4 переменные:

 

S – {f,b} f-вперед; b-назад;

Х – исходный текст программы;

L – входной магазин (стек) (расположена синтенциальная формула, выведена из начального символа к текущему шагу);

- выходной магазин (использованное для вывода правила грамматики).

 

На вход подается входная строка Х и грамматика

(f,x,б,e) б-начальный символ грамматики;

 

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

-вершина, в ней нетерминал (вершина входного магазина находится слевав);

2.

а- поместили в выходной магазин

- в вершине магазина находится терминал и он совпадает с 1-м символом входной строки.

 

3.

- входная строка пуста и входной магазин пуст

- содержит левосторонний вывод входной цепочки.

 

4.

- переходим в состояние возврата, с этого момента начинается возврат.

 

5. Возврат по входной строке.

 

- у выходного магазина вершина справа – терминал.

 

6.

- выходной магазин пустой, входной содержит 1-ый символ грамматики;

- входная строка не принадлежит языку или программа записана с ошибкой, вывод построить нельзя.

 

7. а).

-номер какого-то правила, либо может быть терминал.

 

Если такого правила нет, то:

б).

 

Пример:

 

правило

На вход ab

-начальное состояние

- если уберем все терминалы, то оставшиеся правила дают вывод:

- левосторонний вывод.

 

Нисходящий анализатор без возвратов (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)