Решенные задачи на экзамен Опалевой / variaNTS / VAR_8

Вариант № 8

1. Описать цикл while на С++ . Условие задается отношением, тело цикла состоит из

операторов присваивания, состоящих из простых переменных = арифметические

выражения.

<циекл_с_предусловием>::= while (<выраж_условие> ) <тело_цикла>

<выраж_условие> ::= <арифм_выр> <опер_отнош> <арифм_выраж> <остаток>

<остаток>::=

<остаток>::= , <выраж_условие>

<опер_отнош>::= = | > | < | <= | >= | !=

<арифм_выр>::= <арифм_выр> + <слагаемое>

<арифм_выр>::= <слагаемое>

<арифм_выр>::= <арифм_выр> - <слагаемое>

<слагаемое>::= <слагаемое> * <множитель>

<слагаемое>::= <множитель>

<слагаемое>::= <слагаемое> / <множитель>

<множитель>::= <идентификатор>

<множитель>::= <число>

<множитель>::= ( <арифм_выр> )

<тело_цикла>::= <присваивание>;

<тело_цикла>::= { <блок_опер> }

<тело_цикла>::= ;

<блок_опер>::=

<блок_опер>::= <операторы>

<блок_опер>::=

<операторы>::= < операторы > <остаток1>

<операторы>::= <присваивание>;

<операторы>::={<операторы>}

<остаток1>::= < операторы >

<остаток1>::=

<присваивание>::= <идентификатор> = <арифм_выр>

<идентификатор>::= <буква> { <буква> | <цифра> }

<буква>::=A|B|C…Y|Z|a|b|c…z|

<цифра>::= 0|1|2|3|4|5|6|7|8|9

<число>::= [ +|-] <число_без_знака>

<число_без_знака>::= <цифра> { <цифра> }

2. ДМП-автомат, распознающий цепочки 1^n 0^m 1^n , где n,m>0.

S1A, A1A, A0B, B0B, B1C, C1C, C ε

Управляющая таблица для состояния S :

q0	0	1	Eps
1
		A

Управляющая таблица для состояния A:

q1	0	1	Eps
1	B	A


Управляющая таблица для состояния B:

q2	0	1	Eps
1	B	C


Управляющая таблица для состояния C:

q3	0	1	Eps
1		C


Функции перехода:

 (q₀ , 1, )  {(q₁ ,1)}

 (q₁ , 1, 1)  {(q₁ ,11)}

 (q₁ , 0, 1)  {(q₂ ,1)}

 (q₂ , 0, 1)  {(q₂ ,1)}

 (q₂ , 1, 1)  {(q₃ , )}

 (q₃ , 1, 1)  {(q₃ ,)}

4. R={S->aAd, S->bAB, A->cA, A->c, B->d}. Построить управляющую таблицу SLR(1).

Описание алгоритма:

1. Строим пополненную грамматику G’ для исходной грамматики G.

S’ S (0)

S  aAd (1)

S  bAB (2)

A cA (3)

A c (4)

B d (5)

2. Вычисление отношения ВПОД для грамматических вхождений грамматики G’.

2.1. Из определения отношения ВПОД  ВПОД Y_j тогда и только тогда, когда

Y_j  ВПЕРВ(S₀).

Из S можно вывести цепочки: S a A d и S  b A B

Следовательно ВПЕРВ(S₀) = {a₁, b₂, S₀} и тогда

 ВПОД a₁ ,  ВПОД b₂ ,  ВПОД S₀

2. Рассмотрим правило (1) S  a A d . Из определения отношения ВПОД

сле­дует, что a₁ ВПОД Y_j для всех Y_j  ВПЕРВ(A₁).

Из A можно вывести цепочки: A c A (3) и A  c (4)

Следовательно ВПЕРВ(A₁) = {c₃, c₄, A₁} и тогда

a₁ ВПОД c₃ , a₁ ВПОД c₄ , a₁ ВПОД A₁

