5.2. Примеры фрагментов описаний в языках программирования.

Рассмотрим несколько примеров формального описания в языке Си.

Пример 1. Описание унарных операций — — и + +.

G=<Vт,Vн, P,S>;

V={0-9, A-Z, a-Z, + +, — — };

Vн={<выражение>, <имя переменной>, <оператор>, <цифра>, <буква>, <слово>};

S≡<выражение>;

P:

<выражение>®<оператор> <имя переменной>;

<выражение>® <имя переменной> <оператор>;

<имя переменной>::=<буква>;

<имя переменной>::=<буква> <слово>;

<слово>::= <буква> <слово>;

<слово>::=<цифра> <слово>;

<слово>::=<цифра>;

<слово>::=<буква>;

<буква>::=ABZ;

<буква>::=abZ;

<цифра>::=019;

<оператор>::= — —;

<оператор>::= + +.

Пример 2. Доступ к члену класса или структуры.

G=<Vт,Vн, P,S>;

Vт={0-9, A-Z, a-Z, . , ® };

Vн={<выражение>, <имя переменной>, оператор, <цифра>, <буква>, <слово>};

S≡<выражение>;

P:

<выражение>::= <имя переменной>оператор <имя переменной>;

<имя> ::= <буква>;

<имя> ::= <буква> <слово>;

<слово> ::= <буква> <слово>;

<слово> ::= <цифра> <слово>;

<слово> ::= <цифра>;

<слово> ::= <буква>;

<буква> ::= ABZ;

<буква> ::= abZ;

<цифра> ::= 019;

<оператор> ::= ®;

<оператор> ::= .

Пример 3. Для цикла с предусловием while.

G=<Vт,Vн, P,S>;

Vт={while, ( ), 0-9, A-Z, a-Z, +, —, =, >, < , !=, ==, >=, <=};

Vн={<цикл>, <условное_выражение>, <имя переменной>, <оператор>, <цифра>, <буква>, <слово>, <число>, <операнд>, <знак>, <мантисса>};

S≡<цикл>;

P:

<цикл>::= while( <условное_выражение>);

<условное_выражение> ::= <операнд><оператор><операнд>;

<операнд> ::= <число> <знак><число>;

<операнд> ::= <имя переменной>;

<число> ::= <цифра><цифра><число>;

<число>::= <цифра>.<мантисса>;

<мантисса>::= <цифра><мантисса>;

<мантисса>::= <цифра>;

<имя переменной>::= <буква>;

<имя переменной>::= <буква><слово>;

<слово> ::=<буква><буква><слово><цифра> <цифра><слово>;

<слово> ::=;

<знак> ::= +—;

<оператор> ::= <>> =<=!===;

<буква> ::= ABZabZ;

<цифра> ::=019.

5.3. Порождающая грамматика

Одна из задач, которая решается в формальных языках, заключается в выявлении множества слов, которые могут быть построены с помощью данной грамматики. Чаще решается обратная задача: для заданного языка построить грамматику, которая порождает этот язык. Такие грамматики называются порождающими. Пример решения такой задачи рассмотрены выше (пример 5). При этом необходимо определить алфавиты V, N, описать множество правил P. Если алфавит V определяется однозначно из вида слов языка, то алфавит N можно определить по-разному. В примере 5 можно не определять понятие <знак>, тогда правила p1, р2 и p3 заменятся двумя правилами

p1: <число> ::= + <модуль>, p2: <число> ::= - <модуль>.

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

Порождающая грамматика G = (V, N, S, P) позволяет выводить (порождать) цепочки языка из некоторой начальной цепочки с помощью заданных правил замены (подстановки). Вывод — это пошаговый процесс, в котором из цепочки, полученной на предыдущем шаге, путем применения правил замены можно получить новую цепочку.

Правило вывода записывают в виде:   .

Цепочку  называют левой частью правила вывода, а цепочку  — правой.

Цепочка  должна содержать вхождение хотя бы одного символа нетерминального алфавита N.

Буквы терминального алфавита называют терминальными символами (терминалами), а нетерминального алфавита — нетерминальными символами (нетерминалами). Любую цепочку в терминальном (нетерминальном) алфавите называют терминальной (нетерминальной) цепочкой.

