6.3. Грамматики предшествования Флойда

Отношения предшествования в грамматиках операторного предшествования Флойда определяются только между терминальными символами, причём в правилах вывода не допускаются два рядом стоящих нетерминала: .

Алгоритм свертки по Флойду включает те же пункты, что и алгоритм свертки по Вирту.

В грамматике по Флойду множество левых и правых символов определяется следующим образом:

Отношения предшествования между любыми терминальными символами S1 и S2 определяются следующим образом:

Пример 6.2

Матрица предшествования: S  ( S1/S2 [ ]  + S  ( <· <· A <· <· B ) [ <· <· <· ] ·> ·> ·> ·> ·>  ·> ·> ·> ·> + ·> ·>		+	*	a.z	(	)
		<·	<·	<·	<·
+	·>	·>	<·	<·	<·	·>
*	·>	·>	·>	<·	<·	·>
a..z	·>	·>	·>			·>
(		<·	<·	<·	<·
)	·>	·>	·>			·>

Матрица предшествования представлена на рис. 6.4.

Рис. 6.4

Выполним свертку по Флойду цепочки -



>

,,,

Рис. 6.5

Таким образом, можно сделать вывод, что цепочка принадлежит языку.

По сравнению с грамматикой Вирта, в грамматиках по Флойду матрица предшествования гораздо меньше, но алгоритм свертки работает гораздо дольше из-за необходимости перебора всех правил вида A. Ошибки при свертке про Флойду возникают в следующих случаях:

если между двумя символами, стоящими рядом на одном из шагов вывода цепочки, нет отношения предшествования;

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

Введение семантики в грамматику по Флойду осуществляется так же, как в грамматиках по Вирту.