Дерево вывода и цепочка вывода, построенные на основе входной цепочки. Преобразование дерева синтаксического обзора в дерево операций

Триады - многоадресный код с неявно именуемым результатом C=A*12+K*(2-3*B) 1. *(A,12) 2. *(3,B) 3. – (2,2 ) 4. *(K,3 ) 5. +(1 ,4 ) 6.:= (C,5 ) 2. Тетрады – многоадресный код с явно именуемым результатом C=A*12+K*(2-3*B) 1. *(A,12,D1) 2. *(3,B,D2) 3. – (2,D2,D3) 4. *(K,D3,D4) 5. +(D1,D4,D5) 6.:= (D5,0,C) 3. Построение таблицы идентификаторов методом бинарного дерева. Идентификаторы поступают в следующем порядке: K1, A22, B1, M, P3, L. Решение: создаем дерево идентификаторов, листья пишутся с точи зрения расположения букв в алфавите – если по алфавиту меньше то на налево, если больше то направо.

Обратная польская запись операций

Вычислить выражения в обратной польской записи с использованием стека. Выражение: 5*9-6*(3+4)

5		9		*		6		3		4		+		*		-
										4
								3		3		7
		9				6		6		6		6		42
5		5		45		45		45		45		45		45		3

 

Заполнение таблицы идентификаторов методом цепочек (хэш адресация методом цепочек)

Идентификаторы поступают в следующем порядке: ab, ac, an, ak, bc, az, ck. Максимальное значение ХФ N_m=13 (под ХТ будет выделен объем памяти, равный 13). Используемая ХФ-ASCII-код первой буквы идентификатора.

h(ab)=h(ac)=h(an)=h(ak)=h(az)=d7

h(bc)=d3

h(ck)=d9

	ХТ			ТИ
d1			a1	ab	a2
d2			a2	ac	a3
d3	a5		a3	an	a4
d4			a4	ak	a5
d5			a5	bc	a6
d6			a6	az	a7
d7	a1		a7	ck	-
d8
d9	a7
d10
d11
d12
d13

Указатель

6. Заполнение таблицы идентификаторов методом рехеширования с помощью произведения

Формула для простого рехеширования h_i(A)=(h(A)+i)mod N_m

Формула для рехеширования с помощью произведения h_i(A)=(h(A)*i)mod N_m

Идентификаторы поступают в следующем порядке: ab, ac, an, ak, bc, az, ck. Максимальное значение ХФ N_m=13 (под ТИ будет выделен объем памяти, равный 13). Используемая ХФ- ASCII-код первой буквы идентификатора.

h(ab)=h(ac)=h(an)=h(ak)=h(az)=d7

h(bc)=d3

h(ck)=d9

	ТИ
d1	ac
d2	ak
d3
d4
d5	ck
d6
d7	ab
d8	an
d9	az
d10
d11
d12
d13

Шаг 1. h(ab)=d7

Шаг 2. h(ac)=d7 - коллизия

h1(ac)=(h(ac)*1)mod13=d7 - коллизия

h2(ac)=(h(ac)*2)mod13=d1

Шаг 3. h(an)=d7 - коллизия

h1(an)=(h(an)*1)mod13=d7 - коллизия

h2(an)=(h(an)*2)mod13=d1- коллизия

h3(an)=(h(an)*3)mod13=d8

Шаг 4. h(ak)=d7 - коллизия

h1(ak)=(h(ak)*1)mod13=d7 - коллизия

h2(ak)=(h(ak)*2)mod13=d1 - коллизия

h3(ak)=(h(ak)*3)mod13=d8 - коллизия

h4(ak)=(h(ak)*4)mod13=d2

Шаг 5. h(bc)=d3

Шаг 6. h(az)=d7 - коллизия

h1(az)=(h(az)*1)mod13=d7 - коллизия

h2(az)=(h(az)*2)mod13=d1 - коллизия

h3(az)=(h(az)*3)mod13=d8 - коллизия

h4(az)=(h(az)*4)mod13=d2 - коллизия

h5(az)=(h(az)*5)mod13=d9

Шаг 7. h(ck)=d9 - коллизия

h1(ck)=(h(ck)*1)mod13=d9 - коллизия

h2(ck)=(h(ck)*2)mod13=d5

Цепочки вывода и дерево вывода

На основе заданной грамматики построить множество цепочек вывода. Если число без знака (допустим 575), то начинаем разбор по правилу с крайнего правого символа, если число со знаком (+ или -, т.е. -9856 или +9856), то начинаем разбор с крайнего левого символа.

S=>*575 S=>*-9856

P: S→T¹|+T²|-T³

T→F⁴|TF⁵

F→0⁶|1⁷|2⁸|3⁹|4¹⁰|5¹¹|6¹²|7¹³|8¹⁴|9¹⁵

S T TF T5 TF5 T75 F75 575

S=>⁷575 – 7 это то количество шагов, за которые мы получили 575

-T -TF -TFF -TFFF -FFFF -9FFF -9F5F -985F -9856

S=>⁸-9856

Преобразование конечного автомата (КА) в детерминированный конечный автомат (ДКА)

Задан КА M({H,A,B,S},{a,b,c}, ,H,{S})

: (a,H)=A (c,A)=B (c,H)=B (b,B)=A (a,A)=B (b,B)=S

Необходимо построить эквивалентный ему ДКА

M’(Q’,V’, ’,q₀’,F’)

1. Находим множество состояний эквивалентного ДКА

Поскольку в КА 4 состояния (n=4), то в ДКА будет m=2ⁿ-1=15

