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

                                                                              23
                 ( ) ) ) ( ( ( ) – не соответствует правилу 1.
      Не существует способа представления этого языка с помощью
регулярного выражения или его генерирования с помощью грамматики типа
3. Однако этот язык генерируется следующей контекстно-свободной
грамматикой:
                 S → (S)
                 S → SS
                 S→ε
      В большинстве    языков     программирования и языков описания
аппаратуры имеются пары скобок, которые необходимо согласовывать,
например:
( ) , [ ] , begin end
      каждой открывающей скобке должна соответствовать закрывающая.
Так
      begin () end – правильно
      begin (end) – неправильно
      Контекстно-свободная     грамматика       позволяет        специфицировать
подобные ограничения. Как правило, большая часть синтаксиса языков
программирования и специализированных языков САПР описывается с
помощью КС-грамматики. Однако у большинства языков есть некоторые
свойства, которые нельзя выразить с помощью КС-грамматики. Например,
присваивание X:=Y может быть допустимым, если объявлено, что X и Y
имеют соответствующие типы, или недопустимым при несоответствии
типов. Условие такого вида не может быть специфицировано КС-
грамматикой, и компиляторы обычно выполняют проверку типа не на фазе
формального синтаксического анализа. Однако идею КС-грамматики можно
расширить, включив некоторые контекстно-зависимые свойства языков.
      Двухуровневые грамматики (W-грамматики, названной так в честь
их изобретателя – А. ван Вейнгаардена). Идея применения двухуровневой
грамматики состоит в том, что если правила обычной грамматики