Пример. Четверка G = ({a,b}, {S, A, B}, S, {S  aAB, aA  aB, S  bb, B  aB}) задает грамматику с терминальным алфавитом V = {a,b}, нетерминальным алфавитом N = {S, A, B}, аксиомой S и множеством правил вывода P = {S  aAB, aA  aB, S  bBb, B  aB, B  bb}.

Цепочка  непосредственно выводима в грамматике G из цепочки , если существуют такие цепочки  и  и такое правило вывода    из P, что  =  (т. е. существует вхождение левой части правила вывода в цепочку ), а  = .

Говоря другими словами, непосредственная выводимость подразумевает получение цепочки  из цепочки  за одно применение какого-либо правила вывода.

В вышеприведенном примере цепочка aAB непосредственно выводима из цепочки S, а цепочка aB — из цепочки aA.

Цепочка  выводима в грамматике G из цепочки  (обозначим как  ├ ), если найдутся такие слова 0 = , 1, 2, …, n = , что 0├ 1 ├…├ n.

Выводом в грамматике G называют саму последовательность слов 0 = , 1, 2, …, n = , таких, что 0 ├ 1 ├ 2 ├ … ├ n.. В вышеприведенном примере цепочка aAaB выводима из цепочки S.

Выводом же будет цепочка слов S ├ aAB ├ aAaB.

Понятия непосредственной выводимости, выводимости и вывода могут быть сопоставлены известным из теории графов понятиям непосредственной достижимости, достижимости и пути (для ориентированных графов) соответственно.

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

L(G) = {x: S ├ x, x  V+}.

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

Для сокращения записи правил с одинаковой левой частью примем следующее соглашение: вместо записи A  1, A  2, …, A  n будем писать A  1 , 2  …  n.

Пример. Рассмотрим грамматику, моделирующую простейший фрагмент русского языка. Терминальными символами данной грамматики являются некоторые слова русского языка, а нетерминальными — грамматические категории: «предложение», «подлежащее», «сказуемое».

G1 = (V={землекоп, корабль, оркестр, играет, копает, плывет}, N={<предложение>, <подлежащее>, <сказуемое>}, S=<предложение>, P1).

Множество правил вывода P1 имеет вид:

{<предложение>  <подлежащее> <сказуемое>,

<подлежащее>  землекоп  корабль  оркестр,

<сказуемое>  играет  копает  плывет}.

Первое правило вывода можно толковать следующим образом: «предложение — это подлежащее, за которым следует сказуемое».

Второе правило вывода означает: «подлежащее — это или “землекоп” или “корабль” или “оркестр”».

Третье правило вывода означает: «сказуемое — это или “играет” или “копает” или “плывет”».

Построим какой-нибудь вывод в грамматике G1:

<предложение> ├ <подлежащее> <сказуемое> ├ корабль < сказуемое > ├ корабль играет.

Отметим, что «смысл» (семантика) выводимой цепочки нас не интересует. Так что корабль может играть, оркестр плыть и т. д.

Таким образом, грамматику можно рассматривать как систему определений некоторых «понятий». Выделяется самое общее понятие — аксиома. В данном примере это <предложение>. Оно сводится к менее общим понятиям — нетерминалам. В конечном итоге получаем «конкретные объекты» – терминальные цепочки.

Пример. Рассмотрим грамматику G = (V, N, S, P), у которой

V = {a, b, c, , , , (, )},

N = {I},

S = {I},

P = {I  (I  I)

I  (I  I)

I  I

I  a

I  b

I  c}.

Эта грамматика описывает язык булевых формул с переменными a, b, c и логическими операциями , , . Выведем в данной грамматике формулу

f = (ā  b  c)  (a  b).

(I)  (I  I)  ((I  I)  I))  (((I  I)  I)  I)  (((I  I)  I)  (I  I)) 

 (((I  I)  I)  (I  I))  (((a  I)  I)  (I  I))  (((a  b)  I)  (I  I)) 

 (((a  b)  c)  (I  I))  (((a  b)  c)  (a  I))  (((a  b)  c)  (a  b)).

Следует отметить, что хотя порождающая грамматика и описывает процесс порождения цепочек языка L(G), но описание это не является алгоритмическим. В грамматике отсутствует одно из основных свойств алгоритма — детерминированность. То есть не фиксируется конкретный порядок применения правил подстановки. Так, в рассмотренном выше примере после цепочки (I  I) мы могли перейти не к цепочке ((I  I)  I)), а к цепочке (I  (I  I)).