Языки и грамматики. Обозначения, определения

И КЛАССИФИКАЦИЯ

Вначале дадим ряд определений.

Алфавит - это непустое конечное множество элементов. Элементы алфавита называются символами

Всякая конечная последовательность символов алфавита называется цепочкой. Так a, b, c, ab, aaca - цепочки в алфавите A = {a,b,c}.

Допустим существование пустой цепочки e, не содержащей ни одного символа.

Важен порядок символов в цепочке. Цепочка ab отличается от ba.

Длина цепочки ½a½ равна количеству символов в цепочке. Так ½ a ½ =1, ½ abc ½ =3, ½ e ½ =0.

Если a и b - цепочки, то их конкатенацией ab является цепочка, полученная путем дописывания символов цепочки b вслед за символами цепочки a. Например, если a=ab, b=bc, то ab= abbc и ba= bcab. Поскольку e - цепочка, не содержащая символов, то в соответствии с правилами конкатенации для любой цепочки a можно записать

ea=ae=a.

Обращением цепочки a (обозначается a ^R ) называется цепочка a, записанная в обратном порядке, т.е. если a = a₁...a_n, где все a_i - символы, то a^R= a_n... a₁. Кроме того, e ^R=e.

Если g = ab - цепочка, то a - голова (префикс), а b - хвост (суффикс) цепочки g. При этом, a - правильная голова, если b - не пустая цепочка ( b ¹ e ), b - правильный хвост, если a ¹ e. Таким образом, если a = abc, то e, a, ab и abc - головы a, и все они, кроме abc, - правильные головы.

Иногда удобнее и нагляднее писать

a... вместо ab,

если нас не интересует b - остальная часть цепочки. Три точки "... " будут обозначать любую возможную цепочку, включая пустую.

Языком L в алфавите A называется множество цепочек в A.

Это определение подходит почти для любого языка. Языки Паскаль, С, Модула-2, английский и русский охватываются этим понятием.

Рассмотрим простые примеры языков в алфавите A.

Пустое множество Æ - это язык. Множество { e }, содержащее только пустую цепочку, также является языком.

Заметим, что Æ и { e } - это два разных языка.

Обозначим через A ^* множество, содержащее все цепочки в алфавите A, включая e.

Например, если A бинарный алфавит {0,1}, то

A ^* = { e, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110,...}.

Каждый язык в алфавите A является подмножеством множества A ^*. Множество всех цепочек в A, за исключением e, обозначим A ⁺ , то есть A ^* = A ⁺ È e.

Формально цепочку в алфавите A можно определить следующим образом:

1). e - цепочка в A,

2). если a цепочка в A и a Î A, то aa - цепочка в A ( aa Î A ^*),

3). b - цепочка в A, тогда и только тогда, когда она является таковой в силу 1) или 2).

Цепочку, состоящую из i символов a будем обозначать a ⁱ, то есть a⁰=e, a¹= a, a²= aa, a³= aaa и т.д.

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

В грамматике, определяющей язык L, используется два конечных непересекающихся множества: множества терминальных символов (терминалов) S имножества нетерминалов N. Из терминалов образуются слова (цепочки) языка L, а нетерминалы - суть синтаксические понятия (синтаксические единицы) языка, служащие для порождения (вывода) слов языка L. Сердцевину же грамматики составляет конечное множество продукций образования (правил вывода) R, которые описывают процесс порождения цепочек языка. Правило - это просто пара цепочек, а точнее элемент декартового произведения:

( N È S) ^* N (N È S) ^* ´ (N È S) ^*.

Иначе говоря, первым компонентом правила служит любая цепочка, содержащая хотя бы один нетерминал, а вторая - любая цепочка из терминалов и нетерминалов, включая e. Правила обычно записывают в виде

a ® b

или

a ::= b

что означает a порождает (состоит из) b.

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

S ® b

где S Î N - начальный символ, а bÎ (N È S) ^* - любая цепочка.

В последующем, если не оговорено дополнительно, используем следующие обозначения. Грамматику языка обозначим через G, возможно с индексом, или G(S). Язык L, определяемый грамматикой G, обозначим L(G). Терминальные символы обозначим малыми буквами, а нетерминалы - прописными, или в виде текста в угловых скобках, например, <нетерминал>. Цепочки будем обозначать греческими буквами. Если в грамматике встречаются правила с одинаковыми левыми частями

a::=b₁

a::=b₂

..........

a::=b_n,

то будем писать

a::=b₁ ½ b₂ ½ ... ½ b_n

в виде одного правила, имеющего ряд альтернатив в правой части. Правило вида

a::=b ½ bg

можно представить

a::=b [ g ]

где [g] - факультативный (необязательный) элемент. Последние обозначения используются в системе записи метаязыка Хомского, которая носит название Бэкусовой нормальной формы (БНФ) или формы Бэкуса-Наура. Она была предложена Д.Бэкусом в 1959 году и впервые применена П.Науром для описания языка Алгол-60. Напомним, что метаязыком называется язык, который используется для описания других языков.

Рассмотрим ряд грамматик и обсудим алгоритм порождения, применяемый для вывода цепочек языка.

Дата добавления: 2015-06-27