lekcii_dm

8.07.Замечания.

1.Синтаксический анализатор "grammatika" реализован исходя из вида детерминированного конечного автомата. Этот же самый анализатор может иметь множество других программных реализаций, как-то:

a) в качестве основы может быть взята грамматика;

b) могут использоваться различные программные конструкции языков программирования и другие причины.

2.Синтаксический анализатор может быть реализован на любом, доступном студенту, алгоритмическом языке: PL, Си, TURBO Pascal, ассемблер, BASIC и других. Нельзя на PHP, PERL.

В качестве иллюстрации приведем синтаксический анализатор, реализованный на языке ассемблера.

Пусть задано регулярное выражение (cc) (ba10)* (0а)*, т. е. имеется

язык:

L75 = {(cc)m (balO)n (Oa)p : m, n, p > 0}.

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

TITLE (cc)* (bа10)*(0а)* code segment assume cs:code, ds:code

org l00h begin: JMP MAIN ;------------------------------------------------------

clf egu OAh, ODh

OKMSG db clf, 'O-K TESTED ! $' ERMSG db clf, 07h, 'Invalid simvol !', '$' WMSG db clf, 'Press the ENTER for exit!', '$' ;———————————————— MAIN proc

S:call GCHR

221

cmp al, Odh jeOK

cmp al,'c' jeT

cmp al, 'b' jeV cmp al, '0' jeY

jmpNO T:

T:call GCHR

cmp al, 'c' jeS jmpNO

V: call GCHR cmp al, 'a' jeW jmpNO W:call GCHR cmp al, ' 1' jeX jmpNO X: call GCHR

cmp al, '0' je U jmp NO

U: call GCHR cmp al, 'b'

je V cmp al, '0' je Y

cmp al, Odh je OK

jmp NO

Y: call GCHR cmp al, 'a'

je Z

222

jmp NO

Z: call GCHR cmp al,'0'

je Y

cmp al, Odh je OK

NO: lea dx, ERMSG mov ah, 09h

Int 21h call WAI ret

OK: lea dx, OKMSG mov ah, 09h

Int 21h call WAI ret

MAIN endp ;------------------------------------------------------

GCHR proc mov ah, Olh Int21h

Ret GCHR endp

;--------------------------------------------------------------------

WAI proc lea dx, WMSG mov ah, 09h Int 21h

call GCHR

223

cmp al, Odh jne WT

ret WAI endp ;------------------------------------------------------

code ends

end begin ; IT WORKS !

