Задачи
(Приложение к учебному пособию"Формальные грамматики и языки. Элементы теории трансляции")
I. Порождающие грамматики. Языки, порождаемые грамматиками.
Классификация грамматик и языков по Хомскому

1. Дана грамматика. Построить вывод заданной цепочки.

	a)	S ® T | T+S | T-S		b)	S ® aSBC | abC
		T ® F | F*T				CB ® BC
		F ® a | b				bB ® bb
		Цепочка   a-b*a+b			bC ® bc
							cC ® cc
							Цепочка   aaabbbccc

2. Построить все сентенциальные формы для грамматики с правилами:

			S ® A+B | B+A
			A ® a
			B ® b

3. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? Указать ммаксимаьно возможный номер типа грамматки и языка.

	a)	S ® APA	b)	S ® A | SA | SB
		P ® + | -		A ® a 
		A ® a | b		B ® b

	c)	S ® 1B	d)	S ®  aQb | 
		B ® B0 | 1		Q ® cSc 
				
	e)	S ® a | Ba	f)	S ® Ab
		B ® Bb | b		A ® Aa | ba

	g)	S ® 0A1 | 01	h)	S ® AB
		0A ® 00A1		AB ® BA
		A ® 01		A ® a
				B ® b

	i)	S ® A | B	j)	S ® 0A | 1S
		A  aAb | 0		A  0A | 1B
		B  aBbb | 1		B  0B | 1B | 

	k)	S  0S | S0 | D	l)	S  0A | 1S | 
		D  DD | 1A | 		A  1A | 0B
		A  0B | 		B  0S | 1B
		B  0A | 0

	m)	S  SS | A	n)	S  AB
		A  a | bb		A  a | cA
				B  bA

	o)	S  aBA | 	p)	S  Ab | c
		B  bSA		A  Ba
		AA  c		B  cS
	
	r)	1. S  KF			      7.	Bb  bB
2. K  KB | CB		      8. 	Ab  bA
3. C  CA | DA		      9. 	DF  E
4. DA  aAD			    10. 	BE  Eb
5. Aa  aA			    11. 	AE  Ea
6. DB  bBD			    12. 	bE  b

s) 	1. 	S  DC			 6.	Ba  aB
2.	D  aDA | bDB | aA |bB	 7. 	Ab  bA
3. 	AC  aC			 8. 	Bb  bB
4. 	BC  bC			 9.    	C  
5. 	Aa  aA			    

t)	S  aAc
		aA  aaBbC | ab
		Bb  bb | abbbc | aDbbbcc
		C  c
		D  ab

u) 	S  0A1
		0A  0B1 | 0
		B1  0C11 | 01
		C  0D | 00D1 | 0
		D  01

4. Построить грамматику, порождающую язык :

a)	L = { an bm | n, m >= 1}
b)	L = { ccc | , ,  - любые цепочки из a и b}
c)	L = { a1 a2 ... an an ... a2 a1 | ai = 0 или 1, n >= 1}
d)	L = { 0n 1[n/2], n1}
e)	L = { cancbmcn, n0, m0 }
f)	L = { an bm | n  m ; n, m >= 0}
g)	L = { цепочки из 0 и 1 с неравным числом 0 и 1}
h)	L = {  |   {a,b}+}
i)	L = {  |   {0,1}+ и содержит равное количество 0 и 1, причем любая подцепочка, взятая с левого конца, содержит единиц не меньше, чем нулей}.
j)	L = { (a2m bm)n | m >= 1, n >= 0}
k)	L = {  | n >= 1}
l)	L = {  | n >= 1}
m)	 L = { | n >= 1}
	
Каков тип этой грамматики? Каков тип языка?

5. К какому типу по Хомскому относится данная грамматика (указать максимально возможный номер)?  Какой язык она порождает? Каков тип языка? Выписать грамматику, в состав которой входит только один нетерминал – цель грамматики, подтверждающую ответ.
	a)	S  AB | ASB		b)	S  1A0		
		A  a					1A  11A0 | 01		
		aB  b
		bB  bb

6. Эквивалентны ли грамматики с правилами :

	а)	S ® AB	и	S ® AS | SB | AB
		A ® a | Aa	A ® a
		B ® b | Bb	B ® b

	b)	S ® aSL | aL	и	S ® aSBc | abc
		L ® Kc	cB ® Bc
		cK ® Kc	bB ® bb
		K ® b

