Лабораторная работа № 6 Моделирование фу. Лабораторная работа 6 Тема работы Моделирование функционирования распознавателя для ll (1) грамматик
 Скачать 0.58 Mb.
|
|
В лабораторной работе № 6 - построим детерминированный конечный распознаватель для: последовательности действительных чисел в формате с фиксированной точкой (число не может начинаться и заканчиваться десятичной точкой), разделенных запятыми, и заканчивающейся символом #, например, (+65.372,-785.34,457.7#); последовательности действительных чисел в формате с фиксированной точкой (число не может начинаться и заканчиваться десятичной точкой), разделенных точкой с запятой, и заканчивающейся символом #, например, (+65.372;-785.34;457.7#); последовательности действительных чисел в формате с фиксированной точкой (число не может начинаться и заканчиваться десятичной точкой), разделенных слэшами, и заканчивающейся символом #, например, (+65.372/-785.34/457.7#); последовательности действительных чисел в формате с плавающей точкой, разделенных запятой, и заканчивающейся символом #, например, (65.3Е-2,+785.3E4,457.7E+2#); последовательности действительных чисел в формате с плавающей точкой, разделенных точкой с запятой, и заканчивающейся символом #, например, (65.3Е-2;+785.3E4;457.7E+2#); последовательности действительных чисел в формате с плавающей точкой, разделенных слэшами, и заканчивающейся символом #, например, (65.3Е-2/+785.3E4/457.7E+2#); последовательности целых чисел, разделенных запятыми, и заканчивающейся символом #, например, (65,+78534,-4577#); последовательности целых чисел, разделенных точкой с запятой, и заканчивающейся символом #, например, (65;+78534;-4577#); последовательности целых чисел, разделенных слэшами, и заканчивающейся символом #, например, (65/+78534/-4577#); последовательности составных имен объектов, разделенных слэшами, и заканчивающейся символом # , т.е. точечных нотаций идентификаторов, разделенных точками, идентификатор может содержать латинские буквы, цифры и знаки подчеркивания, а начинаться либо с буквы, либо со знака подчеркивания, например, (q.ad.w/e.w1/re.r5.а#); последовательности составных имен объектов, разделенных точкой с запятой, и заканчивающейся символом # , т.е. точечных нотаций идентификаторов, разделенных точками, идентификатор может содержать латинские буквы, цифры и знаки подчеркивания, а начинаться либо с буквы, либо со знака подчеркивания, например, (q.ad.w;e.w1;re.r5.а#); последовательности составных имен объектов, разделенных запятыми, и заканчивающейся символом # – т.е. точечных нотаций идентификаторов, разделенных точками, идентификатор может содержать латинские буквы, цифры и знаки подчеркивания, а начинаться либо с буквы, либо со знака подчеркивания, например, (q.ad.w,e.w1,re.а,r5#); полной и сокращенной спецификации файла, например (a:\w1\data.pas) либо (ааа.dat); последовательностей путей поиска файлов, разделенных запятой, и заканчивающихся точкой с запятой, например (a:\data,c:\work;) последовательности элементов типа «дата» в немецком формате (ДД.ММ.ГГГГ), разделенных запятыми, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться четырьмя символами, например, ({01.12.2001},{05.07.2003}); последовательности элементов типа «дата» в немецком формате (ДД.ММ.ГГГГ), разделенных точкой с запятой, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться четырьмя символами, например, ({01.12.2001};{05.07.2003}); последовательности элементов типа «дата» в немецком формате (ДД.ММ.ГГ), разделенных запятыми, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться двумя символами, например, ({01.12.01},{05.07.03}); последовательности элементов типа «дата» в немецком формате (ДД.ММ.ГГ),, разделенных запятыми, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться двумя символами, например, ({01.12.01},{05.07.03}); последовательности элементов типа «дата» в американском формате (ММ/ДД/ГГГГ), разделенных запятыми, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться четырьмя символами, например, ({01/12/2001},{05/07/2003}); последовательности элементов типа «дата» в американском формате (ММ/ДД/ГГГГ), разделенных точкой с запятой, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться четырьмя символами, например, ({01/12/2001};{05/07/2003}); последовательности элементов типа «дата» в американском формате (ММ/ДД/ГГ), разделенных запятыми, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться двумя символами, например, ({01/12/01},{05/07/03}); последовательности элементов типа «дата» в американском формате (ММ/ДД/ГГ), разделенных точкой с запятой, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться двумя символами, например, ({01/12/01};{05/07/03}). Построим детерминированный конечный распознаватель для последовательности элементов типа «дата» в формате, удобном для сортировки (ГГГГ/ММ/ДД), разделенных точкой с запятой, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться четырьмя символами, последовательность должна завершаться знаком «#», например, ({2001/12/01};{2005/07/03}#). Выполнение лабораторной работы № 6 распадается на следующие этапы: Составление формальной грамматики, описывающей язык, содержащий приведенную фразу; Построение конечного автомата по созданной грамматике; Составление блок-схемы и программы, моделирующей работу конечного автомата. Составление формальной грамматики. Фраза языка представляет собой список, поэтому из начального символа грамматики должен выводится список: R0: <предложение>::==<фраза># R1: <фраза>::==<фраза>;<дата> | <дата> Дата представляет собой линейную структуру: R2: <дата>::=={<год>/<месяц>} Аналогично год, месяц и день: R3: <год>::==<цифра><цифра><цифра><цифра> R4: <месяц>::==<месяцб>/<деньб>|<месяцм>/<деньм>|<февраль>/<деньф> R5: <месяцб>::=01|03|05|07|08|10|12 R6: <месяцм>::=04|06|09|11 R7: <февраль>::=02 R8: <деньб>::==<цифра2><цифра>| 3<цифра1> R9: <деньм>::==<цифра2><цифра>| 30 R10: <деньф>::==<цифра1><цифра>| 2<цифра3> R11: <цифра>::==0|1|2|3|4|5|6|7|8|9| R12: <цифра1>::==0|1 R13: <цифра2>::==0|1|2 R14: <цифра3>::==0|1|2|3|4|5|6|7|8 Таким образом, требуемую грамматику можно описать следующей структурой: Множество терминальных символов: {,},/,0,1,2,3,4,5,6,7,8,9. Множество нетерминальных символов: <фраза>, <дата>, <год>, <месяц>, <день>, <цифра>, <цифра1>, <цифра2>. Множество правил вывода R0,R1, R2, R3, R4, R5, R6, R7, R8, R9, R10, R11, R12, R13, R14. конечный автомат число программа Построение конечного автомата. Между конечными автоматами и автоматными грамматиками существует тесная связь: класс языков, допускаемых конечными автоматами, совпадает с классом языков, порождаемых автоматными грамматиками. Для построения конечного автомата составленную грамматику путем введения дополнительных состояний надо преобразовать к автоматному виду, в результате получится следующая таблица переходов.
Программное моделирование работы конечного автомата. #include "stdafx.h" #include "iostream.h" #include "stdio.h" #include "conio.h" int main() { int i,j,kol,tsost,slsost,tsymb; int tabl[23][15]={{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},//da {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},//net {1,1,1,1,1,1,1,1,1,1,3,1,1,1,1},//data {4,4,4,4,4,4,4,4,4,4,1,1,1,1,1},//god {5,5,5,5,5,5,5,5,5,5,1,1,1,1,1},//cg1 {6,6,6,6,6,6,6,6,6,6,1,1,1,1,1},//cg2 {7,7,7,7,7,7,7,7,7,7,1,1,1,1,1},//cg3 {1,1,1,1,1,1,1,1,1,1,1,1,8,1,1},//cg4 {9,10,1,1,1,1,1,1,1,1,1,1,1,1,1},//mes {1,11,13,11,12,11,12,11,12,11,1,1,1,1,1},//mes0 {11,12,11,1,1,1,1,1,1,1,1,1,1,1,1},//mes1 {1,1,1,1,1,1,1,1,1,1,1,1,14,1,1},//mesb {1,1,1,1,1,1,1,1,1,1,1,1,18,1,1},//mesm {1,1,1,1,1,1,1,1,1,1,1,1,21,1,1},//feb {15,15,15,17,1,1,1,1,1,1,1,1,1,1,1},//denb {16,16,16,16,16,16,16,16,16,16,1,1,1,1,1},//db1 {1,1,1,1,1,1,1,1,1,1,1,20,1,1,1},//db2 {16,16,1,1,1,1,1,1,1,1,1,1,1,1,1},//cf1 {15,15,15,19,1,1,1,1,1,1,1,1,1,1,1},//denm {16,1,1,1,1,1,1,1,1,1,1,1,1,1,1},//cf0 {1,1,1,1,1,1,1,1,1,1,1,1,1,2,0},//razd {15,15,22,1,1,1,1,1,1,1,1,1,1,1,1},//denf {16,16,16,16,16,16,16,16,1,1,1,1,1,1,1}//cf3 }; printf("matrica\n"); for (i=0;i<23;i++) {for (j=0;j<15;j++) printf("%4d",tabl[i][j]); printf("\n");}; char ch, inpstr[80] ; printf("\n ENTER STRING "); i=0; while ((ch=getch()) !=13 && i<80) {putch(ch); inpstr[i++]=ch;} inpstr[i]='\0'; kol=i-1; printf("\n input string:"); printf(inpstr); printf("\n"); tsost=2; for (i=0;i<=kol;i=i+1) { tsymb=inpstr[i]; switch (tsymb) { case '0': slsost=tabl[tsost][0]; break; case '1': slsost=tabl[tsost][1]; break; case '2': slsost=tabl[tsost][2]; break; case '3': slsost=tabl[tsost][3]; break; case '4': slsost=tabl[tsost][4]; break; case '5': slsost=tabl[tsost][5]; break; case '6': slsost=tabl[tsost][6]; break; case '7': slsost=tabl[tsost][7]; break; case '8': slsost=tabl[tsost][8]; break; case '9': slsost=tabl[tsost][9]; break; case '{': slsost=tabl[tsost][10]; break; case '}': slsost=tabl[tsost][11]; break; case '/': slsost=tabl[tsost][12]; break; case ';': slsost=tabl[tsost][13]; break; case '#': slsost=tabl[tsost][14]; break; default: slsost=1;} printf("%5d\n",slsost); tsost=slsost; }; switch (slsost) { case 1:cout<<"\n STRING is WRONG \n"; break; case 0:cout<<"\n STRING is RIGHT \n";break;} return 0; }; Реализация конечного автомата лабораторной работы № 6 средствами ООП: // заголовочный файл konavt.h описание класса конечного автомата class konavt {int kolsost;// число состояний автомата int kolsimv;// число символов входного алфавита char *alfavit; // входной алфавит int nachstate; //начальное состояние int kolkon;//число заключительных состояний int *fin; //заключительные состояния int **per;//матрица переходов int dlina;// текущая длина входной цепочки int dlina0;// начальная длина входной цепочки char *vxod;// входная цепочка int avtstate; //текущее состояние int nomstep;// номер шага автомата int *protokol;// протокол работы автомата public:bool error; //признак ошибки konavt();//конструктор без параметров void show_sost();//проверка заполнения матрицы void sled();//срабатывание переходов void show();//показ текущего состояния; void init();//инициализация новой строкой bool konec();// проверка финальности состояния bool zaversh(); //проверка исчерпания строки bool proverka();// проверка принадлежности символов алфавиту }; //Файл реализации класса автомата konavt.cpp # include "konavt.h" # include # include # include # include //конструктор konavt::konavt() {int i,j,vyb; // возможен ввод исходных данных как из файла, так и с клавиатуры cout<<"constructor working..."< cout <<"Istochnik dannyx(0-klaviatura,1-file)"< cin>>vyb; // ввод с клавиатуры if (vyb==0) {cout<<"\n Enter kolvo sostoianiy\t"; cin>>kolsost; cout< cin>>kolsimv; alfavit=new char [kolsimv]; per=new int*[kolsost]; for (i=0;i per[i]=new int [kolsimv]; }; cout< for (j=0;j cin>>alfavit[j]; }; cout< for (i=0;i for (j=0;j cin>>per[i][j]; }; cout< }; cout<<"enter nachalnoe sostoianie"< cin>>nachstate; cout< cout<<"enter kolvo konechnyh sostoianiy"< cin>>kolkon; cout< fin=new int[kolkon]; cout<<"enter konechnye sostoiania"< for (i=0;i cin>>fin[i]; } cout< // запись исходных данных в файл int otv; cout<<"save to file?(1-yes,0-no)"; cin>>otv; cout< if (otv==1) {char fname[30]; cout<<"enter filename "; cin>>fname; cout< ofstream out_stream; out_stream.open(fname); if (out_stream.fail()) {cout<<"Error output file"< out_stream< out_stream< for (i=0;i for (i=0;i for (j=0;j out_stream< out_stream< out_stream< for (i=0;i out_stream.close(); cout<<"End of output file..."< }; } else // ввод исходных данных из файла { char filename[30]; cout<<"Enter Filename "; cin>>filename; cout< ifstream in_stream; in_stream.open(filename); if (in_stream.fail()) {cout<<"net faila "< }; in_stream>>kolsost; cout<<"kolsost="< in_stream>>kolsimv; cout<<"kolsimv="< alfavit=new char[kolsimv]; for (i=0;i for (i=0;i cout< per=new int*[kolsost]; for (i=0;i for (i=0;i for (j=0;j in_stream>>per[i][j];}} for (i=0;i for (j=0;j cout< in_stream>>nachstate; cout<<"begin state "< in_stream>>kolkon; cout<<"Number of end states "< fin=new int[kolkon]; for (i=0;i for (i=0;i cout< in_stream.close(); cout<<"End of output file..."< } return;}; //показ текущего состояния void konavt::show_sost() {int i; cout<<"sostoyanie "< cout< //cout<<"ostatok vxoda "< cout<<"ostatok vxoda "; //for (i=0; i //cout< for (i=0; i cout< for (i=0;i cout< }; //переход к следующему состоянию void konavt::sled() {int slsost,i,num; num=-1; char teksimv; teksimv=vxod[0]; cout<<"symbol "< for (i=0;i if (num==-1){cout<<"illegal symbol "< else {slsost=per[avtstate][num]; avtstate=slsost; protokol[nomstep]=slsost; nomstep++; for (i=0;i vxod[dlina-1]=' '; dlina=dlina-1; }; return;}; //проверка допустимости входной строки bool konavt::proverka() {int i,j; bool prizn; for (i=0;i {prizn=false; for (j=0;j if (!prizn) {cout<<"illegal symbol "< }; return prizn; }; //ввод новой входной строки void konavt::init() {int i; cout<<"enter dlina"< cin>>dlina; dlina0=dlina; vxod=new char[dlina+1]; protokol=new int [dlina+1]; for (i=0;i cout< for (i=0;i //vxod[dlina]='\0'; cout< //cout<<"ostatok vxoda "< cout<<"ostatok vxoda "; for (i=0; i cout< if (proverka()) {avtstate=nachstate; protokol[0]=nachstate; nomstep=1; error=false;} else error=true; return;}; //показ параметров автомата void konavt::show() {int i,j; cout<<"parametry avtomata"< cout<<"kolvo sostoianiy "< cout<<"kolvo simvolov alfavita "< cout<<"simvoly alfavita"< for (j=0;j cout< }; cout< for (i=0;i for (j=0;j cout< }; cout< }; cout<<"nachalnoe sostoianie "< cout<<"konechnye sostoiania "< for (i=0;i cout< };cout< return;}; //проверка завершающего состояния bool konavt::konec() {int i; bool kon; kon=false; i=-1; for (i=0;i return kon; }; //проверка исчерпания входной строки bool konavt::zaversh() {bool prizn; if(dlina==0) prizn=true; else prizn=false; return prizn; }; // головная программа # include "konavt.h" # include int main() { konavt tavt; tavt.show(); int povt; povt=1; while (povt==1) {tavt.init(); tavt.show_sost(); if (!tavt.error) {do { tavt.sled(); tavt.show_sost(); } while (!((tavt.error)&&(tavt.zaversh()))); if ((tavt.zaversh()) && (tavt.konec())) cout<<"\n !!!stroka prinimaetsa"< cout<<"\n !!!stroka ne prinimaetsa"< cout<<"repeat?(1,0)\n"; cin>>povt; cout< }; return 0; } СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ: 1. Алексеева И.В. Сборник задач и упражнений по курсу «Информатика». - Обнинск: Обнинский институт атомной энергетики, 2014. 2. Власов В.К., Королев Л.Н. Элементы информатики./ Под. Ред. Л.Н. Королева.- М.: Наука, 2016 г. 3. Информатика.- / Под ред. Н.В. Макаровой. - М.: Финансы и статистика, 2016. - 768 с. 4. Информатика: Учебник для вузов.- / Под ред. С.В. Симоновича. - СПб.: Питер, 2016. 5. Кураков Л.П., Лебедев Е.К. Информатика. - М.: Вуз и школа, 2019. - 636с. 6. Могилев и др. Информатика: Учебное пособие для вузов / А.В.Могилев, Н.И.Пак, Е.К.Хеннер; Под ред. Е.К. Хеннера. - М.: Изд. центр "Академия", 2008 7. Острейковский В.А. Информатика. - м.: Высшая школа, 2007.- 512с. 8. Першиков В.И., Савинков В.М. Толковый словарь по информатике. - 2-е изд. Доп. - М.: Финансы и статистика, 2008. 9. Фигурнов В.Э. IBM PC для пользователей. - М.: 2007. 10. Якубайтис Э.А. Информационные сети и системы: Справочная книга.- М.: Финансы и статистика, 2008 11. Бубнов А.Е. Компьютерный дизайн. Основы, Мн: Знание, 2008 г. 12. Кричалов А.А. Компьютерный дизайн. Учебное пособие, Мн.: СТУ МГМУ, 2008 г. 13. Стоянов П.Г. Работа с цветом и графикой, Мн.: БГУИР, 20 14. Лавров С.М. Excel: сб. примеров и задачи М.: Финансы и статистика, 2003.- 332с. 16. Макарева Н.В. и др. Информатика: учебник- 3-е изд М.: Финансы и статистика, 2003.- 758с. 2022.- 3 ст. изд 17. Информатика Базовый курс Учебное пособие для студентов вузов СПб.: Питер, 2003.- 638с. СПб.: Питер, 2021 18. Информатика Уч пособие Ч.2 У-Удэ, 2021.- 59с./ Габеева Д.А., Дамбаева Г-Х.Б и др. 19. Самоучитель Ms Windows 98 М.: Новый диск, 2021 20. Симонович С.В. Общая информатика: Учеб пособие М., 2016.- 591с. 21. Симонович С.В. Специальная информатика Уч пособие М., 2016.- 479с. 22. Симонович С.В. Windows: лаборатория мастера Работа с компьютером без проблем М., 2016.- 655с. |