Формальные грамматики и их свойства. Формальные грамматики Формальные грамматики распознающие и порождающие
Аннотация: В данном разделе рассматриваются основы дисциплины: "формальная грамматика". Эта дисциплина рассматривает любые операции с символами, а ее выводы широко используются при анализе формальных и "человеческих" языков, а также в искусственном интеллекте. Эта лекция является самой важной и, одновременно, самой сложной для понимания лекцией курса. В связи с этим автор преподносит читателю только ее выводы, опуская математические доказательства. Для лучшего понимания материала может потребоваться обращение к материалам предыдущих и последующих лекций.
10.1. Алфавит
Изучение любого языка человек начинает с азбуки. В формальной грамматике язык определяется вне зависимости от его смысла. Более того, один и тот же язык может формироваться несколькими грамматиками! Это как в школе - не так важен результат (который можно прочитать в конце учебника), как его получение - зафиксированное в тетради решение задачи. Поэтому подойдем к определению алфавита также формально.
О п р е д е л е н и е . Алфавит - это непустое конечное множество элементов.
В "классическом" языке алфавит - это набор литер. В фонетике - набор издаваемых человеком звуков речи. В музыке - это набор нот, и т.д.
С помощью алфавита часто возможно описать бесконечное множество слов. Совокупность всех слов, которую можно создать при помощи грамматики (иначе говоря, порождаемые грамматикой ), называется языком. В отличие от алфавита язык может быть бесконечным.
Всякая конечная последовательность символов алфавита называется словом, или, более профессионально, цепочкой. Цепочками, состоящими из символов {a, b, c}, будут следующие последовательности: a, b, c, aa, ab, bc, ac , bb, abba и другие. Также допускается существование пустой цепочки Л - полное отсутствие символов. Важен также порядок следования символов в цепочке. Так, цепочки ab и ba - разные цепочки. Далее заглавные латинские буквы будут использованы как переменные и символы, а строчные латинские буквы будут обозначать цепочки. Например:
X = SVT Листинг 10.1.
цепочка, состоящая из символов S , V и T , и именно в этом порядке.
О п р е д е л е н и е . Длиной цепочки называется число символов в этой цепочке. Она обозначается как |x| . Например: |Л| = 0, |A| = 1, |BA| = 2, |ABBA| = 4 .
Если x и y являются цепочками, то их конкатенацией будет цепочка xy . От перестановки цепочек при конкатенации результат меняется (как и в теории групп). Если z = xy - цепочка, то x - голова, а y - хвост цепочки. Если нам безразлична голова цепочки, мы будем обозначать:
Z = … x Листинг 10.2.
а если нам безразличен хвост, мы будем писать:
Z = x … Листинг 10.3.
О п р е де л е н и е . Произведение двух множеств цепочек определяется как конкатенация всех цепочек, входящих в эти множества . Например, если множество A = {a, b}, а B = {c,d} , то:
AB = {ac, ad, bc, bd} Листинг 10.4.
В произведении множеств, как и при конкатенации, порядок множителей существенен.
И при конкатенации цепочек, и при перемножении множеств цепочек истинным остается ассоциативный закон, записывающийся как:
Z = (ab)c = a(bc) = abc Листинг 10.5.
D = (AB)C = A(BC) = ABC Листинг 10.6.
И, наконец, определим степень цепочки. Если x - непустая цепочка, то x 0 = {Л}, x 1 = x, x 2 = xx, x n = x(x) (n-1) . То же самое обстоит и со степенью множеств.
10.2. Терминальные и нетерминальные символы
Понятие терминальных и нетерминальных символов тесно связано с понятием правила подстановки (или продукции). Дадим его определение .
О п р е д е л е н и е . Продукцией, или правилом подстановки, называется упорядоченная пара (U, x ), записываемая как:
U::= x Листинг 10.7.
где U - символ, а x - непустая конечная цепочка символов .
Символы, встречающиеся только в правой части, называются терминальными символами . Символы, встречающиеся и в левой, и в правой части правил, называются нетерминальными символами, или синтаксическими единицами языка. Множество нетерминальных символов обозначается как VN, а терминальных символов - VT.
Примечание . Данное определение терминальных и нетерминальных символов истинно для КС- грамматик и A- грамматик (см. раздел 10.4.3).
О п р е д е л е н и е . Грамматикой G[Z] называют конечное, непустое множество правил, содержащее нетерминальный символ Z хотя бы один раз на множестве правил. Символ Z называют начальным символом. Далее мы все нетерминальные символы будем обозначать как <символ>.
[Пример 01]
Грамматика : "число"
<число> ::= <чс> <чс> ::= <цифра> <чс> ::= <чс><цифра> <цифра> ::= 0 <цифра> ::= 1 <цифра> ::= 2 <цифра> ::= 3 <цифра> ::= 4 <цифра> ::= 5 <цифра> ::= 6 <цифра> ::= 7 <цифра> ::= 8 <цифра> ::= 9
Дадим еще определение :
О п р е д е л е н и е . Цепочка v непосредственно порождает цепочку w , если:
V = xy, а w = xuy Листинг 10.8.
где ::= u - правило грамматики . Это обозначается как v => w . Мы также говорим, что цепочка w непосредственно выводима из v . При этом цепочки x и y могут быть пустыми.
О п р е д е л е н и е . Говорят, что v порождает w , или w приводится к v , если существует конечная цепочка выводов u0, u1, …, u[n] (n > 0) , такая, что
V = u0 => u1 => u2 => … => u[n] = w Листинг 10.9.
Эта последовательность называется выводом длиной n , и обозначается v =>+ w . И, наконец, пишут:
V =>* w, если v => w или v =>+ w Листинг 10.10.
10.3. Фразы
О п р е д е л е н и е
. Пусть G[Z]
- грамматика
, x
- цепочка. Тогда x
называют сентенциальной формой, если
О п р е д е л е н и е . Пусть G[Z] - грамматика . И пусть w = xuy - сентенциальная форма. Тогда u называется фразой сентенциальной формы w для нетерминального символа , если:
Z =>* xy и =>+ u Листинг 10.11.
Z =>* xy и => u Листинг 10.12.
то цепочка u называется простой фразой.
Следует быть осторожным с термином "фраза". Тот факт, что =>+ u (цепочка u выводима из ) вовсе не означает, что u является фразой сентенциальной формы xy; необходима также выводимость цепочки xy из начального символа грамматики Z .
В качестве иллюстрации фразы рассмотрим [Пример 01] сентенциальную форму <чс>1 . Значит ли это, что символ <чс> является фразой, если существует правило: <число> ::= <чс> ? Конечно же, нет, поскольку невозможен вывод цепочки: <число><1> - из начального символа: <число> . Какие же фразы сентенциальной формы <чс>1 ? Рассмотрим вывод :
<число> => <чс> => <чс><цифра> => <чс><1> Листинг 10.13.
Таким образом,
<число> =>* <чс> и <чс> =>+ <чс>1 Листинг 10.14.
Рассмотрим формальную грамматику, которая в какой-то степени напоминает фрагмент грамматики русского языка и задает формальный язык, состоящий из четырех русских предложений. В этой формальной грамматике используются элементы, играющие роль членов предложения или частей речи:
<предложение>
<подлежащее>
<сказуемое>
<дополнение>
<прилагательное>
<существительное>
Эти элементы заключены в угловые скобки, чтобы отличать их от слов из фактического словаря, составляющих предложения языка. В нашем примере словарь состоит из следующих пяти слов, или «символов»: V= {дом, дуб, заслоняет, старый, (точка)}. В грамматике имеются определенные правила, содержащие информацию о том, как их этих символов можно строить предложения языка. Одно из этих правил таково:
1. <предложение> ® <подлежащее> <сказуемое> <дополнение>.
Это правило интерпретируется следующим образом: «Предложение может состоять из подлежащего, за которым следует сказуемое, затем дополнение и точка». В грамматике вполне могут быть и другие правила, задающие предложения другой структуры. Однако в данной грамматике таких правил нет. Остальные правила таковы:
2. <подлежащее> ® <прилагательное> <существительное>
3. <дополнение> ® <прилагательное> <существительное>
4. <сказуемое> ® заслоняет
5. <прилагательное> ® старый
6. <существительное> ® дом
7. <существительное> ® дуб
Применим эту грамматику для порождения (или вывода) предложения.
По правилу 1 предложение имеет вид:
<предложение> 1 ® <подлежаще е> <сказуемое> <дополнение> 2 →
2 →<прилагательное><существительное> <сказуемое><дополнение > 3 →
3 →<прилагательно е><существительное> <сказуемое> <прилагательное> <существительное> 4 →Старый <существительное> <сказуемое> <прилагательно е> <существительное>
4 → Старый <существительное > <сказуемое> старый <существительное >
6,7 →Старый дом <сказуемое> старыйдуб
4 → Старый домзаслоняетстарыйдуб
Таким образом, получаем готовое предложение:
Старый дом заслоняет старый дуб .
Этот вывод можно наглядно изобразить в виде дерева. Дерево вывода показывает, какие правила применялись к различным промежуточным элементам, но скрывает порядок их применения. Таким образом, можно видеть, что результирующая цепочка не зависит от порядка, в котором делались замены промежуточных элементов. Говорят, что дерево представляет собой «синтаксическую структуру» предложения.
Идея вывода показывает другие интерпретации правил, подобных правилу <подлежащее> ® <прилагательное> <существительное> . Вместо того, чтобы говорить «подлежащее это прилагательное , за которым следует существительное », можно сказать, что подлежащее «порождает» (или «из него выводятся», или «его можно заменить на») <прилагательное> <существительное>.
С помощью приведенной выше грамматики можно вывести также три других предложения, а именно:
Старый дуб заслоняет старый дом.
Старый дом заслоняет старый дом.
Старый дуб заслоняет старый дуб.
Эти предложения и предложение, выведенное раньше, и есть все предложения порождаемые данной грамматикой.
Множество, состоящее из этих четырех предложений, называется языком, который определяется данной грамматикой («порождается ею» или «выводится в ней»).
При создании формальных языков необходимо выбрать множество базовых знаков для формирования лексем, указать множество синтаксических правил написания выражений и предложений, согласовать множество семантических правил для интерпретации их значений. Подобно естественным языкам, грамматики формальных языков организованы в виде иерархии синтаксических конструкций, формирующих лексемы и последовательности лексем - выражения и предложения. Элементы нижнего уровня образованы знаками базового набора и формируют слова или лексемы формального языка. Элементы следующих уровней, образованные цепочками лексем и/или синтаксических переменных, формируют выражения формального языка. Элементы самого верхнего уровня, образованные цепочками выражений, формируют предложение. Так как языки программирования являются формальными языками, то все последующие обсуждения будем сопровождать примерами на этих языках.
Множество базовых знаков, используемых в языках программирования, опирается на 26 строчных и прописных букв латинского алфавита, на 10 арабских цифр и на 26 специальных символов, имеющих фиксированное значение (знаки препинания, арифметических действий, сравнения и т.п.).
Множество синтаксических правил, по которым строят синтаксически правильные выражения и предложения программы, определяет содержание грамматики языка программирования.
Для формирования модели грамматики обозначим элементарные лексические единицы языка строчными буквами латинского алфавита. Знаки этого множества называют терминальными (от лат. terminus - предел,конец). Множество терминальных символов обозначим знаком V T . Это множество называют также словарем или лексикой языка. Множество V T - счетно, но не конечно, т.к. всегда можно добавить новую лексему для какой-либо синтаксической переменной.
Элементарными лексическими единицами большинства языков программирования являются:
значения идентификаторов констант, переменных, программ, процедур, функций и т.п. в виде последовательности букв латинского алфавита и цифр, начинающейся обязательно с буквы;
<служебные слова>: := AND ½ ARRAY ½ BEGIN ½ CASE ½ CONS ½ DIV ½ DOWNTO ½ DO ½ ELSЕ ½ END ½ FILE ½ FOR ½ FUNCTION ½ GOTO ½ IF ½ IN ½ LABEL ½ MOD ½ NIL ½ NOT ½ OF ½ OR ½ PACKED ½ PROCEDURE ½ PROGRAM ½ RECORD ½ REPEAT ½ SET½ THEN ½ TO ½ TYPE ½ UNTIL ½ VAR ½ WHILE ½ WITH ;
<специальные символы>: := + ½ - ½ * ½ / ½ = ½ < ½ > ½ <= ½ >= ½ [ ½ ] ½ (½) ½ _ ½:= ½ " ½ " ½ . ½ , ½: ½ ; ½ ¹ ½# ½$ ;
десятичные числа без знака.
В выражениях и предложениях формального языка, cодержащих лексемы и синтаксические переменные, лексемы всегда заключены в кавычки. Например, "BEGIN", "NOT", AND" и др.
Для обозначения синтаксических переменных введем прописные буквы латинского алфавита. Знаки этого множества называют нетерминальными. Обозначим множество нетерминальных символов знаком V N .
Множество V N - счетно и конечно.
Элементарными синтаксическими переменными для языка программирования являются:
<блок > :: = <блок-операторов>½<блок-процедуры>½<блок-функции>½...;
<заголовок > ::= <заголовок-программы>½<заголовок-процедуры>½
<заголовок-функции>½...;
<идентификатор > ::= <идентификатор-программы>½<идентификатор-
переменной>½...;
<оператор > ::= <оператор-присваивания>½<оператор-ЕСЛИ>...;
<операция > ::= <операция-сложения>½<операция-умножения>
½<операция-отношения>½...;
и другие синтаксические переменные.
В языке Паскаль всего около 240 синтаксических переменных.
В выражениях и предложениях формального языка, содержащих синтаксические переменные, их заключают в угловые скобки. Например, "PROGRAM" <идентификатор-программы> ";" "BEGIN" <блок-операторов> "END" и др.
Объединение символов двух множеств V T и V N представляет множество символов формального языка, т.е.
V = V T ÈV N . (2)
Цепочки символов формального языка могут содержать различное количество терминальных и/или нетерминальных символов. Поэтому множество правильных цепочек может быть записано так:
Если каждый элемент множества V* обозначить строчной буквой греческого алфавита, то множество V* можно описать перечислением его элементов:
V* = { a ; b ; g ;... } (4)
Например,
a:= "PROGRAM"<идентификатор-программы>";"<блок>".";
b:= "CONST" <определение-константы> "; " ;
g:= "(" <идентификатор> { " , " <идентификатор> } ") " ;
где знак ":=" означает: "...присвоить значение...". Цепочка a ÎV* содержит пять символов множества V, цепочка b ÎV* - три символа и цепочка g Î V* - не менее трех символов, т.к. в языках программирования знак "{ .. }" означает многократное повторение выражения, заключенного в фигурные скобки, включая нуль раз.
Конструкция программы на любом языке программирования состоит, как правило, из двух частей: заголовка - <заголовок-программы> и тела программы - <блок>. В заголовке программы, начинающемся служебным словом "PROGRAM", ей присваивается имя (идентификатор), вслед за которым в круглых скобках задается перечень идентификаторов тех файлов, через которые программа взаимодействует с внешним миром. В теле программы должны следовать в определенном порядке разделы меток, констант, типов, переменных, процедур, функций и операторов. Так как разделы, предшествующие разделу операторов, носят описательный характер, то каждый из них может быть пустой цепочкой, а раздел операторов является основным и должен присутствовать в любой программе. Поэтому в последующих объяснениях <блок> содержит только описание операторов, т.е. исполняет функции <блока-операторов>.
Синтаксические правила формальной грамматики можно рассматривать как элементарные операторы подстановки, которые, будучи примененными в определенной последовательности к исходной цепочке терминальных и/или нетерминальных символов, порождают правильные цепочки этих же символов. Поэтому эти правила часто называют правилами подстановки или продукциями.
Продукцию или правило подстановки записывают так:
где a - левая часть правила,
b - правая часть правила.
Если правил несколько,то их необходимо индексировать:
p i: a i::= b i , где i = 1;2;3;... (6)
Левая часть правила не может быть пустой цепочкой и всегда содержит один или несколько нетерминальных символов, т.е.
a ÎV* \ e, где e - пустая цепочка. (7)
Правая часть правила может содержать пустые цепочки и не содержать нетерминальных символов, т.е.
b ÎV * или b ÎV*\ V N . (8)
Пример 3 . Пусть даны несколько правил языка программирования Паскаль:
<программа> ::= <заголовок-программы> " ; "<блок>" . ";
<заголовок-программы> ::= "PROGRAM"<идентификатор-программы>;
<блок> ::= <раздел-операторов> | ...;
<раздел-операторов> ::= "BEGIN" <оператор> " END" ;
<оператор> ::= <оператор-присваивания> |...;
<оператор-присваивания> ::= <переменная> " := " <выражение>;
<выражение> ::= <терм> <операция-сложения> <терм> ;
<терм> ::= <множитель> <операция-умножения> <множитель>;
<множитель> ::= <переменная> ;
<переменная> ::= <идентификатор-переменной> ;
<операция-сложения> ::= " + " | " - " | "OR";
<операция-умножения> ::= " x " | " / " | "DIV" | "MOD" |"AND".
Синтаксической переменной <идентификатор-программы> присвоим какое-либо значение (например, "ALGEBRA"), т.е.
<идентификатор-программы>::= "ALGEBRA".
Cинтаксической переменной <идентификатор-переменной> также присвоим какое-либо значение, начинающееся с буквы (например," i "), т.е.
<идентификатор-переменной> ::= " i ".
Последовательность использования правил подстановки в процессе формирования цепочки терминальных и/или нетерминальных символов называют выводом. Поэтому эти же правила часто называют правилами вывода. Для указания процесса вывода используют знак "=>".
Выводы бывают левосторонние и правосторонние. При левостороннем выводе продукцию применяют к самому левому нетерминальному символу цепочки, а при правостороннем - к самому правому.
Пример 4 . а) Для начального символа <программа> (пример 3) исполнить левосторонний вывод:
<программа> => <заголовок-программы> ";" <блок> "." => "PROGRAM" <идентификатор-программы> ";" <блок> "." => "PROGRAM" "ALGEBRA" ";" <блок> "." => "PROGRAM" "ALGEBRA" ";" <раздел-операторов> "." => <оператор> "END" "." => "PROGRAM" "ALGEBRA" ";" "BEGIN" <оператор-присваивания> "END" "." => ."PROGRAM" "ALGEBRA" ";" "BEGIN" <переменная> ":= " <выражение> "END" "." => "PROGRAM" "ALGEBRA" ";" "BEGIN" <идентификатор-переменной> ":=" <выражение> "END" "." => "PROGRAM" "ALGEBRA" ";" "BEGIN" " i " ":=" <выражение> "END" "." => ..
b) Для начального символа <программа> (пример 3) исполнить правосторонний вывод:
<программа> => <заголовок-программы> ";" <блок> "." => <заголовок-программы> ";" <раздел-операторов> "." => <заголовок-программы> ";" "BEGIN" <оператор> "END" "." => <заголовок-программы> ";" "BEGIN" <оператор-присваивания> "END" "." => <заголовок-программы> ";" "BEGIN" <переменная> ":=" <выражение> "END" "." => ...
Cинтаксической переменной <выражение> может быть любое арифметическое, алгебраическое или логическое выражение. Так как содержание этого выражения не определено, то оба вывода остановились на этой синтаксической переменной. Остальные члены предложения <программа> представлены элементарными лексическими единицами текста программы.,
Пример 5 . Для cинтаксической переменной <выражение> (пример 3) выполнить левосторонний вывод:
<выражение> => <терм><операция-сложения><терм>=> <множитель> <операция-умножения><множитель><операция-сложения><терм> => <переменная><операция-умножения><множитель><операция-сложения> <терм>=> <идентификатор-переменной><операция-умножения> <множитель> <операция-сложения><терм> => "i" <операция-умножения> <множитель><операция-сложения><терм> => "i" "x" <множитель><операция-сложения><терм> => "i" "x" <переменная><операция-сложения><терм> => "i" "x" <идентификатор-переменной><операция-сложения><терм> => "i" "x" "i" <операция-сложения><терм> => "i" "x" "i" "+" <терм> => "i" "x" "i" "+" <множитель><операция-умножения><множитель> => "i" "x" "i" "+" <переменная> <операция-умножения><множитель> => "i" "x" "i" "+" <идентификатор-переменной><операция-умножения> <множитель> => "i" "x" "i" "+" "i" <операция-умножения> <множитель> => "i" "x" "i" "+" "i" "x" <множитель> "i" "x" "i" "+" "i" "x" <переменная> => "i" "x" "i" "+" "i" "x"<идентификатор-переменной> => "i" "x" "i" "+" "i" "x" "I".
Имя начальной синтаксической переменной языка, для которой дано множество правил вывода называют начальным символом и обозначают буквой J. Роль начального символа может исполнять любая синтаксическая переменная. Для текста программы начальной синтаксической переменной является <программа>. Для части текста программы - выражения - начальной синтаксической переменной является <выражение>.
Итак, модель формальной грамматики может быть описана совокупностью четырех основных компонент:
G = á V T ; V N ;J ; P ñ , (9)
где V T = { a;b;c;... } - терминальные символы;
V N = { A;B;C;...} - нетерминальные символы;
JÎ Vn - начальный символ;
P = { p i |i = 1; 2; 3; ... } - синтаксические правила.
Множество правильных цепочек терминальных символов представляет выражения и предложения формального языка данной формальной грамматики L(G) :
L (G) = { a , b , g ,...½ a , b , g Î V *\ VN }. (10)
Текст программы, ограниченный разделителем ".", называют предложением, а часть текста, ограниченную разделителем ";" , - выражением.
Если для начального символа дана цепочка терминальных и/или нетерминальных символов, то формальная грамматика позволяет установить, является ли эта цепочка правильной, и, в случае положительного ответа, выяснить структуру этой цепочки. Такая грамматика называется распознающей. Например, синтаксический анализатор компилятора проверяет текст исходной программы и, в случае положительного ответа, транслирует его на язык вычислительной машины. Для такого анализатора должны быть разработаны правила разбора текста программы.
Если для начального символа не дана цепочка терминальных и/или нетерминальных символов или дана ее часть, то формальная грамматика оказывает помощь в построении синтаксически правильной цепочки терминальных символов с указанием ее состава и структуры. Такая грамматика называется порождающей.
Алгоритм был ранее определен как алфавитный оператор с конечной системой правил преобразования. Для записи входных, промежуточных и выходных слов используется некоторый алфавит. Каким-то образом должны быть описаны и правила преобразования. Очевидно, для этого требуется некоторый язык. Пригоден ли для описания алгоритма обычный разговорный язык?
Любой естественный язык возникал как средство общения людей. Именно по этой причине ему присущи такие особенности как:
· изменчивость, которая состоит в непостоянстве словарного состава языка;
· неоднозначность трактовки фраз различными людьми;
· избыточность, о чем шла речь в главе «Кодирование символьной информации».
Перечисленные особенности не позволяют применить естественный язык для записи алгоритма, поскольку одним из свойств алгоритма является его детерминированность, т.е. однозначность выполнения шагов любым исполнителем. Наиболее простой путь преодоления нежелательных свойств естественных языков - построение языков искусственных со строгим синтаксисом и полной смысловой определенностью - такие языки получили название формальных.
В любом языке - естественном или искусственном - можно выделить две составляющие: синтаксис и семантику. Синтаксис (грамматика языка) - это совокупность правил, согласно которым строятся допустимые в данном языке конструкции. Семантика - смысловая сторона языка - она соотносит единицы и конструкции языка с некоторым внешним миром, для описания которого язык используется.
Для описания формального языка необходим другой язык, с помощью которого будут создаваться языковые конструкции. Описываемый формальный язык называется языком-объектом, а язык, средствами которого производится описание - метаязыком. Метаязык должен обеспечивать как описание структурных единиц языка и правил объединения их в допустимые предложения, так и содержательную (смысловую) сторону языковых конструкций.
Любая грамматика начинается с указания алфавита, т.е. набора символов, посредством которого строятся конструкции языка.
Синтаксис формального языка задается некоторой системой правил (порождающей системой), которая из небольшого набора исходных конструкций порождает все допустимые их комбинации, т.е. язык образуется как множество разрешенных правилами сочетаний исходных конструкций. Кроме этого, синтаксис содержит формулировку условия, которое выполняется для законченных конструкций языка и не выполняется в противном случае.
Помимо синтаксиса устанавливается система правил, позволяющих конструкциям языка придать смысл - эти правила образуют семантику языка.
Формальная грамматика - система правил, описывающая множество конечных последовательностей символов формального алфавита.
Конечные цепочки символов называются предложениями формального языка, а само множество цепочек - языком, описываемым данной грамматикой.
Набор синтаксических правил формального языка аналогичен системе подстановок, используемых в нормальных алгоритмах Маркова. Вывод в данной порождающей грамматике есть последовательность цепочек, в которой любая, начиная со второй, получается из предыдущей применением какого-либо правила вывода.
Формальная грамматика задается упорядоченной четверкой {T , N, S, Р }, где Т и N - непересекающиеся конечные множества, образующие алфавит или словарь порождаемого формального языка; Т называется множеством (словарем) терминальных символов; N - множеством (словарем) нетерминальных (вспомогательных) символов. S - начальный (выделенный) вспомогательный символ из множества N. Р - набор правил вывода конструкций языка (подстановок) из выделенного вспомогательного символа, имеющие вид g → h, где g и h - цепочки, состоящие как из терминальных, так и нетерминальных символов.
Подстановки работают следующим образом: если в преобразуемой цепочке есть слово g , то оно заменяется словом h. Единственное ограничение на вид подстановок состоит в том, что слово g не может состоять только из терминальных символов. Это означает, что получение на некотором шаге цепочки, состоящей только из терминальных символов, свидетельствует о прекращении процесса порождения - эта цепочка является правильной, завершенной конструкцией порождаемого языка. Подстановки Р могут применяться к трансформируемой цепочке в произвольном порядке.
- Tutorial
Мотивация
Время от времени на Хабре публикуются посты и переводные статьи, посвященные тем или иным аспектам теории формальных языков. Среди таких публикаций (не хочется указывать конкретные работы, чтобы не обижать их авторов), особенно среди тех, которые посвящены описанию различных программных инструментов обработки языков, часто встречаются неточности и путаница. Автор склонен считать, что одной из основных причин, приведших к такому прискорбному положению вещей, является недостаточный уровень понимания идей, лежащих в основании теории формальных языков.Этот текст задуман как популярное введение в теорию формальных языков и грамматик. Эта теория считается (и, надо сказать, справедливо) довольно сложной и запутанной. На лекциях студенты обычно скучают и экзамены тем более не вызывают энтузиазма. Поэтому и в науке не так много исследователей в этой тематике. Достаточно сказать, что за все время, с зарождения теории формальных грамматик в середине 50-х годов прошлого века и до наших дней, по этому научному направлению было выпущено всего две докторских диссертации. Одна из них была написана в конце 60-х годов Алексеем Владимировичем Гладким, вторая уже на пороге нового тысячелетия - Мати Пентусом.
Далее в наиболее доступной форме описаны два основных понятия теории формальных языков: формальный язык и формальная грамматика. Если тест будет интересен аудитории, то автор дает торжественное обещание разродиться еще парой подобных опусов.
Формальные языки
Коротко говоря, формальный язык - это математическая модель реального языка. Под реальным языком здесь понимается некий способ коммуникации (общения) субъектов друг с другом. Для общения субъекты используют конечный набор знаков (символов), которые проговариваются (выписываются) в строгом временном порядке, т.е. образуют линейные последовательности. Такие последовательности обычно называют словами или предложениями. Таким образом, здесь рассматривается только т.н. коммуникативная функция языка, которая изучается с использованием математических методов. Другие функции языка здесь не изучаются и, потому, не рассматриваются.Чтобы лучше разобраться в том, как именно изучаются формальные языки, необходимо сначала понять, в чем заключаются особенности математических методов изучения. Согласно Колмогорову и др. (Александров А.Д., Колмогоров А.Н., Лаврентьев М.А. Математика. Ее содержание, методы и значение. Том 1. М.: Издательство Академии Наук СССР, 1956.), математический метод, к чему бы он ни применялся, всегда следует двум основным принципам:
- Обобщение (абстрагирование). Объекты изучения в математике - это специальные сущности, которые существуют только в математике и предназначены для изучения математиками. Математические объекты образуются путем обобщения реальных объектов. Изучая какой-нибудь объект, математик замечает только некоторые его свойства, а от остальных отвлекается. Так, абстрактный математический объект «число» может в реальности обозначать количество гусей в пруду или количество молекул в капле воды; главное, чтобы о гусях и о молекулах воды можно было
говорить как о совокупностях. Из такой «идеализации» реальных объектов следует одно важное свойство: математика часто оперирует бесконечными совокупностями, тогда как в реальности таких совокупностей не существует. - Строгость рассуждений. В науке принято для выяснения истинности того или иного рассуждения сверять их результаты с тем, что существует в действительности, т.е. проводить эксперименты. В математике этот критерий проверки рассуждения на истинность не работает. Поэтому выводы не проверяются экспериментальным путем, но принято доказывать их справедливость строгими, подчиняющимися определенным правилам, рассуждениями. Эти рассуждения называются доказательствами и доказательства служат единственным способом обоснования верности того или иного утверждения.
В качестве известного примера такой математической абстракции можно привести модель, известную под неблагозвучным для русского уха названием «мешок слов». В этой модели исследуются тексты естественного языка (т.е. одного из тех языков, которые люди используют в процессе повседневного общения между собой). Основной объект модели мешка слов - это слово, снабженное единственным атрибутом, частотой встречаемости этого слова в исходном тексте. В модели не учитывается, как слова располагаются рядом друг с другом, только сколько раз каждое слово встречается в тексте. Мешок слов используется в машинном обучении на основе текстов в качестве одного из основных объектов изучения.
Но в теории формальных языков представляется важным изучить законы расположения слов рядом друг с другом, т.е. синтаксические свойства текстов. Для этого модель мешка слов выглядит бедной. Поэтому формальный язык задается как множество последовательностей, составленных из элементов конечного алфавита. Определим это более строго.
Алфавит представляет собой конечное непустое множество элементов. Эти элементы будем называть символам. Для обозначения алфавита обычно будем использовать латинское V, а для обозначения символов алфавита - начальные строчные буквы латинского алфавита. Например, выражение V = {a,b} обозначает алфавит из двух символов a и b.
Цепочка представляет собой конечную последовательность символов. Например, abc - цепочка из трех символов. Часто при обозначении цепочек в символах используют индексы. Сами цепочки обозначают строчными символами конца греческого алфавита. Например, omega = a1...an - цепочка из n символов. Цепочка может быть пустой, т.е. не содержать ни одного символа. Такие цепочки будем обозначать греческой буквой эпсилон.
Наконец, формальный язык L над алфавитом V - это произвольное множеств цепочек, составленных из символов алфавита V. Произвольность здесь означает тот факт, что язык может быть пустым, т.е. не иметь ни одной цепочки, так и бесконечным, т.е. составленным из бесконечного числа цепочек. Последний факт часто вызывает недоумение: разве имеются реальные языки, которые содержат бесконечное число цепочек? Вообще говоря, в природе все конечно. Но мы здесь используем бесконечность как возможность образования цепочек неограниченной длины. Например, язык, который состоит из возможных имен переменных языка программирования C++, является бесконечным. Ведь имена переменных в C++ не ограничены по длине, поэтому потенциально таких имен может быть бесконечно много. В реальности, конечно, длинные имена переменных не имеют для нас особого смысла т.к. к концу чтения такого имени уже забываешь его начало. Но в качестве потенциальной возможности задавать неограниченные по длине переменные, это свойство выглядит полезным.
Итак, формальные языки - это просто множества цепочек, составленных из символов некоторого конечного алфавита. Но возникает вопрос: как можно задать формальный язык? Если язык конечен, то можно просто выписать все его цепочки одну за другой (конечно, можно задуматься, имеет ли смысл выписывать цепочки языка, имеющего хотя бы десять тысяч элементов и, вообще, есть ли смысл в таком выписывании?). Что делать, если язык бесконечен, как его задавать? В этот момент на сцену выходят грамматики.
Формальные грамматики
Способ задания языка называет грамматикой этого языка. Таким образом, грамматикой мы называем любой способ задания языка. Например, грамматика L = {a^nb^n} (здесь n - натуральное число) задает язык L, состоящий из цепочек вида ab, aabb, aaabbb и т.д. Язык L представляет собой бесконечное множество цепочек, но тем не менее, его грамматика (описание) состоит всего из 10 символов, т.е. конечна.Назначение грамматики - задание языка. Это задание обязательно должно быть конечным, иначе человек не будет в состоянии эту грамматику понять. Но каким образом, конечное задание описывает бесконечные совокупности? Это возможно только в том случае, если строение всех цепочек языка основано на единых принципов, которых конечное число. В примере выше в качестве такого принципа выступает следующий: «каждая цепочка языка начинается с символов a, за которыми идет столько же символов b». Если язык представляет собой бесконечную совокупность случайным образом набранных цепочек, строение которых не подчиняется единым принципам, то очевидно для такого языка нельзя придумать грамматику. И здесь еще вопрос, можно или нет считать такую совокупность языком. В целях математической строгости и единообразия подхода обычно такие совокупности языком считают.
Итак, грамматика языка описывает законы внутреннего строения его цепочек. Такие законы обычно называют синтаксическими закономерностями. таким образом, можно перефразировать определение грамматики, как конечного способа описания синтаксических закономерностей языка. Для практики интересны не просто грамматики, но грамматики, которые могут быть заданы в рамках единого подхода (формализма или парадигмы). Иначе говоря, на основе единого языка (метаязыка) описания грамматик всех формальных языков. Тогда можно придумать алгоритм для компьютера, который будет брать на вход описание грамматики, сделанное на этом метаязыке, и что-то делать с цепочками языка.
Такие парадигмы описания грамматик называют синтаксическими теориями. Формальная грамматика - это математическая модель грамматики, описанная в рамках какой-то синтаксической теории. Таких теорий придумано довольно много. Самый известный метаязык для задания грамматик - это, конечно, порождающие грамматики Хомского. Но имеются и другие формализмы. Один из таких них - окрестностные грамматики, будет описан чуть ниже.
С алгоритмической точки зрения грамматики можно подразделить по способу задания языка. Имеются три основных таких способа (вида грамматик):
- Распознающие грамматики. Такие грамматики представляют собой устройства (алгоритмы), которым на вход подается цепочка языка, а на выходе устройство печатает «Да», если цепочка принадлежит языку, и «Нет» - в противном случае.
- Порождающие грамматики. Этот вид устройств используется для порождения цепочек языков по требованию. Образно говоря, при нажатии кнопки будет сгенерирована некоторая цепочка языка.
- Перечисляющие грамматики. Такие грамматики печатают одну за другой все цепочки языка. Очевидно, что если язык состоит из бесконечного числа цепочек, то процесс перечисления никогда не остановится. Хотя, конечно его можно остановить принудительно в нужный момент времени, например, когда будет напечатана нужная цепочка.
Окрестностные грамматики
В середине 60-х годов советский математик Юлий Анатольевич Шрейдер предложил простой способ описания синтаксиса языков на основе т.н. окрестностных грамматик. Для каждого символа языка задается конечное число его «окрестностей» - цепочек, содержащих данный символ (центр окрестности) где-то внутри. Набор таких окрестностей для каждого символа алфавита языка называется окрестностной грамматикой. Цепочка считается принадлежащей языку, задаваемому окрестностной грамматикой, если каждый символ этой цепочки входит в нее вместе с некоторой своей окрестностью.В качестве примера рассмотрим язык A = {a+a, a+a+a, a+a+a+a,...} . Этот язык представляет собой простейшую модель языка арифметических выражений, где роль чисел играет символ «a», а роль операций - символ "+". Составим для этого языка окрестностную грамматику. Зададим окрестности для символа «a». Символ «a» может встречаться в цепочках языка A в трех синтаксических контекстах: вначале, между двумя символами "+" и в конце. Для обозначения начала и конца цепочки введем псевдосимвол "#". Тогда окрестности символа «a» будут следующими: #a+, +a+, +a# . Обычно для выделения центра окрестности этот символ в цепочке подчеркивается (ведь в цепочке могут быть и другие такие символы, которые не являются центром!), здесь этого делать не будем за неимением простой технической возможности. Символ "+" встречается только между двух символов «a», поэтому для него задается одна окрестность, цепочка a+a .
Рассмотрим цепочку a+a+a и проверим, принадлежит ли она языку. Первый символ «a» цепочки входит в нее вместе с окрестностью #a+ . Второй символ "+" входит в цепочку вместе с окрестностью a+a . Подобное вхождение можно проверить и для остальных символов цепочки, т.е. данная цепочка принадлежит языку, как и следовало ожидать. Но, например, цепочка a+aa языку A не принадлежит, поскольку последний и предпоследний символы «a» не имеют окрестностей, с которыми они входят в эту цепочку.
Не всякий язык может быть описан окрестностной грамматикой. Рассмотрим, например, язык B, цепочки которого начинаются либо с символа «0», либо с символа «1». В последнем случае далее в цепочке могут идти символы «a» и «b». Если же цепочка начинается с нуля, то далее могут идти только символы «a». Нетрудно доказать, что для этого языка нельзя придумать никакой окрестностной грамматики. Легитимность вхождения символа «b» в цепочку обусловлена ее первым символом. Для любой окрестностной грамматики, в которой задается связь между символами «b» и «1» можно будет подобрать достаточно длинную цепочку, чтобы всякая окрестность символа «b» не доставала до начала цепочки. Тогда в начало можно будет подставить символ «0» и цепочка будет принадлежать языку A, что не отвечает нашим интуитивным представлениям о синтаксическом строении цепочек этого языка.
С другой стороны, легко можно построить конечный автомат, который распознает этот язык. Значит, класс языков, которые описываются окрестностными грамматиками, уже класса автоматных языков. Языки, задаваемые окрестностными грамматиками, будем называть шрейдеровскими. Таким образом, в иерархии языков можно выделить класс шрейдеровских языков, который является подклассом автоматных языков.
Можно сказать, что шрейдеровские языки задают одно простое синтаксическое отношение - «быть рядом» или отношение непосредственного предшествования. Отношение дальнего предшествования (которое, очевидно, присутствует в языке B) окрестностной грамматикой задано быть не может. Но, если визуализировать синтаксические отношения в цепочках языка, то для диаграмм отношений, в которые превращаются такие цепочки, можно придумать окрестностную грамматику.