7. Построить КС-грамматику, эквивалентную грамматике с правилами:

	а)	S ® aAb	b)	S ® AB | ABS
		aA ® aaAb		AB ® BA
		A ® 		BA ® AB
				A ® a
				B ® b

8. Построить регулярную грамматику, эквивалентную грамматике с правилами:

	а)	S ® A | AS	b)	S ® A.A
		A ® a | bb		A ® B | BA
				B ® 0 | 1
9.  Привести пример грамматики, все правила которой имеют вид 
A ® Bt, 	либо   A ® t B,		либо   A ® t, 
для которой не существует эквивалентной регулярной грамматики.

10. Доказать, что грамматика с правилами:

		S ® aSBC | abC
			CB ® BC
		bB ® bb
		bC ® bc
		cC ® cc

порождает язык L = {an bn cn | n >= 1}. 

Для этого показать, что в данной грамматике
1.	выводится любая цепочка вида an bn cn (n >= 1) и
2.	не выводятся никакие другие цепочки.

11. Дана грамматика с правилами:

	a)	S ® S0 | S1 | D0 | D1	b)	S ® if B then S | B = E
		D ® H.		E ® B | B + E
		H ® 0 | 1 | H0 | H1		B ® a | b

Построить восходящим и нисходящим методами дерево вывода для цепочки:
a)   10.1001					b)   if a then b = a+b+b

12. Определить тип грамматики. Описать язык, порождаемый этой грамматикой. Написать для этого языка КС-грамматику.

		S ® P
		P ® 1P1 | 0P0 | T
		T ® 021 | 120R
		R1 ® 0R
		R0 ® 1
		R® 1

13. Построить регулярную грамматику, порождающую цепочки в алфавите 
{a, b}, в которых символ a не встречается два раза подряд.

14. Написать КС-грамматику для языка L, построить дерево вывода и левосторонний вывод для цепочки aabbbcccc.

		L = {a2n bm c2k | m=n+k, m>1}.

15. Построить грамматику, порождающую сбалансированные относительно круглых скобок цепочки в алфавите { a, ( , ),  }. Сбалансированную цепочку  определим рекуррентно: цепочка  сбалансирована, если
a)	 не содержит скобок,
b)	 = (1) или = 1 2, где 1 и 2 сбалансированы.

16. Написать КС-грамматику, порождающую язык L, и вывод для цепочки aacbbbcaa в этой грамматике.

		L = {an cbm can | n, m>0}.

17. Написать КС-грамматику, порождающую язык L, и вывод для цепочки 110000111 в этой грамматике.

		L = {1n 0m 1p | n+p>m;   n, p, m>0}.

18. Дан язык L = {13n+2 0n | n>=0}. Определить его тип, написать грамматику, порождающую L. Построить левосторонний и правосторонний выводы, дерево разбора для цепочки 1111111100.

19. Написать общие алгоритмы построения по данным КС-грамматикам G1 и G2, порождающим языки L1 и L2, КС-грамматики для
a)	L1L2
b)	L1 * L2
c)	L1*

Замечание: L = L1 * L2 - это конкатенация языков L1 и L2, т.е.L = {  |   L1,   L2};  L = L1* - это итерация языка L1, т.е. объединение {}  L1  L1*L1  L1*L1*L1  ...

20. Написать КС-грамматику для L={i 2 i+1R | i  N, i=(i)2 - двоичное представление числа i, R - обращение цепочки }. Написать КС-грамматику для языка L* (см. задачу 19 раздела I).

21. Показать, что грамматика

		E ® E+E | EE | (E) | i

неоднозначна. Как описать этот же язык с помощью однозначной грамматики?

22. Показать, что наличие в КС-грамматике правил вида

a)	A ® AA | 
b)	A ® AA | 
c)	A ® A | A | 

где , ,   (VTVN)*, A  VN, делает ее неоднозначной. Можно ли преобразовать эти правила таким образом, чтобы полученная эквивалентная грамматика была однозначной?

23. Показать, что грамматика G неоднозначна. Какой язык она порождает? Является ли этот язык однозначным?

	G:	S ® aAc | aB
		B ® bc
		A  b

24. Дана КС-грамматика G={VT, VN, P, S}. Предложить алгоритм построения множества
		X={A  VN | A  }.

