字符串表達式解析技巧？

今年假期我很無聊，隨機決定爲Java寫一個簡單的列表理解/過濾庫（我知道那裏有一些很棒的列表，我只是想把它寫成我的自我）。字符串表達式解析技巧？

對於這個列表：

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

語法是：

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

我知道它的醜陋，但如果我使用靜態導入和使用較短的方法名就變得非常簡潔。

以下語法是終極目標：

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

顯然表達分析是不是我與解析嵌套/多條件語句最強的區域，有IM麻煩。任何人都知道我可能會找到一些有用的資源/文獻？

我只有一個條件表達式正在從字符串lambda語法成功解析："x=> x.Name == Jack"。我的底層表達式結構相當穩固，可以輕鬆處理任意數量的嵌套，問題僅僅是從字符串解析表達式。

感謝

只是踢，這裏是一個小的洞察力，以幕後表達結構如何工作（顯然我可以指定「op.GreaterEqual」，等等......在下面的例子中，但我想證明它是如何靈活地嵌套的任何金額）：

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

來源

2010-01-17 jdc0589

''x => x.Age> = 21＆x.Age <= 50「'對我沒有很好的解析：你能說清楚嗎？在'＆'前面有三個表達式，這與vanilla sql style子句非常不同。 – Chii 2010-01-17 08:04:42

我不打算寫一個提供程序將我的實用程序鏈接到關係數據庫，儘管它可能很有趣。到底你在問我詳細說明一下？ – jdc0589 2010-01-17 08:14:17

@Chii：我認爲，「x => x.Age> = 21＆x.Age <= 50」相當於一個匿名函數，它接受一個參數x，並通過計算右邊的表達式來返回true或false '=>'操作符。 – MAK 2010-01-17 09:14:17

基本上你會希望是表達式recursive descent parser。這是編譯器理論中的一個主題，因此任何關於編譯器的書都將涵蓋這個主題。在正式的語法方面，它會是這個樣子：

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

語法上面是ANTLR形式（主要）作爲我最熟悉的。

解析布爾或算術表達式是處理解析時的經典介紹性主題，所以您應該能夠找到大量關於它的文獻。如果你想追求ANTLR（因爲你使用Java），我強烈建議閱讀The Definitive ANTLR Reference: Building Domain-Specific Languages。

如果所有這些看起來像是過度殺傷，並且所有這些都有可能讓你接受，那麼你可能是對的。這是一個艱難的話題開始在你有

一個替代方案是不是創造一個任意的字符串表達式，而是使用一個流暢的界面（像你這樣做）。

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

，因爲這是說明代碼中的表達式樹應該更容易實現。

來源

2010-01-17 08:01:51 cletus

我想這就是我將要研究的領域。感謝一堆，至少我現在有一個起點。 – jdc0589 2010-01-17 08:16:55

我並不是說我目前的實現已經完成，但它可以處理我迄今爲止能夠拋出的任何東西。儘管它需要效率方面的一些工作。我真的認爲，通過字符串實現（這將被解析爲現在使用的完全相同的基礎表達式結構），我認爲減少冗長到我將會滿意的唯一方法就是通過字符串實現。 – jdc0589 2010-01-17 08:48:55

要添加到cletus答案，您將首先要定義您的語法。

對於大多數情況，下面的表達式語法工作得非常好，不幸的是，正常的遞歸下降不允許您在每個生產中首先定義遞歸部分。這會導致您遞歸調用生產方法，直到出現堆棧溢出。

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

普通遞歸下降將要求您定義mulexpr，例如：

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

但有了這個語法的問題是，表達式樹將被建立在這樣一種方式，你的訂單操作將全部相反。

妥協：在上面編寫的原始語法中使用遞歸下降。從右向左分析表達式。從右向左構建你的樹。它將保持操作的順序。

在遞歸下降中，您通常會爲每個生產編寫一個解析方法。 parseOr（）方法可能如下所示：

 
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; 
    }

來源

2010-01-17 08:34:25 rayd09

感謝所有的提示傢伙。我決定大部分這樣做比我需要的多，所以我最終把它搞亂了，把事情搞到可管理的組中，我可以很容易地解析20-30行代碼。

我得到了字符串LambdaExpression接口工作差不多以及流暢的接口，只有一個或兩個小錯誤。

爲了好玩，我可能會繼續開發它，但它顯然效率太低，不能真正使用，因爲它基於90％的反射。

來源

2010-01-21 04:53:58 jdc0589

字符串表達式解析技巧？

回答

相關問題