Лекции Русакова (1021002), страница 23
Текст из файла (страница 23)
Для рассматриваемого варианта граф имеетследующий вид:8.2. Формулировка задания.Для заданного варианта регулярного выражения написать регулярнуюграмматику.Представить детерминированный конечный автомат, соответствующийрегулярной грамматике.Написатьипроверитьработоспособностьсоответствующегосинтаксического анализатора.Краткие сведения из теорииКонечный автомат — это устройство для распознавания строк какоголибо языка. Конечный автомат — это пятерка М = (К, Σ, δ, S, F),215гдеK — конечное множество состояний;Σ — конечный входной алфавит;δ — множество переходов;S — начальное состояние (S ∈ К);F — множество последних состояний (F ⊆ К).По мере считывания каждой литеры строки автоматом контрольпередается от состояния к состоянию в соответствии с заданным множествомпереходов.Определение.Если после считывания последней литеры строки автомат будетнаходиться в одном из последних состояний, то о строке говорят, что онапринадлежит языку, принимаемому автоматом.
В противном случае строкане принадлежит языку, принимаемому автоматом.Пример.Рассмотрим автомат M0 = (К, Σ, δ, S, F),гдеК ={А, В}, S = {0, 1}, S = {A}, F = {A},δ = {δ (А, 0) = А, δ (А, 1) = В, δ (В, 0) = В, δ (В, 1) = А}.Эти переходы означают, что "при чтении 0 в состоянии А управлениепередается в состояние А и т. д.Причтениистроки0110010111управлениепоследовательнопередается в следующем порядке через состояния А, А, В, А, А, А, В, В, А,В, А.Так как А — есть последнее состояние, строка принимается конечнымавтоматом.Однако, при чтении строки 00111 автомат проходит через состояния А,А, А, В, А, В. В не является последним состоянием ⇒ строка 00111 непринимается, т.е. она не принадлежит языку, принимаемому этим автомат.216В связи с тем, что нули не влияют на состояние автомата, каждаяединица изменяет его состояние с А на В и с В на А, и начальное состояниеявляется тем же, что и последнее состояние.
Язык, принимаемый автоматом,состоит из тех строк, которые содержат четное число единиц.Переходы можно представить также с помощью таблицы исхематически:Определение.Автомат называется детерминированным, если в каждом элементетаблицы переходов содержится одно состояние. В недетерминированном конечном автомате это положение не выдерживается.Следовательно, автомат M 0 — детерминированный.8.04. Последовательность выполнения.Для выполнения лабораторной работы требуется умение писатьпрограммы на алгоритмическом языке, а также начальные знания попорождающим грамматикам.Таким образом, последовательность выполнения лабораторной работыследующая:1. Ознакомится с теорией регулярных грамматик.2.
В соответствии с заданным регулярным выражением написатьрегулярную грамматику.3. Записать соответствующий детерминированный конечный автомат суказанием таблицы переходов.4. Написать и отладить на компьютере синтаксический анализатор,распознающий выражения регулярного языка.2175. Привести контрольную распечатку.6. Оформить отчет.Работа считается выполненной только после оформления отчета,защиты и подписи преподавателя.8.05. Методический пример.Программа "grammatika", представляющая синтаксический анализатор,соответствующий детерминированному конечному автомату М, имеетследующий вид:program grammatika;uses crt;type perehod = recordold, term, new: char;end;var sost:array [1 ..
13] of perehod;stroka: string [255];sim, neterm: string [1];dlina, n, i: integer;ok: boolean;begin { блок определения таблицы переходов }sost[1].old :='S';sost[1].term :='2';sost[1].new := 'A';sost[2].old :='A';sost[2].term :='2';sost[2].new := 'B';sost[3].old :='B';sost[3].term :='1’;sost[3].new := 'C';sost[4].old := 'C';sost[4].term := 'b';sost[4].new := 'S';sost[5].old := 'S';sost[5].term := 'b';sost[5].new := 'D';sost[6].old :='D';sost[6].term :='2';sost[6].new :='E';sost[7].old :='E';sost[7] .term := '1';sost[7].new :='F';sost[8].old := 'F';sost[8].term := 'b';sost[8].new := 'D';sost[9].old := 'F';sost[9].term := '2';sost[9].new := 'K';218sost[10].old:='B';sost[10].term :='2';sost[10].new := 'K';sost[11].old := 'K';sost[11].term := '2';sost[11].new := 'L';sost[12].old := 'L';sost[12].term := '2';sost[12].new := 'M';sost[13].old := 'M'; sost[13].term := '2';sost[13].new := 'L';clrscr;{ блок основной программы }while TRUE do beginwriteln ('Введите строку символов’);readln (stroka);dlina := length (stroka);n:=0;ok :=' TRUE;neterm := 'S';while ok and (n < dlina) dobegin i := 0;n:=n+ 1sim := copy (stroka, n, 1);ok := FALSE;repeat i:=i+l;if ((sost [i].old = neterm) and(sost [i].term = sim)) thenbeginok := TRUE;neterm := sost[i].new;end;until ( ok or (i = 13));end;if ((neterm = 'S') or (neterm = 'B') or (neterm = 'F') or (neterm = 'L') and okthen writeln ('Данная строка принадлежит языку')219else writeln ('Данная строка не принадлежит языку'); readkey; end; end.8.06.
Контрольная распечатка.Введите строку символов 221b2Данная строка не принадлежит языкуВведите строку символов 221b221b221bДанная строка принадлежит языкуВведите строку символов b21Данная строка принадлежит языкуВведите строку символов b21b21Данная строка принадлежит языкуВведите строку символов 22222222Данная строка принадлежит языкуВедите строку символов 221b221bb21b21b212222Данная строка принадлежит языкуВведите строку символов 211bДанная строка не принадлежит языкуВведите строку символовДанная строка принадлежит языку2208.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 segmentassume cs:code, ds:codeorg l00h begin: JMP MAIN;-----------------------------------------------------clf egu OAh, ODhOKMSG db clf, 'O-K TESTED ! $'ERMSG db clf, 07h, 'Invalid simvol !', '$'WMSG db clf, 'Press the ENTER for exit!', '$';————————————————MAIN procS:call GCHR221cmp al, OdhjeOKcmp al,'c'jeTcmp al, 'b'jeVcmp al, '0'jeYjmpNO T:T:call GCHRcmp al, 'c'jeS jmpNOV:call GCHR cmp al, 'a' jeW jmpNOW:call GCHR cmp al, ' 1' jeX jmpNOX:call GCHRcmp al, '0'je Ujmp NOU:call GCHRcmp al, 'b'je Vcmp al, '0'je Ycmp al, Odhje OKjmp NOY:call GCHRcmp al, 'a'je Z222jmp NOZ:call GCHRcmp al,'0'je Ycmp al, Odhje OKNO: lea dx, ERMSGmov ah, 09hInt 21hcall WAIretOK: lea dx, OKMSGmov ah, 09hInt 21hcall WAIretMAIN endp;-----------------------------------------------------GCHR procmov ah, OlhInt21hRetGCHR endp;-------------------------------------------------------------------WAI proclea dx, WMSGmov ah, 09hInt 21hcall GCHR223cmp al, Odhjne WTret WAI endp;-----------------------------------------------------code endsend begin ; IT WORKS !синтаксического анализатора (на любом из реализованных накомпьютерной технике.8.08.
Отчет по практической работе.Отчет оформляется в соответствии с требованиями, предъявляемыми коформлению лабораторных работ в вузе, и должен содержать:1. Титульный лист.2. Наименование и цель работы.3. Исходные данные варианта задания.4. Алгоритм решения задачи (граф, таблица переходов).5. Листинг программы с исходными и выходными данными (листингпрограммы).6. Анализ результатов (контрольная распечатка).7. Выводы.Замечание: листы отчета должны быть скреплены.8.09.
Контрольные вопросы1. Какие грамматики называются регулярными?2. Чемотличаетсядетерминированныйконечныйнедетерминированного?3. Связь регулярных грамматик и конечных автоматов.4. Что такое регулярное выражение?224автоматот5. Алгоритм получения детерминированного конечного автомата изнедетерминированного.6. Какиепрограммныеособенностиотмеченыпринаписаниисинтаксического анализатора.7. Что такое состояние отказа в автомате, соответствующем анализатору?8. Что такое грамматика?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)*22520. (1ab0)* (11ab)* (11a0)*21.
(bba2)* (bb01)* (bb0a)*22. (bb00)* (a12b)* (baab)*23. (1100)* (1000)* (1011)*24. (1abb)* (1aa0)* (1bbb)*25. (2110)* (1210)* (1101)*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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