25. Для произвольной КС-грамматики G предложить алгоритм, определяющий, пуст ли язык L(G).

26. Написать приведенную грамматику, эквивалентную данной.

	a)	S ® aABS | bCACd	b)	S ® aAB | E
		A ® bAB | cSA | cCC		A ® dDA | 
		B ® bAB | cSB		B ® bE | f
		C ® cS | c		C ® cAB | dSD | a
				D ® eA
				E ® fA | g

27. Язык называется распознаваемым, если существует алгоритм, который за конечное число шагов позволяет получить ответ о принадлежности любой цепочки языку. Если число шагов зависит от длины цепочки и может быть оценено до выполнения алгоритма, язык называется легко распознаваемым. Доказать, что язык, порождаемый неукорачивающей грамматикой, легко распознаваем.

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

29. Доказать, что нециклическая КС-грамматика порождает конечный язык. 
Замечание: Нетерминальный символ A  VN - циклический, если в грамматике существует вывод A  1A2. КС-грамматика называется циклической, если в ней имеется хотя бы один циклический символ.

30. Показать, что условие цикличности грамматики (см. задачу 29) не является достаточным условием бесконечности порождаемого ею языка.

31. Доказать, что язык, порождаемый циклической приведенной КС-грамматикой, содержащей хотя бы один эффективный циклический символ, бесконечен.
Замечание: Циклический символ называется эффективным, если A  A, где |A| > 1; иначе циклический символ называется фиктивным.

II. Регулярные грамматики, ДС, анализаторы по ДС.
Преобразование НКА к ДКА

1. Дана регулярная грамматика с правилами:

		S ® S0 | S1 | P0 | P1
		P ® N.
		N ® 0 | 1 | N0 | N1 .

Построить по ней диаграмму состояний и использовать ДС для разбора цепочек : 11.010 , 0.1 , 01. , 100 . Какой язык порождает эта грамматика ?

2. Дана ДС.
a)	Осуществить разбор цепочек 1011 , 10+011 и 0-101+1 .
b)	Восстановить регулярную грамматику, по которой была построена данная ДС.
c)	Какой язык порождает полученная грамматика ?

3. Пусть имеется переменная c и функция gc(), считывающая в с очередной символ анализируемой цепочки. Дана ДС с действиями:

a)	Определить, что будет выдано на печать при разборе цепочки 1+101//p11+++1000/5?
b)	Написать на Си анализатор по этой ДС.

4. Написать регулярную леволинейную грамматику для заданного языка, по ней построить ДС, а по  ДС - программу анализатора. 

	a) L  =  { x  y   |    {x, y}*}
	b) L  =  { (x y3)n   |  n >= 1 } 
	с) L = {(abb)k| k >= 1}
	d) L = { |   {0,1}* , где за каждой 1 непосредственно следует 0}
	e) L = {11 |   {0,1}+ , где все подряд идущие 0 – подцепочки нечетной длины}

5. Дана регулярная грамматика:

		S ® A
		A ® Ab | Bb | b
		B ® Aa

Определить язык, который она порождает; построить ДС; написать на Си анализатор.

6. Построить ДС, по которой в заданном тексте, оканчивающемся на , выявляются все парные комбинации <>, <= и >= и подсчитывается их общее количество.

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

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

9. Даны две грамматики G1 и G2.

G1:	S ® 0C | 1B	G2:	S ® 0D | 1B
		B ® 0B | 1C | 		B ® 0C | 1C
		C ® 0C | 1C		C ® 0D | 1D | 
				D ® 0D | 1D
		L1 = L(G1);    L2 = L(G2).

 Построить регулярную грамматику для:

a)	L1L2
b)	L1L2
c)	L1* \ {}
d)	L2* \ {}
e)	L1L2
Если разбор по ней оказался недетерминированным, построить эквивалентную ей грамматику, допускающую детерминированный разбор.

10. Написать леволинейную регулярную грамматику, эквивалентную данной праволинейной, допускающую детерминированный разбор.

	a)	S ® 0S | 0B	b)	S ® 0B
		B ® 1B | 1C		B ® 1C | 1S
		C ® 1C | 		C ® 

	c)	S ® aB
		B ® aC | aD | dB
		C ® aB
		D ® 

