Второй этап: по ДС пишем программу
#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. Построить лексический блок (преобразователь) для кода Морзе. Входом служит последовательность "точек", "тире" и "пауз" (например, ..--. .- ...- ^). Выходом являются соответствующие буквы, цифры и знаки пунктуации. Особое внимание обратить на организацию таблицы.