Составление формальной грамматики

1 Составление формальной грамматики

 

Фраза языка представляет собой список, поэтому из начального символа грамматики должен выводится список:

R0: <предложение>::==<фраза>

R1: <фраза>::==<дата> | <дата>,<фраза>

Дата представляет собой линейную структуру:

R2: <дата>::=={<месяц>.<год>}

Аналогично год, месяц и день:

R3: <год>::==<цифра><цифра><цифра><цифра>

R4: <месяц>: :== <месяцб>. <деньб> |<месяцм>. <деньм>| <февраль> <деньф>

R5: <месяцб>::=01|03|05|07|08|10|12

R6: <месяцм>::=04|06|09|11

R7: <февраль>::=02

R8: <деньб>::==<цифра2><цифра>| 3<цифра1>

R9: <деньм>::==<цифра2><цифра>| 30

R10: <деньф>::==<цифра1><цифра>| 2<цифра3>

R11: <цифра>::==0|1|2|3|4|5|6|7|8|9|

R12: <цифра1>::==0|1

R13: <цифра2>::==0|1|2

R14: <цифра3>::==0|1|2|3|4|5|6|7|8

Таким образом, требуемую грамматику можно описать следующей структурой:

·          Множество терминальных символов: {, }, ., , ,0,1,2,3,4,5,6,7,8,9.

·          Множество нетерминальных символов: <фраза>, <дата>, <год>, <месяц>, <день>, <цифра>, <цифра1>, <цифра2>.

·          Множество правил вывода R0,R1, R2, R3, R4, R5, R6, R7, R8, R9, R10, R11, R12, R13, R14.

2 Построение конечного автомата

 

Между конечными автоматами и автоматными грамматиками существует тесная связь: класс языков, допускаемых конечными автоматами, совпадает с классом языков, порождаемых автоматными грамматиками.

Для построения конечного автомата составленную грамматику путем введения дополнительных состояний надо преобразовать к автоматному виду, в результате получится следующая таблица переходов:

0

1

2

3

4

5

6

7

8

9

{

}

.

,

да

нет

день

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

денф

нет

денб

Дб1

Дб1

Дб1

Цф1

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

Дб1

Дб2

Дб2

Дб2

Дб2

Дб2

Дб2

Дб2

Дб2

Дб2

Дб2

нет

нет

нет

нет

Дб2

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

мес

нет

Цф1

Дб2

Дб2

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

денм

Дб1

Дб1

Дб1

Цф0

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

Цф0

Дб2

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

денф

Дб1

Дб1

Цф3

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

Цф3

Дб2

Дб2

Дб2

Дб2

Дб2

Дб2

Дб2

Дб2

нет

нет

нет

нет

нет

нет

мес

Мес0

Мес1

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

Мес0

нет

месб

фев

месб

месм

месб

месм

месб

месб

месм

нет

нет

нет

нет

Мес1

месб

месм

месб

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

месб

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

денб

нет

месм

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

денм

нет

дата

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

год

нет

нет

нет

год

Цг1

Цг1

Цг1

Цг1

Цг1

Цг1

Цг1

Цг1

Цг1

Цг1

нет

нет

нет

нет

Цг1

Цг2

Цг2

Цг2

Цг2

Цг2

Цг2

Цг2

Цг2

Цг2

Цг2

нет

нет

нет

нет

Цг2

Цг3

Цг3

Цг3

Цг3

Цг3

Цг3

Цг3

Цг3

Цг3

Цг3

нет

нет

нет

нет

Цг3

Цг4

Цг4

Цг4

Цг4

Цг4

Цг4

Цг4

Цг4

Цг4

Цг4

нет

нет

нет

нет

Цг4

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

да

нет

день

3 Граф детерминированного автомата

 

Для того, чтобы улучшить зрительное восприятие и облегчить понимание сложных синтаксических описаний, часто применяют представление правил грамматики в виде синтаксических диаграмм.

