Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



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




Читайте также:
  1. Алгоритмы поиска кратчайших путей Дейкстры и Флойда
  2. Грамматика
  3. Грамматика
  4. Грамматика
  5. Грамматика
  6. Грамматика
  7. Грамматика
  8. Грамматика
  9. Грамматика
  10. Грамматика

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

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

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

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


Пример 6.2:

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

 

^ + * a.z ( )
^  
+ ·> ·> ·>
* ·> ·> ·> ·>
a..z ·> ·> ·>     ·>
(  
) ·> ·> ·>     ·>

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

 



Рис. 6.4.

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

^

>

 





, , ,

Рис. 6.5.

 

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

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

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

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

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

 

 


Дата добавления: 2014-11-13; просмотров: 27; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2022 год. (0.027 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты