Написание мини-языка

StackOverflow https://stackoverflow.com/questions/615040

  •  03-07-2019
  •  | 
  •  

Вопрос

У меня есть приложение, которое должно позволять пользователям писать выражения, похожие на Excel:

(H1 + (D1 / C3)) * I8

и более сложные вещи, такие как

If(H1 = 'True', D3 * .2, D3 * .5)

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

Спасибо!

Это было полезно?

Решение

На какой-нибудь другой вопрос вы найдете подсказки в:

Удачи!

Другие советы

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

n1 = y and n2 > z
n2 != x or (n3 > y and n4 = z)

и так далее.На английском языке вы могли бы сказать, что есть атомы, соединенные символами AND и OR, и каждый атом состоит из трех элементов - левого атрибута, оператора и значения.Поскольку это было так лаконично, я думаю, что синтаксический анализ был проще.Набор возможных атрибутов известен и ограничен (например:имя, размер, время).Операторы различаются в зависимости от атрибута:разные атрибуты принимают разные наборы операторов.И диапазон и формат возможных значений также варьируются в зависимости от атрибута.

Для синтаксического анализа я разделяю строку на пробелы с помощью String.Split().Позже я понял, что перед Split() мне нужно было нормализовать входную строку - вставить пробелы до и после скобок.Я сделал это с помощью regex.Replace().

Результатом разделения является массив токенов.Затем синтаксический анализ происходит в большом цикле for с переключением на значение атрибута с левой стороны.С каждым повторением цикла я был настроен отхлебывать по группе жетонов.Если первый токен был open-paren, то группа состояла всего из одного токена в длину:сам отец.Для токенов, которые были хорошо известными именами - значениями моего атрибута, - синтаксический анализатор должен был использовать группу из 3 токенов, по одному для имени, оператора и значения.Если в какой-либо момент токенов недостаточно, анализатор выдает исключение.В зависимости от потока токенов состояние анализатора будет меняться.Соединение (AND, ИЛИ, XOR) означало поместить предыдущий атом в стек, и когда следующий атом был закончен, я вставлял предыдущий атом и соединял эти два атома в составной атом.И так далее.Управление состоянием происходило в конце каждого цикла синтаксического анализатора. 

Atom current;
for (int i=0; i < tokens.Length; i++) 
{
  switch (tokens[i].ToLower())
  {
    case "name":
        if (tokens.Length <= i + 2)
            throw new ArgumentException();
        Comparison o = (Comparison) EnumUtil.Parse(typeof(Comparison), tokens[i+1]);
        current = new NameAtom { Operator = o, Value = tokens[i+2] };
        i+=2;
        stateStack.Push(ParseState.AtomDone);
        break;
    case "and": 
    case "or":
        if (tokens.Length <= i + 3) 
          throw new ArgumentException();
        pendingConjunction = (LogicalConjunction)Enum.Parse(typeof(LogicalConjunction), tokens[i].ToUpper());
        current = new CompoundAtom { Left = current, Right = null, Conjunction = pendingConjunction };
        atomStack.Push(current);
        break;

    case "(":
        state = stateStack.Peek();
        if (state != ParseState.Start && state != ParseState.ConjunctionPending && state != ParseState.OpenParen)
          throw new ArgumentException();
        if (tokens.Length <= i + 4)
          throw new ArgumentException();
        stateStack.Push(ParseState.OpenParen);
        break;

    case ")":
        state = stateStack.Pop();
        if (stateStack.Peek() != ParseState.OpenParen)
            throw new ArgumentException();
        stateStack.Pop();
        stateStack.Push(ParseState.AtomDone);
        break;

    // more like that...
    case "":
       // do nothing in the case of whitespace
       break;
    default:
        throw new ArgumentException(tokens[i]);
  }

  // insert housekeeping for parse states here

}

Это упрощено, совсем немного.Но идея заключается в том, что каждое утверждение case довольно простое.Это легко разобрать в атомарной единице выражения.Самым сложным было надлежащим образом соединить их все вместе.

