Escribir un mini idioma
https://stackoverflow.com/questions/615040
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Tengo una aplicación que debe permitir a los usuarios escribir expresiones similares a Excel:
(H1 + (D1 / C3)) * I8
y cosas más complejas como
If (H1 = 'Verdadero', D3 * .2, D3 * .5)
Solo puedo hacer mucho con expresiones regulares. Cualquier sugerencia sobre el enfoque correcto para hacer esto, así como cualquier recurso del que pueda aprender sería muy apreciada.
¡Gracias!
Solución
Alguna otra pregunta, encontrará sugerencias en:
- ¿Cómo escribir un lenguaje de programación?
- Aprendiendo a escribir un compilador
- Escribir un compilador para un DSL en python
¡Buena suerte!
Otros consejos
Cuando me enfrento a una situación similar, la necesidad de manejar expresiones cortas de una línea, escribí un analizador sintáctico. Las expresiones eran lógica booleana, de la forma
n1 = y and n2 > z
n2 != x or (n3 > y and n4 = z)
y así sucesivamente. En inglés se podría decir que hay átomos unidos por AND y OR, y cada átomo tiene tres elementos: un atributo del lado izquierdo, un operador y un valor. Debido a que fue tan sucinto, creo que el análisis fue más fácil. El conjunto de atributos posibles es conocido y limitado (por ejemplo, nombre, tamaño, tiempo). Los operadores varían según el atributo: diferentes atributos toman diferentes conjuntos de operadores. Y el rango y el formato de los valores posibles también varían según el atributo.
Para analizar, dividí la cadena en el espacio en blanco usando String.Split (). Más tarde me di cuenta de que antes de Split (), necesitaba normalizar la cadena de entrada, insertando espacios en blanco antes y después de parens. Lo hice con una expresión regular. Reemplazar ().
La salida de la división es una matriz de tokens. Luego, el análisis se produce en un bucle for grande con un interruptor en el valor del atributo del lado izquierdo. Con cada vuelta del circuito, estaba listo para sorber en un grupo de fichas. Si la primera ficha era un par abierto, entonces el grupo tenía solo una ficha de longitud: el par mismo. Para los tokens que eran nombres conocidos, mis valores de atributo, el analizador tuvo que sorber en un grupo de 3 tokens, uno para el nombre, el operador y el valor. Si en algún momento no hay suficientes tokens, el analizador lanza una excepción. Según el flujo de tokens, el estado del analizador cambiaría. Una conjunción (AND, OR, XOR) significaba empujar el átomo anterior a una pila, y cuando el siguiente átomo estaba terminado, hacía estallar el átomo anterior y unía esos dos átomos en un átomo compuesto. Y así. La gestión del estado se produjo al final de cada ciclo del analizador.
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
}
Eso está simplificado, solo un poco. Pero la idea es que cada declaración de caso es bastante simple. Es fácil analizar en una unidad atómica de la expresión. La parte difícil era unirlos a todos apropiadamente.
Ese truco se logró en la sección de limpieza, al final de cada bucle sorbo, usando la pila de estado y la pila de átomos. Pueden ocurrir cosas diferentes según el estado del analizador. Como dije, en cada enunciado de caso, el estado del analizador podría cambiar, y el estado anterior sería empujado a una pila. Luego, al final de la declaración de cambio, si el estado decía que acababa de analizar un átomo y había una conjunción pendiente, movería el átomo analizado al CompoundAtom. El código se ve así:
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);
}
El otro trozo de magia fue el EnumUtil.Parse. Eso me permite analizar cosas como & Quot; & Lt; & Quot; en un valor enum. Supongamos que define sus enumeraciones de esta manera:
internal enum Operator
{
[Description(">")] GreaterThan,
[Description(">=")] GreaterThanOrEqualTo,
[Description("<")] LesserThan,
[Description("<=")] LesserThanOrEqualTo,
[Description("=")] EqualTo,
[Description("!=")] NotEqualTo
}
Normalmente Enum.Parse busca el nombre simbólico del valor enum, y < No es un nombre simbólico válido. EnumUtil.Parse () busca la cosa en la descripción. El código se ve así:
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);
}
}
Obtuve esa cosa EnumUtil.Parse () de otro lugar. ¿Tal vez aquí?
Un pequeño analizador de descenso recursivo es perfecto para esto. Probablemente ni siquiera tenga que construir un árbol de análisis: puede hacer la evaluación mientras analiza.
/* 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;
}
Ahora, si solo llama a ParseTop, calculará el valor de una expresión para usted.
El motivo de la macro PARSE_HIGHER es facilitar la adición de operadores en niveles intermedios de precedencia.
Para hacer " if " declaración es un poco más complicado. Cada rutina de análisis necesita un & Quot; enable & Quot; argumento, por lo que no hace ningún cálculo a menos que esté habilitado. Luego analiza la palabra & Quot; if & Quot ;, analiza la expresión de prueba y luego analiza las dos expresiones de resultado, con la inactiva desactivada.
Puede usar el compilador .NET JScript o la interfaz con IronPython, IronRuby o IronScheme (nombrado alfabéticamente, no preferencia; p).
Tengo un contraejemplo de cómo no hacerlo: Will o & # 8217; el Wisp (ya que este es mi propio código, confío en criticarlo)
¿Qué es bueno sobre el Código?
- Utiliza un patrón de diseño en consecuencia: El patrón de intérprete
- Tiene un diseño bastante limpio
- Utiliza atributos de una manera agradable.
- Produce buenos gráficos. ;-)
¿Qué es malo sobre el código?
- ¡Es lento !
- El lenguaje está mal definido con respecto a las listas (datos versus código).
Consulte ANTLR . Defina una sintaxis de idioma, pruébela utilizando una herramienta GUI y genere código fuente en una variedad de idiomas. Código abierto.
Recomendaría el libro Construyendo pequeños idiomas . Le lleva a través de muchos conceptos básicos del compilador necesarios para completar esta tarea correctamente.
Has mencionado el hecho de que las expresiones regulares no funcionarán a menos que tengas algunos límites estrictos en tu idioma. Como otros han dicho, un Recursive Descent Parser hará el truco.
La siguiente opción sería si usar un Parser Generator como ANTLR , o escribir uno desde cero.
Echa un vistazo a este proyecto de código abierto:
Recomiendo mirar el trabajo de CoreCalc / FunCalc: http://www.itu.dk/people/sestoft/funcalc/
He usado su gramática para el generador de analizadores COCO \ R en producción y funciona muy rápido.
Todo lo que necesitas hacer es: 1. obtener la gramática de excel de corecalc 2. ejecute coco.exe en él (genera un analizador para expresiones similares a Excel) 3. traducir el árbol de expresión a la notación polaca inversa 4. calc simple
