Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 40 стр.

                                                                        40
            7. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ
     Грамматики типа 3 (регулярные) удобны для генерирования символов,
которые создаются во время лексического анализа, но они не очень подходят
для описания способов объединения этих символов в предложения типичных
языков высокого уровня. Например, как уже отмечалось выше, согласование
скобок нельзя специфицировать с помощью грамматики типа 3. КС-
грамматики (типа 2), хотя и не могут специфицировать все свойства
типичных языков программирования, являются более универсальными и
поэтому более пригодными в качестве основы для фазы синтаксического
анализа (разбора) компиляции.
     КС-грамматики            традиционно   служат   основой   для    фазы
синтаксического           анализа   компиляции.   Если   какой-либо   язык
программирования нельзя генерировать с помощью КС-грамматики, всегда
можно найти такую КС-грамматику, которая генерирует надмножество
языка, т.е. язык, включающий в себя заданный язык программирования.
     Применение такой грамматики для синтаксического анализа означает,
что ряд ограничений в реальном языке (например, обязательное объявление
всех идентификаторов в программе) не будет проверяться анализатором.
Однако в компиляторе нетрудно предусмотреть другие действия по
выполнению необходимых проверок в исходной программе (например, за
счет применения таблицы символов).
     Из определения КС-грамматики ясно, что класс КС-грамматик более
мощный (т.е. может генерировать больше языков), чем класс регулярных
грамматик, но менее мощный, чем класс контекстно-зависимых (КЗ-
грамматик). Язык
     { an b n | n ≥ 0 }
     является контекстно-свободным, но не регулярным. Он генерируется
грамматикой с порождающими правилами
     S → aSb | ε
     С другой стороны, язык