Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Грамматика предшествования Флойда
|
|
Отношения предшествования в грамматиках по Флойду определяются только между терминальными символами и не допускаются в правилах вывода двух рядом стоящих нетерминалов: 
.
Алгоритм свертки по Флойду включает те же пункты, что и алгоритм свертки по Вирту.
В грамматике по Флойду множество левых и правых символов определяется следующим образом:
Отношения предшествования между любыми терминальными символами S1 и S2 определяются следующим образом:
Пример 6.2:
| ^ | + | * | a.z | ( | ) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ^ | 
| < · | < · | < · | < · | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| + | ·> | ·> | < · | < · | < · | ·> | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| * | ·> | ·> | ·> | < · | < · | ·> | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| a..z | ·> | ·> | ·> | ·> | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ( | < · | < · | < · | < · |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ) | ·> | ·> | ·> | ·> |
Матрица предшествования:
Рис. 6.4.
Выполним свертку по Флойду цепочки - 
^
>
, 
, 
, 
Рис. 6.5.
Таким образом, можно сделать вывод, что цепочка принадлежит языку.
По сравнению с грамматикой Вирта, в грамматиках по Флойду матрица предшествования гораздо меньше, но алгоритм свертки работает гораздо дольше из-за необходимости перебора всех правил вида A 
. Ошибки при свертке по Флойду возникают в следующих случаях:
1) Если между двумя символами, стоящими рядом на одном из шагов вывода цепочки, нет отношения предшествования;
2) Если для выделенной основы для свертки выполнены все переборы, а соответствующих правил для замены в грамматике нет.
Введение семантики в грамматику по Флойду осуществляется так же, как в грамматиках по Вирту.