КЛАССИФИКАЦИЯ ГРАММАТИК И ЯЗЫКОВ ( КЛАССИФИКАЦИЯ ХОМСКОГО ) Рейн Т. С.

Тип 0: грамматики с фразовой структурой На структуру их правил не накладывается никаких ограничений : для грамматики вида G (VT, VN, P, S), V = VN U VT, правила имеют вид α β, где α из V +, β из V*. Это самый общий тип грамматик. Грамматики, которые относятся только к типу 0 и не могут быть отнесены к другим типам, являются самыми сложными по структуре. Практического применения грамматики, относящиеся только к типу 0, не имеют.

Тип 1: контекстно - зависимые ( КЗ ) и неукорачивающие грамматики В этот тип входят два основных класса грамматик : Цепочки α 1 и α 2 в правилах грамматики обозначают контекст ( α 1 – левый контекст, α 2 – правый контекст ), в общем случае любая из них ( или даже обе ) может быть пустой.

Тип 1: контекстно - зависимые ( КЗ ) и неукорачивающие грамматики Структура правил КЗ - грамматик такова, что при построении предложений заданного ими языка один и тот же нетерминальный символ может быть заменён на ту или иную цепочку символов в зависимости от того контекста, в котором он встречается. Значение одного и того же символа может быть различным в зависимости от того, в каком контексте он встречается.

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

Тип 2: контекстно - свободные ( КС ) грамматики Неукорачивающие контекстно - свободные ( НКС ) грамматики G (VT, VN, P, S), V = VN U VT, имеют правила вида А β, где А из VN, β из V+. Такие грамматики называют НКС - гграмматиками, поскольку видно, что в правой части правил у них должен всегда стоять как минимум один символ. Существует также почти эквивалентный им класс грамматик – укорачивающие контекстно - свободные ( УКС ) грамматики G (VT, N, P, S), V = VN U VT, правила которых могут иметь вид : А β, где А из VN, β из V*. Эти два класса составляют тип контекстно - свободных грамматик.

Тип 3: регулярные грамматики (2 класса – леволинейные и праволинейные ) Леволинейные грамматики G (VT, VN, P, S), V = VN U VT, могут иметь правила двух видов : А B γ или А γ, где А, В из VN, γ из VT*. Праволинейные грамматики G (VT, VN, P, S), V = VN U VT, могут иметь правила тоже двух видов : А γВ или А γ, где А, В из VN, γ из VT*.

Иерархия грамматик ( по Хомскому )

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

Пример Если язык L может быть задан гграмматиками G1 и G2, относящимися к типу 1 ( КЗ ), грамматикой G3, относящейся к типу 2 ( КС ), и грамматикой G4, относящейся к типу 3 ( регулярные ), сам язык должен быть отнесён к типу 3 и является регулярным языком.

Пример Гграмматика типа 0 G1 ({0, 1}, {A, S}, P1, S) и КС - гграмматика G2 ({0, 1}, {S}, P2, S), где P1: S 0A1 P2: S 0S1 | 01 0A 00A1 A ε описывают один и тот же язык L = L (G1) = L (G2) = {0^n 1^n | n > 0} Язык L называют КС - языком, т. к. существует КС - грамматика, его описывающая. Но он не является регулярным языком, т. к. не существует регулярной грамматики, описывающей этот язык.

Пример регулярной грамматики Гграмматика S aS | a является праволинейной ( неукорачивающей ) грамматикой. Она порождает регулярный язык {a^n | n> 0}. Этот язык может быть порожден и леволинейной грамматикой : S Sa | a.

Пример регулярной грамматики S aS | ε является праволинейной и порождает регулярный язык {a^n | n >= 0}. Для любого регулярного языка существует неукорачивающая регулярная гграмматика. Неукорачивающаяся регулярная гграмматика для данного языка : S

Пример контекстно - свободной грамматики является контекстно - свободной ( неукорачивающей ) и порождает КС - язык {(ac)^n (cb)^n | n > 0}, который, как язык {a^n b^n | n >0}, не является регулярным, т. е. не может быть порожден ни одной регулярной грамматикой.

Пример контекстно - зависимой грамматики Неукорачивающая порождает язык, который является языком типа 1, но не является языком типа {a^n b^n c^n, n>0}

Гграмматика без ограничений В грамматике типа 0 S SS SS ε второе правило не удовлетворяет ограничениям неукорачивающей грамматики. Существует бесконечно много выводов в данной грамматике, однако порождаемый язык конечен и состоит из единственной цепочки : { ε }.

Цепочки вывода Выводом называется процесс порождения предложения языка на основе правил определяющей язык грамматики. Цепочка β = δ 1 γ δ 2 называется непосредственно выводимой из цепочки α = δ 1 ω δ 2 в грамматике G (VT, VN, P, S), V = VN U VT; δ 1, γ, δ 2 из V*, ω из V+, если в грамматике существует правило ω γ.

