Глава 9. Формальные языки и I рамматики

способа довольно проста. Это можно легко заметить, если посмотреть на описа­ние понятия «число» из грамматики G с помощью диаграмм на рис. 9.1.

Число:

Рис. 9.1. Графическое представление грамматики целых десятичных чисел со знаком: вверху — для понятия «число»; внизу — для понятия «цифра»

Как уже было сказано выше, данный способ в основном применяется в литерату­ре при изложении грамматик языков программирования. Для пользователей — разработчиков программ — он удобен, но практического применения в компиля­торах пока не имеет.

Классификация языков и грамматик

Выше уже упоминались различные типы грамматик, но не было указано, как и по какому принципу они подразделяются на типы. Для человека языки быва­ют простые и сложные, но это сугубо субъективное мнение, которое зачастую за­висит от личности человека.

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

рования, зависит сложность распознавателя для этого языка. Чем сложнее язык, тем выше вычислительные затраты компилятора на анализ цепочек исходной программы, написанной на этом языке, а следовательно, сложнее сам компиля­тор и его структура. Для некоторых типов языков в принципе невозможно по­строить компилятор, который бы анализировал исходные тексты на этих языках за приемлемое время на основе ограниченных вычислительных ресурсов (имен­но поэтому до сих пор невозможно создавать программы на естественных язы­ках, например на русском или английском).

Классификация грамматик.

Четыре типа грамматик по Хомскому

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

По классификации Хомского выделяют четыре типа грамматик.

Тип О: грамматики с фразовой структурой

На структуру их правил не накладывается никаких ограничений: для граммати­ки вида G(VT,VN,P,S), V - VNuVT правила имеют вид: а->р, где aeV⁺, (3eV*.

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

Практического применения грамматики, относящиеся только к типу 0, не имеют.

Тип 1: контекстно-зависимые (КЗ) и неукорачивающие грамматики

В этот тип входят два основных класса грамматик.

Контекстно-зависимые грамматики G(VT,VN,P,S), V = VNuVT имеют правила вида: сцАсхг-нх^аг, где a₁,a₂eV*, AeVN, (JeV⁴.

Неукорачивающие грамматики G(VT,VN,P,S), V = VNu VT имеют правила вида: a->(3, где a,(3eV⁺, |p|>|a|.

Структура правил КЗ-грамматик такова, что при построении предложений за­данного ими языка один и тот же нетерминальный символ может быть заменен на ту или иную цепочку символов в зависимости от того контекста, в котором он встречается. Именно поэтому эти грамматики называют «контекстно-зависимы­ми». Цепочки 0ц и а₂ в правилах грамматики обозначают контекст (оц — левый контекст, а а₂ — правый контекст), в общем случае любая из них (или даже обе) может быть пустой. Говоря иными словами, значение одного и того же символа может быть различным в зависимости от того, в каком контексте он встречается.