синтаксического анализатора (на любом из реализованных на компьютерной технике.

8.08. Отчет по практической работе.

Отчет оформляется в соответствии с требованиями, предъявляемыми к оформлению лабораторных работ в вузе, и должен содержать:

1.Титульный лист.

2.Наименование и цель работы.

3.Исходные данные варианта задания.

4.Алгоритм решения задачи (граф, таблица переходов).

5.Листинг программы с исходными и выходными данными (листинг программы).

6.Анализ результатов (контрольная распечатка).

7.Выводы.

Замечание: листы отчета должны быть скреплены.

8.09.Контрольные вопросы

1.Какие грамматики называются регулярными?

2.Чем отличается детерминированный конечный автомат от недетерминированного?

3.Связь регулярных грамматик и конечных автоматов.

4.Что такое регулярное выражение?

224

5.Алгоритм получения детерминированного конечного автомата из недетерминированного.

6.Какие программные особенности отмечены при написании синтаксического анализатора.

7.Что такое состояние отказа в автомате, соответствующем анализатору?

8.Что такое грамматика?

225

8.10. Варианты заданий.

Вариант задания определяется по последним двум цифрам зачётной книжки.

1.(0110)* (1101)* (0111)*

2.(abaa)* (baba)* (abbb)*

3.(a120)* (a001)* (baa0)*

4.(a1b1)* (11a1)* (b1aa)*

5.(21b)* (112b)* (b122)*

6.(baba)* (abab)* (aaba)*

7.(1011)* (1100)* (0001)*

8.(a1b1)* (b12a)* (bb1)*

9.(bba1)* (11aa)* (1ba1)*

10.(b211)* (1abb)* (b11a)*

11.(ab11)* (a11b)* (1aa1)*

12.(bb12)* (2bb1)* (1b21)*

13.(1000)* (1001)* (0001)*

14.(1ab1)* (2b22)* (ab1b)*

15.(ba21)* (1bba)* (2a11)*

16.(ba22)* (11bb)* (2baa)*

17.(0001)* (1011)* (1000)*

18.(bb2a)* (a2bb)* (12ba)*

19.(1b0a)* (1ab2)* (120a)*

20.(1ab0)* (11ab)* (11a0)*

21.(bba2)* (bb01)* (bb0a)*

22.(bb00)* (a12b)* (baab)*

23.(1100)* (1000)* (1011)*

24.(1abb)* (1aa0)* (1bbb)*

25.(2110)* (1210)* (1101)*

226

26.(baba)* (cbab)* (abbb)*

27.(1010)* (c010)* (1110)*

28.(01ab)* (ba10)* (a10a)*

29.(a010)* (0010)* (0110)*

30.(ab11)* (11ab)* (a1a1)*

31.(ccaa)* (0caa)* (a0ca)*

32.(a010)* (0011)* (1001)*

33.(1001)* (1aa0)* (0a11)*

34.(10a1)* (0011)* (1100)*

35.(a100)* (01a0)* (11aa)*

36.(a010)* (01a0)* (aa11)*

37.(01a0)* (a011)* (010a)*

38.(10a0)* (1a01)* (110a)*

39.(1b01)* (01b1)* (b1b1)*

40.(1101)* (c010)* (00cc)*

41.(0c10)* (0101)* (1101)*

42.(abca)* (caca)* (baba)*

43.(0001)* (0101)* (0a10)*

44.(00a1)* (a110)* (a10a)*

45.(11a0)* (a01a)* (01a0)*

46.(10a1)* (0a10)* (01a0)*

47.(ca0a)* (caca)* (c0c0)*

48.(01cc)* (cc10)* (c01c)*

49.(01aa)* (1010)* (a00a)*

50.(a00a)* (01a0)* (0a01)*

51.(0aa1)* (a001)* (a0a1)*

52.(0a01)* (10a1)* (0a10)*

53.(10a1)* (0a10)* (a1a1)*

54.(a0a0)* (a001)* (0a1a)*

227

55.(aa01)* (01aa)* (000a)*

56.(a01a)* (a001)* (00a0)*

57.(0a10)* (a101)* (a001)*

58.(0a10)* (00a1)* (a100)*

59.(1a01)* (a101)* (001a)*

60.(1a01)* (0a10)* (a01a)*

61.(1021)* (2021)* (2010)*

62.(2010)* (2100)* (2220)*

63.(2102)* (2201)* (2202)*

64.(2010)* (0012)* (2001)*

65.(1010)* (2001)* (2220)*

66.(1210)* (0201)* (2202)*

67.(01a0)* (01a1)* (1a01)*

68.(a101)* (a110)* (a10a)*

69.(1202)* (2102)* (2001)*

70.(0012)* (2011)* (1021)*

71.(abab)* (baba)* (bbaa)*

72.(baab)* (abab)* (bbaa)*

73.(a101)* (1a01)* (0a11)*

74.(1a01)* (a10a)* (a101)*

75.(0a10)* (a111)* (aa10)*

76.(a10a)* (a101)* (a1aa)*

77.(aaa0)* (a010)* (011a)*

78.(a010)* (a1a0)* (a100)*

79.(aa11)* (100a)* (0a10)*

80.(10aa)* (a0a1)* (1a10)*

81.(a10a)* (a1a0)* (01a1)*

82.(a10a)* (a1a0)* (00a1)*

83.(a1a0)* (0a01)* (a101)*

228

84.(1a01)* (a1a0)* (a0a1)*

85.(abac)* (caba)* (baca)*

86.(1010)* (1c01)* (cc10)*

87.(01c0)* (0110)* (c0c0)*

88.(0c01)* (c01c)* (c110)*

89.(1012)* (2100)* (0120)*

90.(1021)* (1210)* (2210)*

91.(1101)* (2010)* (2012)*

92.(2010)* (1021)* (2121)*

93.(caba)* (cabb)* (abac)*

94.(abab)* (abcc)* (ccab)*

95.(caca)* (baba)* (bacc)*

96.(abcc)* (abca)* (cbaa)*

97.(0120)* (0012)* (2100)*

98.(abab)* (cbcc)* (baca)*

99.(baca)* (babc)* (cbba)*

100.(babb)* (aacb)* (ccab)*

229

Домашняя работа №1. По всей теории

Необходимо выполнить по два задания из каждого раздела предписанные вариантом задания. Вариант определяется по последней цифре в зачётной книжке.

Вариант 1: 1.1 1.39 1.19 1.21. 1.40 2.1 .2.5 2.6 .2.8 .2.11 6.1 6.11 Вариант 2: 1.2 1.38 1.19 1.21. 1.40 2.1 .2.5 2.6 .2.8 .2.11 6.2 6.12 Вариант 3: 1.3 1.37 1.19 1.21. 1.40 2.1 .2.5 2.6 .2.8 .2.11 6.3 6.13 Вариант 4: 1.4 1.36 1.19 1.21. 1.40 2.1 .2.5 2.6 .2.8 .2.11 6.4 6.14 Вариант 5: 1.5 1.35 1.19 1.21. 1.40 2.1 .2.5 2.6 .2.8 .2.11 6.5 6.15 Вариант 6: 1.6 1.34 1.19 1.21. 1.40 2.1 .2.5 2.6 .2.8 .2.11 6.6 6.16 Вариант 7: 1.7 1.33 1.19 1.21. 1.40 2.1 .2.5 2.6 .2.8 .2.11 6.7 6.17 Вариант 8: 1.8 1.32 1.19 1.21. 1.40 2.1 .2.5 2.6 .2.8 .2.11 6.8 6.18 Вариант 9: 1.9 1.31 1.19 1.21. 1.40 2.1 .2.5 2.6 .2.8 .2.11 6.9 6.19 Вариант 10: 1.10 1.30 1.19 1.21. 1.40 2.1 .2.5 2.6 .2.8 .2.11 6.10 6.20

230