11. Для данной грамматики
a)	определить ее тип;
b)	какой язык она порождает;
c)	написать Р-грамматику, почти эквивалентную данной;
d)	построить ДС и анализатор на Си.

		S ® 0S | S0 | D
		D ® DD | 1A | 
		A ® 0B | 
		B ® 0A | 0

12. Построить ДС, соответствующую заданной леволинейной регулярной грамматике. Если ДС задает НКА, то преобразовать НКА к ДКА, используя алгоритм преобразования. По получившемуся ДКА написать анализатор. Выписать соотвествующую ДКА грамматику.

a)	S  Sa | Ab | b		b)	S  Sb | Aa | a
	A  Ab | Sa | a			A  Sb | a | b

c)	S  C			d)	S  A
C  A1 | B1 | 1			A  Bb | a
A  A1 | C0 | 0			B  Bb | b
B  C0 | 0

e)	S  B0 | C0			f)	S  Bb | Cc
	B  B0 | 0				B  Bb | Ab
	C  C1 | A1				C  Cc | Ab
	A  0					A  a

g)	S  S1 | A0			h)	S  Sa | Cc | a
	A  B1 | C1				C  Bb
	B  A0				B  Sa | a
	C  C0 | 0

i)	S  C				j)	S  A
	C  A1 | B1 | 1				A  Bb | a
	A  A1 | C0 | 0				B  Bb | b
	B  C0 | 0

k)	S ® C			l)	S ® C
	B ® B1 | 0 | D0			C ® B1
	C ® B1 | C1				B ® 0 | D0
	D ® D0 | 0				D ® B1

m)	S ® A0			n)	S  B0 | 0
	A ® A0 | S1 | 0			B  B0 | C1 | 0 | 1
						C  B0

o)	S  A0 | A1 | B1 | 0 | 1	p)	S  S0 | A1 | 0 | 1
	A  A1 | B1 | 1			A  A1 | B0 | 0 | 1
	B A0				B  A0

r)	S  Sb | Aa | a | b
	A  Aa | Sb | a

13. Грамматика G определяет язык L=L1L2, причем L1 L2 =. Написать регулярную грамматику G1, которая порождает язык L1*L2 (см. задачу 19 раздела I.). Для нее построить ДС и анализатор.

		S  A
		A  A0 | A1 | B1
		B  B0 | C0 | 0
		C  C1 | 1

14. Даны две грамматики G1 и G2, порождающие языки L1 и L2. Построить регулярные грамматики для
a)	L1  L2
b)	L1  L2
c)	L1 * L2 (см. задачу 19 раздела I.)

G1:	S ® S1 | A0	G2:	S ® A1 | B0 | E1
		A ® A1 | 0		A ® S1
				B ® C1 | D1
				C ® 0
				D  B1
				E  E0 | 1

Для полученной грамматики построить ДС и анализатор.

15. По данной грамматике G1 построить регулярную грамматику G2 для языка L1*L1 (см. задачу 19 раздела I.), где L1 = L(G1); по грамматике G2 - ДС и анализатор.

G1:	S ® S1 | A1
		A ® A0 | 0

16. Построить лексический блок (преобразователь) для кода Морзе. Входом служит последовательность "точек", "тире" и "пауз" (например, ..--. .- ...- ). Выходом являются соответствующие буквы, цифры и знаки пунктуации. Особое внимание обратить на организацию таблицы.

III. Метод рекурсивного спуска (РС-метод). Применимость  РС-метода.
КС-грамматики с действиями

1. Определить, применим ли РС-метод грамматике. Ответ обосновать.

а)	S  cA | B | d			b)	S  aAbc | A
	A  abA | c | 			A  bB | cBc
	B  bSc | aAb			B  bcB | a | ε

c)	S  aSB | bAf | 		d)	S  aSB | bA
	A  bAc | cS				A  aS | cA | 
	B  cB | d				B  bB | d

e) 	S  bABCb | d		f)	S  aAb | cC
A  aA | cB | 			A  a { bab }
B  Sc				B  cAc | aB | 
C  a {bb}				C  Bb

g) 	S  aA{xx}			h)	S  aSc | bA | 
A  bA | cBx | 			A  cS{da}bA | d
B  bSc

i)	S  bS | aAB			j)	S  aASb | cfAd
	A  bcA | ccA | 			A  bA | c | 
	B  cbB | 
	
2. Восстановить грамматику по функциям, реализующим синтаксический анализ методом рекурсивного спуска. Можно ли было по этой грамматике вести анализ методом рекурсивного спуска?

