1.3.4.2. Классификация распознавателей по типу языков

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

Проблема распознавания разрешима, если существует такой алгоритм, который за конечное число шагов дает ответ на вопрос, принадлежит ли произвольная цепочка над основным словарем грамматики языку, порождаемому этой грамматикой. Если такой алгоритм существует, то язык называется распознаваемым. Если к тому же число шагов алгоритма распознавания зависит от длины цепочки и может быть оценено до выполнения алгоритма, язык называется легко распознаваемым.

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

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

Согласно классификации, предложенной в 1959 г. американским лингвистом Ноамом Хомским, профессором МТИ (Массачусетского технологического института), формальные грамматики классифицируются по структуре их правил. Если все без исключения правила грамматики удовлетворяют некоторой заданной структуре, то такую грамматику относят к определенному типу соответствующему этой структуре. Если хотя бы одно правило в грамматике не удовлетворяет требованиям структуры правил, эта грамматика уже не попадает в заданный тип.

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

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

На структуру их правил не накладывается никаких ограничений: для грамматики G <T, N, P, S> правила имеют вид:

  , где   V⁺,   V^*.

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

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

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

Контекстно-зависимые (КЗ) грамматики имеют правила вида

₁A₂  ₁₂, где ₁ и ₂  V^*, A  N,   V⁺.

Неукорачивающие грамматики имеют правила вида

  , где ,   V⁺,   .

Структура правил КЗ-грамматик такова, что при построении предложений заданного языка один и тот же нетерминальный символ может быть заменен на ту или иную цепочку символов в зависимости от того контекста, в котором он встречается. Почему они и называются «контекстно-зависимыми».

Цепочки ₁ и ₂ в правилах КЗ-грамматики обозначают контексты (₁ – левый контекст, ₂ – правый контекст). В общем случае любой или сразу оба контекста могут быть .

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

Доказано, что эти два класса грамматик эквивалентны.

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

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

КС грамматики имеют правила вида A  , где A  N,   V⁺. Замена нетерминала A на строку  происходит без учета контекста, поэтому они и называются контекстно-свободными. Такие грамматики также иногда называют неукорачивающими КС (НКС), т. к. в правой части правил у них должен всегда стоять как минимум один символ. Существует также почти эквивалентный им класс грамматик – укорачивающие КС (УКС) грамматики, которые от НКС отличаются тем, что   V^*, т. е. в УКС может иметь место пустая цепочка, а в НКС нет. Общее обозначение этих грамматик – КС-грамматики, если наличие пустой цепочки не имеет принципиального значения.

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

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

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

Леволинейные грамматики могут иметь правила двух видов:

A  B или A  , где A, B  N,   T^*.

Праволинейные грамматики могут иметь правила тоже двух видов:

A  B или A  , где A, B  N,   T^*.

Эти два класса эквивалентны и относятся к типу регулярных. Их еще называют автоматными грамматиками (A-грамматики).

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

Соотношения между типами грамматик следующие. Все типы грамматик могут быть отнесены к типу 0. Сложность грамматик обратно пропорциональна номеру типа: грамматики, которые относятся только к типу 0 – самые сложные, а грамматики, которые можно отнести к типу 3 – самые простые. Для классификации грамматики всегда выбирают максимально возможный тип, к которому она может быть отнесена.