Форум программистов, компьютерный форум CyberForum.ru

Построить детерминированный конечный распознаватель - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.67
Iliabobr
3 / 3 / 1
Регистрация: 04.11.2009
Сообщений: 98
14.06.2011, 21:46     Построить детерминированный конечный распознаватель #1
Всем привет)
у меня проблема, завтра надо курсач сдавать, у меня есть готовая лаба другого варианта, как переделать не знаю, помогите плиз))
Вот мое задание: Построить детерминированный конечный распознаватель для последовательности действительных чисел в формате с фиксированной точкой (число не может начинаться и заканчиваться десятичной точкой), разделенных запятыми, и заканчивающейся символом #, например, (+65.372,-785.34,457.7#);

Вот лаба др. варианта cpp формат
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# include "konavt.h"
# include <iostream.h>
int main()
{
    konavt tavt;
    tavt.show();
    int povt;
    povt=1;
    while (povt==1) 
    {   tavt.init();
        tavt.show_sost();
        if (!tavt.error)
        {do
        { tavt.sled();
          tavt.show_sost();
        } while (!((tavt.error)&&(tavt.zaversh())));
if ((tavt.zaversh()) && (tavt.konec())) 
cout<<"\n !!!stroka prinimaetsa"<<endl;else
        cout<<"\n !!!stroka ne prinimaetsa"<<endl;}
        cout<<"repeat?(1,0)\n";
        cin>>povt;
        cout<<endl;
    };
    system("pause");
}
а вот .h
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
# include <iostream.h>
# include <fstream.h>
# include <string.h>
# include <stdlib.h>
 
class konavt {int kolsost;// число состояний автомата
                int kolsimv;// число символов входного алфавита
                char *alfavit; // входной алфавит
                int nachstate; //начальное состояние
                int kolkon;//число заключительных состояний         
                int *fin; //заключительные состояния
                int **per;//матрица переходов
                int dlina;// текущая длина входной цепочки
                int dlina0;// начальная длина входной цепочки
                char *vxod;// входная цепочка
                int avtstate; //текущее состояние
                int nomstep;// номер шага автомата
                int *protokol;// протокол работы автомата
public:         
                bool error; //признак ошибки
                konavt();//конструктор без параметров
                void show_sost();//проверка заполнения матрицы
                void sled();//срабатывание переходов
                void show();//показ текущего состояния;
                void init();//инициализация новой строкой
                bool konec();// проверка финальности состояния
                bool zaversh(); //проверка исчерпания строки
            bool proverka();// проверка принадлежности символов алфавиту
};
 
//Файл реализации класса автомата  konavt.cpp
 
