Добавил:

Studfiles2 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Санкт-Петербургский государственный электротехнический университет "ЛЭТИ"

Предмет:

Теория языков программирования

Файл:

VAR_7

.DOC

Скачиваний:

Добавлен:

01.05.2014

Размер:

205.82 Кб

Скачать

☆

Вариант №7

Составить А-грамматику, КС-грамматику, распознающую язык {aⁿb^m, n>0, m>0}

Автоматная грамматика

T = {a,b}

N= {S, A, B}

R={ S a A, A aA, AbB, BbB, B  }

Управляющая таблица детерминированного конечного автомата по автоматной

грамматике G = <T, N, S,R >

	a	b	Eps
S (q₀)	A
A(q₁)	A	B
B(q₂)		B

Функции перехода : q₂– заключительное состояние

 (q₀, a)  q₁

 (q₁, a)  q₁

 (q₁, b)  q₂

 (q₂, b)  q₂

Контекстно-свободная грамматика

T = {a,b}

N= {S, A, B}

R={ S AB, A Aa, Aa, BBb, Bb}

КС -> НКС . Например: R ={ S–>aA, S–>bB, A–>1A0, A–>ε, B–>1B00, B–>ε }

KC-грамматика называется грамматикой без ε -правил (НKC-грамматикой) , если либо множество R не содержит ε -правил, либо есть единственное правило S -> ε , и S не встречается

в правых частях других правил.

Алгоритм:

Построение укорачивающих нетерминалов G : Nε

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

Nε = {A,B}

Построение R^’. G1=<{a,b,0,1}, {A,B,S},S,{ S–>aA, S–>a, S–>bB, S–>b, A–>1A0, A–>10,

B–>1B00, B–>100 }>

AT- грамматику для сравнения арифметических выражений. Допускается использование круглых

скобок ,+,* .Перевести в триады.

E_t	выражение	t - синтезированный
E`_p,t	остаток выражения	p - унаследованный, t - синтезированный
EAR_t	арифметическое выражение	t - синтезированный
T_t	терм	t - синтезированный
T`_p,t	остаток терма	p - унаследованный, t - синтезированный
P_t	произведение	t - синтезированный
P`_p,t	остаток произведения	p - унаследованный, t - синтезированный
F_t	фактор	t - синтезированный
Используем как терминал:
VAR_t	переменная	t – синтезированный

E_t2  EAR_p1 E`_p2,t1

p2p1

t2t1 t1 – тип значения арифметического выражения

E`_p1,t2  = EAR_q1 {равно}_p2,q2,r2 E`_r2,t1

r1,r2НОВЭЛТ r2 – адрес триады, сгенерированной в соответствии с

таблицей 1

p2p1 p2,q2 – адреса, где находятся значения выражений

q2q1

t2t1

E`_p1,t2 < EAR_q1 {меньше}_p2,q2,r2 E`_r2,t1

r1,r2НОВЭЛТ

p2p1

q2q1

t2t1

E`_p1,t2 > EAR_q1 {больше}_p2,q2,r2 E`_r2,t1

r1,r2НОВЭЛТ

p2p1

q2q1

t2t1

E`_p1,p2 

p2p1

EAR_t2  + T_t1

t2t1

EAR_t2   T_t1 {поменять_знак}_t1

t2t1

EAR_t2  T_t1

t2t1

T_t₂  P_p1 T`_p2,t1

p2p1

t2t1

T`_p1,t2 + P_q1 {сложить}_p2,q2,r2 T`_r2,t1

r1,r2НОВЭЛТ

p2p1

q2q1

t2t1

T`_p1,t2  P_q1 {вычесть}_p2,q2,r2 T`_r2,t1

r1,r2НОВЭЛТ

p2p1

q2q1

t2t1

T`_p1,p2  

p2p1

P_t₂  F_p1 P`_p2,t1

p2p1

t2t1

P`_p1,t2 * F_q1 {умножить}_p2,q2,r1 P`

r1,r2НОВЭЛТ

p2p1

q2q1

t2t1

P`_p1,t2  / F_q1 {делить}_p2,q2,r1 P`_r2,t1

r1,r2НОВЭЛТ

p2p1

q2q1

t2t1

