ГРАММАТИКИ

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

{U 2, 3}

обозначает множество, содержащее целые числа 1, 2 и 3. Объединение

(U) и пересечение () множеств определяются как обьшно:

{Г, 2, 3}U {3, 4, 5} = {1. 2, 3, 4. 5), П, 2. 3}П{3,4. 5Н{3}.

Мы говорим, что множество A включает () множество S, если каждый элемент В является элементом Л, например

{3. 4. 5} э {3).

Аналогично множество В включается () в множество А, если каждый элемент В имеется также и в А: 3} £ {3, 4, 5}.

Мы употребляем символ s, чтобы показать, что элемент содержится в множестве, например

3 е {3. 4. 5}.

Пустое множество обозначается посредством 0. Поэтому

Если А есть множество и мы определяем В как то В будет множеством

{1, 2} П {3, 4, 5}=0. {2. 4, 9, 8} В~{х\х А и X есть четное число).

{2, 4. 8}.

В задается с помощью предиката, в данном случае это «х с А и x есть четное число».

Мы определяем алфавит (или словарный состав) как множество символов. Например, им может быть латинский или греческий алфавит либо десятичные цифры О - 9. Представим алфавит

Д={0..1. 2, 3. 4. 5. б. 7. 8, 9}.

Если А есть алфавит, А* (замыкание A) используется для обозначения множества всех строк (включая пустую строку, состоящую из нулей), составленных* из символов, входящих в А. А + обозначает множество всех строк (исключая пустую строку), состоящих из символов, входящих в А. Пустая строка обычно обозначается с помощью s .

Синтаксис языка можно специфицировать, пользуясь системой изображения множеств, например

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

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

1. {a-&Vjn>0):

2. (а™*»"! m, «>0Ь

т.е. число а с последующим числом (не обязательно тем же самым) Ь, например

будет принадлежать этому языку;

3. {х"\т - простое число);

4. {a"ftVm = n или п=р}.

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

и воспользуемся следующими правилами:

1. S-OSl.

2. 5€,

Чтобы вывести предложение этого языка, поступим следующим образом. Начнем с символа S и заменим его на 0S1 или s. Если S опять появится в полученной строке, его опять можно заменить с помощью одного из этих правил, и т. д. Полученная таким образом любая строка, не содержащая S, является предложением этого языка. Например,

Последовательность указаннтх шагов называется выводом строки 000111, а символ = служит, для разделения шагов вывода. Все предложения данного языка можно вывести, руководствуясь приведенными выше двумя правилами, и любая строка, которую нельзя вывести с их помощью, не является предложением этого языка. Грамматику часто (и справедливо) называют системой перезаписи. Определим теперь грамматику более формально.

Грамматика определяется как четверка

просто

iVj,V, Р, S),

где Vт-алфавит, символы которого называются терминальными (или терминалами); VN- алфавит, символы которого называются

X J. у - А. X

нетерминальными (или нетерминалами), и у Vт, и VN нет общих символов, т. е.

V определяется как Vт и VN

Р есть набор порождающих правил, каждый элемент которых состоит из пары (а, в), где а находится в V+, a в в V*. а обычно известна как левая часть правила, а в - как правая, и правило записывается следующим образом:

SeVN и называется начальным символом (или аксиомой). Этот символ является отправной точкой в получении любого предложения языка.

Грамматикой, генерирующей язык

является Go, где

грамматика, генерирующая строки в наборе имеет вид

Здесь элементами р будут

Начав с символа S и применяя последовательно по одному из правил замены не терминала в выводимой строке, мы можем генерировать строку aaabb:

Каждая строка, которую можно вывести из начального символа (например, аАВ, аааВ), называется сентенциальной формой. Предложение есть сентенциальная форма, содержащая только терминальные символ означает, что строку (символов) 5 можно вывести из строки у, однократно или неоднократно применяя правила грамматики G. (G можно опустить, если ясно, какая грамматика предполагается). Из изложенного видно, что

аАВ аааЬВ.

Аналогичным образом

означает, что строку 5 можно вывести из строки у с помощью нуля или более приложений правил грамматики G. (G также можно опустить при соответствующих обстоятельствах.) Например,

Там, где правило используется точно один раз, применяется символ =>, например

или, если опускается Gj,

АВ аАВ

АВаАВ.