Генерация ОПС для арифметических выражений

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

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

При этом надо учесть, что терминальные символы в КС-грамматике на самом деле являются лексемами, распознаваемыми лексическим анализатором. Некоторые из лексем, например имена переменных и константы, содержат дополнительную семантическую информацию – ссылки на таблицы переменных или таблицы констант, т.е. одинаковые терминальные символы в КС-грамматике семантически могут различаться.

Удобнее всего показать использование семантической таблицы на примере.

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

Табл. 13 в каждой клетке содержит действия LL(1)-анализатора, а ниже – синхронно выполняемые с ними семантические действия по генерации ОПС. В них знаком □ отмечены пустые действия, символом a – запись в ОПС операнда из входной цепочки (переменной или константы), символы + и * обозначают запись в ОПС знаков операций. Сами эти действия будут выполняться в момент выталкивания их из дополнительного магазина.

Табл. 13

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

Так как одинаковые терминальные символы a в КС-грамматике семантически могут различаться, будем во входной цепочке различные операнды обозначать разными символами: a, b и др., при этом все они будут соответствовать одному и тому же терминальному символу a. При этом операнды могут быть как именами переменных, так и константами.

Лексический анализатор, непосредственно анализирующий входную цепочку символов, на каждом шаге работы LL(1)-анализатора выдает ему тип лексемы. Если эта лексема – имя, а в магазине верхний символ a, то анализатор ищет это имя в таблице переменных, и если оно там будет найдено, то генерируется в ОПС тип переменной и ее номер в таблице. Если же такого имени в таблице нет, то это ошибка в анализируемом тексте программы, и анализатор должен выдать об этом диагностическое сообщение. Если очередная лексема – константа, то ее значение записывается в таблицу констант, а ее тип и номер в таблице констант генерируется в ОПС.

Пример работы LL(1)-анализатора с генерацией ОПС для входной цепочки a*(c + d) _┴ представлен в табл. 14.

Табл. 14

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

Рассмотренная грамматика простых арифметических выражений позволяет задавать формулы не только с операциями + и *, но и с некоторыми другими операциями. Тогда под обозначением + надо понимать и другие операции с таким же приоритетом, в частности, операцию – (минус), а под обозначением * еще и операцию / (делить). Заметим, что в заданной грамматике операция + имеет меньший приоритет, чем операция *. При этом конкретная операция, которая генерируется в ОПС, должна переписываться из анализируемой цепочки в дополнительный магазин, а уже оттуда – в ОПС.

Эту грамматику можно расширить для того, чтобы можно было записывать унарные операции (+ и –) перед операндом. Для этого достаточно добавить еще один нетерминал и порождающие правила:

F → +G

G → (S) | a

При работе анализатора по правилу F → +G в магазин следует записывать цепочку: +G□, а в дополнительный магазин: □□+, где под знаком + следует понимать группу унарных операций (+ и –), которые должны отличаться от бинарных.

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

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

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

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

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