La scrittura di un mini-lingua

https://stackoverflow.com/questions/615040

03-07-2019
|

Domanda

Ho un'applicazione che deve consentire agli utenti di scrivere espressioni simili a excel:

(H1 + (D1 / C3) * I8

e cose più complesse come

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

Posso solo fare così tanto con le espressioni regolari.Eventuali suggerimenti per l'approccio giusto per fare questo, come anche tutte le risorse che posso imparare da sarebbe molto apprezzato.

Grazie!

Soluzione

Qualche altra domanda, troverai suggerimenti in:

Buona fortuna!

Altri suggerimenti

Di fronte a una situazione simile - la necessità di gestire brevi espressioni di una riga - ho scritto un parser. Le espressioni erano logiche booleane, nella forma

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

e così via. In inglese potresti dire che ci sono atomi uniti da AND e OR, e ogni atomo ha tre elementi: un attributo sul lato sinistro, un operatore e un valore. Perché era così succinto penso che l'analisi fosse più semplice. L'insieme di possibili attributi è noto e limitato (ad esempio: nome, dimensione, tempo). Gli operatori variano in base all'attributo: attributi diversi accettano insiemi di operatori diversi. E anche l'intervallo e il formato dei possibili valori variano in base all'attributo.

Per analizzare, ho diviso la stringa su spazi bianchi usando String.Split (). In seguito mi sono reso conto che prima di Split (), dovevo normalizzare la stringa di input - inserendo spazi bianchi prima e dopo le parentesi. L'ho fatto con un regex.Replace ().

L'output della divisione è un array di token. Quindi l'analisi si verifica in un grande ciclo for con un interruttore sul valore dell'attributo sul lato sinistro. Ad ogni giro del circuito, ero pronto a bere un gruppo di token. Se il primo token era un open-paren, allora il gruppo era solo un token di lunghezza: il paren stesso. Per i token che erano nomi noti - i miei valori di attributo - il parser ha dovuto digerire in un gruppo di 3 token, uno ciascuno per il nome, l'operatore e il valore. Se in qualsiasi momento non ci sono abbastanza token, il parser genera un'eccezione. In base al flusso di token, lo stato del parser cambierebbe. Una congiunzione (AND, OR, XOR) intendeva spingere l'atomo precedente su una pila, e quando l'atomo successivo era finito, farei scoppiare l'atomo precedente e unire quei due atomi in un atomo composto. E così via. La gestione dello stato è avvenuta alla fine di ogni ciclo del parser.

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

}

È semplificato, solo un po '. Ma l'idea è che ogni affermazione del caso sia abbastanza semplice. È facile analizzare in un'unità atomica dell'espressione. La parte difficile è stata unirli tutti insieme in modo appropriato.

Quel trucco è stato compiuto nella sezione delle pulizie, alla fine di ogni slurp-loop, usando la pila di stato e la pila di atomi. Diverse cose possono accadere in base allo stato del parser. Come ho detto, in ogni istruzione del caso, lo stato del parser potrebbe cambiare, con lo stato precedente inserito in uno stack. Quindi alla fine dell'istruzione switch, se lo stato dicesse che avevo appena finito di analizzare un atomo, e c'era una congiunzione in sospeso, avrei spostato l'atomo appena analizzato in CompoundAtom. Il codice è simile al seguente:

            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); 
            }

L'altro pezzo di magia era EnumUtil.Parse. Questo mi permette di analizzare cose come & Quot; & Lt; & Quot; in un valore enum. Supponi di definire i tuoi enum in questo modo:

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

Normalmente Enum.Parse cerca il nome simbolico del valore enum e < non è un nome simbolico valido. EnumUtil.Parse () cerca la cosa nella descrizione. Il codice è simile al seguente:

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);
    }

}

Ho preso quella cosa EnumUtil.Parse () da qualche altra parte. Forse qui?

Un po 'di parser ricorsivo-discendente è perfetto per questo. Probabilmente non dovrai nemmeno costruire un albero di analisi - puoi fare la valutazione mentre analizzi.

 /* 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;
}

Ora se chiami semplicemente ParseTop, calcolerà il valore di un'espressione per te.

Il motivo della macro PARSE_HIGHER è quello di facilitare l'aggiunta di operatori a livelli intermedi di precedenza.

Per fare il " if " dichiarazione è un po 'più coinvolta. Ogni routine di analisi richiede un ulteriore & Quot; abilita & Quot; argomento, quindi non esegue alcun calcolo a meno che non sia abilitato. Quindi si analizza la parola & Quot; if & Quot ;, analizza l'espressione di test e quindi analizza le due espressioni di risultato, con quella inattiva disabilitata.

Si potrebbe utilizzare l' .NET JScript compilatore, o interfaccia con IronPython, IronRuby o IronScheme (nome in ordine alfabetico, non di preferenza ;p ).

Ho un contro-esempio di come non farlo: Will & o # 8217; il Wisp (dato che questo è il mio codice, mi sento sicuro di criticarlo).

Che cosa è buono sul codice?

Utilizza di conseguenza un modello di progettazione: il modello di interprete
Ha un design piuttosto pulito
Utilizza gli attributi in modo piacevole.
Produce una bella grafica. ; -)

Grafica tartaruga http: // i3 ? .codeplex.com / progetto / download / FileDownload.aspx ProjectName = filo amp &; DownloadId = 34823

Che cosa è negativo sul codice?

È lento !
La lingua è mal definita per quanto riguarda gli elenchi (dati vs. codice).

Guarda ANTLR . È possibile definire una sintassi del linguaggio, testarlo utilizzando uno strumento GUI e generare il codice sorgente in una varietà di lingue. Open Source.

Consiglierei il libro Costruire piccole lingue . Ti guida attraverso molte nozioni di base del compilatore necessarie per completare correttamente questa attività.

Hai accennato al fatto che le espressioni regolari non funzioneranno a meno che tu non abbia dei limiti rigorosi nella tua lingua. Come altri hanno già detto, un Recursive Descent Parser farà il trucco.

La scelta successiva sarebbe se usare un Parser Generator come ANTLR , o per scriverne uno da zero.

Dai un'occhiata a questo progetto open source:

Funzioni finanziarie di Excel

Consiglio di guardare al lavoro CoreCalc / FunCalc: http://www.itu.dk/people/sestoft/funcalc/

Ho usato la loro grammatica per il generatore di parser COCO \ R in produzione e funziona molto velocemente.

Tutto quello che devi fare è: 1. ottenere la grammatica Excel da corecalc 2. esegui coco.exe su di esso (genera un parser per espressioni simili a Excel) 3. tradurre l'albero delle espressioni per invertire la notazione polacca 4. calc semplice

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow