КАТЕГОРИИ:
Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)
Отношения предшествования
 |
Вспомним восходящий разбор. При применении любых из методов восходящего разбора возникает вопрос, как найти основу и выяснить, к какому нетерминалу нужно её приводить Мы рассмотрим этот вопрос для определённого класса грамматик называемых грамматиками простого предшествования (грамматики класса 2 по Холмскому или LL1 грамматики).
Как же найти основу, если задача сентенциальная форма x? Хотелось бы, двигаясь слева направо и по любым только двум соседних символам, одновременно суметь определить: нашли ли мы хвост основы. А затем, двигаясь назад к левому концу сентенциальной формы, найти голову основы, опять принимая каждый раз решение только по двум соседним символам.
Пусть U, C, D - нетерминальные символы, x, y, z, w – любые цепочки, возможно пустые.
Грамматикой предшествования называют грамматику, в которой:
1) Для каждой упорядоченной пары терминальных и нетерминальных символов выполняется не более, чем одно из трёх отношений предшествования, определяемых следующим образом:
А) Si 
Sj, если и только есть 
правило U -> xSiSjy
Б) Si 
Sj, если и только есть правило U->xSiDy и вывод D=>*Sjz.
В) Si Sj, если и только есть правило U->x c Sjy и вывод С=>*zSi или правило U ->x c Dy и выводы С=>*zSi; D=>*Sjw.
Заметим, что между любыми двумя (2) соседними символами Si и Sj приводимой строки могут существовать лишь 3 отношения:
Si Si, если символ Si – самый левый символ некоторой основы Si Sj…
Si- основа
Si 
Si+1, если символ Si - самый правый символ основы …Si Si+1. (…Si - основа)
S+ 
Si+1, если символы Si и Si+1 принадлежат одной основе … SiSi+1… - основа
Отношения предшествования зависят от порядка, в котором стоят символы и из Si Sj не следует Sj Si.
2) Разные порождающие правила имеют различные правые части.
|
|
|
Первое условие обеспечивает единственность отношения предшествования для каждой упорядоченной пары соседних символов в приводимой строке. Если между какими-либо двумя символами нет отношения предшествования, то это означает, что они не могут находиться рядом ни водном элементе разбора синтаксически правильной сентенциальной формы. Второе условие обеспечивает однозначность редукций.
|
|
|
|
|
Дата добавления: 2014-01-11; Просмотров: 1884; Нарушение авторских прав?; Мы поможем в написании вашей работы!