3.2.4.Другие способы задания грамматик

Форма Бэкуса—Наура — удобный с формальной точки зрения, но не всегда дос­тупный для понимания способ записи формальных грамматик. Рекурсивные определения хороши для формального анализа цепочек языка, но не удобны с точки зрения человека. Например, то, что правила <чс>→<цифра>|<чс><цифра> отражают возможность для построения числа дописывать справа любое число цифр, начиная от одной, неочевидно и требует дополнительного пояснения.

Но при создании языка программирования важно, чтобы его грамматику пони­мали не только те, кому предстоит создавать компиляторы для этого языка, но и пользователи языка — будущие разработчики программ. Поэтому существуют другие способы описания правил формальных грамматик, которые ориентирова­ны на большую понятность человеку.

Далее рассмотрим запись пра­вил грамматик с использованием метасимволов.

Запись правил грамматики с использованием метасимволов предполагает использование специальных символов в строке правила грамматики. Эти символы имеют специальный смысл. Чаще всего в качестве метасимволов применяют следующие:

() – круглые скобки. Они означают, что из всех перечисленных в них через разделитель запятую цепочек символов в данном месте правила может стоять только одна;

[] – квадратные скобки.Указывает на необязательное присутствие перечисленных внутри них элементов в данном месте правила;

{} – фигурные скобки. Означают повторяемость содержимого от 0 до скольугодного количества раз;

\ - наклонная черта используется для включения в цепочку символов самих метасимволов.

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

Запишем правила рассмотренной выше грамматике на языке метасимволов:

<число>→[(+,-)]<цифра>{<цифра>}

<цифра>→(0,1,2,3,4,5,6,7,8,9)

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

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

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

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

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

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

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

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

На структуру их правил не накладывается никаких ограничений: для граммати­ки вида G(VT,VN,P,S), V = VNVT правила имеют вид: α→β, где αV⁺, βV^*.

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

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

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

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

Контекстно-зависимые грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: α₁Aα₂→α₁βα₂, где α₁,α₂V^*, AVN, βV⁺.

Неукорачивающие грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: α→β, где αβV⁺, |β|≥|α|.

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

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

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

При построении компиляторов такие грамматики не применяются, поскольку языки программирования, рассматриваемые компиляторами, имеют более про­стую структуру и могут быть построены с помощью грамматик других типов.

Тип 2: контекстно-свободные (КС) грамматики

Контекстно-свободные (КС) грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: А→β, где AVN, βV⁺. Такие грамматики также иногда называют неукорачивающими контекстно-свободными (ИКС) грамматиками (видно, что в правой части правила у них должен всегда стоять как минимум один символ). Существует также почти эквивалентный им класс грамматик — укорачивающие контекстно-свободные (УКС) грамматики G(VT,VN,P,S), V = VNVT, правила которых могут иметь вид: А→β, где AVN, βV^*.

Разница между этими двумя классами грамматик заключается лишь в том, что в УКС-грамматиках в правой части правил может присутствовать пустая це­почка (), а в НКС-грамматиках — нет. Отсюда ясно, что язык, заданный НКС-грамматикой, не может содержать пустой цепочки. Доказано, что эти два класса грамматик почти эквивалентны. В дальнейшем, когда речь будет идти о КС-грамматиках, уже не будет уточняться, какой класс грамматики (УКС или НКС) имеется в виду, если возможность наличия в языке пустой цепочки не имеет принципиального значения.

КС-грамматики широко используются при описании синтаксических конструк­ций языков программирования. Синтаксис большинства известных языков про­граммирования основан именно на КС-грамматиках, поэтому в данном курсе им уделяется большое внимание.

Внутри типа КС-грамматик кроме классов НКС и УКС выделяют еще целое множество различных классов грамматик, и все они относятся к типу 1. Далее, когда КС-грамматики и КС-языки будут рассматриваться более подробно, на не­которые из этих классов грамматик и их характерные особенности будет обраще­но особое внимание.

Тип 3: регулярные грамматики

К типу регулярных относятся два эквивалентных класса грамматик: леволинейные и праволинейные.

Леволинейные грамматики G(VT,VN,P,S), V = VNVT могут иметь правила двух видов: А→В или А→, где A,BVN, VT*.

В свою очередь, праволинейные грамматики G(VT,VN,P,S), V = VNVT могут иметь правила тоже двух видов: А→В или А→, где A,BVN, VT*.

Эти два класса грамматик эквивалентны и относятся к типу регулярных грам­матик.

Регулярные грамматики используются при описании простейших конструкций языков программирования: идентификаторов, констант, строк, комментариев и т. д. Эти грамматики исключительно просты и удобны в использовании, поэтому в компиляторах на их основе строятся функции лексического анализа входного языка (принципы их построения будут рассмотрены далее).

Типы грамматик соотносятся между собой особым образом. Из определения типов 2 и 3 видно, что любая регулярная грамматика является КС-грамматикой, но не наоборот. Также очевидно, что любая грамматика может быть отнесена и к типу 0, поскольку он не накладывает никаких ограничений на правила. В то же время существуют укорачивающие КС-грамматики (тип 2), которые не являют­ся ни контекстно-зависимыми, ни неукорачивающими (тип 1), поскольку могут содержать правила вида «А→», недопустимые в типе 1. В целом можно сказать, что сложность грамматики обратно пропорциональна тому максимально воз­можному номеру типа, к которому может быть отнесена грамматика. Граммати­ки, которые относятся только к типу 0, являются самыми сложными, а грамма­тики, которые можно отнести к типу 3 — самыми простыми.