Разработка компиляторов
Некоторые свойства грамматик
Отметим некоторые свойства грамматик, которые нам придется учитывать в дальнейшем при построении грамматик реальных языков программирования.
Во-первых, различные грамматики могут порождать один и тот же язык (такие грамматики называются эквивалентными). Например, приведенная выше грамматика эквивалентна следующей грамматике , где правила из P определены следующим образом: .
Несмотря на эквивалентность определяемых языков, одна грамматика может быть значительно удобнее другой с точки зрения ее использования в компиляторе. Поэтому в дальнейшем мы будем рассматривать некоторые приемы преобразования грамматик с целью улучшения удобства работы с языком.
Во-вторых, необходимо отметить, что определение грамматик не накладывает никаких ограничений на количество нетерминалов в левой части правил и приведенные выше примеры не должны создавать обманчивого впечатления, что все грамматики содержат один и только один нетерминал в левой части каждого правила. В качестве иллюстрации приведем следующий пример: , где содержит следующие правила: . Это абсолютно законная грамматика, порождающая язык .
В качестве другого примера приведем еще одну грамматику, эквивалентную грамматике , где . В этом варианте левая часть одного из правил содержит пару из терминального и нетерминального символа.
В-третьих, упомянем одно соглашение, которое нам пригодится впоследствии: для обозначения n правил вида мы будем использовать следующую запись: . В правилах такого вида вертикальная черта читается как "или".
