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

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

#include <stdio.h>

#include <ctype.h>

#define BUFSIZE 80

typedef struct tabl * ptabl;

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 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!!!");

else printf("O.K.!!!");

}

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 | e 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

Если разбор по ней оказался недетерминированным, найти эквивалентную ей грамматику, допускающую детерминированный разбор.

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

A ® A0 | S1 | 0

44. Грамматика G определяет язык L=L1ÈL2, причем L1 ÇL2 =Æ. Написать регулярную грамматику G1, которая порождает язык L1*L2 (см. задачу 20). Для нее построить ДС и анализатор.

S ® 0A | 1S

A ® 0A | 1B

B ® 0B | 1B | ^

45. Даны две грамматики G1 и G2, порождающие языки L1 и L2. Построить регулярные грамматики для

a) L1 È L2

b) L1 Ç L2

c) L1 * L2 (см. задачу 20)

G1: S ® 0B | 1S G2: S ® B^

B ® 0C | 1B | e A ® B1 | 0

C ® 0B | 1S B ® A1 | C1 | B0 | 1

C ® A0 | B1

Для грамматики b) построить ДС и анализатор.

46 По данной грамматике G1 построить регулярную грамматику G2 для языка L1* L1 (см. задачу 20), где L1 = L(G1); по грамматике G2 - ДС и анализатор.

G1: S ® 0S | 0B

B ® 1B | 1C

C ® 1C | e

47. Написать регулярную грамматику, порождающую язык:

a) L = {w^ | w Î {0,1}^*, где за каждой 1 непосредственно следует 0};

b) L = {1w1^ | w Î {0,1}⁺, где между вхождениями 1 нечетное количество 0};

по ней построить ДС, а по ДС написать на Си анализатор.

48. Построить лексический блок (преобразователь) для кода Морзе. Входом служит последовательность "точек", "тире" и "пауз" (например,..--..-...- ^). Выходом являются соответствующие буквы, цифры и знаки пунктуации. Особое внимание обратить на организацию таблицы.

Дата добавления: 2015-06-27