Стартовая страница G l o s s a r y   C o m m a n d e r

Служба тематических толковых словарей

glossary.ru
park.glossary.ru
Служебная библиотека
 н а  п р а в а х  р е к л а м ы 

 Чтение: 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  | 10  | 11  | 12  | 13  | 14
 
В.А.Серебряков, С.Ю.Соловьев


ЗАДАЧА СОВМЕСТИМОСТИ СВОЙСТВ ФОРМАЛЬНЫХ ГРАММАТИК

(авторская копия статьи)
 
Серьезное
чтение
на glossary.ru
Скачать.pdf
( 0.6 Mb )
© В.А.Серебряков, С.Ю.Соловьев, 2012 Оригинал
Образец цитирования
Серебряков В.А., Соловьев С.Ю. Задача совместимости свойств формальных грамматик. // Информационные процессы, том 12, No. 4, 2012. C. 408-437
Рассматривается формальная постановка задачи существования контекстно-свободных грамматик, обладающих заданным набором свойств. Сформулированы достаточные условия разрешимости задачи. Исследованы шесть классов и девять свойств, для которых установлена возможность их совмещения в одной грамматике.
1. ВВЕДЕНИЕ
В известной монографии Ахо и Ульмана [1] упоминаются более шестидесяти свойств/характеристик формальных грамматик; грамматики бывают "автоматные", "без e-правил", "общего вида" и т.д. В широком смысле под свойством грамматики понимается ее принадлежность заранее определенному классу. После выхода монографии прошло 40 лет, наука шагнула далеко вперед, и количество изученных классов увеличилось кратно. Исподволь, но настойчиво стала заявлять о себе проблема совместимости в одной грамматике нескольких свойств. Скажем, левая факторизация способна породить цепные правила вывода [1], а устранение цепных правил вывода может потребовать повторной левой факторизации, и т.д. Есть ли выход из этого круга? Можно ли надеяться на существование грамматик, не имеющих цепных правил и не требующей левой факторизации? Этот конкретный вопрос для пары свойств подводит к постановке общей задачи совместимости.
2. МОДЕЛЬ СОВМЕСТИМОСТИ СВОЙСТВ
3. МНОЖЕСТВО КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК
3.1 Наименования правил и символов
3.2 Подвиды КС-грамматик
3.3 Кросс-функционал
4. СВОЙСТВА КС-ГРАММАТИК
4.1 Грамматики без цепных правил
4.2 Грамматики без бесполезных символов
4.3 Грамматики без нерекурсивных нетерминалов
4.4 Грамматики без синонимов
4.5 Грамматики без протых нетерминалов
4.6 Грамматики без ЛНФ-нетерминалов
4.7 Грамматики без ПНФ-нетерминалов
4.8 Грамматики без делимых слева нетерминалов
4.9 Грамматики без делимых справа нетерминалов
5. НОРМАЛЬНЫЕ ФОРМЫ КС-ГРАММАТИК
6. ЗАКЛЮЧЕНИЕ
ПРИЛОЖЕНИЕ A. КС-ГРАММАТИКИ БЕЗ СИНОНИМОВ
A.1 Дополнительная терминология деревьев вывода
A.2 Универсальный подход к устранению синонимии
A.3 Специальный подход к устранению синонимии
A.4 Общий подход к устранению синонимии
A.5 Особенности КС-грамматик без синонимов
ПРИЛОЖЕНИЕ B. УСТРАНЕНИЕ ДЕЛИМЫХ НЕТЕРМИНАЛОВ
B.1 Устранение делимых-слева нетерминалов
B.2 Устранение делимых-справа нетерминалов

СПИСОК ЛИТЕРАТУРЫ
  1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. тт. 1,2. - М.: Мир, 1978.
  2. Соловьев С.Ю. Эквивалентные преобразования контекстно-свободных грамматик. // Информационные процессы, 2010, том 10, No.3, стр.292-302.

    www.park.glossary.ru/serios/read_10.php

  3. Мальцев А.И. Алгебраические системы. - М.: Наука, 1970.
  4. Серебряков В.А. Теория и реализация языков программирования. - М.: Физматлит, 2012.
  5. Соловьев С.Ю. Нормализация контекстно-свободных грамматик для целей грамматического вывода. // Труды XII национальной конференции по искусственному интеллекту с международным участием КИИ-2010. - М.: Физматлит, 2010, том 1, стр.218-224.

    www.park.glossary.ru/serios/read_09.php



П|р|о|д|о|л|ж|е|н|и|е ►



Copyright ©
2000-2014
Web-and-Press


webadmin@glossary.ru