//конструктор
konavt::konavt()
{int i,j,vyb;
// возможен ввод исходных данных как из файла, так и с клавиатуры
cout<<"constructor working..."<<endl;
cout <<"Istochnik dannyx(0-klaviatura,1-file)"<<endl;
cin>>vyb;
// ввод с клавиатуры
if (vyb==0)
{   cout<<"\n Enter kolvo sostoianiy\t";
    cin>>kolsost;
    cout<<endl<<"enter kolvo simvolov alfavita\t";
    cin>>kolsimv;
    alfavit=new char [kolsimv];
    per=new int*[kolsost];
    for (i=0;i<kolsost;i++){
        per[i]=new int [kolsimv];
    };
    cout<<endl<<"enter alfavit"<<endl;
    for (j=0;j<kolsimv;j++){
        cin>>alfavit[j];
    };
    cout<<endl<<"enter matrica"<<endl;
    for (i=0;i<kolsost;i++){
    for (j=0;j<kolsimv;j++){
        cin>>per[i][j];
    };
    cout<<endl;
    };
    cout<<"enter nachalnoe sostoianie"<<endl;
    cin>>nachstate;
    cout<<endl;
    cout<<"enter kolvo konechnyh sostoianiy"<<endl;
    cin>>kolkon;
    cout<<endl;
    fin=new int[kolkon];
    cout<<"enter konechnye sostoiania"<<endl;
    for (i=0;i<kolkon;i++){
        cin>>fin[i];
    }
    cout<<endl;
// запись исходных данных в файл
    int otv;
    cout<<"save to file?(1-yes,0-no)";
    cin>>otv;
    cout<<endl;
    if (otv==1)
    {char fname[30];
        cout<<"enter filename  ";
        cin>>fname;
        cout<<endl;
        ofstream out_stream;
        out_stream.open(fname);
        if (out_stream.fail())
            {cout<<"Error output file"<<endl; return;}
                out_stream<<kolsost<<' ';
                out_stream<<kolsimv<<' ';
        for (i=0;i<kolsimv;i++) out_stream<<alfavit[i]<<' ';
        for (i=0;i<kolsost;i++){
            for (j=0;j<kolsimv;j++){
                out_stream<<per[i][j]<<' ';}}
        out_stream<<nachstate<<' ';
        out_stream<<kolkon<<' ';
        for (i=0;i<kolkon;i++)out_stream<<fin[i]<<' ';
        out_stream.close();
        cout<<"End of output file..."<<endl;
    };
} else
// ввод исходных данных из файла
{   char filename[30];
    cout<<"Enter Filename  ";
    cin>>filename;
    cout<<endl<<"vvedeno  "<<filename<<endl;
    ifstream in_stream;
    in_stream.open(filename);
    if (in_stream.fail())
    {cout<<"net faila "<<filename<<endl; return;
    };
    in_stream>>kolsost;
    cout<<"kolsost="<<kolsost<<endl;
    in_stream>>kolsimv;
    cout<<"kolsimv="<<kolsimv<<endl;
    alfavit=new char[kolsimv];
    for (i=0;i<kolsimv;i++){ in_stream>>alfavit[i];};
    for (i=0;i<kolsimv;i++) cout<<alfavit[i]<<" ";
    cout<<endl;
    per=new int*[kolsost];
    for (i=0;i<kolsost;i++) per[i]=new int [kolsimv];
    for (i=0;i<kolsost;i++){
        for (j=0;j<kolsimv;j++){
                in_stream>>per[i][j];}}
    for (i=0;i<kolsost;i++){
        for (j=0;j<kolsimv;j++){
                cout<<per[i][j];}cout<<endl;}
 
        in_stream>>nachstate;
        cout<<"begin state "<<nachstate<<endl;
        in_stream>>kolkon;
        cout<<"Number of end states "<<kolkon<<endl;
        fin=new int[kolkon];
        for (i=0;i<kolkon;i++)in_stream>>fin[i];
        for (i=0;i<kolkon;i++)cout<<fin[i]<<" ";
        cout<<endl;
        in_stream.close();
        cout<<"End of output file..."<<endl;
}
return;};
 
//показ текущего состояния
void konavt::show_sost()
{int i;
cout<<"sostoyanie  "<<avtstate<<endl;
cout<<dlina<<endl;
//cout<<"ostatok vxoda  "<<vxod<<endl;
cout<<"ostatok vxoda  ";
//for (i=0; i<dlina;i++) cout<<vxod[i]<<"\t"; // *(vxod+i)
//cout<<endl;
for (i=0; i<dlina;i++) cout<<*(vxod+i)<<"\t"; 
cout<<endl<<"protokol  ";
for (i=0;i<dlina0+1;i++) cout<<protokol[i]<<"\t";
cout<<endl;
};
 
//переход к следующему состоянию
void konavt::sled()
{int slsost,i,num;
num=-1;
char teksimv;
teksimv=vxod[0];
cout<<"symbol "<<teksimv<<endl;
for (i=0;i<kolsimv;i++) if (teksimv==alfavit[i]) {num=i;break;};
if (num==-1){cout<<"illegal symbol "<<teksimv<<endl;error=true;}
else {slsost=per[avtstate][num];
avtstate=slsost;
protokol[nomstep]=slsost;
nomstep++;
for (i=0;i<dlina;i++)vxod[i]=vxod[i+1];
vxod[dlina-1]=' ';
dlina=dlina-1;
};
return;};
 