Цепочки вывода Иными словами, цепочка β выводима из цепочки α в том случае, если можно взять несколько символов в цепочке α, поменять их на другие символы, согласно некоторому правилу грамматики, и получить цепочку β. Непосредственная выводимость цепочки β из цепочки α обозначается как : α β.

Цепочки вывода Цепочка β называется выводимой из цепочки α ( α * β ) в случае, если выполняется одно из двух условий : β непосредственно выводима из α ( α β ); существует γ такая, что γ выводима из α, и β непосредственно выводима из γ ( α γ, γ β ).

Пример 1. Гграмматика для языка целых десятичных чисел со знаком

Пример 2 вывода предложения aaaabbbbcccc для грамматики G языка Задана гграмматика G ({a, b, c}, {B, C, D, S}, P, S) с правилами Таким образом цепочка aaaabbbbcccc выводима из S:

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

Сентенциальная форма грамматики Цепочка символов α из V* называется сентенциальной формой грамматики G (VT, VN, P, S), V = VT UVN, если она выводима из целевого символа грамматики S: S * α. Если цепочка α из VT* получена в результате законченного вывода, то она называется конечной сентенциальной формой.

Левосторонний и правосторонний выводы Вывод называется левосторонним, если в нём на каждом шаге вывода правило грамматики применяется всегда к крайнему левому нетерминальному символу в цепочке. на каждом шаге вывода происходит подстановка цепочки символов на основании правила грамматики вместо крайнего левого нетерминального символа в исходной цепочке. Вывод называется правосторонним, если в нём на каждом шаге вывода правило грамматики применяется всегда к крайнему правому нетерминальному символу в цепочке. Пример 1 – (1,4), (2,3,4)

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

Пример 2 Рассмотренный в примере 2 не является ни левосторонним, ни правосторонним. Гграмматика относится к типу 1, и для неё нельзя построить такой вывод, на каждом шаге которого только один нетерминальный символ заменялся бы на цепочку символов.

Цепочки вывода. Пример В грамматике для одной и той же цепочки может быть несколько выводов. Например, для цепочки a+b+a в грамматике G ({a, b, +}, {S, T}, P, S) P: S T | T+S; T a | b можно построить выводы : 2 – л ; 3- п ;

Дерево вывода Деревом вывода грамматики G (VT, VN, P, S) называется дерево, которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям : каждая вершина дерева обозначается символом грамматики А из (VT U VN U { ε }); корнем дерева является вершина, обозначенная целевым символом грамматики – S; листьями дерева ( концевыми вершинами ) являются вершины, обозначенные терминальными символами грамматики или символом пустой цепочки ε ; если некоторый узел дерева обозначен нетерминальным символом А, а связанные с ним узлы – символами b1, b2, …, bn из VT U VN ; n > 0, то в грамматике G существует правило A b1 | b2 | … | bn из Р.

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

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

Построение дерева Если для каждой цепочки символов языка, заданного грамматикой, можно построить единственный левосторонний ( и единственный правосторонний ) вывод или, построить единственное дерево вывода, то такая гграмматика называется однозначной. Иначе гграмматика называется неоднозначной.

Дерево вывода. Пример 3. Условный оператор, включённый во многие языки программирования, описывается с помощью грамматики с правилами : S if b then S else S | if b then S | a где b – логическое выражение, а а – безусловный оператор. Эта гграмматика неоднозначна, т. к. в ней возможны два левых вывода цепочки if b then if b then a else a:

Наличие двух различных выводов предполагает две различные интерпретации цепочки if b then if b then a else a: первая из них – if b then (if b then a) else a, вторая – if b then (if b then a else a). При описании языка программирования эту неоднозначность преодолевают, добавляя к семантическим правилам правило вида : « ключевое слово else ассоциируется с ближайшим слева ключевым словом if». Дерево вывода. Пример 3.

Дерево вывода. Неоднозначная гграмматика. Пример Для цепочки if b then if b then a else a можно построить два раз - личных дерева вывода :

Разные деревья вывода предполагают соответствие else разным then. Если договориться, что else должно соответствовать ближайшему к нему then, и подправить грамматику G, то неоднозначность будет устранена : S if b then S | if b then S' else S | a S if b then S' else S' | a Дерево вывода. Неоднозначная гграмматика. Пример

КС - - грамматики. Дерево вывода. Пример Для КС - грамматик существуют определённого вида правила, по наличию которых во всём множестве правил грамматики можно утверждать, что она является неоднозначной : 1) А АА | α 2) А АαА | β 3) А αА | A β | γ 4) А αА | α A β A | γ Здесь A из VN; α, β, γ из (VN U VT)*.