Детерминированный LL-разбор

КС-грамматика, преобразованная к обобщенной нормальной форме Грейбах, допускает однозначный LL-разбор, если для каждой группы порождающих правил с одним и тем же нетерминалом в левой части правые части будут однозначно различимы по нескольким первым терминальным символам. В самом простом случае они должны различаться по одному символу, тогда на каждом шаге разбора проверяется на совпадение один верхний символ магазина (если он терминал) и очередной символ на входе. Такой разбор называется LL(1)-анализом, а алгоритм разбора – LL(1)-анализатором.

Будем считать, что входная цепочка символов, также как для лексического анализатора, всегда заканчивается ограничителем _┴. Для работы LL(1)-анализатора необходимо построить таблицу, в которой столбцы помечены терминальными символами (включая _┴), а строки – нетерминалами преобразованной грамматики. Для каждого из правил вида A → aγ, правая часть заносится на пересечение строки, помеченной нетерминалом A, и столбца, помеченного терминалом a. Если же правая часть правила пустая, то во все клетки строки, не занятые другими правилами, записывается λ.

До начала работы в магазин записывается ограничитель _┴, а затем начальный нетерминал. На каждом шаге анализатор проверяет, допустим ли очередной входной символ, и если да, то выполняет одно из двух действий:

1) если на вершине магазина нетерминал, то, в зависимости от того, каков очередной входной символ, этот нетерминал заменяется символами правой части соответствующего правила, причем символы записываются в обратном порядке. Если для очередного входного символа в таблице записано λ, то нетерминал удаляется из магазина, а если в таблице пустая клетка, то анализатор прекращает цикл из-за ошибочного символа во входной цепочке;

2) если на вершине магазина терминал, то он сравнивается с очередным входным символом. При совпадении терминал удаляется из магазина и делается переход к следующему символу входной цепочки. При несовпадении анализатор прекращает цикл из-за ошибочного символа во входной цепочке.

Цикл прекращается, когда входная цепочка символов оказалась вся просмотрена. Если при этом магазин пуст, то входная цепочка символов считается распознанной, если не пуст – то нераспознанной.

Пример 8. Пусть задана грамматика простых арифметических выражений, преобразованная к обобщенной нормальной форме Грейбах:

S → (S)VU | aVU

U → + TU | λ

T → (S)V | aV

V → * FV | λ

F → (S) | a

В табл. 7 приведены действия LL(1)-анализатора.

Табл. 7

	+	*	(	)	a	_┴
S			(S)VU		aVU
U	+ TU	λ	λ	λ	λ	λ
T			(S)V		aV
V	λ	* FV	λ	λ	λ	λ
F			(S)		a

Пусть на вход анализатора поступает цепочка: a * (a + a)_┴. Шаги работы анализатора представлены в табл. 8.

Табл. 8

№ шага	Входные символы	Содержимое магазина	Порождающее правило
	a*(a+a)_┴	S _┴	S → aVU
	a*(a+a)_┴	aVU _┴
	*(a+a)_┴	VU _┴	V → * FV
	*(a+a)_┴	*FVU _┴
	(a+a)_┴	FVU _┴	F → (S)
	(a+a)_┴	(S)VU _┴
	a+a)_┴	S)VU _┴	S → aVU
	a+a)_┴	aVU)VU _┴
	+a)_┴	VU)VU _┴	V → λ
	+a)_┴	U)VU _┴	U → + TU
	+a)_┴	+TU )VU _┴
	a)_┴	TU )VU _┴	T → aV
	a)_┴	aVU )VU _┴
	)_┴	VU )VU _┴	V → λ
	)_┴	U )VU _┴	U → λ
	)_┴	)VU _┴
	_┴	VU _┴	V → λ
	_┴	U _┴	U → λ
	_┴	_┴

Пусть на вход анализатора поступает ошибочная цепочка: a)_┴. Шаги работы анализатора представлены в табл. 9.

Табл. 9

№ шага	Входные символы	Содержимое магазина	Порождающее правило
	a)_┴	S _┴	S → aVU
	a)_┴	aVU _┴
	)_┴	VU _┴	V → λ
	)_┴	U _┴	U → λ
	)_┴	_┴	<ошибка>

Конец примера.

<== предыдущая страница	\|	следующая страница ==>
Преобразование КС-грамматики к обобщенной нормальной форме Грейбах	\|	Обратная польская строка для арифметических выражений

Дата добавления: 2015-07-26; просмотров: 151; Нарушение авторских прав

Мы поможем в написании ваших работ!

lektsiopedia.org - Лекциопедия - 2013 год. | Страница сгенерирована за: 0.003 сек.