a).	#include <iostream.h>
int c;
void A(); 
void B(); 

void gc() {cin >> c;}

void S() {
 		A(); 
if ( c != '')
throw c;
}
	
void A() {
B();
while ( c == 'a') {
gc();
B();
} 
          	}

void B() {
if ( c == 'b' )
gc();
 	}

int main() {
		try {	gc();
S();
cout << "SUCCESS !!!" << endl;
return 0;
   		}
catch (int c) {
cout << "ERROR on lexeme" << c << endl;
return 1;
}
}
	
b).	#include <iostream.h>
int c;
void A(); 
void B(); 

void gc() {cin >> c;}

void S() {
 		if (c == ’a’) {
gc();
A();
}
else 
if (c == ‘b’ ) {
gc();
B();
}
else
throw c;
}

void A() {
if ( c == ‘c’) {
gc();
S();
}
}

void B() {
while ( c == ',' ) {
gc();
if (c != ’b’)
throw c;
gc();
} 
}

int main() {
try {	gc();
S();
cout << "SUCCESS !!!" << endl;
return 0;
}	
catch (int c) {
cout << "ERROR on lexeme" << c << endl;
return 1;
}
}

c) 	#include <iostream.h>
int c;
void A(); 

void gc() {cin >> c;}

void S (void) {
if (c == 'a'){
   			gc();
S();
    			if (c == 'b')
gc();
    			else
throw c;
}
   		else A();
 	}

void A (void) {
  		if (c == 'b')
gc();
   		else
 			throw c;
   		while (c == 'b')
gc();
}

int main() {
try {	gc();
S();
cout << "SUCCESS !!!" << endl;
return 0;
}
catch (int c) {
cout << "ERROR on lexeme" << c << endl;
return 1;
}
}

d) #include <iostream.h>
int c;
void A(); 
void B(); 

void gc() {cin >> c;}

void S (void) {
  		A();
if ( c != '')
			throw c;
}

void A (void) {
  		B();
while ( c == 'a' ) {
gc();
B();
}
B();
  	}

void B (void) {
  		if ( c == 'b' )
gc();
}

int main() {
try {	gc();
S();
cout << "SUCCESS !!!" << endl;
return 0;
}
catch (int c) {
cout << "ERROR on lexeme" << c << endl;
return 1;
}
}

3. Задана КС-грамматика G=(VT, VN, P, S). По ней написать синтаксический анализатор, реализующий РС-метод, предварительно преобразовав заданную грамматику, если это требуется для применимости РС-метода и если это возможно.

	a)	S  bS | aAB				b) 	S  aASb | cfAd	
		A  bcA | ccA | 				A  bA | c | 
		B  cbB | 
 	
	c)	S  Sa | Sbb | fAc			d)	S  cAd
		A  aB | d					A  Aa | bB
		B  abB | Sb					B  abB | 

	e)	S ® E			f)	S ® P := E | if E then S | if E then S else S
		E ® () | (E {, E}) | A			P ® I | I (E)
		A ® a | b				E ® T {+T}
							T ® F {*F}
							F ® P | (E)
							I ® a | b

	g)	F ® function I(I) S; I:=E end		h)	S ® SaAb | Sb | bABa
		S ® ; I:=E S | 				A ® acAb | cA | 
		E ® E*I | E+I | I				B ® bB | 

	i)	S  Ac | dBea				j)	S  fASd | 
		A  Aa | Ab | daBc				A  Aa | Ab | dB | f
		B  cB | 					B  bcB | 

4. Какой язык порождает заданная грамматика? Провести анализ цепочки (a,(b,a),(a,(b)),b).

		S ® <k = 0> E 
		E ® A | (<k=k+1; if (k == 3) ERROR();> E {,E}) <k = k-1>
		A ® a | b

5. Есть грамматика, описывающая цепочки в алфавите {0, 1, 2, }:

	S ® A
	A ® 0A | 1A | 2A | 

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

6. Дана грамматика, описывающая цепочки в алфавите {a, b, c, }:

	S ® A
	A ® aA | bA | cA | 

Дополнить эту грамматику действиями, исключающими из языка все цепочки, в которых не выполняется хотя бы одно из условий:
•	в цепочку должно входить не менее трех букв с ;
•	если встречаются подряд две буквы а, то за ними обязательно должна идти буква b.

