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

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

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

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

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

Пример 6.2:

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

Матрица предшествования:

Рис. 6.4.

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



>

,,,

Рис. 6.5.

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

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

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

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

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