Студопедия
Карамелька - детский развивающий канал


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

Соотношение классов КС-языков




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

 
 

Рисунок 3.7– Соотношение между различными классами КС-языков

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

Также LL-языки являются собственным подмножеством LR-языков: всякий LL-язык является одновременно LR-языком, но существуют LR-языки, которые не являются LL-языками. Поэтому LL-языки образуют более узкий класс, чем LR-языки.

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

В то же время языки простого предшествования и LL-языки несопоставимы ме­жду собой: существуют языки простого предшествования, которые не являются LL-языками, и в то же время существуют LL-языки, которые не являются языка­ми простого предшествования. Однако существуют языки, которые одновремен­но являются и языками простого предшествования, и LL-языками. Аналогичное замечание относится также к соотношению между собой языков операторного предшествования и LL-языков.

Можно еще отметить, что язык арифметических выражений над символами а и b, заданный грамматикой G({+, -, /, *, a, b}, {S, T, E}, P, S), Р = {S->S+T|S-T|T, Т->Т*Е|Т/Е|Е, E->(S)|a|b), который многократно использовался в примерах в данном учебном пособии, подпадает под все указанные выше классы языков. Из приведенных ра­нее примеров можно заключить, что этот язык является и LL-языком, и языком операторного предшествования, а следовательно, и языком простого предшествования и, конечно, LR(1)-языком. В то же время этот язык по мере изложения материала пособия описывался различными грамматиками, не все из которых могут быть отнесены в указанные классы.

Таким образом, соотношение классов КС-языков не совпадает с соотношением задающих их классов КС-грамматик. Это связано с неразрешимостью проблем преобразования и эквивалентности грамматик, которые не имеют строго форма­лизованного решения.





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


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

Лучшие изречения: Для студента самое главное не сдать экзамен, а вовремя вспомнить про него. 9099 - | 6855 - или читать все...

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

  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.228.38.35 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.


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