Запись мини-языка

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

 /* 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 состоит в том, чтобы помочь добавить операторы на промежуточных уровнях приоритета.

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

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

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

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

Графика с относительными командами http://i3.codeplex.com/Project/Download/FileDownload.aspx?ProjectName=wisp&DownloadId=34823

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

1. Это медленно!
2. Язык является неточным относительно списков (данные по сравнению с кодом).

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

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

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

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

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

Вывод разделения является массивом маркеров. Затем парсинг происходит в большом для цикла с переключателем на левой стороне значение атрибута. С каждой каруселью цикла я был установлен хлебать в группе маркеров. Если первый маркер был открытым-paren, то группа была всего одним маркером в длине: сам paren. Для маркеров, которые были известными именами - моими значениями атрибута - синтаксический анализатор должен был хлебать в группе из 3 маркеров, один каждый для имени, оператора и значения. Если в какой-либо точке существует недостаточно маркеров, синтаксический анализатор выдает исключение. На основе потока маркеров изменилось бы состояние синтаксического анализатора. Соединение (И, ИЛИ, 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

}

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

Тот прием был выполнен в разделе обслуживания, в конце каждого хлебать-цикла, с помощью стека состояния и стопки атома. Другой материал может произойти согласно состоянию синтаксического анализатора. Как я сказал в каждом операторе выбора, состояние синтаксического анализатора могло бы измениться, при этом предшествующее состояние было бы продвинуто на стек. Затем в конце оператора переключения, если бы состояние сказало, что я только что закончил анализировать атом, и было незаконченное соединение, я переместил бы просто проанализированный атом в 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. Синтаксический анализ. Это позволяет мне анализировать вещи как" <" в перечисление значений. Предположим, что Вы определяете свои перечисления как это:

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

Обычно Перечисление. Синтаксический анализ ищет символьное имя перечисления значений, и <не допустимое символьное имя. EnumUtil. Синтаксический анализ () ищет вещь в описании. Код похож на это:

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. Синтаксический анализ () вещь от где-то в другом месте. Возможно, здесь?

Выезд ANTLR. Вы определяете синтаксис языка, тестируете его с помощью инструмента GUI и генерируете исходный код во множестве языков. Открытый исходный код.

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

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

Я рекомендовал бы книгу, Создающую Небольшие Языки. Это берет Вас через многие основы компилятора, необходимые для того, чтобы выполнить эту задачу правильно.

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

Выбор затем состоял бы в том, использовать ли Парсер-генератор как ANTLR, или записать тот с нуля.