P`_p1,p2  

p2p1

F_t2  cns_t1

t2t1 t1 – значение константы

F_t2  ( EAR_t1 )

t2t1

F_t2  VAR_t1

t2t1 t1 – значение переменной

НОВЭЛТ - процедура, которая выдает значение указателя на свободную позицию таблицы, используемой для запоминания результата.

Операционные символы:

{равно}_A_1,А2,_R	R = адрес триады, сгенерированной в соответствии с таблицей 1
{меньше}_A_1,А2,_R	R = адрес триады, сгенерированной в соответствии с таблицей 2
{больше}_A_1,А2,_R	R = адрес триады, сгенерированной в соответствии с таблицей 3
{поменять_знак}_A	Генерируется триада в соответствии с таблицей 4
{сложить}_A_1,А2,_R	R = адрес триады, сгенерированной в соответствии с таблицей 5
{вычесть}_A_1,А2,_R	R = адрес триады, сгенерированной в соответствии с таблицей 6
{умножить}_A_1,А2,_R	R = адрес триады, сгенерированной в соответствии с таблицей 7
{делить}_A_1,А2,_R	R = адрес триады, сгенерированной в соответствии с таблицей 8

Таблица 1:

==	integer	real	complex	boolean
integer	==I A₁,A₂
real		==R A₁,A₂
complex			==C A₁,A₂
boolean				==B A₁,A₂

Таблица 2:

<	integer	real	complex	boolean
integer	<I A₁,A₂
real		<R A₁,A₂
complex			<C A₁,A₂
boolean				<B A₁,A₂

Таблица 3:

>	integer	real	complex	boolean
integer	>I A₁,A₂
real		>R A₁,A₂
complex			>C A₁,A₂
boolean				>B A₁,A₂

Таблица 4:

- (бинарный)	integer	real	complex	boolean
integer	negI A₁,A₂
real		negR A₁,A₂
complex			negC A₁,A₂
boolean

Таблица 5:

+	integer	real	complex	boolean
integer	addI A₁,A₂
real		addR A₁,A₂
complex			addC A₁,A₂
boolean

Таблица 6:

-	integer	real	complex	boolean
integer	subI A₁,A₂
real		subR A₁,A₂
complex			subC A₁,A₂
boolean

Таблица 7:

*	integer	real	complex	boolean
integer	mulI A₁,A₂
real		mulR A₁,A₂
complex			mulC A₁,A₂
boolean

Таблица 8:

/	integer	real	complex	boolean
integer	divI A₁,A₂
real		divR A₁,A₂
complex			divC A₁,A₂
boolean

P.S. Из всех таблиц необходимо убрать строку и столбец: complex

Определить, является ли грамматика грамматикой операторного предшествования.

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

Строки матрицы предшествования отмечаются символами из T{}, а столбцы – символами из. T{}.

Операторная грамматика G = < T, N, S, R > называется грамматикой операторного предшествования, если между любыми двумя терминалами или символами  и  выполняется не более одного отношения операторного предшествования.

Отношения предшествования практически строятся также, как и для простого предшествования.

E  E or T (1)

E  T (2)

T  T and P (3)

T  P (4)

P  i (5)

P  ( E ) (6)

P  not P (7)

Отношения ищем только между терминальными символами.

a b, если A  aCb  R , где С – либо нетерминал, либо пусто.

Отсюда: (  )

a <• b, если A  aB  R и B + Cb, где С – либо нетерминал, либо пусто.

Т. е. ищем нетерминалы, перед которыми стоят какие-либо Т – символы, и строим все возможные цепочки из этих нетерминалов:

1-ое: E E or T, из Т возможы выводы: T  T and P  P and P  i and P

 ( E ) and P

 not P and P

Получили: or <• and, or <• i, or <• ( , or <• not

3-е: T  T and P, из P возможны выводы: P i , P ( E ), P not P

Получили отношения: and <• i, and <• (, and <• not

6-ое: P  ( E ), ищем все возможные символы, с которых начинаются цепочки,

выводимые из Е:

E  E or T  T or T  P or T  i or T

 T and P or T  ( E ) or T

 not P or T

Отсюда отношения: (<• or, (<• i, (<• ), (<• not , (<• and.

7-ое: P not P, в предыдущем правиле на промежуточном этапе мы уже нашли все

возможные символы, с которых начинаются цепочки, выводимые из P: i, (, not.

Отношения: not<• i, not<• (, not<• not

Из начального символа грамматики выводятся цепочки, начинающиеся с символов:

E  E or T  T or T  P or T  i or T

 T and P or T  ( E ) or T

 not P or T

Отсюда отношения: <• and, <• or,  <• i, <• ), <• not.

a •> b, если A  Bb  R и B + aC, где С – либо нетерминал, либо пусто.

В исходной грамматике ищем правила, содержащие нетерминал, непосредственно за которым следует какой-либо символ.

1-ое : E  E or T , найдем все символы, на которые могут заканчиваться выводы

из Е  E or T  E or P  E or i P  not P

 E or T and P  E or ( E )

Можем занести в матрицу отношения: or•> or, and•> or, i•> or, ) •> or , not •> or

3-е: T  T and P , в превыдущем правиле мы нашли символы, на которые

заканчиваются цепочки из T:

Отношения: and•> and, i•> and, ) •> and, not •> and

6-ое: P  ( E ), все возможные символы, заканчивающие цепочки из E, найдены:

or •> ), and •> ), i•> ), ) •> ) , not •> )

Так как E является начальным символом грамматики, то также можем добавить следующие отношения: or •> , and •> , i•> , ) •> , not •> 

МАТРИЦА ПРЕДШЕСТВОВАНИЯ :

	or	and	i	not	(	)	Eps
or	>	<	<	<	<	>	>
and	>	>	<	<	<	>	>
i	>	>				>	>
not	>	>	<	<	<	>	>
(	<	<	<	<	<	
)	>	>				>	>
	<	<	<	<	<

Т.к. нет пересечений – грамматика операторного пред-я.

функция "перенос"

	or	and	i	not	(	)	Eps
or	C	П	П	П	П	C	C
and	C	C	П	П	П	C	C
i	C	C				C	C
not	C	C	П	П	П	C	C
(	П	П	П	П	П	П
)	C	C				C	C
	П	П	П	П	П
 E	П	П	П	П	П		Д

Остовная грамматика:

E  E or E (1)

E  E and E (3)

E  i (5)

E  ( E ) (6)

E  not E (7)

Рассмотрим правило ( 5 ) E  i

остовной грамматики G_0s. В магазине ниже правой части этого правила i могут быть только те символы b, для которых b <• i, т.е. множество символов { ( , or , and, not , }. Поэтому g ((Ci) = 5, g (orCi) = 5,

g (andCi) = 5, g (Ci) = 5, g (not Ci) = 5, где С  {E, }

	g()
(E or E	1
E or E	1
or E and E	3
(E and E	3
 E and E	3
( i	5
or i	5
and i	5
not i	5
 i	5
and ( E )	6
not ( E )	6
or ( E )	6
( ( E )	6
 ( E )	6
and not E	7
or not E	7
not not E	7
 not E	7
( not E	7

Соседние файлы в папке variaNTS

#
01.05.2014181.76 Кб9VAR_2.DOC
#
01.05.201472.19 Кб8VAR_3.DOC
#
01.05.201458.88 Кб8VAR_4.DOC
#
01.05.2014170.5 Кб9VAR_5.DOC
#
01.05.2014205.82 Кб9VAR_7.DOC
#
01.05.201481.41 Кб10VAR_8.DOC
#
01.05.2014169.47 Кб9VAR_9.DOC

	or	and	i	not	(	)	Eps
or	>	<	<	<	<	>	>
and	>	>	<	<	<	>	>
i	>	>				>	>
not	>	>	<	<	<	>	>
(	<	<	<	<	<	
)	>	>				>	>
	<	<	<	<	<

	or	and	i	not	(	)	Eps
or	>	<	<	<	<	>	>
and	>	>	<	<	<	>	>
i	>	>				>	>
not	>	>	<	<	<	>	>
(	<	<	<	<	<	
)	>	>				>	>
	<	<	<	<	<

	or	and	i	not	(	)	Eps
or	>	<	<	<	<	>	>
and	>	>	<	<	<	>	>
i	>	>				>	>
not	>	>	<	<	<	>	>
(	<	<	<	<	<	
)	>	>				>	>
	<	<	<	<	<