Понятие о формальных языках и порождающих рамматиках

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

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

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

Синтаксис языка (от греч. syn — вместе и taxis — порядок) представляет собой систему правил, на основании которых можно строить «правильные» с точки зрения этого языка конструкции, состоящие из отдельных слов. Например, конструкция «if a> then c:=d» будет правильной с точки зрения языка программирования Pascal, а конструкция «if a> c:=d then» — неправильной.

Каждое слово языка состоит из некоторого набора символов, определяемых алфавитом. Стоит отметить, что термины «слово» и «символ», применяемые по отношению к языкам, не всегда являются словами и символами в обычном понимании. Например, если «символом» считать слово естественного языка, то «словами» в этом случае будут п редл ожен и я.

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

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

Семантика языка (от греч. seman-tikos — обозначающий) предполагает сопоставление цепочке языка некоторого смысла. Синтаксически верная языковая конструкция не всегда имеет смысл. Например, предложение «Дерево строит автомобиль» построено по правилам русского языка, но бессмысленно.

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

Синтаксис, семантика и прагматика являются характеристиками языка в его интуитивном понимании. Для более строгого определения введем ряд понятий.

Пусть V = {ai, й2, …, а_п} — некоторый конечный алфавит, состоящий из букв oi, «2,…, а_п. Множество всех слов в алфавите V обозначается как V*. Можно показать, что V* счетно.

Языком в алфавите V называется произвольное подмножество множества V*. Элементами языка являются слова (называемые также цепочками).

Язык является множеством, поэтому над его элементами возможно выполнять все стандартные операции над множествами: пересечение, объединение, разность, дополнение и др. Кроме этих операций вводятся специальные.

Пусть x (i) означает г-й символ в слове х. Тогда слово s длины к можно записать как s = $(1)^(2)… s (k), а слово t длины р можно записать как t = t ()t (2)… t (p).

Конкатенацией (соединением) слов s и t называется слово.

Но определению, полагается хХ = Хх = х, где Л — нулевое слово. Иногда операция конкатенации обозначается точкой (•).

Свойства операции конкатенации.

• 1. Длина результата равна сумме длин слов: st = |s| -I- .
• 2. Ассоциативность: s (tr) = (st)r.
• 3. Некоммутативность в общем случае: st Ф ts.

Говорят, что слово s входит, в слово t, если в рассматриваемом языке существуют такие слова и и г, что t = usv. Например, слово .5 ="кон" входит в слово t = «экономика»: здесь и ="э" и v ="омика". Проверка:

Нетрудно видеть, что каждое слово входит само в себя и что нулевое слово входит в. любое слово.

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

Классическим способом определения языков через порождающую процедуру является их определение с помощью порождающих грамматик (грамматик Н. Хомского). Общая схема порождения новых слов состоит в следующем:

• 1. Задается некоторое первоначальное слово.
• 2. На основании некоторого конечного числа правил, называемых правилами вывода (зальены, подстановки, переписывания), первоначальная цепочка определенным образом преобразуется в новое слово.
• 3. К полученной цепочке вновь применяются правила замены и т. д. Так как количество правил конечно, то число полученных «правильных» слов будет также конечно.

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

Терминальный алфавит V — это алфавит, из символов которого будут состоять порождаемые слова языка. Этот алфавит соответствует ранее рассмотренному определению алфавита. Символы этого алфавита также называют терминалами.

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

Нетерминальный и терминальный алфавит не должны иметь общих символов, т. е. V П N = 0.

Аксиома S — один из символов нетерминального алфавита. С аксиомы начинается порождение (вывод) правильных слов языка.

