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

D = (N + F);
// учли знак порядка
если signP = +1, то D = D *(10^P);        
если signP = -1, то D = D /(10^P);
D = D * signN;                  // учли знак числа

Листинг 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;
}

struct Number
{   int signN;      // знак числа
       double N;        // целая часть числа
    double F;       // дробная часть числа
    double FP;      // коэффициент умножения дробной части
    bool signP;     // знак порядка
    double P;       // порядок
    // конструктор по умолчанию
    Number():signN(+1),N(),FP(),F(),signP(true),P() {}
}

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;                 // следующий символ
}

Листинг 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;
}