Sugerencias de análisis de expresión de cadena?

Question

Me aburrí durante la temporada de vacaciones de este año y al azar decidí escribir una lista simple de biblioteca de comprensión/filtrado para Java (sé que hay algunos excelentes por ahí, solo quería escribirlo por mi propia cuenta) .

para esta lista:

LinkedList<Person> list = new LinkedList<Person>(); 
      list.add(new Person("Jack", 20)); 
      list.add(new Person("Liz", 58)); 
      list.add(new Person("Bob", 33)); 

sintaxis es:

Iterable<Person> filtered = Query.from(list).where(
    Condition.ensure("Age", Op.GreaterEqual, 21) 
    .and(Condition.ensure("Age", Op.LessEqual, 50)); 

Sé que es feo, pero si uso importaciones estáticos y uso más cortos nombres de los métodos que se convierte en bastante conciso.

La siguiente sintaxis es el objetivo final:

Iterable<Person> list2 = Query.from(list).where("x=> x.Age >= 21 & x.Age <= 50"); 

Al parecer, el análisis de expresión no es mi área más fuerte, estoy teniendo problemas con el análisis de las condiciones anidadas/múltiple. ¿Alguien sabe de algunos recursos/literatura que pueda ser útil?

Solo tengo expresiones condicionales individuales analizadas con éxito desde la sintaxis String lambda en este momento: "x=> x.Name == Jack". Mi estructura de Expresión subyacente es bastante sólida y puede manejar fácilmente cualquier cantidad de anidamiento, el problema es solo la expresión que se analiza desde una cadena.

Gracias

Sólo por diversión, aquí hay una pequeña idea de cómo la estructura de expresión detrás de las escenas puede trabajar (obviamente que podría haber especificado 'op.GreaterEqual', etc ... en el siguiente ejemplo, pero quería demostrar cómo es flexible a cualquier cantidad de anidación):

Condition minAge1 = Condition.ensure("Age", Op.Equal, 20); 
Condition minAge2 = Condition.ensure("Age", Op.Greater, 20); 
Expression minAge = new Expression(minAge1, Express.Or, minAge2); 
Expression maxAge = Condition.ensure("Age", Op.Equal, 50).or(Condition.ensure("Age", Op.Less, 50)); 
Expression ageExpression = new Expression(minAge, Express.And, maxAge); 

Condition randomException = Condition.ensure("Name", Op.Equal, "Liz"); 
Expression expressionFinal = new Expression(ageExpression, Express.Or, randomException); 

Answer 1

Básicamente lo que querrá es una recursive descent parser las expresiones adecuadas. Es un tema destacado en gran medida en la teoría del compilador por lo que cualquier libro sobre compiladores cubrirá el tema. En términos gramaticales formales que se verá algo como esto:

condition : orAtom ('||' orAtom)+ ; 
orAtom  : atom ('&&' atom)+ ; 
atom  : '(' condition ')' 
      | expression ; 
expression : value OPER value ; 
value  : VARIABLE | LITERAL ' 
VARIABLE : (LETTER | '_') (LETTER | DIGIT | '_')* ; 
LITERAL : NUMBER 
      | STRING ; 
NUMBER  : '-'? DIGIT+ ('.' DIGIT+)? ; 
STRING  : '"' . CHAR* . '"' ' 
CHAR  : ('\\' | '\"' | .) + ; 
LETTER  : 'a'..'z' | 'A'..'Z' ; 
DIGIT  : '0'..'9' ; 
OPER  : '>' | '>=' | '<' | '<=' | '=' | '!=' ; 

La gramática anterior es (en su mayoría) en ANTLR forma que la que lo que estoy más familiarizado.

El análisis de expresiones booleanas o aritméticas es un tema introductorio clásico cuando se trata de analizar, por lo que debería poder encontrar mucha literatura sobre él. Si desea realizar ANTLR (ya que está usando Java), le sugiero que lea The Definitive ANTLR Reference: Building Domain-Specific Languages.

Si todo esto parece excesivo y un poco demasiado para asimilar, es posible que tenga razón. Es un tema difícil para iniciarse en

Una de las alternativas que tienes no es para crear una expresión cadena arbitraria, pero en lugar de utilizar una interfaz fluida (como lo está haciendo):.

List results = from(source) 
    .where(var("x").greaterThan(25), var("x").lessThan(50)) 
    .select("field1", "field2"); 

ya que es declarando el árbol de expresiones en el código y debería ser más fácil de implementar.

Answer 2

Para agregar a la respuesta de cletus, primero querrá definir su gramática.

La siguiente gramática de expresión funciona bastante bien para la mayoría de los casos, desafortunadamente, el descenso recursivo normal no le permite definir la parte recursiva primero en cada producción.Esto causaría que llamara al método de producción recursivamente hasta que obtenga un desbordamiento de pila.

 
     orexpr ::= orexpr '|' andexpr 
        | andexpr 

     andexpr ::= andexpr '&' comparison 
        | comparison 

     comparison ::= addexpr compareOp addexpr 
        | addexpr 

     addexpr ::= addexpr '+' mulexpr 
        | addexpr '-' mulexpr 
        | mulexpr 

     mulexpr ::= mulexpr '*' value 
        | mulexpr '/' value 
        | mulexpr '%' value 
        | value 

     value ::= integer 
        | float 
        | variable 
        | quotation 
        | '(' orexpr ')' 

descendente recursivo normal requeriría definir mulexpr, por ejemplo, como:

 
     mulexpr ::= value '*' mulexpr 
        | value '/' mulexpr 
        | value '%' mulexpr 

Pero el problema con esta gramática es que el árbol de expresión se construye de tal manera que su orden de las operaciones serán todas en reversa.

Compromiso: utilice el descenso recursivo inverso en la gramática original escrita anteriormente. Analiza la expresión de derecha a izquierda. Construye tu árbol de derecha a izquierda. Preservará el orden de las operaciones.

En el descenso recursivo generalmente se escribe un método de análisis para cada producción. El método parseOr() podría verse de la siguiente manera:

 
private MyExpression parseOr(MyScanner scanner) { 
     MyExpression expression = null; 

     MyExpression rightExpr = parseAnd(scanner); 
     Token token = scanner.getCurrentToken(); 
     if (token.hasValue("|") { 
      expression = new MyExpression(); 
      expression.setOperator(OR); 
      Token nextToken = scanner.getNextToken(); // remember, this is scanning in reverse 
      MyExpression leftExpression = parseOr(scanner); 
      expression.setLeft(leftExpression); 
      expression.setRight(rightExpression); 
     } 
     else { 
      expression = rightExpression; 
     } 
     return expression; 
    } 

Answer 3

Gracias por todos los consejos chicos. Decidí que la mayor parte de esto era mucho más de lo que necesitaba, así que terminé descomponiéndolo para llevar cosas a grupos manejables que podía analizar fácilmente en 20-30 líneas de código.

Tengo la interfaz LambdaExpression de cadena trabajando casi, así como la interfaz fluida, solo uno o dos pequeños errores.

Probablemente sigamos desarrollándolo un poco solo por diversión, pero obviamente es demasiado ineficiente para usarlo realmente ya que está basado en un 90% de reflexión.