Рассматривается формальная постановка задачи существования контекстно-свободных грамматик, обладающих заданным набором свойств. Сформулированы достаточные условия разрешимости задачи. Исследованы шесть классов и девять свойств, для которых установлена возможность их совмещения в одной грамматике.

В известной монографии Ахо и Ульмана [1] упоминаются более шестидесяти свойств/характеристик формальных грамматик; грамматики бывают "автоматные", "без e-правил", "общего вида" и т.д. В широком смысле под свойством грамматики понимается ее принадлежность заранее определенному классу. После выхода монографии прошло 40 лет, наука шагнула далеко вперед, и количество изученных классов увеличилось кратно. Исподволь, но настойчиво стала заявлять о себе проблема совместимости в одной грамматике нескольких свойств. Скажем, левая факторизация способна породить цепные правила вывода [1], а устранение цепных правил вывода может потребовать повторной левой факторизации, и т.д. Есть ли выход из этого круга? Можно ли надеяться на существование грамматик, не имеющих цепных правил и не требующей левой факторизации? Этот конкретный вопрос для пары свойств подводит к постановке общей задачи совместимости.

3.1 Наименования правил и символов

3.2 Подвиды КС-грамматик

3.3 Кросс-функционал

4.1 Грамматики без цепных правил

4.2 Грамматики без бесполезных символов

4.3 Грамматики без нерекурсивных нетерминалов

4.4 Грамматики без синонимов

4.5 Грамматики без протых нетерминалов

4.6 Грамматики без ЛНФ-нетерминалов

4.7 Грамматики без ПНФ-нетерминалов

4.8 Грамматики без делимых слева нетерминалов

4.9 Грамматики без делимых справа нетерминалов

A.1 Дополнительная терминология деревьев вывода

A.2 Универсальный подход к устранению синонимии

A.3 Специальный подход к устранению синонимии

A.4 Общий подход к устранению синонимии

A.5 Особенности КС-грамматик без синонимов

B.1 Устранение делимых-слева нетерминалов

B.2 Устранение делимых-справа нетерминалов