Также А₁ ВПОД d₁

2. Рассмотрим правило (2) S  b A B . Из определения отношения ВПОД

сле­дует, что b₂ ВПОД Y_j для всех Y_j  ВПЕРВ(A₂).

Из A можно вывести цепочки: A c A (3) и A  c (4)

Следовательно ВПЕРВ(A₂) = {c₃, c₄, A₂} и тогда

b₂ ВПОД c₃ , b₂ ВПОД c₄ , b₂ ВПОД A₂

Также A₂ ВПОД Y_j для всех Y_j  ВПЕРВ(B₂).

Из B можно вывести цепочки: B d (5)

A₂ ВПОД d₅ A₂ ВПОД B₂

2. Рассмотрим правило (3) A  c A . Из определения отношения ВПОД

сле­дует, что c₃ ВПОД Y_j для всех Y_j  ВПЕРВ(A₃).

Из A можно вывести цепочки: A c A (3) и A  c (4)

Следовательно ВПЕРВ(A₃) = {c₃, c₄, A₃} и тогда

c₃ ВПОД c₃ , c₃ ВПОД c₄ , c₃ ВПОД A₃

Матрица отношений ВПОД:

	S0	a1	A1	d1	b2	A2	B2	c3	A3	c4	d5
S0
a1			1					1		1
A1				1
d1
b2						1		1		1
A2							1				1
B2
c3								1	1	1
A3
c4
d5
	1	1			1

3. Определение функции переходов g(X).

3.1. Построим таблицу переходов конечного детерминированного автомата.

Столбцы: символы из V  {}

Строки: каждое грам­матическое вхождение грамматики G’и маркер дна. Элемент в строке, помеченной грамматическим вхождением Х_i или маркером дна , и столбце, отмеченном символом грамматики Y, должен содержать все грамматические вхождения, для которых справед­ливо отношение Х_i ВПОД Y_j.

Таблица переходов конечного (недетерминированного) автомата.

	S	A	B	a	c	b	d
S0
a1		A1			c3, c4
A1							d1
d1
b2		A2			c3, c4
A2			B2				d5
B2
c3		A3			c3, c4
A3
c4
d5
	S0			a1		b2

Преобразуем в детерминированный:

	S	A	B	a	c	b	d
{S0}
{a1}		{A1}			{c3, c4}
{A1}							{d1}
{d1}
{b2}		{A2}			{c3, c4}
{A2}			{B2}				{d5}
{B2}
{c3, c4}		{A3}			{c3, c4}
{A3}
{c3, c4}
{d5}
{}	{S0}			{a1}		{b2}

Определим множество магазинных символов:

	{S0}	{a1}	{A1}	{d1}	{b2}	{A2}	{B2}	{c3, c4}	{A3}	{d5}	{}
Vp	S0	a1	A1	d1	b2	A2	B2	c	A3	d5	

Функции переходов.

	S	A	B	a	c	b	d
S0
a1		A1			c
A1							d1
d1
b2		A2			c
A2			B2				d5
B2
c		A3			c
A3
d5
	S0			a1		b2

Построение функции действия.

Для магазинного символа Т, представляющего множество грамматических вхождений Q, и входного символа a значение f(a) определяется следующим образом.

а) Если начальное вхождение S₀  Q и a = , то f() = ДОПУСК.

б) Если a   и g(a)  ошибка, то f(a) = перенос.

в) Если Xj  Q – самое правое грамматическое вхождение i-го правила AX_j и a  СЛЕД(А), то f(a) = (СВЕРТКА, i). Значение остальных эле­ментов таблицы для f(a) – ОШИБКА.

Если имеется множество грам­матических вхождений, не удов­летворяющих условиям а, б и в, то грамматика не принадле­жит классу SLR(1).

Функция действия:

	a	c	b	d	
S0					Д
a1		П
A1				П
d1					C,1
b2		П
A2				П
B2					C,2
c		П		C,4
A3				C,3
d5					C,5
	П		П