синтаксический анализатор мат.формул

From

Boris Rudakov (2:5054/9.4)

To

George Shuklin (2:5054/9@fidonet)

Date

2000-02-27T12:23:43Z

Area

RU.ALGORITHMS

Hello George!

26 Feb 00 09:38, George Shuklin wrote to Svirskiy Taras:

 GS> А, это ты Svirskiy! Вот что я тебе сказать хотел...
 GS>   В 25 февраля 2000 01:12, Svirskiy Taras решил написать All:
 ST>> Может кто-нибудь знает, или писал  алгоритм сабжа,
 ST>> или где об этом вообще почитать можно.
 ST>> Плиз, пмомогите, сильно надо.
 GS> Вот, лови. Не пинать. Писано в свое время для сдачи по ПОВС, посему
 GS> возможны глюки.
[...]

Плохо :)

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

Вот слегка покоцанный примерчик калькулятора:
(примечания:
* Декларации типов данных я не привожу - большие и к делу мало относятся
* Разбор числовых литералов (чисел) я не привожу, но тут использована одна
  функция из другой библиотеки. Можно заменить на что угодно.
* Оригинал абсолютно рабочий и активно используется около года :)
)

=== Cut ===
/////////////////////////////////////////////////////////////////////////////// /
// Function definitions //
/////////////////////////////////////////////////////////////////////////////// /

#ifdef ISRTLWIN32
#  define NEARPROC __fastcall
#elif defined(ISRTLWIN16)
#  define NEARPROC __near __fastcall
#else
#  define NEARPROC
#endif

typedef bool (NEARPROC *TFnProc)(LPCSTR FAR& Str, double FAR& Val, TCalcExpr FAR& Expr);

bool NEARPROC FnAbs    (LPCSTR FAR& Str, double FAR& Val, TCalcExpr FAR& Expr);
bool NEARPROC FnACos   (LPCSTR FAR& Str, double FAR& Val, TCalcExpr FAR& Expr);
//...Покоцано
bool NEARPROC FnSum    (LPCSTR FAR& Str, double FAR& Val, TCalcExpr FAR& Expr);
bool NEARPROC FnTan    (LPCSTR FAR& Str, double FAR& Val, TCalcExpr FAR& Expr);

/////////////////////////////////////////////////////////////////////////////// /
// Reserved words table //
/////////////////////////////////////////////////////////////////////////////// /

typedef struct TFnDesc {
  LPCSTR Name;
  const GUID FAR* GrpGUID;
  TFnProc Proc;
} TFnDesc, FAR* PFnDesc;

static TFnDesc ResWords[] = {
  {"\3abs",   &IID_ICalcArithmGrp, FnAbs},
  {"\4acos",  &IID_ICalcTrigonGrp, FnACos},
//...Покоцано
  {"\3sum",   &IID_ICalcVectorGrp, FnSum},
  {"\3tan",   &IID_ICalcTrigonGrp, FnTan},
};

int LOCALPROC SearchResWord(LPCSTR Word, int Len)
{
  const int Count = CountOf(ResWords);
  int Hi = Count - 1, Lo = 0;
  int Mid, Cmp, L;

  while (Lo <= Hi) {
    Mid = (Hi + Lo) >> 1;
    L = min((int)ResWords[Mid].Name[0], (int)Len);
    Cmp = MemCmp((LPVOID)Word, (LPVOID)&ResWords[Mid].Name[1], L);
    if (Cmp == 0) Cmp = Len - (int)ResWords[Mid].Name[0];
    if (Cmp > 0) Lo = Mid + 1;
    else if (Cmp < 0) Hi = Mid - 1;
    else return Mid;
  }
  return -1;
}

/////////////////////////////////////////////////////////////////////////////// /
// Parser //
/////////////////////////////////////////////////////////////////////////////// /

void LOCALPROC SkipWhite(LPCSTR FAR& Str)
{
  LPCSTR S = Str;
  while (*S == ' ' || *S == 9 || *S == 13 || *S == 10) S++;
  Str = S;
}