//проверка допустимости входной строки
bool konavt::proverka()
{int i,j;
bool prizn;
for (i=0;i<dlina;i++)
{prizn=false;
for (j=0;j<kolsimv;j++) if (vxod[i]==alfavit[j]) {prizn=true;break;}; 
if (!prizn) {cout<<"illegal symbol "<<endl;break;};
};
return prizn;
};
 
//ввод новой входной строки
void konavt::init()
{int i;
cout<<"enter dlina"<<endl;
cin>>dlina;
dlina0=dlina;
vxod=new char[dlina+1];
protokol=new int [dlina+1];
for (i=0;i<dlina+1;i++)protokol[i]=0;
cout<<endl<<"enter vhodnaya stroka"<<endl;
for (i=0;i<dlina;i++)cin>>vxod[i];
//vxod[dlina]='\0';
cout<<endl;
//cout<<"ostatok vxoda  "<<vxod<<endl;
cout<<"ostatok vxoda  ";
for (i=0; i<dlina;i++) cout<<vxod[i]<<"\t";
cout<<endl;
if (proverka()) {avtstate=nachstate;
                protokol[0]=nachstate;
                nomstep=1;
                error=false;}
 else error=true;
return;};
 
//показ параметров автомата
void konavt::show()
{int i,j;
cout<<"parametry avtomata"<<endl;
cout<<"kolvo sostoianiy "<<kolsost<<endl;
cout<<"kolvo simvolov alfavita "<<kolsimv<<endl;
cout<<"simvoly alfavita"<<endl;
for (j=0;j<kolsimv;j++){
    cout<<alfavit[j]<<"\t";
};
cout<<endl<<"matrica perehodov"<<endl;
for (i=0;i<kolsost;i++){
for (j=0;j<kolsimv;j++){
    cout<<per[i][j]<<"\t";
};
cout<<endl;
};
cout<<"nachalnoe sostoianie  "<<nachstate<<endl;
cout<<"konechnye sostoiania  "<<endl;
for (i=0;i<kolkon;i++){
    cout<<fin[i]<<"\t";
};cout<<endl;
return;};
 
//проверка завершающего состояния
bool konavt::konec()
{int i;
int k;
bool kon;
kon=false;
i=-1;
for (i=0;i<kolkon;i++) if(avtstate==fin[i]){kon=true;break;};
return kon;
};
 
