Студопедия


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram

Определение грамматики операторного предшествования




ОпределениеКС-грамматика G (VN, VT, P, S) называется грамматикой операторного предшествования, если выполняются следующие условия:

1) Для каждой упорядоченной пары терминальных символов выполняется не более чем одно из трех отношений предшествования:

а) а =× b, если и только если существует правило A—>xaby ÎР или правило А->хаСbу, где a,bÎVT, A,C ÎVN, x.yÎV*;

б) а <× b, если и только если существует правило А->хаСу ÎР и вывод C=>*bz или вывод C=>*Dbz, где a,bÎVT, A,C,DÎVN, x,y,zÎV*;

в) а ×> b, если и только если существует правило А—>хСЬу ÎР и вывод C=>*za или вывод C=>*zaD, где a,bÎVT, A,C,DÎVN, x,y,zÎV*.

2) Различные правила в грамматике имеют разные правые части, e-правила от­сутствуют.

3) Правила грамматики операторного предшествования не могут содержать двух смежных нетерминальных символов в правой части, т.е. в грамматике опера­торного предшествования G(VN,VT,P,S) не может быть ни одного правила вида: А->хВСу, где A,B,CÎVN, x,yÎV* (здесь х и у — это произвольные цепочки символов, могут быть и пустыми).

3.5.1.2.2 Построение множеств Lt(A) и Rt(A)

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

Для грамматики данного вида на основе установленных отношений предшествования также строится матрица предшествования, но она содержит только терминальные символы грамматики.

Для построения этой матрицы удобно ввести множества крайних левых и крайних правых терминальных символов относительно нетерминального символаА – Lt(A) или Rt(A):

Lt(A) = {t | A=>*tz или A=>*Ctz }, где tÎVT,A.CÎVN, zÎV*;

Rt(A)= {t | A=>*zt или A=>*ztC }, где tÎVT, A,CÎVN, zÎV*.

Тогда определения отношений операторного предшествования будут выглядеть так:

а) а =× b, если правило A→xaby ÎР или правило U->xaCby, где a,bÎVT, А,СÎVN х,уÎV*;

б) а <× b, если правило А→хаСу ÎР и bÎ Lt (C), где a,bÎVT, A,CÎVN, x,yÎV*;

в) а ×> b, если правило A→xCby ÎР и aÎ Rt(C), где a,bÎVT, A,CÎVN, x,yÎV*.

В данных определениях цепочки символов x,y,z могут быть и пустыми цепочками.

Для нахождения множеств Lt(A) и Rt(A)предварительно необходимо выполнить построение множеств L(A) и R(A), как это было рассмотрено ранее. Далее для построения Lt(A) и Rt(A) используется следующий алгоритм:




Шаг 1. AÎVN:

Rt0(A){t | A→ytB или A→yt, tÎVT, BÎVN, yÎV*;

Lt0(A){t | A→Bty или A→ty, tÎVT, BÎVN, yÎV*;

Для каждого нетерминального символа А ищем все правила, содержащие А в левой части. Во множество L(A) включаем самый левый терминальный символ изправой части правил, игнорируя нетерминальные символы, а во множество R(А) - самый крайний правый терминальный символ из правой части правил. Переходим к шагу 2.

Шаг 2. AÎVN:

Rti(A) = Rti-1(A) Rti-1 (B), В Î (R(A) VN),

Lti(А) = Lti-1(A) Lti-1(B), В Î (L(A) VN).

Для каждого нетерминального символа А: если множество L(A) содержит нетерминальные символы грамматики А', А", ..., то его надо дополнить символами входящими в соответствующие множества L t(А’), L t(A"), ... и не входящими в L t(А). Ту же операцию надо выполнить для множеств R(A) и Rt(А).

Шаг З. Если AÎVN : Rti(A) Rti-1(Aили Lti(А) Lti-1(A), то i:=i+1 и вернутсяк шагу 2, иначе построение закончено: Rt(A) = Rti(A) и Lt(A) = Lti(А).

Если на предыдущем шаге хотя бы одно множество Rt(A) или Lt(A) для некоторого символа грамматики изменилось, то надо вернуться к шагу 2, иначе построение закончено.

Для практического использования матрицу предшествования дополняют символами и ( начало и конец цепочки). Для них определены следующие отношения предшествования:

<· a, aÎVT, если S=>*ax или S=>*Cax, где S,CÎVN, xÎV* или если aÎ Lt(S);



·> а, aÎVT, если S=>*xa или S=>*xaC, где S,CÎVN, xÎV* или если aÎ Rt(S).

Здесь S — целевой символ грамматики.

Матрица предшествования служит основой для работы распознавателя языка, заданного грамматикой операторного предшествования. Поскольку она содержит только терминальные символы, то, следовательно, будет иметь меньший размер, чем аналогичная матрица для грамматики простого предшествования. Следует отметить, что напрямую сравнивать матрицы двух грамматик нельзя — не всякая грамматика простого предшествования является грамматикой операторного пред­шествования, и наоборот.





Дата добавления: 2015-02-18; просмотров: 729; Опубликованный материал нарушает авторские права? | Защита персональных данных | ЗАКАЗАТЬ РАБОТУ


Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Как то на паре, один преподаватель сказал, когда лекция заканчивалась - это был конец пары: "Что-то тут концом пахнет". 7483 - | 7137 - или читать все...

Читайте также:

  1. II. 6.1. Определение понятия деятельности
  2. III. Определение мест участников
  3. III. п.1. Определение функции нескольких переменных
  4. III.6 Определение расчетных сил нажатия тормозных колодок на ось подвижного состава, учетного веса локомотивов, мотор-вагонного подвижного состава
  5. III.7 Определение необходимого количества стояночных (ручных) тормозов и тормозных башмаков
  6. А. Определение глубины заложения фундамента
  7. А. Определение чистоты культуры анаэробов в мазке по Граму
  8. Абстрактные классы: определение, назначение, примеры использования
  9. Аванкамеры и водоприемные камеры насосных станций. Назначение конструкции. Определение основных размеров аванкамер и водоприемных камер
  10. Агентский договор. Определение. Это договор о совершении одним лицом (агентом) для другого (принципала) юридических действий от своего имени либо от имени принципала
  11. Алгоритм Проверка существования языка грамматики
  12. Алгоритм «сдвиг - свертка» для грамматик простого предшествования


 

34.229.194.198 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.


Генерация страницы за: 0.003 сек.