Синтаксическая диаграмма представляет собой ориентированный граф для каждого правила грамматики.

4 Программное моделирование работы конечного автомата

#include "iostream.h"

#include "stdio.h"

#include "conio.h"

int main()

{int i,j,kol,tsost,slsost,tsymb;

int tabl[24][14]={{0,0,0,0,0,0,0,0,0,0,0,0,0,0},//da

{1,1,1,1,1,1,1,1,1,1,1,1,1,1},//net

{1,1,1,1,1,1,1,1,1,1,3,1,1,1},

{4,4,4,5,1,1,1,1,1,1,1,1,1,1},

{1,6,6,6,6,6,6,6,6,6,1,1,1,1},

{8,9,1,1,1,1,1,1,1,1,1,1,1,1},

{1,1,1,1,1,1,1,1,1,1,1,1,20,1},

{16,16,16,16,16,16,16,16,16,16,1,1,1,1},

{1,1,1,1,1,1,1,1,1,1,1,1,10,1},

{1,1,1,1,1,1,1,1,1,1,1,1,11,1},

{12,13,1,1,1,1,1,1,1,1,1,1,1,1},

{14,15,1,1,1,1,1,1,1,1,1,1,1,1},

{1,1,1,1,23,1,23,1,1,23,1,1,1,1},

{23,1,1,1,1,1,1,1,1,1,1,1,1,1},

{1,23,1,23,1,23,1,23,23,1,1,1,1,1},

{23,1,23,1,1,1,1,1,1,1,1,1,1,1},

{17,17,17,17,17,17,17,17,17,17,1,1,1,1},

{18,18,18,18,18,18,18,18,18,18,1,1,1,1},

{19,19,19,19,19,19,19,19,19,19,1,1,1,1},

{1,1,1,1,1,1,1,1,1,1,1,0,1,2},

{21,22,1,1,1,1,1,1,1,1,1,1,1,1},

{1,23,23,23,23,23,23,23,23,23,1,1,1,1},

{23,23,23,1,1,1,1,1,1,1,1,1,1,1},

{1,1,1,1,1,1,1,1,1,1,1,1,7,1},

};

printf("matrica\n");

for (i=0;i<24;i++) {for (j=0;j<14;j++) printf("%4d",tabl[i][j]); printf("\n");};

char ch, inpstr[80] ;

printf("\n ENTER STRING ");

i=0;

 while ((ch=getch()) !=13 && i<80)

{putch(ch);

inpstr[i++]=ch;}

 inpstr[i]='\0';

 kol=i-1;

 printf("\n input string:");

 printf(inpstr);

 printf("\n");

tsost=2;

for (i=0;i<=kol;i=i+1)

{ tsymb=inpstr[i];

switch (tsymb)

{ case '0': slsost=tabl[tsost][0]; break;

case '1': slsost=tabl[tsost][1]; break;

case '2': slsost=tabl[tsost][2]; break;

case '3': slsost=tabl[tsost][3]; break;

case '4': slsost=tabl[tsost][4]; break;

case '5': slsost=tabl[tsost][5]; break;

case '6': slsost=tabl[tsost][6]; break;

case '7': slsost=tabl[tsost][7]; break;

case '8': slsost=tabl[tsost][8]; break;

case '9': slsost=tabl[tsost][9]; break;

case '{': slsost=tabl[tsost][10]; break;

case '}': slsost=tabl[tsost][11]; break;

case '.': slsost=tabl[tsost][12]; break;

case ',': slsost=tabl[tsost][13]; break;

default: slsost=1;}

printf("%5d\n",slsost);

tsost=slsost;

};

switch (slsost)

{ case 1:cout<<"\n STRING is WRONG \n"; break;

 case 0:cout<<"\n STRING is RIGHT \n";break;}

return 0;

};

5 Блок-схема

6 Примеры

Правильные строки:

 

Неправильные строки: