Классификация грамматик по Хомскому

Формальные грамматики

§ 1. Способы задания формальных языков

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

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

Синтаксически правильные предложения могут не иметь однозначного смысла, например, предложение «мать любит дочь» имеет два смысла, а предложение «Он встретил ее на поляне с цветами» - три смысла. Более того, синтаксически правильно построенные предложения могут не иметь смысла. Классическим примером является следующее предложение, построенное с соблюдением синтаксических правил: «Глокая куздра штеко бодланула бокра и кудрячит бокренса».

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

Пусть задан алфавит А ={0,1}. Множество всевозможных слов в алфавите А обозначают через А*, при этом слова в формальной грамматике часто называют цепочками языка.

Пример. Пусть А={0,1}, тогда А*={e,0,1,00,01,10,11,000,…}, здесь e - пустая цепочка (пустое слово).

Множество А* без пустой цепочки обозначают через А⁺. Так для нашего примера А⁺ ={0,1,00,01,10,11,000,…}.

Формальным языком L над алфавитом А называется произвольное подмножество множества А*. Например, для А={0,1} можно положить, что L₁= ={e, 0,1}, L₂ ={00,01,10,11}.

Очевидно, что обычные теоретико-множественные операции над формальными языками вновь приводят к формальным языкам.

Ясно, что если язык содержит конечное множество цепочек, то его можно задать, перечислив их. Например, язык Эллочки Щукиной из произведения Ильфа и Петрова "Двенадцать стульев" содержал 30 цепочек и их можно просто перечислить, не вдаваясь в правила построения:

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

В случае, когда язык содержит более 30 цепочек, перечисление является не лучшим способом. Так, например, в словаре мадмуазель Фимы Собак, подруги Эллочки Щукиной, было уже около 180 слов. Ясно, что перечисление его займет много времени.

Формальный язык может быть задан:

- перечислением слов (если это возможно);

- с помощью формальных грамматик;

- с помощью конечных автоматов;

- различными модификациями машин Тьюринга (например, многоленточными машинами Тьюринга) и другими методами.

Формальные грамматики

Формальная грамматика представляется совокупностью четырех объектов:

G=(T,N,R,S),

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

N - нетерминальный алфавит (словарь) - конечное множество символов, используемых для правил построения цепочек языка,

R - конечная совокупность правил построения цепочек, все эти правила имеют вид x®h, где x, h - цепочки в алфавите ТÈN, причем x - непустая цепочка, содержащая хотя бы один символ из N; множество правил R должна содержать хотя бы одно правило вида S®h, hÎ( ТÈN)*. Считается, что ТÇN=Æ. Правила x®h часто называют подстановками или продукциями. Символ S - выделенный символ из N, соответствующий понятию "предложение".

Будем говорить, что из цепочки t непосредственно выводится цепочка w если:

t = x₁jx₂, w = x₁yx₂

и среди правил есть правило j®y, здесь x₁ и x₂ произвольные, возможно и пустые цепочки.

Цепочка b выводится из цепочки a если найдется последовательность цепочек w₀ = a, w₁, w₂, w₃,…, w_n = b такая, что w_k+1 непосредственно выводится из цепочки w_k , 0 £ k £ n. При этом w₀, w₁, w₂, w₃,…, w_n называется выводом цепочки b из a и записывается в виде a *® b.

Множество всех цепочек терминальных символов, выводимых из S, называется языком, порождаемым формальной грамматикой, т.е.:

L={ x Î Т*: S *® x}.

Этот язык обозначают L=L(G).

Язык, задаваемый грамматикой, порождается следующим образом. Берется цепочка, состоящая из символа S. Среди правил R ищется правило вида S®h (такое правило всегда есть), затем берется любая подстановка j®y. Если в полученной на предыдущем шаге цепочке есть части, совпадающие с j, то заменяем j на y и т.д. до тех пор, пока цепочка не станет состоящей только из терминальных символов. Если цепочка состоит только из терминальных символов, то процесс обрывается, если нет, то продолжается. Этот процесс называется выводом цепочки из S.

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

Так как в языке Эллочки Щукиной трудно найти логические связи, тогда его можно задать формальной грамматикой, использующей обычное перечисление:

