Écrire une mini-langue
https://stackoverflow.com/questions/615040
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai une application qui doit permettre aux utilisateurs d'écrire des expressions similaires à Excel:
(H1 + (D1 / C3)) * I8
et des choses plus complexes comme
Si (H1 = 'Vrai', D3 * .2, D3 * .5)
Je ne peux pas en faire autant avec les expressions régulières. Toute suggestion quant à la bonne approche à adopter ainsi que toutes les ressources pour lesquelles je peux apprendre serait très appréciée.
Merci!
La solution
Autre question, vous trouverez des astuces dans:
- Comment écrire un langage de programmation?
- Apprendre à écrire un compilateur
- Écrire un compilateur pour un DSL en python
Bonne chance!
Autres conseils
Face à une situation similaire - la nécessité de gérer des expressions courtes d'une ligne - j'ai écrit un analyseur. Les expressions étaient de la logique booléenne, de la forme
n1 = y and n2 > z
n2 != x or (n3 > y and n4 = z)
et ainsi de suite. En anglais, vous pouvez dire qu'il y a des atomes reliés par AND et OR, et que chaque atome a trois éléments: un attribut de gauche, un opérateur et une valeur. Parce que c'était si succinct je pense que l'analyse a été plus facile. L'ensemble des attributs possibles est connu et limité (par exemple: nom, taille, heure). Les opérateurs varient selon les attributs: différents attributs prennent différents ensembles d'opérateurs. Et la plage et le format des valeurs possibles varient également en fonction des attributs.
Pour analyser, je divise la chaîne en blanc à l'aide de String.Split (). J'ai par la suite réalisé qu'avant Split (), je devais normaliser la chaîne d'entrée, en insérant des espaces avant et après les parenthèses. Je l'ai fait avec un regex.Replace ().
La sortie de la division est un tableau de jetons. Ensuite, l'analyse se produit dans une grande boucle for avec un commutateur sur la valeur d'attribut de gauche. À chaque tour de la boucle, je devais glisser dans un groupe de jetons. Si le premier jeton était un paren ouvert, le groupe n'avait alors qu'un seul jeton: le paren lui-même. Pour les jetons qui étaient des noms connus - mes valeurs d'attribut -, l'analyseur devait scinder dans un groupe de 3 jetons, un pour le nom, l'opérateur et la valeur. S'il n'y a pas assez de jetons à un moment donné, l'analyseur lève une exception. En fonction du flux de jetons, l'état de l'analyseur changerait. Une conjonction (AND, OR, XOR) signifiait pousser l'atome précédent sur une pile, et lorsque l'atome suivant était fini, je sautais l'atome précédent et joignais ces deux atomes en un atome composé. Etc. La gestion de l’état s’est produite à la fin de chaque boucle de l’analyseur.
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
}
C'est simplifié, juste un peu. Mais l'idée est que chaque déclaration de cas est assez simple. Il est facile d'analyser une unité atomique de l'expression. La partie délicate consistait à les réunir correctement.
Cette astuce a été accomplie dans la section d’entretien, à la fin de chaque boucle slurp, en utilisant la pile d’états et la pile d’atomes. Différentes choses peuvent se produire selon l'état de l'analyseur. Comme je l'ai dit, dans chaque déclaration de cas, l'état de l'analyseur peut changer, l'état précédent étant mis sur une pile. Puis, à la fin de l'instruction switch, si l'État disait que je venais juste d'analyser un atome et qu'il y avait une conjonction en attente, je déplacerais l'atome analysé dans CompoundAtom. Le code ressemble à ceci:
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’autre partie de la magie était EnumUtil.Parse. Cela me permet d’analyser des choses comme & «; & Lt; &»; dans une valeur enum. Supposons que vous définissiez vos enums comme ceci:
internal enum Operator
{
[Description(">")] GreaterThan,
[Description(">=")] GreaterThanOrEqualTo,
[Description("<")] LesserThan,
[Description("<=")] LesserThanOrEqualTo,
[Description("=")] EqualTo,
[Description("!=")] NotEqualTo
}
Normalement, Enum.Parse recherche le nom symbolique de la valeur enum et < n'est pas un nom symbolique valide. EnumUtil.Parse () recherche la chose dans la description. Le code ressemble à ceci:
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);
}
}
J'ai eu ce truc EnumUtil.Parse () ailleurs. Peut-être ici?
Un petit analyseur récursif-descendant est parfait pour cela. Vous n’avez probablement même pas besoin de créer un arbre d’analyse syntaxique - vous pouvez effectuer l’évaluation à mesure que vous analysez.
/* 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;
}
Maintenant, si vous appelez simplement ParseTop, il calculera la valeur d'une expression pour vous.
La macro PARSE_HIGHER a pour but de faciliter l'ajout d'opérateurs aux niveaux de priorité intermédiaires.
Pour faire le " si " La déclaration est un peu plus compliquée. Chaque routine d'analyse nécessite un & Quotile supplémentaire; activer & Quot; argument, donc il ne fait aucun calcul à moins que ce soit activé. Ensuite, vous analysez le mot & "If &"; Analysez l'expression de test, puis analysez les deux expressions de résultat, l'expression inactive étant désactivée.
Vous pouvez utiliser le compilateur .NET JScript ou une interface avec IronPython, IronRuby ou IronScheme (nommé par ordre alphabétique, pas de préférence; p).
J'ai un exemple qui explique comment ne pas le faire: Will o & # 8217; le Wisp (comme il s'agit de mon propre code, je suis confiant de le critiquer).
En quoi le bien sur le code?
- Il utilise un motif de conception en conséquence: Le motif interprète
- Son design est plutôt épuré
- Il utilise les attributs de manière agréable.
- Cela produit de jolis graphismes. ; -)
En quoi le code est-il mauvais ?
- C'est lent !
- La langue est mal définie en ce qui concerne les listes (données vs code).
Découvrez ANTLR . Vous définissez une syntaxe de langue, testez-la à l'aide d'un outil graphique et générez le code source dans différentes langues. Open Source.
Je recommanderais le livre Construire de petits langages . Il vous explique les bases du compilateur nécessaires pour mener à bien cette tâche.
Vous avez évoqué le fait que les expressions régulières ne fonctionneraient pas si vous ne définissiez pas de limites strictes dans votre langue. Comme d’autres l’ont dit, un un analyseur de descente récursif fera l'affaire.
Ensuite, vous devrez choisir un générateur d'analyseur de contenu , comme ANTLR , ou pour en écrire un de toutes pièces.
Découvrez ce projet open source:
Je recommande de regarder le travail sur CoreCalc / FunCalc: http://www.itu.dk/people/sestoft/funcalc/
J'ai utilisé leur grammaire pour le générateur d'analyseur COCO \ R en production et cela fonctionne très rapidement.
Tout ce que vous devez faire est de: 1. obtenir la grammaire excel de corecalc 2. lancer coco.exe dessus (génère un analyseur syntaxique pour les expressions de type Excel) 3. traduire l'arbre d'expression pour inverser la notation polonaise 4. calcul simple
