Операции над языками

Несмотря на то, что формальные языки представляют собой множество цепочек вида L(G) = {a | aÎ V*}, использование теоретико-множественных операций ограничено. Так для класса КС-языков можно применять операции объединения, но недопустимо использовать операции пересечения и дополнения. Если дан язык L(G) = {a | aÎ V*}, то дополнением языка ù L(G) будет множество цепочек, не принадлежащих V*. Это могут быть любые цепочки любых символов. Следовательно, это множество не определено. Если даны два языка L₁ и L₂, то операцию их пересечения можно записать так: (L₁ÇL₂) = ù (ù L₁ Èù L₂). Но множество цепочек языков ù L₁ и ù L₂ не определено. Следовательно, невозможно реализовать операцию пересечения двух языков L₁ и L₂. Поэтому говорят, что класс КС-языков замкнут для операции объединения и не замкнут для операций пересечения и дополнения. Были выделены дополнительные операции умножения, деления, подстановки, итерации, расширившие возможности формирования новых цепочек и новых языков.

Операция умножения. Если даны цепочки a₁, a₂Î V* одного языка L(G) Í V*, то бинарная операция умножения ставит в соответствие каждой паре цепочек a₁ и a₂ новую цепочку a₁a₂, полученную в результате приписывания справа к цепочке a₁ цепочки a₂.

Операцию умножения чаще называют конкатенацией или операцией соединения.

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

Можно также говорить о конкатенации языков L₁ и L₂. При этом формируется новый язык:

L = L₁ L₂ = { a₁a₂| a₁Î L₁ÍV₁*,a₂ÎL₂ÍV₂*} Í. V₁*Ä V₂*. (28)

Если L₁ = L₂ = L, то операцию конкатенации можно записать как обычную мультипликативную операцию, т.е.

LL = L₂, LLL = L₃ и т.д. (29)

Для пустой цепочки e выполняется соотношение

e a = a e = a, для любого aÎ V*. (30)

Операция конкатенации - ассоциативна, т.е.

(a₁a₂)a₃ = a₁(a₂a₃) = a₁a₂a₃. (31)

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

Операция деления. Пусть a₁=g₁g₂ÎL₁ÍV₁* и a₂=g₂ÎL₂ÍV₂*,

Если для цепочек двух языков L₁ и L₂ существуют одинаковые "хвосты", то в результате выполнения операции деления будут выделены цепочки, являющиеся "головами" для цепочек языка L1, т.е.

L = L₁/L₂ = { g₁ | g₁g₂ÎL₁ÍV₁*, g₂ÎL₂ÍV₂* }. (32)

Пусть a₂=g₂g₁ÎL₁ÍV₁* и a₂=g₂ÎL₂ÍV₂*,

Если для цепочек двух языков L₁ и L₂ существуют одинаковые "головы", то в результате выполнения операции деления будут выделены цепочки, являющиеся "хвостами" для цепочек языка L1,т.е.

L=L₁/L₂={g₁ | g₂g₁ÎL₁ÍV₁*, g₂ÎL₂ÍV₂* }. (33)

Операция подстановки. Пусть даны язык L с грамматикой

G=áV_T; V_N;J; Pñ и язык L₁ с грамматикой G₁=áV_T1;V_N1;J₁;P₁ñ. Среди множества терминальных символов языка L выделен символ "a", определяющий возможность перехода к языку L1, т.е. "a" ÎV_T и ("a" ®L₁).Тогда при появлении символа "a" в цепочке aÎ L оказывается возможным выполнить подстановку цепочки a₁Î L₁. Так формируется новый язык:

L* = L ("a" ®L₁). (34)

Если дано множество языков L₁, L₂,...L_n и язык L, у которого среди множества терминальных символов выделены символы "a₁","a₂",..."a_n", то для цепочки aÎLÍV*, содержащей символ "a_i", возможен переход к языку L_i путем замены символа "a_i" цепочкой a_iÎL_iÍV_i*. Так формируется язык L*=L("a_i"®L_i). Обобщением этой операции на множество языков является подстановка нескольких языков в язык L, при которой вместо каждого вхождения символа "a_i" подставляется некоторая цепочка соответствующего языка, т.е.

L* = ("a₁"®L₁, "a₂"®L₂,... "a_n"®L_n). (35)