G=(Т,М,R,S),

где Т - часть русского алфавита, т.е. Т={а,б,..., }, N={S},

R: S® хамите

S® знаменито

…

S® подумаешь

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

G=(Т,М,R,S),

где Т={0,1,2,3,…9}, N={S,A},

R: S® 0

S® 1

S® 2

S® 3

…

S® 9

S® A

A® S

A® SA

Для сокращения записей правила вывода этой грамматики можно записать в виде:

S® 0ê1ê2ê3ê…ê9êА

А® SêSA

где ê означает или.

Построим вывод цепочки 1991 в этой построенной грамматике:

S®А®SА®1А®1SА®19А®19SА®199А®199S®1991

Этот же язык можно задать при том же Т, но N={S}, а правилами являются следующие:

S® 0ê1ê2ê3ê…ê9êSS

Тогда вывод цепочки 1991 будет следующим: S®SS®SSS®SSSS®1SSS® 19SS®199S®1991

Из этих простых примеров следует, что один и тот же язык может порождаться различными грамматиками.

Грамматики G₁ и G₂ называются эквивалентными, если они порождают один и тот же язык, т.е. L(G₁)=L(G₂).

Рассмотрим еще один пример грамматики, назовем его примером «ИП»: G=(T,N,R,S), где T={a,b,c,…,z,0,1,2,3,…,9}, N={S,A,B}, R:

S® aêbêcê…êzêАêВêАB

А® aêbêcê…êz

B® aêbêcê…êz ê0ê1ê2ê3ê…ê9êBB

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

Рассмотренные грамматики называются порождающими. Направив стрелки в правилах в обратную сторону, получим распознающую грамматику. в этих грамматиках вывод заменен разбором (или сверткой): в цепочке ищем часть, совпадающую с одним из h, и заменяем ее на x. Если такой последовательной заменой можно «свернуть» цепочку в нетерминал S, то цепочка принадлежит языку, иначе нет.

Классификация грамматик по Хомскому

Формальные грамматики разделяются на классы (типы) по ограничениям на правила.

Тип 0. Никаких ограничений нет.

Тип 1. Правила имеют вид: jАy®jxy, АÎN, j, y, xÎ(TÈN)*. Такие грамматики называются контекстными (К-грамматиками) или грамматиками непосредственно составляющих (НС-грамматики). Каждое правило указывает: А в контексте j и y может быть заменено цепочкой x.

Тип 2. Правила имеют вид А®x. Такие грамматики называются контекстно-свободными (КС-грамматиками) или бесконтекстными, так как замена А на x, не зависит от контекста. Контекст - тесная связь, соединение.

Тип 3. Правила имеют вид:

А®аВ, А®b,

где а, b – любые буквы из терминального алфавита, а А и В - любые буквы из нетерминального алфавита. Такие грамматики называются автоматными (А-грамматиками) или регулярными грамматиками.

Язык называется языком типа k, если его можно задать грамматикой типа k и нельзя задать грамматикой типа k+1.

Во втором параграфе в примере «ИП» язык идентификаторов Паскаля задается грамматикой типа 2, но для него можно записать и автоматную грамматику:

G=(T,N,R,S), где T={a,b,c,…,z,0,1,2,3,…,9}, N={S,A}, R:

S® aêbêcê…êzêаАêbAêcAê…êzAê

А® aêbêcê…êzê0ê1ê2ê3ê…ê9êaAêbAêcAê…êzAê0Aê1Aê2Aê3Aê…ê9Aê

Таким образом, язык идентификаторов - это автоматный язык. '"Очевидно", что любой язык типа k (k=1,2,3) является также языком типа k-1. Класс языков типа О слишком широк, и о нем можно говорить только слишком обще. Класс языков типа 3 очень хорош с позиций разработчика трансляторов, но он очень узок, даже такой простой язык как язык арифметических выражений, уже не является А-языком. Язык типа 0 неразрешим, поэтому он мало исследуется. Автоматные грамматики наиболее просты для исследования.

Автоматные грамматики исследуются в основном на этапе лексического анализа. КС-грамматики важны для определения синтаксической структуры языка программирования.

Не нашли, что искали? Воспользуйтесь поиском по сайту: