В настоящей книге для обозначения терминалов грамматики мы будем употреблять прописные буквы (или строки прописных букв), а для обозначения не терминалов - заглавные буквы (или строки заглавных букв). Там, где может возникнуть неоднозначность в последовательностях букв, обозначающих терминалы или не терминалы, для разделения символов в правиле мы введем пробелы. Строки терминалов и/или не терминалов представим с помощью греческих букв.

Как правило, предложения языка можно генерировать посредством более чем одной грамматики; две грамматики, генерирующие один и тот же язык, называют эквивалентными. Например, G1 эквивалентна G2, определенной следующим образом:

= ({а, Ь], {S. У]. Р, S}.

где элементами Р являются

С точки зрения составителя компилятора одна грамматика может быть гораздо удобнее другой в качестве основы для фазы синтаксического анализа компиляции.

В приводимых выше примерах левые части правил всегда состояли из одного не терминала. Однако из определения грамматики вытекает, что необязательно должно быть так. Возьмем грамматику

со следующими элементами Р:

Генерироваться будет Типичный вывод;

Рассмотрев, какие роли играют N, Q и R в вышеприведенном выводе, читатель сможет убедиться в том, что генерированный язык и есть объявленный язык. Следует заметить также, что R служит для дублирования N.

Ограничим типы правил, которые могут появляться в грамматике. Это позволит нам определить ряд специальных классов грамматик. Одна из стандартных классификаций известна как иерархия Хомского. Ее можно описать следующим образом.

Любая грамматика определенного ранее вида называется грамматикой типа 0.

Если, однако, грамматика обладает тем свойством, что для всех правил вида

i«l<lP.

где а обозначает длину а, т. е. число символов в а, и то же для Р, то она называется грамматикой типа 2, или контекстно-зависимой.

Если грамматика имеет такое свойство, что все левые части состоят из одного нетерминального символа, то ее называют грамматикой типа 2, или контекстно-свободной.

В том случае, когда каждое правило грамматики имеет одну из форм

где a - терминальный символ, а А и В - нетерминальные, эту грамматику называют грамматикой типа 3, выровненной вправо, или регулярной.

Выровненная влево грамматика определяется аналогично предыдущей, т. е. все ее правила имеют одну из форм

А-а АВа

Она также называется грамматикой типа 3, или регулярной.

Очевидно, что эта иерархия - включающая, т. е. все грамматики типа 3 являются грамматиками типа 2, все грамматики типа 1 являются грамматиками типа 0 и т. д. Иерархии грамматик соответствует иерархия языков. Например, если язык можно генерировать с помощью грамматики типа 2, то его называют языком типа 2, а если с помощью грамматики типа 3,- то его называют языком типа 3. Эта иерархия - опять включающая. Включения также справедливы в том, что существуют языки, которые относятся к типу i, но не к типу (0<i<2).

Можно показать, например, что язык, генерированный посредством (Gз, - контекстно-зависимый, а не контекстно-свободный, т. е. не существует контекстно-свободной грамматики, которая генерирует этот язык. Аналогично язык, генерированный посредством Go, - контекстно-свободный и нерегулярный. Однако тот факт, что язык можно генерировать с помощью нерегулярной контекстно-свободной грамматики, необязательно означает, что он нерегулярный. Например, грамматика G] - контекстно-свободная, но нерегулярная, а язык, генерированный посредством ее, - регулярный, так как его также можно генерировать посредством грамматики G2- (Строго говоря, регулярной будет L(G2)- s, но принято расширять определения грамматики типа 3 и включать правила вида S->s, где S-начальный символ.) Иерархия Хомского важна с точки зрения языков программирования. Чем меньше ограничений в грамматике, тем сложнее ограничения, которые можно наложить на генерируемый язык.

Грамматики типа 3 можно использовать для описания некоторых свойств языков программирования. Например, для генерирования идентификаторов по определению многих языков программирования можно воспользоваться следующими правилами:

IDE NT wiener IDENTleiier REST REST tetter REST -digit REST --letter REST REST -igU REST

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

IDENT-letterUetter REST

REST -leUeridigitltetter REST\digit REST

здесь вертикальную черту следует читать как «или».

Многие «локальные» средства .языков программирования, например константы, слова языка и строки, представляются с помощью грамматик типа 3. Однако можно показать, что грамматики типа 3 генерируют строго ограниченные типы языков. Определим теперь регулярные выражения и скажем, не доказывая, что грамматики типа 3 генерируют все регулярные выражения без исключения

(см. [2], с. 118).

В алфавите А к регулярным выражениям относятся следующие:

1. Элемент А (или пустая строка).

Если Р и Q - регулярные выражения, то ими будут также и выражения

2. PQ(Q следует за Р).

3. PJQ (P или Q).

4. Р* (нуль или более экземпляров Р). В алфавите {а, Ь, с}

- регулярное выражение, следующие строки (помимо прочих):

которое описывает язык,

с саа аЬ

включающим

Если предположить, что регулярные выражения построены с помощью трех знаков операций: конкатенации (представленной соединением), и *, то при написании регулярных выражений знак * будет обладать главным приоритетом, за ним последует конкатенация, а затем знак .

Операция (иногда представляемая как +) является коммутативной и ассоциативной, т. е. для регулярных выражений Р, Q,R

Конкатенация является ассоциативной, но не коммутативной. Для изменения приоритетов, обычно - ассоциируемых с этими обозначениями операций, можно воспользоваться скобками. Так, в алфавите {а, Ь}

{aab\ab)

- регулярное выражение, которое описывает язык, включающий строки:

ааЬаЬааЬ

ababab

aabaabaabab

Регулярное выражение, описывающее идентификатор, имеет вид

L{L\D)\

где L обозначает букву, a D - цифру.