7. Есть грамматика, описывающая цепочки в алфавите {0, 1}:

		S ® 0S | 1S | 

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

8. Написать КС-грамматику с действиями для порождения

L = {am bn ck | m+k = n либо m-k = n}.

9. Написать КС-грамматику с действиями для порождения

L = {1n 0m 1p | n+p > m,   m >= 0}.

10. Дана грамматика с семантическими действиями:

	S ® < A = 0; B = 0 > L {L} < if (A > 5) ERROR() > 
	L ® a < A = A+1 > | b < B = B+1; if (B > 2) ERROR() > |
		   c < if (B == 1) ERROR() >

Какой язык описывает эта грамматика ?

11. Дана грамматика:

	S ® E
	E ® () | (E {, E}) | A
	A ® a | b

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

12. Включить в правила вывода действия, проверяющие выполнение следующих контекстных условий:

a) 	Пусть в языке L есть переменные и константы целого, вещественного и логического типов, а также есть оператор цикла
		S ® for I = E step E to E do S
Включить в это правило вывода действия, проверяющие выполнение следующих ограничений:
•	тип I и всех вхождений Е должен быть одинаковым;
•	переменная логического типа недопустима в качестве параметра цикла.
Для каждой используемой процедуры привести ее текст на Си.

b) 	Дан фрагмент грамматики
P  program D; begin S {; S } end
D  ... | label L{,L} |...
S  L { , L } : S` | S`
S`  ...| goto L |...
L  I
где I -идентификатор.
Вставить в грамматику действия, контролирующие выполнение следующих условий:
•	каждая метка, используемая в программе, должна быть описана и только один раз;
•	не должно быть одинаковых меток у различных операторов;
•	если метка используется в операторе goto, то обязательно должен быть оператор, помеченный такой меткой.
Для каждой используемой процедуры привести ее текст на Си.
IV. Синтаксически управляемый перевод

1. Написать грамматику арифметического выражения, использующего операции  +, - , *, / и круглые скобки (приоритет стандартный), аргументы операций – переменные a и b,. например: a+(b-a)*b/a+b. Предполагая, что анализ грамматики будет производиться РС-методом, вставить в нее действия (в виде cout << …) по переводу таких выражений в ПОЛИЗ.

2. Дана грамматика языка L1, в которую вставлены действия по переводу цепочек языка L1 в цепочки языка L2. Определить языки L1 и L2.

	a) 	S  a < a = 1; b = 0; > A 
A  a < if ( a ) { cout << ‘a’; a = 0; } else a++; > A |
   		        bA < if ( b ) { cout << ‘b’; b = 0; } else b++; > | ε

	b)	S  < a = 0; > E < cout << ‘’; >
E  a < a = 1;> E < cout << ‘a’; > |
   		        b < if (a == 0) cout << ‘b’;> E < cout << ‘b’; > | ε

3. Написать грамматику для языка L1. Вставить в нее действия по переводу цепочек языка L1 в соответствующие цепочки языка L2.
В качестве действий можно использовать только оператор cout << … .
СУ-перевод происходит во время анализа методом рекурсивного спуска.

a) 	L1={ ancmbn, n>=0, m>=1}       
    		L2={ 0n1n+m, n>=0, m>=1 }

b) 	L1={ cn,  ∈ (a,b)*,n>=1}
L2={ ancm, где m – количество символов а в цепочке }

c)	L1 = {  ∈ {a,b}+, где содержится n символов a и m символов b,
расположенных в произвольном порядке; n, m >= 0; n+m > 0 }
L2  =  { 1n+m0n | n, m >= 0; n+m > 0 }

d)	L1 = {  ∈ {a,b}+ , где содержится n символов a,
расположенных в произвольном порядке; n >= 0}
L2 = { 2nR | n >= 0, R - реверс цепочки    }

	e)	L1 = {1n 0m 1m 0n | m,n > 0}
		L2 = {1m 0n+m | m,n > 0}

	f)	L1={  |   {a,b}+ , =n, где =ab | ba, n>=1}
L2={  |  = n , где ={ b, если =ab; либо a, если =ba} }
	
4. Написать грамматику для языка L1. Вставить в нее действия по переводу цепочек языка L1 в соответствующие цепочки языка L2.
В качестве действий можно использовать любые операторы.
СУ-перевод происходит во время анализа методом рекурсивного спуска.

a)	L1 = { 1m 0n | n,m>0}
L2 = { 1m-n | если m>n;
0n-m | если m<n;
 | если m=n}
	
	b)	L1 = {bi | bi =(i)2, т.е. bi -это двоичное представление числа i  N}
		L2 = {(bi+1)R | bi+1=(i+1)2, R - перевернутая цепочка }

	c)	L1={  |   {a,b} }
L2={  |  = bnR , где n - количество символов b в цепочке ,
предшествующих первому вхождению символа a; R - реверс цепочки }

	d)	L1={  |   {a,b}+ , где содержится n символов a и m символов b,
расположенных в произвольном порядке}
L2={   {a,b}* |  = a[n/2] b[m/2] }

	e)	L1={ | {0,1}+  и представляет (bi)R , т.е. реверс двоичного числа i }
L2={  {/}* ,  = /i , т.е. количество /, равное значению i }

5. Построить грамматику, описывающую целые двоичные числа (количество 0 и 1 четно, допускаются незначащие нули). Вставить в нее действия по переводу этих целых чисел в четверичную систему счисления.

6. Написать грамматику для выражений, содержащих переменные, знаки операций +, -, *, /, ** и скобки ( ) с обычным приоритетом операций и скобок. Включить в эту грамматику действия по переводу этих выражений в префиксную запись (операции предшествуют операндам). Предложить интерпретатор префиксной записи выражений.

7. В грамматику, описывающую выражения, включить действия по переводу выражений из инфиксной формы (операция между операндами) в функциональную запись.
Например,
	а+b 	==>   + (a, b)
	a+b*c	==>   + (a, * (b, c))

V. ПОЛИЗ, перевод в ПОЛИЗ

1. Представить в ПОЛИЗе следующие выражения:

	а)	a+b-c	b)	a*b+c/a
	c)	a/(b+c)*a	d)	(a+b)/(c+a*b)
	e)	a and b or c	f)	not a or b and a
	g)	x+y=x/y	h )	(x*x+y*y < 1) and (x > 0)

2. Для следующих выражений в ПОЛИЗе дать обычную инфиксную запись:

	а )	ab*c+	b)	abc*/	c)	ab+c*
	d)	ab+bc-/a+	e)	a not b and not	f)	abca and or and
	g )	2x+2x*<

3. Используя стек, вычислить следующие выражения в ПОЛИЗе:
	а) 	x y*x y /+   			при x = 8, y = 2 ;
	b) 	a 2+b / b 4*+  	 		при a = 4, b = 3 ;
	c) 	a b not and a or not   		при a = b = true ;
	d) 	x y*0 > y 2 x - < and   	при x = y = 1 .

4. Записать на ПОЛИЗе фрагмент программы на С:
a)	S=0; i=1; while( i<10) { S = S*(i+i); i++;}

	b)	if( (x+1) > (2*y) ) x = y; else y = (x+y)*2;

	c)	i = 1; S = 0; while ( i < 10 && S < 40 ) { S = S + f(i); ++i; };

		d) 	if (z<x*y+5) a = x<y, z = (x+6)/(a-y); else z = y<<2;

		e)	a = x +y < z*(t + x) ? - (a + b)/(c-d)*2 : ++x+5;

		f)	S = x+y; i = 1;  for (j = 0; j < n; j++) { S = S + i*j*S; i = i*x; }

		g)	i = 1; S = 0; while ( i < 10 && S < 40 ) { S = S + f(i); ++i; }

		h)	if (z<x*y+5) a = x<y, z = (x+6)/(a-y); else z = y<<2;

		i)	do {x = y; y = 2*y;} while (x < k);

		j)	S = 0;  for (i = 1; i <= k; i = i + 1) S + =  i*i;

	k)	switch (k) {
			case 1: 		a = not a; break;
			case 2: 		b = a or not b ;
			case 3: 		a = b ;
		}

5. Bыражение на ПОЛИЗе	записать в инфиксной форме ( на С )

	a)	x y z a x 5 y / +  z 6 + 8   = = =

	b)	x a x z y / +  z 6 a - * + =
	
6. Является ли запись
y, 15, =,  x, x, a, b, c, 2, / , 1, +, *, -, *, a, -, =, y, y, 2, -, =, y, 10, <=, 4, !F
правильной записью в ПОЛИЗе следующего фрагмента программы на С (считаем, что элементы ПОЛИЗа нумеруются с 1):
y = 15; do {x = x*(a-b*(c/2+1))-a; y = y-2;} while y>10;
Если не является, то объясните почему и предложите свой вариант ПОЛИЗа для этого фрагмента программы.

7. Является ли запись
i, 1, =, i, n, <, 33 ,!F, a, a, b,+,1, -, x, y, y, 2, +, /, -, *, 5 ,+ ,=, i, i, 2, + ,=, 4, !
правильной записью в ПОЛИЗе следующего фрагмента программы на С (считаем, что элементы ПОЛИЗа нумеруются с 1):
for ( i = 1; i < n; i = i+2 )  a = (a+b-1)*(x-y/(y+2))+5;
Если не является, то объясните почему и предложите свой вариант ПОЛИЗа для этого фрагмента программы. 

8.	а) записать на ПОЛИЗе фрагмент программы на С:
i = 1; S = 0; while ( i < 10 && S < 40 ) { S = S + f(i); ++i; };
	b) выражение на ПОЛИЗе
x y z a x 5 y / +  z 6 + 8   = = =
	    записать в инфиксной форме ( на С ).

9. а) записать на ПОЛИЗе фрагмент программы на С:
if (z<x*y+5) a = x<y, z = (x+6)/(a-y); else z = y<<2;

	b) выражение на ПОЛИЗе
	x a x z y / +  z 6 a - * + =
записать в инфиксной форме ( на С ).

10. Предложить ПОЛИЗ для следующих операторов:

	a) if ( E ) S1; S2; S3
семантика этого оператора такова: вычисляется значение выражения Е; если его значение меньше 0, то выполняется оператор S1 ; если равно 0 - оператор S2 , иначе - оператор S3 

f) choice ( S1; S2; S3), E
семантика этого оператора такова: вычисляется значение выражения Е; если его значение равно i, то выполняется оператор Si для i = 1, 2, 3; иначе оператор choice эквивалентен пустому оператору.

g) cycle ( E1; E2; E3), S
семантика этого оператора отличается от семантики оператора for в языке Си только тем, что оператор S выполняется, по крайней мере, один раз (т.е. после вычисления выражения Е1 сразу выполняется оператор S, затем вычисляется значение Е3, потом - значение Е2, которое используется для контроля за количеством повторений цикла также, как и в цикле for).

11. Написать грамматику для выражений, содержащих переменные, знаки операций +, -, *, / и скобки ( ), где операции должны выполняться строго слева направо, но приоритет скобок сохраняется. Определить действия по переводу таких выражений в ПОЛИЗ.

12. Изменить приоритет операций отношения в М - языке ( сделать его наивысшим). Построить соответствующую грамматику, отражающую этот приоритет. Написать синтаксический анализатор, обеспечить контроль типов, задать перевод в ПОЛИЗ.

13. Написать КС-грамматику, аналогичную данной,

		E ® T {+T}
		T ® F {*F}
		F ® (E) | i

с той лишь разницей, что в новом языке будет допускаться унарный минус перед идентификатором, имеющий наивысший приоритет (например, a*-b+-c   допускается и означает a*(-b)+(-c).
В созданную грамматику вставить действия по переводу такого выражения в ПОЛИЗ. Для каждой используемой процедуры привести ее текст на Cи.

14. Дана грамматика, описывающая выражения:

	E ® TE’		E’ ® +TE’ | 
	T ® FT’		T’ ® *FT’ | 
	F ® PF’		F’ ® ^PF’ | 
	P ® (E) | i

Включить в эту грамматику действия по переводу этих выражений в ПОЛИЗ. Для каждой используемой процедуры привести ее текст на Си.

СОДЕРЖАНИЕ

Задачи (Приложение к учебному пособию"Формальные грамматики и языки. Элементы теории трансляции")
I. Порождающие грамматики. Языки, порождаемые грамматиками. Классификация грамматик и языков по Хомскому
II. Регулярные грамматики, ДС, анализаторы по ДС. Преобразование НКА к ДКА
III. Метод рекурсивного спуска (РС-метод). Применимость  РС-метода. КС-грамматики с действиями
IV. Синтаксически управляемый перевод
V. ПОЛИЗ, перевод в ПОЛИЗ