bool LOCALPROC SkipTo(LPCSTR FAR& Str, char To, TError Error, TCalcExpr FAR& Expr)
{
  SkipWhite(Str);
  if (*Str == To) {
    Str++;
    return true;
  } else {
    SetError(Error, Str, Expr);
    return false;
  }
}

bool LOCALPROC GetTerm(LPCSTR FAR& Str, double FAR& Val, TCalcExpr FAR& Expr);
bool LOCALPROC GetMult(LPCSTR FAR& Str, double FAR& Val, TCalcExpr FAR& Expr);
bool LOCALPROC GetExpr(LPCSTR FAR& Str, double FAR& Val, TCalcExpr FAR& Expr);

bool LOCALPROC ParseWord(LPCSTR FAR& Str, double FAR& Val, TCalcExpr FAR& Expr)
{
  LPCSTR S = Str;
  LPCSTR SS = Str;
  char Word[24];
  LPSTR W = Word;
  int L;
  while (TRUE) {
    if ((L = (W - Word)) >= sizeof(Word)) {
      SetError(erNoResWord, S, Expr);
      return false;
    }
    if (*S < 'A') break;
    else *W++ = *S++;
  }
  CharLowerBuffA(Word, L);
  int Fn = SearchResWord(Word, L);
  if (Fn == -1) {
    SetError(erNoResWord, SS, Expr);
    return false;
  }
  Str = S;
  return ResWords[Fn].Proc(Str, Val, Expr);
}

bool LOCALPROC GetTerm(LPCSTR FAR& Str, double FAR& Val, TCalcExpr FAR& Expr)
{
  LPCSTR S = Str;
  double V = 0;
Again:
  SkipWhite(S);
  if (*S == '-') {
    S++;
    if (!GetTerm(S, V, Expr)) return false;
    V = -V;
  } else if (*S == '+') {
    S++;
    while (*S == '+') S++;
    goto Again;  // Знаю-знаю, но уж очень хотелось...
  } else if (*S == '(') {
    S++;
    if (!GetExpr(S, V, Expr)) return false;
    if (!SkipTo(S, ')', erRBrace, Expr)) return false;
  } else if (*S == '.' || (*S >= '0' && *S <= '9')) {
    V = StrToDoubleParseA(&S); // Call some standalone fn for parse numbers,
                               // may be used any sutable code
    if (GetLastError()) {      // Check parsing error
      SetError(erValue, S, Expr);
      return false;
    }
  } else if (*S)
    if (*S < 'A') {
      SetError(erNeedValue, S, Expr);
      return false;
    } else if (!ParseWord(S, V, Expr)) return false;
  Str = S;
  Val = V;
  return true;
}

bool LOCALPROC GetMult(LPCSTR FAR& Str, double FAR& Val, TCalcExpr FAR& Expr)
{
  LPCSTR S = Str;
  double V1 = 0, V2;
  if (!GetTerm(S, V1, Expr)) return false;
  while (*S) {
    SkipWhite(S);
    if (*S == '*') {
      S++;
      bool Pow = *S == '*';
      if (Pow) S++;
      if (!GetTerm(S, V2, Expr)) return false;
      if (Pow) V1 = pow(V1, V2);
      else V1 = V1 * V2;
    } else if (*S == '/') {
      S++;
      if (!GetTerm(S, V2, Expr)) return false;
      Str = S;       // Temporary solution for exception handler
      V1 = V1 / V2;  // Do not check for "/ 0" - will catch exception instead
    } else if (*S == '%') {
      S++;
      if (!GetTerm(S, V2, Expr)) return false;
      V1 = fmod(V1, V2);
    } else break;
  }
  Str = S;
  Val = V1;
  return true;
}

bool LOCALPROC GetExpr(LPCSTR FAR& Str, double FAR& Val, TCalcExpr FAR& Expr)
{
  LPCSTR S = Str;
  double V1 = 0, V2;
  if (!GetMult(S, V1, Expr)) return false;
  while (*S) {
    SkipWhite(S);
    if (*S == '+') {
      S++;
      if (!GetMult(S, V2, Expr)) return false;
      V1 = V1 + V2;
    } else if (*S == '-') {
      S++;
      if (!GetMult(S, V2, Expr)) return false;
      V1 = V1 - V2;
    } else break;
  }
  Str = S;
  Val = V1;
  return true;
}