Этот трюк был выполнен в разделе "Домашнее хозяйство", в конце каждого цикла slurp, с использованием стека состояний и стека атомов.Разные вещи могут происходить в зависимости от состояния анализатора.Как я уже сказал, в каждом операторе case состояние анализатора может изменяться, при этом предыдущее состояние помещается в стек.Затем, в конце инструкции switch, если состояние сообщало, что я только что закончил синтаксический анализ атома, и было ожидающее соединение, я перемещал только что проанализированный атом в CompoundAtom .Код выглядит примерно так: 

            state = stateStack.Peek();
            if (state == ParseState.AtomDone)
            {
                stateStack.Pop();
                if (stateStack.Peek() == ParseState.ConjunctionPending)
                {
                    while (stateStack.Peek() == ParseState.ConjunctionPending)
                    {
                        var cc = critStack.Pop() as CompoundAtom;
                        cc.Right = current;
                        current = cc; // mark the parent as current (walk up the tree)
                        stateStack.Pop();   // the conjunction is no longer pending 

                        state = stateStack.Pop();
                        if (state != ParseState.AtomDone)
                            throw new ArgumentException();
                    }
                }
                else stateStack.Push(ParseState.AtomDone); 
            }

Еще одним волшебством был EnumUtil.Parse .Это позволяет мне анализировать такие вещи, как "<" в значение enum.Предположим, вы определяете свои перечисления следующим образом: 

internal enum Operator
{
    [Description(">")]   GreaterThan,
    [Description(">=")]  GreaterThanOrEqualTo,
    [Description("<")]   LesserThan,
    [Description("<=")]  LesserThanOrEqualTo,
    [Description("=")]   EqualTo,
    [Description("!=")]  NotEqualTo
}

Обычно Enum.Parse ищет символическое имя значения enum, и < не является допустимым символическим именем.EnumUtil.Parse() ищет объект в описании.Код выглядит примерно так: 

internal sealed class EnumUtil
{
    /// <summary>
    /// Returns the value of the DescriptionAttribute if the specified Enum value has one.
    /// If not, returns the ToString() representation of the Enum value.
    /// </summary>
    /// <param name="value">The Enum to get the description for</param>
    /// <returns></returns>
    internal static string GetDescription(System.Enum value)
    {
        FieldInfo fi = value.GetType().GetField(value.ToString());
        var attributes = (DescriptionAttribute[])fi.GetCustomAttributes(typeof(DescriptionAttribute), false);
        if (attributes.Length > 0)
            return attributes[0].Description;
        else
            return value.ToString();
    }

    /// <summary>
    /// Converts the string representation of the name or numeric value of one or more enumerated constants to an equivilant enumerated object.
    /// Note: Utilised the DescriptionAttribute for values that use it.
    /// </summary>
    /// <param name="enumType">The System.Type of the enumeration.</param>
    /// <param name="value">A string containing the name or value to convert.</param>
    /// <returns></returns>
    internal static object Parse(Type enumType, string value)
    {
        return Parse(enumType, value, false);
    }

    /// <summary>
    /// Converts the string representation of the name or numeric value of one or more enumerated constants to an equivilant enumerated object.
    /// A parameter specified whether the operation is case-sensitive.
    /// Note: Utilised the DescriptionAttribute for values that use it.
    /// </summary>
    /// <param name="enumType">The System.Type of the enumeration.</param>
    /// <param name="value">A string containing the name or value to convert.</param>
    /// <param name="ignoreCase">Whether the operation is case-sensitive or not.</param>
    /// <returns></returns>
    internal static object Parse(Type enumType, string stringValue, bool ignoreCase)
    {
        if (ignoreCase)
            stringValue = stringValue.ToLower();

        foreach (System.Enum enumVal in System.Enum.GetValues(enumType))
        {
            string description = GetDescription(enumVal);
            if (ignoreCase)
                description = description.ToLower();
            if (description == stringValue)
                return enumVal;
        }

        return System.Enum.Parse(enumType, stringValue, ignoreCase);
    }

}

Я получил эту вещь EnumUtil.Parse() откуда-то еще.Может быть, здесь?

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

 /* here's a teeny one in C++ */
void ScanWhite(const char* &p){
  while (*p==' ') p++;
}

bool ParseNum(const char* &p, double &v){
  ScanWhite(p);
  if (!DIGIT(*p)) return false;
  const char* p0 = p;
  while(DIGIT(*p)) p++;
  if (*p == '.'){
    p++;
    while(DIGIT(*p)) p++;
  }
  v = /* value of characters p0 up to p */;
  return true;
}

bool ParseId(const char* &p, double &v){
  ScanWhite(p);
  if (ALPHA(p[0]) && DIGIT(p[1])){
    v = /* value of cell whose name is p[0], p[1] */;
    p += 2;
    return true;
  }
  return false;
}

bool ParseChar(const char* &p, char c){
  ScanWhite(p);
  if (*p != c) return false;
  p++;
  return true;
}

