6

我在今年的假期里感到无聊,随机决定为 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");

显然表达式解析不是我最擅长的领域,我在解析嵌套/多个条件时遇到了麻烦。有人知道我可能会觉得有帮助的一些资源/文献吗?

目前,我只有从 String 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);
4

3 回答 3

5

基本上,您需要的是表达式的递归下降解析器。这是编译器理论中的一个重要主题,因此任何有关编译器的书籍都将涵盖该主题。在正式的语法术语中,它看起来像这样:

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-17T08:01:51.077 回答
1

感谢所有提示的家伙。我认为其中大部分都超出了我的需要,所以我最终将其正则表达式以将内容放入可管理的组中,我可以轻松地在 20-30 行代码中解析。

我已经得到了字符串 LambdaExpression 接口的工作几乎和流畅的接口一样,只有一两个小错误。

我可能会继续开发它只是为了好玩,但它显然太低效而无法真正使用,因为它大约 90% 是基于反射的。

于 2010-01-21T04:53:58.153 回答
1

要添加到 cletus 答案,您首先要定义您的语法。

以下表达式语法在大多数情况下工作得很好,不幸的是,正常的递归下降不允许您在每个产生式中首先定义递归部分。这将导致您递归调用生产方法,直到出现堆栈溢出。

        orexpr ::= orexpr '|' 和表达式  
                  | 和表达式  

        andexpr ::= andexpr '&' 比较
                   | 比较

        比较 ::= addexpr compareOp addexpr
                     | addexpr

        addexpr ::= addexpr '+' mulexpr
                   | addexpr '-' 多路数
                   | 多路复用器

        mulexpr ::= mulexpr '*' 值
                   | mulexpr '/' 值
                   | mulexpr '%' 值
                   | 价值

        值 ::= 整数
                   | 漂浮
                   | 多变的
                   | 引述
                   | '(' orexpr ')'

正常递归下降需要您定义 mulexpr,例如:

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

但是这个语法的问题是表达式树的构建方式是你的操作顺序都是相反的。

妥协:在上面写的原始语法上反向使用递归下降。从右到左解析表达式。从右到左构建你的树。它将保留操作的顺序。

在递归下降中,您通常为每个产生式编写一个解析方法。parseOr() 方法可能如下所示:

私人 MyExpression parseOr(MyScanner 扫描仪) {
        MyExpression 表达式 = null;

        MyExpression rightExpr = parseAnd(scanner);
        令牌令牌 =scanner.getCurrentToken();
        if (token.hasValue("|") {
            表达式 = 新的 MyExpression();
            表达式.setOperator(OR);
            令牌 nextToken =scanner.getNextToken(); // 记住,这是反向扫描
            MyExpression leftExpression = parseOr(scanner);
            表达式.setLeft(leftExpression);
            表达式.setRight(rightExpression);
        }
        别的 {
            表达式 = 右表达式;
        }
        返回表达式;
    }

于 2010-01-17T08:34:25.293 回答