Q’={H,A,B,S,HA,HB,HS,AB,AS,BS,HAB,HAS,HBS,ABS,HABS}

2. Строим функцию переходов эквивалентного ДКА по таблице. Если в скобках в самой верхней строке, после запятой (т.е. допустим на месте, где написано «Н» в (a,H)=A), есть искомая буква из столбца, написанная также в скобках после запятой (т.е.допустим «Н» в H (*,H)), то пишем плюс. Если у нас две, три и более искомых букв, то, найдя в самой верхней строке в скобках после запятой любую из них, также ставим плюс.

	(a,H)=A	(c,H)=B	(a,A)=B	(c,A)=B	(b,B)=A	(b,B)=S
H (*,H)	+	+
A (*,A)			+	+
B (*,B)					+	+
S (*,S)
HA (*,HA)	+	+	+	+
HB (*,HB)	+	+			+	+
HS (*,HS)	+	+
AB (*,AB)			+	+	+	+
AS (*,AS)			+	+
BS (*,BS)					+	+
HAB (*,HAB)	+	+	+	+	+	+
HAS (*,HAS)	+	+	+	+
HBS (*,HBS)	+	+			+	+
ABS (*,ABS)			+	+	+	+
HABS (*,HABS)	+	+	+	+	+	+

Как заполнять ’:

1) Из самой верхней строки переписываем те значения, под которыми стоит знак плюса.

2) Заменяем значение после запятой на то, которое указано в столбце, т.е. например в 11 строке (a,H)=A заменим на (a,HAB)=A, (c,H)=B на (c,HAB)=B и т.д.

3) Если после такой замены у нас получается, например, (b,HAB)=A и (b,HAB)=S, то, в связи с тем, что первая маленькая буква у них совпадает, объединяем в (b,HAB)=AS.

’:

(a,H)=A (c,H)=B

2) (a,A)=B (c,A)=B

3) (b,B)=AS

4) -

5) (a,HA)=AB (c,HA)=B

6) (a,HB)=A (c,HB)=B (b,HB)=AS

7) (a,HS)=A (c,HS)=B

8) (a,AB)=B (c,AB)=B (b,AB)=AS

9) (a,AS)=B (c,AS)=B

10) (b,BS)=AS

11) (a,HAB)=AB (c,HAB)=B (b,HAB)=AS

12) (a,HAS)=AB (c,HAS)=B

13) (a,HBS)=A (c,HBS)=B (b,HBS)=AS

14) (a,ABS)=B (c,ABS)=B (b,ABS)=AS

15) (a,HABS)=AB (c,HABS)=B (b,HABS)=AS

3. Строим ДКА

4. Начальное состояние ДКА q₀’=H

Множество конечных состояний

F={S,HS,AS,BS,HAS,HBS,ABS,HABS}

8 конечных состояний

Исключим недостижимые состояния (получим граф переходов полностью определенного ДКА). Как это делать: смотрим по получившемуся графику. Из «Н» по стрелке мы можем переместиться только в «А» и «В». Из «А» можем только в «В», из «В» только в «AS», из «AS» только в «В». Дописываем состояние конца «S» и состояние ошибки «E».

Розовым обозначены недостающие a, b или c. Из каждого состояния обязательно должно выходить и a, и b, и c. И если какого либо из них не хватает, то мы дорисовываем стрелку до ошибки (error, состояние «E») и надписываем недостающие буквы (a, b, c).

Дерево вывода и цепочка вывода, построенные на основе входной цепочки. Преобразование дерева синтаксического обзора в дерево операций

Входная цепочка a+(b-a) – МПА автомат

P: F→F+F¹|F-F²

F→F*F³|F/F⁴

F→(F)⁵|a⁶|b⁷

	+	-	*	/	(	)	a	b	к
+	.>	.>	<.	<.	<.	.>	<.	<.	.>
-	.>	.>	<.	<.	<.	.>	<.	<.	.>
*	.>	.>	.>	.>	<.	.>	<.	<.	.>
/	.>	.>	.>	.>	<.	.>	<.	<.	.>
(	<.	<.	<.	<.	<.	=.	<.	<.
)	.>	.>	.>	.>		.>			.>
a	.>	.>	.>	.>		.>			.>
b	.>	.>	.>	.>		.>			.>
н	<.	<.	<.	<.	<.		<.	<.

<. =. сдвиг

>. свертка

символ до точки с запятой ищем в строке, после точки запятой ищем в столбце

1. {a+(b-a) к; н;Ø}÷сд

2. {+(b-a) к; нa;Ø}÷св

3. {+(b-a) к; нF;6}÷сд

4. {(b-a) к; нF+;6}÷сд

5. {b-a) к; нF+(;6}÷сд

6. {-a) к; нF+(b;6}÷св

7. {-a) к; нF+(F;6,7}÷сд

8. {a) к; нF+(F-;6,7}÷сд

9. {) к; нF+(F-a;6,7}÷св

10. {) к; нF+(F-F;6,7,6}÷св

11. {) к; нF+(F;6,7,6,2}÷сд

12. { к; нF+(F);6,7,6,2}÷св

13. { к; нF+F;6,7,6,2,5}÷св

14. { к; нF;6,7,6,2,5,1}

Разбор закончен. Цепочка принята.

Цепочка вывода: F F+F F+(F) F+(F-F) F+(F-a) F+(b-a) a+(b-a)

Дерево вывода (синтаксическое дерево):

Процесс построения дерева операций разбора:

 

 

---

Дата добавления: 2018-04-05; просмотров: 602; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!