Студопедия


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

Соотношение классов КС-грамматик




В общем случае можно выделить правоанализируемые и левоанализируемые КС-грамматики. Первые предполагают построение левостороннего (восходящего) распознавателя, вторые — правостороннего (нисходящего). Это вовсе не значит, что для КС-языка, заданного, например, некоторой левоанализируемой грамма­тикой, невозможно построить расширенный МП-автомат, который порождает правосторонний вывод. Указанное разделение грамматик относится только к по­строению на их основе детерминированных МП-автоматов и детерминированных расширенных МП-автоматов. Только эти типы автоматов представляют интерес при создании компиляторов и анализе входных цепочек языков программирова­ния. Недетерминированные автоматы, порождающие как левосторонние, так и правосторонние выводы, можно построить в любом случае для языка заданного любой КС-грамматикой, но для создания компилятора такие автоматы интереса не представляют.

На рис. 3.6 изображена условная схема, дающая представление о соотношении классов левоанализируемых и правоанализируемых КС-грамматик

Рисунок 3.6 - Соотношение классов левоанализируемых и правоанализируемых КС-грамматик

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

Следует помнить также, что все упомянутые классы КС-грамматик - это счет­ные, но бесконечные множества. Нельзя построить и рассмотреть все возмож­ные левоанализируемые грамматики или даже все возможные LL(1)-грамматики. Сопоставление классов КС-грамматик производится исключительно на основе
анализа структуры их правил. Только на оснований такого рода анализа произвольная КС-грамматика может быть отнесена в тот или иной класс (или не­
сколько классов).

Рассмотренный в данном посо­бии класс левоанализируемых LL-грамматик является собственным подмноже­ством класса LR-грамматик: любая LL-грамматика является LR-грамматикой, но не наоборот — существуют LR-грамматики, которые не являются LL-грамма-тиками. Значит, любая LL-грамматика является правоанализируемой, но существуют также и другие левоанализируемые грамматики, не попадающие в класс правоанализируемых грамматик.

Любой детерминированный КС-язык может быть задан, например, LR(1)-грамматико, но в то же время, классы левоанализируемых и правоанализируемых грамматик несопоставимы, то напрашивается вывод: один и тот же детерминированный КС-язык может быть задан двумя или более несопоставимыми между собой грамматиками. Та­ким образом, можно вернуться к мысли о том, что проблема преобразования КС-грамматик неразрешима (на самом деле, конечно, наоборот: из неразрешимости проблемы преобразования КС-грамматик следует возможность задать один и тот же КС-язык двумя несопоставимыми грамматиками).





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


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

Лучшие изречения: Увлечёшься девушкой-вырастут хвосты, займёшься учебой-вырастут рога 8694 - | 6847 - или читать все...

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

  1. III Соотношение ПН с другими видами контроля и надзора
  2. Агрессивная внешняя политика правящих классов Японии. Японо-китайская война 1894—1895 гг
  3. Бесклассовая адресация IPv4
  4. Библиотеки классов
  5. В общем случае связь между напряженностью и потенциалом поля тяготения выражается соотношением
  6. В системе MATLAB определено шесть базовых типов данных, каждый из которых является многомерным массивом. Шесть классов - это double, char, sparse, uint8, cell, и struct
  7. Валютный рынок и валютные курсы. Соотношение номинального и реального валютного курса. Плавающий и фиксированный курс валюты
  8. ВВП, способы их измерения. Соотношение показателей в системе национальных счетов
  9. Взаимодействие (соотношение) международного и национального права
  10. Взаимосвязь и соотношение между аптечным и промышленным производством лекарств
  11. Взрывоопасные зоны делятся на 6 классов: В1, В1а, В1бы, В1г, ВІІ, ВІІа; пожароопасные — на 4 классы: П-1, П-ІІ, П-ІІа, П-ІІІ
  12. Взрывоопасные зоны делятся на 6 классов: В1, В1а, В1бы, В1г, ВІІ, ВІІа; пожежонебезпечні — на 4 классы: П-1, П-ІІ, П-ІІа, П-ІІІ


 

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


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