tengo una aplicación que necesita para permitir a los usuarios escribir expresiones similares para sobresalir:Escribir un mini-lenguaje
(H1 + (D1/C3)) * I8
y más complejas cosas como
If (H1 = 'Verdadero', D3 * .2, D3 * .5)
Solo puedo hacer mucho con las expresiones regulares. Cualquier sugerencia sobre el enfoque correcto para hacer esto, así como cualquier recurso del que pueda aprender sería muy apreciada.
Gracias!
Algunos otra pregunta, encontrará consejos en:
Buena suerte!
Tengo un contraejemplo de cómo no para hacerlo: Will o’ the Wisp (dado que este es mi código, me siento seguro de criticarlo).
¿Qué es bien sobre el Código?
¿Qué hay de malo sobre el código?
I lea en el libro Patrones de diseño el patrón de intérprete debe usarse con cuidado. Entonces, ¿estás de acuerdo con eso? – OscarRyz
No recuerdo ese pasaje de GoF y desafortunadamente le presté mi copia a un amigo, así que no puedo verificarlo ahora. De hecho, me gusta el patrón porque es fácil y poderoso. Por otro lado, si se usa sin cuidado, puede incurrir en una sobrecarga, consulte mi proyecto de ejemplo. ;-) –
Tener un vistazo a este proyecto de código abierto:
cuando se enfrentan a una situación similar - la necesidad de manejar expresiones de una sola línea cortos - Escribí un analizador. 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, podría decirse 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 (p. Ej., 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 posibles valores varían según el atributo también.
Para analizar, divido la cadena en espacios 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 un regex.Replace().
La salida de la división es una matriz de tokens. A continuación, el análisis se produce en un ciclo for grande con un interruptor en el valor del atributo del lado izquierdo. Con cada vuelta del ciclo, estaba listo para sorber un grupo de fichas. Si el primer token era un paren abierto, entonces el grupo solo tenía una longitud simbólica: el paren mismo. Para los tokens que eran nombres conocidos, mis valores de atributo, el analizador tuvo que sorber 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 arroja una excepción. Basado en la secuencia de tokens, el estado del analizador cambiaría. Una conjunción (Y, O, XOR) significaba empujar al átomo anterior a una pila, y cuando el siguiente átomo estaba terminado, explotaba el átomo anterior y unía esos dos átomos en un átomo compuesto. Y así. La administración del estado sucedió 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 se simplifica, solo un poco. Pero la idea es que cada declaración de caso es bastante simple. Es fácil de analizar en una unidad atómica de la expresión. La parte difícil fue unirlos a todos apropiadamente.
Ese truco se llevó a cabo en la sección de limpieza, al final de cada slurp-loop, usando la pila de estado y la pila de átomos. Diferentes cosas pueden suceder de acuerdo con el estado del analizador. Como dije, en cada declaración de caso, el estado del analizador puede cambiar, y el estado previo se puede insertar en una pila. Luego, al final de la instrucción switch, si el estado decía que acababa de analizar un átomo, y que había una conjunción pendiente, movería el átomo recién 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 pedacito de magia era el EnumUtil.Parse. Eso me permite analizar cosas como "<" en un valor enum. Suponga 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 de enumeración, 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 de EnumUtil.Parse() desde otro lugar. ¿Tal vez aquí?
Puede usar el compilador .NET JScript, o la interfaz con IronPython, IronRuby o IronScheme (nombrado alfabéticamente, no preferencia, p).
Un pequeño analizador sintáctico de descenso recursivo es perfecto para esto. Probablemente ni siquiera tengas que construir un árbol de análisis sintáctico; puedes hacer la evaluación a medida que analizas.
/* 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 incorporación de operadores con niveles intermedios de precedencia.
Hacer la afirmación "if" es un poco más complicado.Cada rutina de análisis necesita un argumento de "habilitación" adicional, por lo que no realiza ningún cálculo a menos que esté habilitado. A continuación, analiza la palabra "si", analiza la expresión de prueba y luego analiza las dos expresiones de resultado, con la desactivada desactivada.
Echa un vistazo ANTLR. Usted define una sintaxis de lenguaje, la prueba usando una herramienta GUI y genera código fuente en una variedad de idiomas. Fuente abierta.
No recomendaría ANTLR para proyectos muy pequeños, ya que es una herramienta muy pesada que produce analizadores muy sofisticados que, a su vez, son muy pesados. –
Incluso si no usa ANTLR para producir el analizador sintáctico, es una herramienta excelente para ayudar a definir y probar una gramática. Manipulé cosas muy simples, pero creo que conozco muchas de las trampas (ya que he caído en la mayoría de ellas :-()) Para cosas complejas es un pan comido –
Recomendaría el libro Constructing Little Languages. Le lleva a través de muchos fundamentos de compilación 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. Al igual que otros han dicho, un Recursive Descent Parser hará el truco.
La opción siguiente sería si usar Parser Generator como ANTLR, o escribir uno desde cero.
me recomiendan para buscar en el trabajo/FunCalc CoreCalc: http://www.itu.dk/people/sestoft/funcalc/
He usado su gramática para el generador de análisis COCO \ R en la producción y funciona muy rápido.
Todo lo que necesita hacer es: 1. get sobresalir gramática de corecalc coco.exe 2. ejecutan en él (genera analizador de expresiones similar a Excel) 3. traducir árbol de expresión de notación polaca inversa 4. calc simple
¿Desea compilar el código para el CLR? Ese parece un objetivo razonable para un DSL. – MSalters
Esta es una tarea bastante difícil (para interpretar esos tipos de funciones). Dirigirse al CLR no necesariamente lo hará más fácil ... –
posible duplicado de [Aprender a escribir un compilador] (http://stackoverflow.com/questions/1669/learning-to-write-a-compiler) –