Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Второй этап: по ДС пишем программу
#include <stdio.h> #include <ctype.h> #define BUFSIZE 80 extern ptabl TW, TID, TD, TNUM; char buf[BUFSIZE]; /* для накопления символов лексемы */ int c; /* очередной символ */ int d; /* для формирования числового значения константы */ 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();} else error();} Замечание: символом Nx в диаграмме (и в тексте программы) обозначен номер лексемы x в ее классе.
void scan (void) {enum state {H, ID, NUM, COM, ASS, DLM, ER, FIN}; state TC; /* текущее состояние */ FILE* fp; TC = H; fp = fopen("prog","r"); /* в файле "prog" находится текст исходной программы */ c = fgetc(fp); do {switch (TC) { case H: if (c == ' ') c = fgetc(fp); else if (isalpha(c)) {clear(); add(); c = fgetc(fp); TC = ID;} else if (isdigit (c)) {d = c - '0'; c = fgetc(fp); TC = NUM;} else if (c=='{') {c=fgetc(fp); TC = COM;} else if (c == ':') {c = fgetc(fp); TC = ASS;} else if (c == '^') {makelex(2, N^); TC = FIN;} else TC = DLM; break; case ID: if (isalpha(c) || isdigit(c)) {add(); c=fgetc(fp);} else {if (j = look (TW)) makelex (1,j); else {j = putl (TID); makelex (4,j);}; TC = H;}; break; case NUM: if (isdigit(c)) {d=d*10+(c - '0'); c=fgetc (fp);} 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-12-30; просмотров: 346; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.224.68.131 (0.018 с.) |