Тип 2: контекстно-свободные (кс) языки

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

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

Однако среди КС-языков существует много классов языков, для которых эта зависимость линейна. Многие языки программирования можно отнести к одному из таких классов.

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

Тип 3: регулярные языки

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

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

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

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

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

Далее приводятся примеры некоторых языков указанных типов.

Рассмотрим в качестве первого примера ту же грамматику для целых десятичных чисел со знаком G({0,1,2,3,4,5,6,7,8,9,-,+},{S,Т,F},P,S):

По структуре своих правил данная грамматика G относится к контекстно-свободным грамматикам (тип 2). Конечно, ее можно отнести и к типу 0, и к типу 1, но максимально возможным является именно тип 2, поскольку к типу 3 эту грамматику отнести никак нельзя: строка T-»F | TF содержит правило T->TF, которое недопустимо для типа 3 и, хотя все остальные правила этому типу соответствует, одного несоответствия достаточно.

Для того же самого языка (целых десятичных чисел со знаком) можно построить и другую грамматику G'({0.1.2,3.4,5,б,7,8,9,-,+},{S,Т},P.S):

По структуре своих правил грамматика G' является праволинейной и может быть отнесена к регулярным грамматикам (тип 3).

Для этого же языка можно построить эквивалентную леволинейную грамматику (тип 3) G"({0,l,2,3,4,5,6,7.8.9,-,+},{S,T},P,S):

Следовательно, язык целых десятичных чисел со знаком, заданный грамматиками G, G' и G", относится к регулярным языкам (тип 3).

В качестве второго примера возьмем грамматику G₂({0,1},{A.S},P,S) с правилами Р:

Эта грамматика относится к типу 0. Она определяет язык, множество предложений которого можно было бы записать так: L(G₂) = {Oⁿlⁿ | n > 0}.

Для этого же языка можно построить также контекстно-зависимую грамматику G₂'({0,1},{A.S},P',S) с правилами Р':

Однако для того же самого языка можно использовать и контекстно-свободную грамматику G₂"({0,1},{S}.P",S) с правилами Р":

Следовательно, язык L = {0"1" n > 0} является контекстно-свободным (тип 2).

В третьем примере рассмотрим грамматику G₃({a,b,c},{B,C,D,S}.P,S) с правилами Р:

Эта грамматика относится к типу 1. Очевидно, что она является неукорачивающей. Она определяет язык, множество предложений которого можно было бы записать так: L(G₃) = {aⁿbⁿcⁿ | n > 0}. Известно, что этот язык не является КС-языком, поэтому для него нельзя построить грамматики типов 2 или 3. Язык L = {aⁿbⁿcⁿ | n > 0} является контекстно-зависимым (тип 1).

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

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

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

Цепочки вывода. Сентенциальная форма

Вывод. Цепочки вывода

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

Цепочка (β = δ₁γδ₂ называется непосредственно выводимой из цепочки а = β₁а>β₂ в грамматике G(VT,VN,P,S), V = VTuVN, δ1, γ, δ₂ е V*, со е V⁺, если в грамматике G существует правило: w-»γ s Р. Непосредственная выводимость цепочки β из цепочки а обозначается так: а=>β. Иными словами, цепочка β выводима из цепочки а в том случае, если можно взять несколько символов в цепочке а, заменить их на другие символы согласно некоторому правилу грамматики и получить цепочку β. В формальном определении непосредственной выводимости любая из цепочек δ₁ или δ₂ (а равно и обе эти цепочки) может быть пустой. В предельном случае вся цепочка а может быть заменена на цепочку β, тогда в грамматике G должно существовать правило: а-»β е Р.

Цепочка р называется выводимой из цепочки а (обозначается а=>*р) в том случае, если выполняется одно из двух условий:

--- β непосредственно выводима из а (а=>β);

--- γ, такая, что: у выводима из а и β непосредственно выводима из у (а=>*у и у=>β).

Это рекурсивное определение выводимости цепочки. Суть его заключается в том, что цепочка β выводима из цепочки а, если а=>β или же если можно построить последовательность непосредственно выводимых цепочек от а к р следующего вида: a=>y₁=>...=>y_i=>...=>y_n=>β, п>1. В этой последовательности каждая последующая цепочка у_i непосредственно выводима из предыдущей цепочки у_и.

Такая последовательность непосредственно выводимых цепочек называется выводом или цепочкой вывода. Каждый переход от одной непосредственно выводимой цепочки к следующей в цепочке вывода называется шагом вывода. Очевидно, что шагов вывода в цепочке вывода всегда на один больше, чем промежуточных цепочек. Если цепочка р непосредственно выводима из цепочки а: а=»β, то имеется всего один шаг вывода.

Если цепочка вывода из а к р содержит одну или более промежуточных цепочек (два или более шагов вывода), то она имеет специальное обозначение а=>+β (говорят, что цепочка β нетривиально выводима из цепочки а). Если количество шагов вывода известно, то его можно указать непосредственно у знака выводимости цепочек. Например, запись а=>⁴β означает, что цепочка β выводится из цепочки а за 4 шага вывода¹.

Возьмем в качестве примера ту же грамматику для целых десятичных чисел со знаком G({0.1.2.3.4.5.6,7.8.9.-,+}.{SJ,F}.P,S):

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

Возьмем в качестве второго примера грамматику G₃({a,b,c},{B,C,D,S},P,S) с правилами Р, которая уже рассматривалась выше:____________________________________________________

**1| В литературе встречается также обозначение а=>°β, которое означает, что цепочка а выводима из цепочки Р за 0 шагов — иными словами, в таком случае эти цепочки равны: a - β. Подразумевается, что обозначение вывода а=>*β допускает и такое толкование — включает в себя вариант а=>°β.|

Как было сказано ранее, она задает язык L(G₃) = {Oⁿlⁿ | n > 0}. Рассмотрим пример вывода предложения «ааааЬЬЬЬсссс » языка L(G₃) на основе грамматики G₃:

S => BD => аВbСD => ааВbСbСD => аааВbСЬСЬСD => ааааbbСbСbСD => ааааbbbССbСD => ааааЬbbСbССD => ааааbbbbСССD => ааааbbbbbССDс => ааааbbbbСDсс => ааааbbbbDссс => ааааbbbbсссс. Тогда для грамматики G₃ получаем вывод: S => * ааааbbbbсссс.

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