void ParseExpr(const char* &p, double &v); /* forward declaration */

void ParsePrimitive(const char* &p, double &v){
  if (ParseNum(p, v));
  else if (ParseId(p, v));
  else if (ParseChar(p, '(')){
    ParseExpr(p, v);
    if (!ParseChar(p, ')'){/* throw syntax error */}
  }
  else {/* throw syntax error */}
}
#define PARSE_HIGHER ParsePrimitive

void ParseUnary(const char* &p, double &v){
  if (ParseChar(p, '-')){
    ParseUnary(p, v);
    v = -v;
  }
  else {
    PARSE_HIGHER(p, v);
  }
}
#undef  PARSE_HIGHER
#define PARSE_HIGHER ParseUnary

void ParseProduct(const char* &p, double &v){
  double v2;
  PARSE_HIGHER(p, v);
  while(true){
    if (ParseChar(p, '*')){
      PARSE_HIGHER(p, v2);
      v *= v2;
    }
    else if (ParseChar(p, '/')){
      PARSE_HIGHER(p, v2);
      v /= v2;
    }
    else break;
  }
}
#undef  PARSE_HIGHER
#define PARSE_HIGHER ParseProduct

void ParseSum(const char* &p, double &v){
  double v2;
  PARSE_HIGHER(p, v);
  while(true){
    if (ParseChar(p, '+')){
      PARSE_HIGHER(p, v2);
      v += v2;
    }
    else if (ParseChar(p, '-')){
      PARSE_HIGHER(p, v2);
      v -= v2;
    }
    else break;
  }
}
#undef  PARSE_HIGHER
#define PARSE_HIGHER ParseSum

void ParseExpr(const char* &p, double &v){
  PARSE_HIGHER(p, v);
}

double ParseTopLevel(const char* buf){
  const char* p = buf;
  double v;
  ParseExpr(p, v);
  return v;
}

Теперь, если вы просто вызовете ParseTop, он вычислит значение выражения для вас.

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

Выполнение инструкции "if" немного сложнее.Каждой процедуре синтаксического анализа требуется дополнительный аргумент "включить", поэтому она не выполняет вычислений, если она не включена.Затем вы анализируете слово "if", анализируете тестовое выражение, а затем анализируете два результирующих выражения, отключив неактивное.

Вы могли бы использовать .Компилятор NET JScript или интерфейс с IronPython, IronRuby или IronScheme (с именами в алфавитном порядке, а не с предпочтениями;p ).

У меня есть контрпример того, как не чтобы сделать это: Блуждающий огонек (поскольку это мой собственный код, я чувствую себя уверенно, критикуя его).

Что такое хорошо о Коде?

  1. Следовательно, он использует шаблон проектирования:Шаблон интерпретатора
  2. Он имеет довольно чистый дизайн
  3. Он использует атрибуты приятным способом.
  4. Он создает приятную графику.;-)

Графика черепахи http://i3.codeplex.com/Project/Download/FileDownload.aspx?ProjectName=wisp&DownloadId=34823

Что такое плохой о коде?

  1. Это медленно!
  2. Язык нечетко определен в отношении списков (data vs.код).

Проверьте ANTLR ( АНТЛР ).Вы определяете синтаксис языка, тестируете его с помощью графического интерфейса пользователя и генерируете исходный код на различных языках.Открытый исходный код.

Я бы порекомендовал эту книгу Конструирование Маленьких языков.Он познакомит вас со многими основами компилятора, необходимыми для правильного выполнения этой задачи.

Вы упомянули тот факт, что регулярные выражения не будут работать, если у вас нет каких-то строгих ограничений на вашем языке.Как уже говорили другие, a Анализатор Рекурсивного Спуска сделает свое дело.

Следующий выбор будет заключаться в том, использовать ли Генератор синтаксического анализа Нравится ANTLR ( АНТЛР ), или написать его с нуля.

Взгляните на этот проект с открытым исходным кодом:

Финансовые функции Excel

Я рекомендую посмотреть на работу CoreCalc / FunCalc:http://www.itu.dk/people/sestoft/funcalc/

Я использовал их грамматику для COCO \ R parser generator в производстве, и она работает действительно быстро.

Все, что вам нужно сделать, это:1.получите грамматику Excel из corecalc 2.запустите coco.exe на нем (генерирует анализатор для выражений, похожих на Excel) 3.перевести дерево выражений в обратную польскую нотацию 4.простой расчет

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top