//проверка исчерпания входной строки
bool konavt::zaversh()
{bool prizn;
if(dlina==0) prizn=true; else prizn=false;
return prizn;
};
если вводить из файла то он такой

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 3 1 1 1 1
4 4 4 4 4 4 4 4 4 4 1 1 1 1 1
5 5 5 5 5 5 5 5 5 5 1 1 1 1 1
6 6 6 6 6 6 6 6 6 6 1 1 1 1 1
7 7 7 7 7 7 7 7 7 7 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 8 1 1
9 10 1 1 1 1 1 1 1 1 1 1 1 1 1
1 11 13 11 12 11 12 11 12 11 1 1 1 1 1
11 12 11 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 14 1 1
1 1 1 1 1 1 1 1 1 1 1 1 18 1 1
1 1 1 1 1 1 1 1 1 1 1 1 21 1 1
15 15 15 17 1 1 1 1 1 1 1 1 1 1 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 20 1 1 1
16 16 1 1 1 1 1 1 1 1 1 1 1 1 1
15 15 15 19 1 1 1 1 1 1 1 1 1 1 1
16 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 2 0
15 15 22 1 1 1 1 1 1 1 1 1 1 1 1
16 16 16 16 16 16 16 16 1 1 1 1 1 1 1
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
15.06.2011, 06:16     Построить детерминированный конечный распознаватель #2
распознавание последовательности
распознавание комментария
комментарии ближе к твоему случаю
Iliabobr
3 / 3 / 1
Регистрация: 04.11.2009
Сообщений: 98
15.06.2011, 08:06  [ТС]     Построить детерминированный конечный распознаватель #3
все равно не очень помогло((
Iliabobr
3 / 3 / 1
Регистрация: 04.11.2009
Сообщений: 98
18.06.2011, 00:42  [ТС]     Построить детерминированный конечный распознаватель #4
еще надо какуюто схему нарисовать...
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
18.06.2011, 06:11     Построить детерминированный конечный распознаватель #5
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>
#include <ctype.h>
 
enum states {
    NORMAL,
    SIGN,
    INTPART,
    FRACPART,
    END
};
 
struct stack {
    char v[100], *p;
};    
 
/* +65.372,-785.34,457.7# */
int main(void)
{
    const char *str = "+65.372,-785.34,457.7#", *p;
    enum states s;
    int c;
    
    struct stack stack;
    stack.p = stack.v;
    
    s = NORMAL;
    for (p = str; (c = (unsigned char) *p) != '\0'; p++)
        switch (s) {
        case NORMAL:
            if (c == '+' || c == '-') {
                *stack.p++ = c;
                s = SIGN;
            } else if (isdigit(c)) {
                p--;
                s = INTPART;
            } else if (c == '#')
                s = END;
            break;
        case SIGN:
            if (isdigit(c)) {
                p--;
                s = INTPART;
            } else {
                p--;
                stack.p = stack.v;
                s = NORMAL;
            }
            break;
        case INTPART:
            if (isdigit(c))
                *stack.p++ = c;
            else if (c == '.') {
                *stack.p++ = c;
                s = FRACPART;
            } else if (c == '#')
                s = END;
            else {
                p--;
                stack.p = stack.v;
                s = NORMAL;
            }
            break;
        case FRACPART:
            if (isdigit(c))
                *stack.p++ = c;
            else if (c == ',' || c == '#') {
                if (stack.p > stack.v) {
                    printf("%.*s\n", stack.p - stack.v, stack.v);
                    stack.p = stack.v;
                }
                s = (c == ',') ? NORMAL : END;
            } else {
                p--;
                stack.p = stack.v;
                s = NORMAL;
            }
            break;
        case END:
            break;
        }
    
    return 0;
}
Код
[guest@localhost tests]$ ./t
+65.372
-785.34
457.7
[guest@localhost tests]$
в случае ошибок идёт переход в нормальное состояние
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
18.06.2011, 07:20     Построить детерминированный конечный распознаватель #6
Вот ликбез. Тут и проги найдешь.

Перевод дробных констант
Перевод дробных констант немного сложнее целых: нужно отдельно вычислять целую и дробную часть числа, а так же показатель степени. Пусть, как ранее, целая часть числа накапливается в переменной N, дробная часть накапливается в переменной F, а показатель степени — в переменной P. Символы входной строки можно разделить на следующие классы:
- знак числа;
- цифра;
- точка;
- порядок — символы «E» или «е»;
- знак порядка — символы «+» или «-»;
- другой — все остальные символы.
Набор правил перехода можно записать так (не показаны переходы по ошибкам):
// start – начальное состояние
// допустимы: цифра – переход в s2
// точка – переход в s1
start: цифра -> s2; N = digit(ch); // заносим первую цифру
start: знак -> s1; если ch ==’-’ signN = -1; // учет знака
------------------
// s1: после знака
// допустимы: цифра – переход в s2
s1: цифра -> s2; N = digit(ch); // заносим первую цифру
------------------
// s2: после первой цифры
// допустимы: цифра – остаемся в s2
// точка - переход в s3
// порядок - переход в s5
// другой - конец числа, переход в finish
s2: цифра -> s1; N = N*10+digit(ch); // вычисляем целую часть
s2: точка -> s2; // закончилась целая часть
s2: E -> s5; // начался порядок
s2: другой -> finish; // завершаем
------------------
// s3: после точки
// допустимы: цифра - переход в s4
s3: цифра -> s4; FP = 0.1;
F = F+digit(ch)*0.1; // накапливаем дробную часть
------------------
// s4: после первой дробной цифры
// допустимы: цифра - остаемся в s4
// порядок - переход в s5
// другой - конец числа, переход в finish
s4: цифра -> s3; FP = FP/10;
F = F+digit(ch)*FP; // накапливаем дробную часть
s4: E -> s5; signP = знак; // запомнили знак порядка
s4: другой -> finish; // завершаем
------------------
// s5: после E
// допустимы: знак - переход в s6
цифра - переход в s7
s5: знак -> s6; signP = знак; // знак порядка
s5: цифра -> s7; P = digit(ch); // первая цифра порядка
------------------
// s6: после знака порядка
// допустимы: цифра - переход в s6
s6: цифра –> s7
------------------
// s7: после первой цифры порядка
// допустимы: цифра - остаемся в s7
// другой - конец числа, переход в finish
s7: цифра -> s7; P = P*10+digit(ch); // вычисляем порядок
s7: другой -> finish; // завершаем
Первый выбираемый из строки символ может быть только знаком или цифрой — тем самым мы запрещаем начинать число непосредственно с точки. Если первый символ — не знак и не цифра, то имеем ошибку. Аналогично, после точки тоже должна быть хотя бы одна цифра — таким образом, мы запрещаем записывать и константы, завершающиеся точкой. Описание остальных состояний приведено в комментариях.
На финише окончательно вычисляется число по формуле:
C++
1
2
3
4
5
D = (N + F);
// учли знак порядка
если signP = +1, то D = D *(10^P);      
если signP = -1, то D = D /(10^P);
D = D * signN;                  // учли знак числа
Реализация выполнена новым способом — с помощью матрицы переходов. Матрица переходов представляет собой прямоугольную матрицу, строки которой определяют классы символов, а столбцы — состояния . Значением каждого элемента является состояние, в которое должен перейти автомат из текущего при заданном входном символе. При этом состояния finish и error можно не заполнять.

Представление автомата в виде матрицы переходов очень наглядно и часто помогает увидеть то, что трудно понять при изображении автомата в виде графа или в виде набора правил. Например, переходы в состояние ошибки должны быть определены во всех состояниях при всех входных символах. Матрица описанного автомата представлена в табл. 5.1.
Таблица 5.1. Матрица переходов преобразователя
start s1 s2 s3 s4 s5 s6 s7 finish error
цифра s2 s2 s2 s4 s4 s7 s7 s7
точка error error s3 error error error error error
порядок error error s5 error s5 error error error
знак s1 error error error error s6 error error
другой error error finish error finish error error finish
Обратите внимание, что столбцы матрицы, соответствующие состояниям s1, s3 и s5 отличаются только первым элементом. Такие столбцы — первые кандидаты на сокращение. Для автомата-распознавателя такой матрицы вполне достаточно — в листинге 5.4 показана функция-автомат вместе с функцией type(), определяющей тип символа.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Листинг 5.4.  Распознаватель дробного числа
enum State              // состояния
{ start, s1, s2, s3, s4, s5, s6, s7, fin, err, statesCount = fin };
enum Symbol                 // классы символов
{ Digit, Point, Exp, Sign, Other, ClassCount };
Symbol type(char ch)            // определение класса символа
{ if(isdigit(ch))           return Digit;
  if(ch =='.')              return Point;
  if((ch =='e')||(ch =='E'))    return Exp; 
  if((ch =='-')||(ch =='+'))    return Sign;
  return Other;
}
// распознаватель дробного числа
bool Double(const string &str)
{ State matrix[ClassCount][statesCount] =       // матрица переходов
  {{s2,   s2,  s2,  s4,  s4,     s7,  s7,  s7 },    // цифра Digit 
   {err, err, s3,  err, err, err, err, err},    // точка Point
   {err, err, s5,  err, s5,  err, err, err},    // порядок Exp
   {s1,  err, err, err, err, s6,  err, err},    // знак Sign
   {err, err, fin, err, fin, err, err, fin}     // другой Other
  };
  size_t n = 0;
  State s = start;              // начальное состояние
  while(s != finish)
  {  Symbol t = type(str[n++]);     // получили класс символа
     s = matrix[t][s];          // следующее состояние
     if (s == err) return false;
  }
  return true;          // сюда попадаем только в состоянии finish;
}
Здесь не учтен вариант, когда отсутствует «другой» символ и последним символом строки является цифра. Для устранения этой небольшой проблемы достаточно проверять переменную n — индекс символа в строке
Реализация, как и предыдущий вариант с функциями-состояниями (см. листинг 5.3 и 5.4), тоже проста — в основном цикле ДКА всего 3 строки.
Для преобразователя помимо матрицы переходов нужно определить функции для вычисления числа. Пусть все данные для числа содержатся в следующей структуре:
C++
1
2
3
4
5
6
7
8
9
10
struct Number
{   int signN;      // знак числа
       double N;        // целая часть числа
    double F;       // дробная часть числа
    double FP;      // коэффициент умножения дробной части
    bool signP;     // знак порядка
    double P;       // порядок
    // конструктор по умолчанию
    Number():signN(+1),N(),FP(),F(),signP(true),P() {}
}
;
Каждая функция, реализующая свою часть преобразования, должна получать в качестве параметров такую структуру и очередной символ. Функции требуется вызывать в основном цикле в определенных состояниях. Поэтому если функция возвращает следующее состояние, то вместо матрицы состояний можно инициализировать матрицу указателей на функции:
C++
1
2
3
4
5
6
7
8
typedef State (*Action)(const char &ch, Number &D);
Action matrix[Class][states];
Тогда вызов функции выполняется в цикле таким образом:
while((s != finish))
{  Symbol t = type(str[n]);     // класс символа
   s = matrix[t][s](str[n], D);     // вызов функции
   ++n;                 // следующий символ
}
Функций требуется реализовать меньше, чем элементов в матрице состояний, так как в ней много одинаковых элементов.

Главная функция преобразователя Double() возвращает число типа double. Если во входной строке обнаружены ошибки, то возвращается 0. В этом случае устанавливается глобальный флаг ошибки flagError, который может проверить вызывающая функция. Полная реализация преобразователя (структура Number показана выше) представлена в листинге 5.5.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
Листинг 5.5. Реализация конечного преобразователя для перевода дробных чисел
// автомат-преобразователь для дробных констант
// функция вычисления цифры
const int notDigit = -1;            // не цифра
int digit(char ch)
{ string digits = "0123456789";
  int d;
  for(d = 0; d < 10; ++d)
    if(ch == digits[d]) return d;
  return notDigit;              // символ - не цифра
}
// функция вычисления класса символа
enum Symbol { D, P, E, S, O, Class };
Symbol type(char ch)
{ if(isdigit(ch)) return D;
  if(ch =='.')    return P;
  if((ch =='e')||(ch=='E')) return E; 
  if((ch =='-')||(ch=='+')) return S;
  return O;
}
// состояния
enum State { start, s1, s2, s3, s4, s5, s6, s7, finish, error }; 
// обработка состояния ошибки
State Error(const char &ch, Number &D) 
{ Error.set();      // установка флага ошибки 
  return error; 
}
// завершение обработки
State Other(const char &ch, Number &D)
{ return finish; }
// в состоянии start – обработка знака
State startS(const char &ch, Number &D)
{ if (ch == '-') D.signN = -1; 
  return s1;    // первая цифра
}
// в состоянии start и s1 – обработка первой цифры
State startD(const char &ch, Number &D) 
{ D.N = digit(ch);
  return s2;    // целая часть
}
// в состоянии s2 – обработка цифр целой части
State intD(const char &ch, Number &D)
{ D.N = D.N * 10 + digit(ch);
  return s2;    // целая часть
}
// в состоянии s2 – обработка точки
State Point(const char &ch, Number &D)
{ return s3; }  // после точки
 
// в состоянии s2 – обработка E
State Exp(const char &ch, Number &D)
{ return s5; }  // после E
// в состоянии s3 – обработка первой цифры после точки
State float1D(const char &ch, Number &D)
{ D.FP = 0.1;  D.F = digit(ch) * D.FP;
  return s4;    // дробная часть
}
// в состоянии s4 – обработка цифр дробной части
State floatD(const char &ch, Number &D) 
{ D.FP/=10; D.F = D.F + digit(ch) * D.FP;
  return s4;    // дробная часть
}
// в состоянии s5 и s6 – обработка первой цифры порядка
State exp1D(const char &ch, Number &D) 
{ D.P = digit(ch);
  return s7;    // порядок     
}
// в состоянии s6 – обработка знака порядка
State expS(const char &ch, Number &D) 
{ if(ch == '-') D.signP = false;
  return s7;    // порядок 
}
// в состоянии s7 – обработка цифр порядка
State expD(const char &ch, Number &D) 
{ D.P = D.P * 10 + digit(ch);
  return s7;    // порядок
}
typedef State (*Action)(const char &ch, Number &D); 
double Double(const string &str)
{ Action matrix[Class][states] =
//start   s1      s2     s3       s4      s5     s6     s7
//перед   после   целая  после    дроб.   после  после  порядок
//числом  знака   часть  точки    часть   Е      знака Е
{{startD, startD, intD,  float1D, floatD, exp1D, exp1D, expD },// цифра 
 {Error,  Error,  Point, Error,   Error,  Error, Error, Error},// точка
 {Error,  Error,  Exp,   Error,   Exp,    Error, Error, Error},// порядок
 {startS, Error,  Error, Error,   Error,  expS,  Error, Error},// знак
 {Error,  Error,  Other, Error,   Other,  Error, Error, Other} // другой 
};
  Number D;
  double result;            // возвращаемый результат
  size_t n = 0;         // индекс символа в строке
  State s = start;          // начальное состояние
  while((s != finish)&&(s != error)&&(n < str.size()))
  { Symbol t = type(str[n]);        // получили класс символа
    s = matrix[t][s](str[n], D);    // вызов функции
    ++n;                // след символ
  }
// проверка состояния при выходе  
  if ((s==s2)||(s==s4)||(s==s7)||   // финишные состояния
      (s==finish))
  { result = D.N+D.F;
    if(!D.signP) D.P = -D.P;
    result = D.signN * result * pow(10.0, D.P);
  }
  else result = 0;
  return result;
}
Для получения цифры преобразователь использует функцию digit(), аналогичную описанной в листинге 5.3.
Обратите внимание на то, что функции Point() и Exp(), обрабатывающие символы точки и экспоненты, фактически не делают ничего, кроме перехода в новое состояние. Это довольно частое явление при разработке конечных преобразователей. Функция отражает некоторое состояние. «Пустые» состояния необходимы для отслеживания правильной последовательности символов во входной строке.

Заметим, что состояния, в которых вызывается функция, обрабатывающая «другой» символ (s2, s4, s7), являются финишными — это хорошо видно в матрице состояний автомата-распознавателя. Если во входной строке в конце нет «другого» символа, то автомат выходит из цикла при исчерпании символов строки. Поэтому в основной функции после цикла обработки выполняется проверка, в каком состоянии находился автомат после обработки всей строки.
Хотя преобразователь прекрасно работает с правильными аргументами, однако в нем нет проверки на диапазон порядка. Как известно, порядок числа типа double должен быть в диапазоне от -308 до +308.

Поэтому если пользователь напишет число с порядком вне этого диапазона, наш автомат-преобразователь выдаст неверный результат. Таким образом, автомат должен отслеживать количество цифр порядка (не более 3) и проверять численное значение порядка. Оставляем читателю эту модификацию преобразователя в качестве упражнения (см. «Контрольные вопросы и упражнения»).

Несмотря на то, что реализация выглядит простой и прозрачной, в ней есть свои сложности. Во-первых, теряется наглядность перехода в новое состояние — переход спрятан в функции. Во-вторых, если матрица состояний имеет большую размерность, и функций-обработчиков достаточно много, то заполнение матрицы представляет серьезную проблему. Чтобы избежать ошибок, приходится подробно выписывать правила перехода: в состоянии State при наличии символа S вызвать функцию f(), перейти в состояние Next.
Yandex
Объявления
18.06.2011, 07:20     Построить детерминированный конечный распознаватель
Ответ Создать тему

Метки
конечный автомат
Опции темы

Текущее время: 11:44. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru