Wskazówki do parsowania wyrażenia ciągu?

Question

Nudziłem się podczas sezonu wakacyjnego w tym roku i losowo zdecydowałem się napisać prostą bibliotekę ze zrozumieniem/filtrowaniem list dla Javy (wiem, że jest tam kilka świetnych rzeczy, po prostu chciałem napisać to dla siebie, do diabła) .

Na tej liście:

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

Składnia jest następująca:

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

znam jej brzydki, ale jeśli mogę użyć importu statyczne i używać krótszych nazwy metod staje się dość zwięzłe.

Poniższa składnia jest ostatecznym celem:

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

Widocznie parsowania wyrażenie nie jest moją najsilniejszą obszar, im kłopoty z analizowania zagnieżdżone/wielokrotny warunkowe. Czy ktoś zna jakieś zasoby/literaturę, które mogą okazać się pomocne?

Mam tylko pojedyncze wyrazy warunkowe, które zostały pomyślnie przetworzone z String składni lambda w tej chwili: "x=> x.Name == Jack". Moja podstawowa struktura Wyrażenia jest dość solidna i może z łatwością obsłużyć dowolną ilość zagnieżdżania, problemem jest tylko parsowanie wyrażenia z ciągu znaków.

Dzięki

tylko dla zabawy, tutaj jest trochę wgląd w jaki sposób struktura wyrażenie za kulisami mogą pracować (oczywiście mógłbym określić „op.GreaterEqual”, itp ... w poniższym przykładzie, ale chciałem pokazać, jak to jest elastyczna do dowolnej ilości zagnieżdżenia):

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

zasadzie to, co będziemy chcieli to recursive descent parser dla wyrażeń. Jest to temat w dużym stopniu oparty na teorii kompilacji, więc każda książka na temat kompilatorów omówi ten temat. W sformalizowanych zasadach gramatycznych będzie to wyglądać mniej więcej tak:

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  : '>' | '>=' | '<' | '<=' | '=' | '!=' ; 

Gramatyka powyżej jest (w większości) w ANTLR formie, że to, co mi najbardziej znane.

Analizowanie wyrażeń o charakterze boolowskim lub arytmetycznym jest klasycznym tematem wprowadzającym podczas analizowania składni, więc powinieneś być w stanie znaleźć w nim mnóstwo literatury. Jeśli chcesz zastosować ANTLR (ponieważ używasz Javy), gorąco polecam lekturę The Definitive ANTLR Reference: Building Domain-Specific Languages.

Jeśli wszystko to wygląda na przesadę i wszystko, co należy wziąć pod uwagę, możesz mieć rację. To trudny temat, aby zacząć w

Jedną z alternatyw masz nie jest stworzenie dowolnego wyrażenie łańcuchowe ale zamiast używać biegle interfejs (jak robisz).

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

jak to stwierdzając drzewo wyrażeń w kodzie i powinno być łatwiejsze do wdrożenia.

Answer 2

Aby dodać do odpowiedzi na telefon, najpierw musisz zdefiniować gramatyk.

Poniższe wyrażenie grammer działa całkiem dobrze w większości przypadków, niestety normalne rekurencyjne zejście nie pozwala zdefiniować rekursywną część pierwsza w każdej produkcji.Spowoduje to, że będziesz wywoływał metodę rekursywną, dopóki nie uzyskasz przepełnienia stosu.

 
     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 ')' 

Normal rekurencyjne zejście wymagałoby zdefiniowanie mulexpr, na przykład jako:

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

Ale problem z tym Grammer jest to, że drzewo wyrażenie zostanie zbudowana w taki sposób, że zamówienie z wszystkie operacje będą odwrotne.

Kompromis: używaj rekursywnego zniżania w odwrotnej kolejności na oryginalnym gramacie opisanym powyżej. Przetwórz wyrażenie od prawej do lewej. Twórz drzewo od prawej do lewej. Zachowa kolejność operacji.

W rekurencyjnym zejściu zwykle piszemy metodę parse dla każdej produkcji. Metoda parseOr() może wyglądać następująco:

 
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

Dzięki za wszystkie napiwki. Zdecydowałem, że większość z tego jest o wiele bardziej niż potrzebna, więc skończyło się na tym, że wróciłem do tego, by dostać się do łatwych do opanowania grup, które z łatwością przetworzyłbym w 20-30 liniach kodu.

Dostałem ciąg LambdaExpression interfejs działa prawie, a także płynny interfejs, tylko jeden lub dwa małe błędów.

Prawdopodobnie będę go rozwijał trochę tylko dla zabawy, ale oczywiście jest zbyt nieefektywny, aby go użyć, ponieważ opiera się na 90% odbiciu.