Категории: ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника |
Второй этап: по ДС пишем программу
#include <stdio.h> #include <ctype.h> #define BUFSIZE 80 extern ptabl TW, TID, TD, TNUM; char buf[BUFSIZE]; /* для накопления символов лексемы */ int c; /* очередной символ */ int d; /* для формирования числового значения константы */ enum state {H, ID, NUM, COM, ASS, DLM, ER, FIN}; enum state TC; /* текущее состояние */ FILE* fp;
void clear(void); /* очистка буфера buf */ void add(void); /* добавление символа с в конец буфера buf*/ int look(ptabl); /* поиск в таблице лексемы из buf; результат: номер строки таблицы либо 0 */ int putl(ptabl); /* запись в таблицу лексемы из buf, если ее там не было; результат: номер строки таблицы */ int putnum(); /* запись в TNUM константы из d, если ее там не было; результат: номер строки таблицы TNUM */ int j; /* номер строки в таблице, где находится лексема, найденная функцией look */ void makelex(int,int); /* формирование и вывод внутреннего представления лексемы */ void id_or_word(void) { if (j=look(TW)) makelex(1,j); else { j=putl(TID); makelex(4,j);} } void is_dlm(void) {if(j=look(TD)) {makelex(2,j); gc(); ТС=H;} TC=ER;} void gc(void) { c = fgetc(fp);}
void scan (void) {TC = H; fp = fopen("prog","r"); /* в файле "prog" находится текст исходной программы */ gc(); do {switch (TC) { case H: if (c == ' ') gc(); else if (isalpha(c)) {clear(); add();gc(); TC = ID;} else if (isdigit (c)) {d = c - '0'; gc(); TC = NUM;} else if (c=='{') { gc(); TC = COM;} else if (c == ':') { gc(); TC = ASS;} else if (c == '^') {makelex(2, N^); TC = FIN;} else TC = DLM; break; case ID: if (isalpha(c) || isdigit(c)) {add(); gc();} else {id_or_word(); TC = H;} break; case NUM: if (isdigit(c)) {d=d*10+(c - '0'); gc();} else {makelex (3, putnum()); TC = H;} break; /* ........... */ } /* конец switch */ } /* конец тела цикла */ while (TC != FIN && TC != ER); if (TC == ER) printf("ERROR !!!\n"); else printf("O.K.!!!\n"); }
Задачи.
33. Дана регулярная грамматика с правилами:
S ® S0 | S1 | P0 | P1 P ® N. N ® 0 | 1 | N0 | N1 .
Построить по ней диаграмму состояний и использовать ДС для разбора цепочек : 11.010 , 0.1 , 01. , 100 . Какой язык порождает эта грамматика ?
34. Дана ДС. a) Осуществить разбор цепочек 1011^ , 10+011^ и 0-101+1^ . b) Восстановить регулярную грамматику, по которой была построена данная ДС. c) Какой язык порождает полученная грамматика ?
35. Пусть имеется переменная cи функция gc(), считывающая в с очередной символ анализируемой цепочки. Дана ДС с действиями:
a) Определить, что будет выдано на печать при разборе цепочки 1+101//p11+++1000/5^? b) Написать на Си анализатор по этой ДС.
36. Построить регулярную грамматику, порождающую язык L = {(abb)k^| k >= 1}, по ней построить ДС, а затем по ДС написать на Си анализатор для этого языка.
37. Построить ДС, по которой в заданном тексте, оканчивающемся на ^, выявляются все парные комбинации <>, <= и >= и подсчитывается их общее количество.
38. Дана регулярная грамматика: S ® A^ A ® Ab | Bb | b B ® Aa Определить язык, который она порождает; построить ДС; написать на Си анализатор.
39. Написать на Си анализатор, выделяющий из текста вещественные числа без знака (они определены как в Паскале) и преобразующий их из символьного представления в числовое.
*40. Даны две грамматики G1 и G2. G1: S ® 0C | 1B G2: S ® 0D | 1B B ® 0B | 1C | e B ® 0C | 1C C ® 0C | 1C C ® 0D | 1D | e D ® 0D | 1D L1 = L(G1); L2 = L(G2). Построить регулярную грамматику для: a) L1ÈL2 b) L1ÇL2 c) L1* \ {e} d) L2* \ {e} e) L1*L2 Если разбор по ней оказался недетерминированным, найти эквивалентную ей грамматику, допускающую детерминированный разбор.
41. Написать леволинейную регулярную грамматику, эквивалентную данной праволинейной, допускающую детерминированный разбор.
a) S ® 0S | 0B b) S ® aA | aB | bA B ® 1B | 1C A ® bS C ® 1C | ^ B ® aS | bB | ^
c) S ® aB d) S ® 0B B ® aC | aD | dB B ® 1C | 1S C ® aB C ® ^ D ® ^
42. Для данной грамматики a) определить ее тип; b) какой язык она порождает; c) написать Р-грамматику, почти эквивалентную данной; d) построить ДС и анализатор на Си. S ® 0S | S0 | D D ® DD | 1A | e A ® 0B | e B ® 0A | 0
43. Преобразовать грамматику к виду, допускающему детерминированный разбор (использовать алгоритм преобразования НКА к детерминированному КА). Какой язык порождает грамматика? Написать анализатор. a) S ® C^ b) S ® C^ B ® B1 | 0 | D0 C ® B1 C ® B1 | C1 B ® 0 | D0 D ® D0 | 0 D ® B1
c) S ® A0 *d) S ® B0 | 0 A ® A0 | S1 | 0 B ® B0 | C1 | 0 | 1 C ® B0
*e) S ® A0 | A1 | B1 | 0 | 1 *f) S ® S0 | A1 | 0 | 1 A ® A1 | B1 | 1 A ® A1 | B0 | 0 | 1 B ®A0 B ® A0
*g) S ® Sb | Aa | a | b A ® Aa | Sb | a
44. Грамматика G определяет язык L=L1ÈL2, причем L1 ÇL2 =Æ. Написать регулярную грамматику G1, которая порождает язык L1*L2 (см. задачу 20). Для нее построить ДС и анализатор. S ® A^ A ® A0 | A1 | B1 B ® B0 | C0 | 0 C ® C1 | 1
*45. Даны две грамматики G1 и G2, порождающие языки L1 и L2. Построить регулярные грамматики для a) L1 È L2 b) L1 Ç L2 c) L1 * L2 (см. задачу 20)
G1: S ® S1 | A0 G2: S ® A1 | B0 | E1 A ® A1 | 0 A ® S1 B ® C1 | D1 C ® 0 D ® B1 E ® E0 | 1
Для полученной грамматики построить ДС и анализатор.
46. По данной грамматике G1 построить регулярную грамматику G2 для языка L1*L1 (см. задачу 20), где L1 = L(G1); по грамматике G2 - ДС и анализатор. G1: S ® S1 | A1 A ® A0 | 0
47. Написать регулярную грамматику, порождающую язык:
a) L = {w^ | w Î {0,1}* , где за каждой 1 непосредственно следует 0}; b) L = {1w1^ | w Î {0,1}+ , где все подряд идущие 0 – подцепочки нечетной длины}; по грамматике построить ДС, а по ДС написать на Си анализатор.
48. Построить лексический блок (преобразователь) для кода Морзе. Входом служит последовательность "точек", "тире" и "пауз" (например, ..--. .- ...- ^). Выходом являются соответствующие буквы, цифры и знаки пунктуации. Особое внимание обратить на организацию таблицы.
|
|
Последнее изменение этой страницы: 2016-08-11 lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда... |