Операции над языками L_i и L, где i = 1, 2,...n, порождающие цепочки нового языка a*Î L* путем замены символов "a_i" языка L цепочками соответствующего языка a_iÎ L_i и подстановки их в цепочки aÎ L Í V* называют также суперпозицией, а оператор суперпозиции записывают так:

S(L; "a₁"; "a₂";... "a₂"| L₁,L₂,...L_n). (36)

Главное достоинство операции подстановки заключается в том, что она имеет тот же характер,что и правила КС-грамматики. Следовательно, подстановка цепочек КС-языка в другой КС-язык может быть представлена как подстановка КС-грамматики в другую КС-грамматику, дающая снова КС-грамматику. Отсюда следует, что класс КС- языков замкнут относительно операций подстановки и конкатенации.

Операция итерации. Объединение множества языков L_i, каждый из которых порожден языком L путем многократного умножения, называют итерацией языка, т.е.

L* = L₀ È L₁ È L₂ È... È L_n=_i=0ÈⁿVⁱ, где L₀ = { e }. (37)

Если i = 1,2,...n, то итерацию называют усеченной, т.е.

L* = L1 È L2 È... È Ln=_i=1ÈⁿVⁱ (38)

Заключение

Рассмотренные классы формальных языков, правил формирования цепочек символов, алгоритмы разбора синтаксических конструкций позволяют автоматизировать синтаксический анализ текстов. Эти идеи нашли широкое применение в разработке программных и технических средств современных вычислительных машин.

Программа или техническое средство, выполняющие преобразование исходной программы, написанной на языке высокого уровня, в объектные модули языка вычислительной машины называется транслятором. Для организации такого преобразования необходимо знать алфавиты языков высокого уровня и вычислительной машины, правила построения синтаксических конструкций текстов, написанных на языке высокого уровня и объектных модулей на языке вычислительной машины. Эти знания заложены в синтаксис соответствующего языка. Как правило, для языка высокого уровня это - КС-грамматика, для языка вычислительной машины это - система команд. Если текст исходной программы написан синтаксически верно, то следующим шагом выполняется семантический анализ текста, подготовка и генерация системы команд вычислительной машины. Эти работы определяются типом вычислительной машины и его языком.

Контрольные вопросы и задачи

1. Дайте формальное определение языка для формирования:

а) множества целых положительных чисел;

b) множества слов русского языка;

с) множества идентификаторов языка программирования.

2. Пусть V_T={ 0;1;2 }, а также a = 01, b = 2, g = 011. Выпишите следующие цепочки: ab, ba, abg, a⁴, a⁴b², (b ag)³. Опишите их длины,головы и хвосты.

3. Пусть дана грамматика G = á V_T; V_N; P; J ñ, где

V_T = {a,b,c}, V_N = {A,B,J}, J Î V_N, P = { p1 = J::= aB;

p2 = B::= A;

p3 = B::= b;

p4 = A::= c }.

Докажите истинность или ложность вывода следующих цепочек:

a) J =>...=> a; b) J =>...=> ac;

c) B =>...=> Ac; d) aJ =>...=> aab;

e) aBb =>...=> acb.

Какой тип грамматики?

4. Опишите грамматику, язык которой состоит из множества четных целых чисел.

5. Опишите грамматику, язык которой состоит из нечетной последовательности символа "a".

6. Пусть дана грамматика G = á V_T; V_N; P; J ñ, где

V_T = {a}, V_N = {A,J}, J Î V_N, P ={ p1 = J::= a;

p2 = J::= aJa }.

Цепочки какого языка генерирует грамматика?

7. Пусть дана грамматика G = á V_T; V_N; P; J ñ, где

V_T = {a,b}, V_N = {A,B,J}, J Î V_N, P = { p1 = J::= B;

p2 = J::= AJ;

p3 = AJ::= a;

p4 = B::= b }.

Цепочки какого языка генерирует грамматика?

8. Пусть дана грамматика G = á V_T; V_N; P; J ñ, где

V_T = {a,b}, V_N = {A,B,J}, J Î V_N, P = { p1 = J::= aA;

p2 = A::= a;

p3 = A::= B;

p4 = B::= b B

p5 = B::= b}.

Цепочки какого языка генерирует грамматика?

9. Дано множество правил P = { p1 = J::= ABA;

p2 = A::= Ca;

p3 = A::= bA;

p4 = C::= d }.