/////////////////////////////////////////////////////////////////////////////// /
// TCalcExpr //
/////////////////////////////////////////////////////////////////////////////// /

#ifdef __BORLANDC__
#  include <float.h>
#endif

int LOCALPROC RegisterCalcException(DWORD Code, LPCSTR S, TCalcExpr FAR& Expr)
{
  TError Kind;
  switch (Code) {
    case EXCEPTION_FLT_DIVIDE_BY_ZERO:
    case EXCEPTION_INT_DIVIDE_BY_ZERO:
      Kind = erZeroDivide;
      break;
    case EXCEPTION_FLT_OVERFLOW:
    case EXCEPTION_INT_OVERFLOW:
      Kind = erOverflow;
      break;
    case EXCEPTION_FLT_UNDERFLOW:
      Kind = erUnderflow;
      break;
    default:
      Kind = erSystem;
      break;
  }
#ifdef __BORLANDC__
//
// Reset FPU unit because of very strange program behavior after FPU errors.
//
  switch (Code) {
    case EXCEPTION_FLT_DENORMAL_OPERAND :
    case EXCEPTION_FLT_DIVIDE_BY_ZERO   :
    case EXCEPTION_FLT_INEXACT_RESULT   :
    case EXCEPTION_FLT_INVALID_OPERATION:
    case EXCEPTION_FLT_OVERFLOW         :
    case EXCEPTION_FLT_STACK_CHECK      :
      _fpreset();
      break;
  }
#elif !defined(__MSC)
#  pragma message Need to check FPU recovery after FPU errors !
#endif
  SetError(Kind, S, Expr);
  return EXCEPTION_EXECUTE_HANDLER;
}

// Собственно главный метод калькулятора (он у меня оформлен в виде // COM-объекта).
//
BOOL STDMETHODCALLTYPE TCalcExpr::Calculate()
{
  LPCSTR S = Formula;
  try {
    BOOL Result = GetExpr(S, Value, *this);
    if (Result && *S) {
      SetError(erNeedValue, S, *this);
      return FALSE;
    }
    return TRUE;
  } __except(RegisterCalcException(GetExceptionCode(), S, *this)) {
    return false;
  }
}

/////////////////////////////////////////////////////////////////////////////// /
// Functions implementation //
/////////////////////////////////////////////////////////////////////////////// /

bool NEARPROC FnAbs    (LPCSTR FAR& Str, double FAR& Val, TCalcExpr FAR& Expr)
{
  double V;
  if (!GetTerm(Str, V, Expr)) return false;
  Val = fabs(V);
  return true;
}

bool NEARPROC FnACos   (LPCSTR FAR& Str, double FAR& Val, TCalcExpr FAR& Expr)
{
  double V;
  if (!GetTerm(Str, V, Expr)) return false;
  Val = acos(V);
  return true;
}

// Покоцано...

bool NEARPROC FnSum    (LPCSTR FAR& Str, double FAR& Val, TCalcExpr FAR& Expr)
{
  LPCSTR S = Str;
  double V1, V2;
  if (!SkipTo(S, '(', erLBrace, Expr)) return false;
  if (!GetExpr(S, V1, Expr)) return false;
  SkipWhite(S);
  while (*S == ';') {
    S++;
    if (!GetExpr(S, V2, Expr)) return false;
    V1 += V2;
    SkipWhite(S);
  }
  if (!SkipTo(S, ')', erRBrace, Expr)) return false;
  Str = S;
  Val = V1;
  return true;
}

// Ну и ты-пы

=== Cut ===

Вот и все. Просто и со вкусом.

 GS> George.

Борис Рудаков,               Маю песню услышут ты-ся-чи ух !
BBR

--- Be happy: BBR is looking at you !
 * Origin: АлкАголь малыми дозами безвреден в любых количествах (2:5054/9.4)