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