Найти матрицы связей, таблицы подстановок, синтаксические деревья и их двоичные эквиваленты для цепочки, начинающейся с символа "d".

10. Дано множество правил P = { p1 = J::= ABA;

p2 = J::= DE;

p3 = A::= Ca;

p4 = B::= bC;

p5 = C::= c;

p6 = D:: E;

p7 = E::= cJC }.

Найти матрицы связей, таблицы подстановок, синтаксические деревья и их двоичные эквиваленты для цепочки, начинающейся с символа "c".

11. Нарисуйте синтаксические диаграммы языка программирования Паскаль для синтаксических переменных:

<идентификатор>, <программа>, <целое_без_знака>, <терм>, <простое _выражение>, <конец_блока>, <заголовок_программы>.

12. Используя грамматику арифметических выражений (пример 14), постройте дерево разбора и его двоичный эквивалент для выражений:

a) a x (a + b) / c;

b) (a + b) / c;

c) (a + b) x (a - c) / (b - c).

Индивидуальное задание

Дана грамматика G = á V_T; V_N; P; J ñ, где

V_T = { a, b, c } È { (,), +, -, x, / },

V_N = {<арифм_выражение:-J>, < терм:- T>,

<множитель: -M>, <операнд: - K>, <операция_сложения: - S1>, <операция_умножения: -S2>, <вспом_символ:-S3>},

J - начальный символ грамматики,

P ={ p1 = J::= T | JS1T; p2 = T::= M | TS2M;

p3 = M::= K| S31JS32; p4 = S1::= "+" | "-";

p5 = S2::= "x" | "/"; p6 = K::= "a" | "b" | "c";

p71= S31::= "("; p72= S32::= ")" }.

Нарисовать по заданию варианта:

1) синтаксические диаграммы для подмножества правил

{pi;pj;pk};

2) синтаксическое дерево для арифметического выражения;

3) двоичное дерево для арифметического выражения.

Выполнить грамматический разбор арифметического выражения для вариантов 1 - 30 по алгоритму " сверху-вниз", для вариантов 31 - 60 по алгоритму "снизу-вверх".

номер варианта	индексы i, j, k	арифметическое выражение	номер варианта	индексы i, j, k
	1,2,3	((a + b) x c) + (a - b) / c		2,5,6
	1,2,4	((a + b) / c) - (a -b) / b		2,5,71
	1,2,5	((a^2 - b^2) x c - b) / c		2,5,72
	1,2,6	(a^3 + b^2)/ (c + b)		2,6,71
	1,2,71	((a + b) - c)/ (b + c)		2,6,72
	1,2,72	(a - b) / (c^2+ a)		3,4,5
	1,3,4	(a + b) / (b^2 x (a - c))		3,4,6
	1,3,5	(a^2 + b^2) / (b x a - c)		3,4,71
	1,3,6	(a + b^2) / (b^2 + c^2)		3,4,72
	1,3,71	(a^2 + b^2) / (b^2 - c)		3,5,6
	1,3,72	(a^2 + b^2) x (b - c)		3,5,71
	1,4,5	(a^2 - b x (a - c)) x c		3,5,72
	1,4,6	((a^2 - c) x b) x c^2)		3,6,71
	1,4,71	(a - c) x (b^2 + c)		3,6,72
	1,4,72	a + b + c^2 - b^2		4,5,6
	1,5,6	a^2 + b^2 +c - b		4,5,71
	1,5,71	a^2 / (b^2 - a + c)		4,5,72
	1,5,72	a / (b^2 - a^2-c)		4,6,71
	1,6,71	a x (b^2 +a^2 - c)		4,6,72
	1,6,72	a x (b + a^2 -c)		5,6,71
	2,3,4	a / (b - c) +(a + c)		5,6,72
	2,3,5	a^2 x b^2 + (a - c))		6,5,4
	2,3,6	a^2 - b^2 - c^2		6,5,3
	2,3,71	(a^2 -b) / (b^2 - c)		6,5,2
	2,3,72	a x (((a + b)/ b + c) - a)		6,5,1
	2,4,5	a / (((a - c) x b - a) + b)		5,4,3
	2,4,6	a + ((a x (b + c)- a) - b)		5,4,2
	2,4,71	a - (a - (b x c + c) + b)		5,4,1
	2,4,72	a - (a x ((b - c) / a - c))		4,3,2
	2,5,71	a / (a x ((b+c)^2 -a))		4,3,1

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