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

                                                                     21
генерации языка можно использовать несколько грамматик, то тип языка
соответствует грамматике с наибольшим типом.
     Иерархия Хомского важна с точки зрения построения трансляторов с
различных языков. Чем меньше ограничений в грамматике, тем сложнее
ограничения, которые можно наложить на генерируемый язык. Чем более
универсален класс используемой грамматики, тем больше свойств языка мы
можем описать. Однако чем более универсальна грамматика, тем сложнее
должна быть программа, распознающая строки соответствующего языка.
     Грамматики типа 3 можно использовать для описания некоторых
свойств языков программирования или высокоуровневых языков описания
аппаратуры. Например, для генерирования идентификаторов по определению
многих языков программирования можно воспользоваться следующими
правилами:
             I→l                               R→d
             I→lR                              R→lR
             R→l                               R→dR
где буква (l) и цифра (d) обозначают терминалы (для краткости будем
считать так, потому что перечисление всех возможных букв и цифр
потребовало бы написания слишком большого числа правил). Иногда удобно
объединять правые части правил, имеющих одинаковые левые части.
Вышеприведенную грамматику можно также записать в виде:
                 I→l|lR
                 R→l|d|lR|dR
     Вертикальную черту здесь надо понимать как "или".
     Многие "локальные" средства языков программирования, например
константы, ключевые слова языка и строки, представляются с помощью
грамматик типа 3. Некоторые очень простые языки описания аппаратуры
также можно описать с помощью регулярной грамматики. Однако
грамматики типа 3 генерируют только строго ограниченные типы языков –
регулярные выражения.