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

Формальные грамматики и алгоритмы 12. Формальные грамматики и автоматы 12.1 Типы языков теории языков рассматриваются принципы и особенности построения различных языков. До начала XX века существовали только естественные (разговорные языки). При этом под языком понималось средство общения между людьми. С развитием лингвистики было установлено, что средства общения присущи не только человеку. В настоящее время под языком понимается любое средство общения. Язык включает следующие составные части:  знаковую систему ( множество допустимых последовательностей знаков );  множество смыслов этой системы;  соответствие между последовательностями знаков и смыслами. В качестве знаков языка могут выступать:  символы (буквы) некоторого алфавита (письменная форма языка);  звуки (устная форма языка);  жесты, цвет, запахи и т.д. Наиболее развитыми являются знаковые системы на основе символов. Символ является простейшим элементом знаковой системы. Из символов строятся более сложные конструкции. При анализе разговорных языков иерархия конструкций языка выглядит следующим образом: Буква Þ слово Þ предложение Þ текст. (знак, символ) (фраза) В теории формальных языков используется формальный подход, при котором набор конструкций языка выглядит следующим образом:Символ Þ строка Þ текст. (знак, буква) (цепочка, предложение) Отметим, что в ЭВМ вся информация представляется в виде строк. Таким образом, любое преобразование данных в ЭВМ заключается в преобразовании одних строк в другие. В любом языке можно выделить правильные (допустимые) и неправильные конструкции. Правила построения правильных текстов составляют синтаксис языка. Описание соответствия между смыслами и текстами составляют семантику языка. Семантика языка зависит от происхождения и характера языка, т.е. от характера объектов, описываемых языком. Синтаксис языка меньше зависит от характера языка. Поэтому при изучении синтаксиса можно использовать формальный подход. Суть формального подхода заключается в том, что язык рассматривается как множество формальных объектов, построенных по определенным правилам. В качестве формальных объектов выступают последовательности символов. При построении таких последовательностей их смысл не учитывается. Появление и развитие формального подхода связано с необходимостью решения задач следующего типа: машинный перевод с одного естественного языка на другой; разработка трансляторов;распознавание образов. В зависимости от происхождения и степени универсальности языки можно разделить на типы, представленные на рис.12.1Естественные языки возникают и развиваются постепенно с развитием общества в течение длительного времени. Искусственные языки разрабатываются специально для определенной области применения за относительно короткий период времени. Универсальные языки используются для общения людей в повседневной жизни. Специализированные языки являются средством общения достаточно узкого круга людей при обмене информацией в некоторой специальной области знаний. Примерами специализированных языков могут быть различные профессиональные жаргоны (язык пользователей ЭВМ), язык алгебры, язык алгебры логики и т.д.12.2. Естественные языки и их особенности. Особенности естественных языков вытекают из их происхождения. Основные особенности, затрудняющие формальный подход к изучению естественных языков, перечислены ниже.* Зависимость синтаксиса от семантики (смысла). Например, окончания слов могут зависеть от того, к каким объектам относятся эти слова, одушевленным или неодушевленным. Для примера рассмотрим две похожих фразы:”Я увидел пень” (Что?).”Я увидел оленя” (Кого?).* Семантическая и синтаксическая неоднозначность. Семантическая неоднозначность возникает из-за того, что некоторые слова могут иметь различный смысл. Например, фраза “Косой шел с косой” может иметь различный смысл в зависимости от контекста. Синтаксическая неоднозначность возникает из-за недостаточной строгости синтаксических правил. Например, фраза “Бытие определяет сознание” может быть истолкована различным образом. Если считать, что базовым элементом является бытие, то исходную фразу можно заменить на фразу ” Бытие является главным и оно определяет сознание”. Но исходная фраза может быть истолкована и так: “Бытие определяется сознанием”.* Возможность появления парадоксальных предложений. Парадоксальные предложения построены так, что их нельзя отнести ни к истинным, ни к ложным. Примером парадоксального предложения является фраза: “Данное предложение является ложным”.^ * Зависимость смысла от ситуации. *Изменчивость языка во времени. *Большое число синтаксических правил с многочисленными исключениями. 12.3. Формальные языки и их особенности. Большинство искусственных языков использует при построении предложений формальные, т.е. не зависящие от смысла, правила. Такие языки называются формальными. Синтаксис формальных языков должен обеспечивать возможность формального подхода к построению предложений. Поэтому формальные языки имеют следующие особенности Независимость синтаксических правил от смысла. Невозможность появления парадоксов. Строгость синтаксических правил и отсутствие исключений. Конечное число синтаксических правил. Формальные языки, как и естественные, могут со временем изменяться. Но в отличие от естественных языков эти изменения проявляются не постепенно, а путем появления новых версий языков. При этом различные версии одного и того языка можно рассматривать как различные языки. Наименьшей синтаксической единицей формального языка является символ. Символ (буква) – это простой неделимый знак. Множество символов языка составляют алфавит. Примеры алфавитов: Русский алфавит – {А, а, Б, б, В, в, …, Я, я }. Латинский алфавит – {A, a, b, b, C, c, …, Z, z }. Арабские цифры – { 0, 1, 2, . . . , 9 }. Символы языка объединяются в строки. Строка – это упорядоченная последовательность символов. Примеры строк:Строки в русском алфавите – ” упорядоченная” , ” последовательность” , “а”.Строки в латинском алфавите – “BEGIN” , “THEN” , “END” .Строки в двоичном алфавите – “0”, “1”, “00”, “10”, “01010101” . Количество символов в строке называется длиной строки. Строка символов а1а2а3 . . . аn имеет длину n. Если длина строки равна нулю, то строка называется пустой. Пустая строка обозначается символом l . Заметим, что символ l не является символом алфавита. Множество всех строк алфавита А называется замыканием над алфавитом А и обозначается символом А*. , А* = А0 U А1 U А2 U . . . U Аn = где: А0 Î {l } – пустая строка; Аn – строка длины n. ^ Множество непустых строк А+ определяется следующим образом: А+ = А* \ {l} = Язык в общем случае представляет собой произвольное подмножество множества А*. Так как множество А* по определению бесконечно, то и язык в общем случае тоже является бесконечным. Поэтому язык невозможно задать явно, т.е. перечислением всех допустимых строк. Например, невозможно перечислить все правильные предложения русского языка. Для описания языка нужна специальная система, которая в сжатой форме описывает правила построения допустимых предложений языка. Такая система называется порождающей или формальной грамматикой. Язык, построенный при помощи формальной грамматики, называется формальным языком. Заметим, что строки языка, в том числе и формального, наделены определенным смыслом. Смысл строк языка определяется благодаря некоторой дополнительной информации.12.4 Формальные грамматики В теории формальных языков основными являются две задачи: каким образом строить правильные предложения заданного языка?;  как установить, является ли данное предложение синтаксически правильным, допустимым для данного языка? Первая задача решается при помощи формальных грамматик. Формальная грамматика содержит строгие правила порождения правильных предложений языка. Определение формальной грамматики имеет следующий вид:Формальная (порождающая) грамматика G – это формальная система, определяемая четверкой символов:G = { N, T, P, S },где: N – конечное непустое множество нетерминальных (или вспомогательных) символов;^ T – конечное непустое множество терминальных (или конечных) символов;S – начальный или корневой символ;P – конечное множество правил вывода (правил продукции).Множества N и T являются непересекающимися множествами: N Ç T =Æ. Множества N и T представляют собой алфавиты нетерминальных и терминальных символов.Начальный символ ^ S является исходным символом, из которого при помощи правил вывода строятся все предложения (цепочки) данного языка.Правила вывода P определяют синтаксис формального языка, т.е. правила построения правильных предложений языка.Обычно при описании формальных грамматик принимаются следующие обозначения:  символы нетерминального алфавита обозначаются прописными латински- ми буквами (A, B, C, D, . . . ,Z);  символы терминального алфавита обозначаются строчными буквами (a, b, c, d, . . .) первой половины латинского алфавита;  цепочки терминальных символов обозначаются строчными буквами ( . . . , x, y, z) второй половины латинского алфавита;  цепочки терминальных и нетерминальных символов (смешанные цепочки) обозначаются строчными греческими буквами (a, b, g, d, e, h, w ,,. . . ).Правила вывода представляют собой правила подстановки вида:e ® h где e и h – смешанные цепочки (цепочки в алфавите V = N U T).Правило вывода e ® h означает, что цепочка e заменяется цепочкой h.Цепочка b непосредственно выводима из цепочки a в грамматике G, если a = ged, b = g h d и e ® h является правилом вывода из грамматики G. Например, если цепочка a представляет собой строку символов “ПРИМЕР” и существует правило вывода МЕ® БО, то из цепочки a непосредственно выводится цепочка b = “ПРИБОР”.Цепочка b называется выводимой из цепочки a, если существует последовательность правил вывода, переводящих цепочку a в цепочку b. Так, если a = “ПРИМЕР” и существуют правила вывода МЕ ® БО и И ® О, то из цепочки a выводится цепочка b = “ПРОБОР”.Формальным языком L (G), порожденным грамматикой G, называется множество всех цепочек в терминальном алфавите, выводимых из корневого символа S. Другими словами, формальный язык, порождаемый грамматикой G-это множество цепочек, удовлетворяющих двум условиям: Цепочки состоят только из терминальных символов. Каждая цепочка выводима из S при помощи последовательности правил вывода.12.5 Типы формальных грамматик Формальные грамматики отличаются друг от друга прежде всего типом правил вывода. Классификацию формальных грамматик по типу правил вывода ввел американский лингвист Ноам Хомский. По Хомскому формальные грамматики делятся на 4 типа.Формальная грамматика типа 0 (неограниченная грамматика или грамматика произвольного типа) использует подстановки вида:a ® b, где a и b – цепочки произвольного вида.Формальная грамматика типа 1 или контекстная грамматика (контекстно-зависимая грамматика) использует подстановки вида a A b® aw b где ^ A – нетерминальный символ; a, w, b – цепочки произвольного вида, при этом цепочка w не является пустой или w Î (N U T)+; a, b – контекст правила.Формальная грамматика типа 2 или бесконтекстная грамматика (контекстно-свободная грамматика) использует подстановки вида^ A ® a,где a – произвольная непустая строка, т.е. a Î (N U T)+ .Формальная грамматика типа 3 или регулярная грамматика использует подстановки видаA ® a B или A ® a,где A и B – нетерминальные символы, а – терминальный символ.В теории формальных языков доказывается, что все регулярные грамматики бесконтекстны, все бесконтекстные – контекстны, все контекстные – неограничены. Пример регулярной грамматики:G = {N, T, P, S).N ={S}; T = {a, b}P: S ® a; : S ® b; S ® aS; S ® bS.При помощи этой грамматики порождаются строки символов a и b. Последовательность порождения строк можно пояснить следующей схемой: Применяемое правило вывода Содержание строки S S ® aS aS S ® aS aaS S ® b aabРезультатом вывода является строка aab.Пример бесконтекстной грамматики:G = {N, T, P, S).N ={S}; T = {a, b}P: S ® aSb; S ® ab.При помощи этой грамматики порождаются строки вида anbn.Пример вывода строки a3b3.Применяемое правило вывода Содержание строки S S ® aSb aSb S ® aSb aaSbb S ® ab. aaabbbПример бесконтекстной грамматики более сложного вида:G = {N, T, P, S).N ={S}; T = { IF, THEN, ELSE, U, B}P: S ® B; S ® IF U THEN S; S ® IF U THEN S ELSE S.Эта грамматика позволяет формировать различные условные операторы языка типа Паскаль. Например, оператор IF È THEN IF È THEN B ELSE B может быть сформирован следующим образом.Применяемое правило вывода Содержание строки SS ® IF È THEN S IF È U THEN SS ® IF È THEN S ELSE S IF È THEN IF È THEN S ELSE SS ® B IF È THEN IF È THEN B ELSE SS ® B IF È THEN IF È THEN B ELSE B.Возможен второй вариант: Применяемое правило вывода Содержание строки SS ® IF È U THEN S ELSE S IF È THEN S ELSE SS ® IF È U THEN S IF È THEN IF È THEN S ELSE SS ® B IF È THEN IF È THEN B ELSE SS ® B IF È THEN IF È THEN B ELSE B.12.6. Грамматический разбор Грамматический разбор – это процедура установления правильности данного предложения в данной грамматике. Грамматический разбор может выполняться двумя способами – разбор “сверху вниз”. и разбор “сверху вниз” Разбор “сверху вниз” начинается с корневого символа. Сущность разбора заключается в попытках путем повторяющегося применения правил вывода получить заданное предложение. Если предложение представляет собой арифметическое или логическое выражение, то вначале подбирается подстановка, которая интерпретирует последнюю по порядку выполнения операцию. Разбор “снизу вверх” начинается с заданного предложения и заключается в попытках получить корневой символ при помощи инверсных правил подстановки. Если предложение представляет собой арифметическое или логическое выражение, то первым следует применить правило для интерпретации той операции, которая выполняется первой при вычислении значения данного предложения. Процедуру грамматического разбора удобно проводить. используя специальную разновидность графов – деревья. Дерево – это конечное множество, состоящее из одного или более узлов. Узлы соединяются между собой ветвями. Из каждого узла может выходить несколько ветвей. При этом:  Существует один выделенный узел, называемый корнем дерева.  Остальные узлы разделены на непересекающиеся множества, каждое из которых является деревом. Эти непересекающиеся множества называются поддеревьями. Число поддеревьев узла называется степенью узла. Узел с нулевой степенью называется листом. Листья представляют собой узлы, из которых не выходит ни одной ветви. Отметим, что на рисунках корень дерева располагается вверху, а само дерево вычерчивается сверху вниз. Рассмотрим пример использования деревьев при грамматическом разборе. Пусть задана следующая грамматика: G = {N, T, P, S).N ={S}; T = {a, b, c, Ú, &, ù, (, ) };P: S ® (S Ú S); S (S & S); S ® ù S; S ® a; S ® b; S ® c.Данная грамматика позволяет записывать логические функции трех переменных. Например, последовательность разбора функции ______ _( a Úb ) & cможет быть представлена следующим образом.Применяемое правило вывода Содержание строки S S ® (S & S) (S & S) S ® ù S (ù S & S) S ® (S Ú S) (ù (S Ú S) & S) S ® ù S (ù (S Ú S) & ù S)S ® a (ù (a Ú S) & ù S)S ® b (ù (a Ú b) & ù S)S ® c (ù (a Ú b) & ù c)При помощи дерева последовательность вывода представляется в виде рис. 12.2.. При обходе листьев дерева слева направо можно записать полученное предложение: (ù (a Ú b) & ù c).При грамматическом разборе “снизу вверх” в качестве исходных данных используется проверяемое предложение. Последовательность разбора предложения (ù (S v S) & ù S) показана на рис. 12.3.При грамматическом разборе основными операциями являются операции поиска символов в строке и операции сравнения. Эти операции могут быть выполнены при помощи автоматов с памятью.12.7. Автоматы и формальные грамматики В формальных грамматиках основной операцией преобразования данных является реализация одного из прямых или инверсных правил вывода.(правил продукции или подстановки). В общем случае подстановка заключается в замене строки одного алфавита на другую строку (обычно другого алфавита). Задача замены строк может быть решена в несколько этапов: Разбиение исходного текста на конструкции языка. Выделение простых конструкций.  Подбор правила вывода. Замена простой конструкции в соответствии с выбранным правилом вывода. Реализация каждого этапа является строго формальной процедурой. Поэтому для каждого этапа может быть построен автомат с памятью. Для первых трех этапов необходимо построить автоматы, которые могут обнаружить в тексте символы начала и окончания определенных конструкций языка. Автомат такого типа называют распознавателем. При обнаружении заданной строки в последовательности входных символов он выдает определенный сигнал. Пример синтеза такого автомата приведен в п. 5.2. Для третьего этапа можно использовать автомат-преобразователь, выдающий по сигналу распознавателя определенную последовательность выходных сигналов. Таким образом, для решения задачи грамматического разбора вполне достаточно рассмотренных выше методов синтеза автоматов. В первую очередь для этого подходят автоматы с программным формированием выходных сигналов, которые легко перестраиваются с учетом заданной грамматики. Таким автоматом может быть компьютер. Для решения задачи построения правильных предложений в заданной грамматике в настоящее время также используют компьютер.^ Контрольные вопросыКакие составные части включает язык, рассматриваемый как средство общения?Из каких элементов может состоять знаковая система языка?Что такое синтаксис языка?Что такое семантика языка?Перечислите возможные типы языков.Приведите особенности естественных языков.Приведите пример специализированного естественного языка.Приведите особенности формальных языков.Перечислите конструкции формальных языков.Что такое алфавит?Что такое замыкание над алфавитом?В чем заключается формальный подход к языку?Как задается формальная грамматика?Какие типы символов используются при задании формальной грамматики?Что представляют собой правила вывода?Что такое формальный язык?Какими свойствами обладают предложения формального языка?Дайте характеристику неограниченной формальной грамматики.Дайте характеристику контекстной формальной грамматики.Дайте характеристику бесконтекстной формальной грамматики.Дайте характеристику регулярной формальной грамматики.Что такое грамматический разбор?