Правила вывода Р — конечное множество правил, записываемых как а —> (3, где аир — слова в алфавите VU N. Часть правила, а называется левой частью правила вывода, Р — правой частью. Правая часть должна содержать хотя бы один нетерминальный символ. Символ —> (стрелка) не принадлежит ни одному из алфавитов грамматики. Если имеются два правила а —> р и а —" 7, то запись упрощают до вида а —> ру. Порождающей грамматикой называется кортеж.

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

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

Пример 9.5. Рассмотрим порождающую грамматику G = (V, N, S, Р), в которой.

В качестве букв, из которых будут состоять конечные порожденные слова, выступают символы {а, 6,0,1}. В соответствии с первым правилом из аксиомы могут быть порождены слова а, b или слова, начинающиеся с этих символов, после которых следует нетерминал D. В соответствии со вторым правилом D может быть заменен на одно из восьми указанных в правиле слов. Нетрудно заметить, что данная грамматика порождает слова, содержащие произвольное количество символов алфавита V и начинающиеся на а или 6, т. е. порождает имена идентификаторов в четырехбуквенном алфавите {а, 6,0,1}.

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

В грамматике G слово S непосредственно выводимо из слова 7, если в этой грамматике существуют слова у, ф и правило а —> Р, такие что 7 = <�раф и S = фРф.

Непосредственная выводимость фактически означает, что некоторая часть слова 7 является словом, а и в то же время некоторая часть слова 6 является словом д. Для обозначения непосредственной выводимости используют обозначение 7 «—> 6.

Например, для рассмотренной выше грамматики Gi слово ab выводимо из слова (iD, так как существует правило D —> Ь. Математически ото можно записать как.

Выводом в грамматике G называют произвольную конечную или бесконечную последовательность слов ао, fli, … в которой для любого г ^ 0 имеет место а* ь-> а_|+1,.

если а*+1 существует.

Число п ^ 0 называется длиной вывода, если последовательность конечна и а_п — ее последний элемент. В этом случае говорят, что а_п выводится из ао за п шагов. Выводимость слова а_п из слова а₀ обозначается а.₀ «->* а_п.

Всякая подпоследовательность вывода, которая сама является выводом, называется фрагментом вывода.

Язык, порожденный грамматикой G, — это множество L (G) всех выводимых из аксиомы грамматики терминальных цепочек:

Пример 9.6. Рассмотрим язык так называемых правильных скобочных структур, порождаемый грамматикой G2 = (V, N, S, Р), в которой.

Нетрудно видеть, что правильной скобочной структурой с является либо слово (), либо ©, либо последовательность двух правильных скобочных структур. Цспочка ((()))()() является правильной, так как существует вывод

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

На правила вывода вида, а —> 0 в порождающих грамматиках накладывается только одно ограничение: левая часть, а должна содержать как минимум один нетерминал. С практической и теоретической точки зрения вызывают интерес грамматики, на правила вывода которых накладываются дополнительные условия. С этой позиции выделяют следующие виды грамматик.

Грамматика типа О (ТО) или грамматика общего вида. На правила вывода не накладывается никаких дополнительных ограничений.

Неукорачивающие грамматики. Каждое правило имеет вид а —>? 0, где |а| ^ . Другими словами, длина выводимого слова должна быть не меньше исходного.

Контекстно-зависимые грамматики (КЗ-грамматики). Каждое правило имеет вид раф —" р0ф, где а является нетерминалом, 0 — некоторое слово в объединенном алфавите VUN, 0 ф А. Слова р и ф, располагающиеся слева и справа нетерминала о, создают некоторый «контекст» (окружение) слова а. Данный вид грамматик используют для анализа естественных языков.

Если для правил КЗ-грамматики снять требование 0 ф А, то полученную грамматику называют обобщенной (ОКЗ-грамматикой).

Контекстно-свободные грамматики (КС-грамматики). Каждое правило имеет вид, а —> 0, где, а — нетерминал, 0 — произвольная (в том числе и пустая) цепочка в объединенном алфавите V U N. Синтаксис языков программирования описывается в терминах именно этих грамматик.

Линейные грамматики (Л). Каждое правило имеет вид а —> р0ф или а —" <�р, где а и 0 — нетерминалы. Другими словами, правая часть правил может содержать не более одного нетерминала.

Регулярные грамматики (Р). Представляют собой частный случай линейных грамматик. Каждое правило задается в виде, а —> ip0 или а —> р, где а и 0 — нетерминалы, р — терминал, либо пустое слово. Грамматики этого типа применяются при описании простейших конструкций языков программирования: идентификаторов, констант, строк. Еще одно важное приложение — описание шаблонов (масок) и регулярных выражений, широко использующихся при создании поисковых запросов.

Можно показать, что имеют место следующие отношения:

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

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

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