Второй этап: по ДС пишем программу

 

#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();}

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