Советы по разбору выражения строки? - PullRequest
Новая
       24

Советы по разбору выражения строки?

6 голосов
/ 17 января 2010

Мне стало скучно во время курортного сезона в этом году, и я случайно решил написать простую библиотеку для понимания и фильтрации списков для 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");

Очевидно, синтаксический анализ выражений - не самая сильная моя область, у меня проблемы с анализом вложенных / множественных условных выражений. Кто-нибудь знает о некоторых ресурсах / литературе, которые могут оказаться полезными для меня?

Я получил только одно условное выражение, которое в данный момент успешно анализируется из строкового лямбда-синтаксиса: "x=> x.Name == Jack". Моя базовая структура Expression довольно прочная и может легко обрабатывать любое количество вложений, проблема заключается только в анализе синтаксического выражения из строки.

Спасибо

Для простоты, вот небольшое понимание того, как может работать структура выражения за кулисами (очевидно, я мог бы указать «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);

Ответы [ 3 ]

5 голосов
/ 17 января 2010

В основном вам нужен синтаксический анализатор рекурсивного спуска для выражений. Эта тема широко обсуждается в теории компиляторов, поэтому любая книга по компиляторам будет освещать эту тему. В формальной грамматике это будет выглядеть примерно так: 

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), я настоятельно рекомендую прочитать Полное руководство по ANTLR: построение доменных языков .

Если все это выглядит как излишнее и слишком много, вы можете быть правы. Это сложная тема для начала.

Один из вариантов, который у вас есть, - не создавать произвольное строковое выражение, а вместо этого использовать свободный интерфейс (как вы делаете): 

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

, поскольку это указывает на дерево выражений в коде и должно быть проще в реализации.

1 голос
/ 21 января 2010

Спасибо за все советы, ребята. Я решил, что большая часть этого была намного больше, чем мне было нужно, и в итоге я перевыполнил это до чертиков, чтобы привести вещи в управляемые группы, которые я мог бы легко проанализировать в 20-30 строках кода.

У меня есть интерфейс строки LambdaExpression, работающий почти , а также свободный интерфейс, всего одна или две небольшие ошибки.

Я, вероятно, буду продолжать его немного развлекать, но, очевидно, он слишком неэффективен, чтобы его реально использовать, поскольку он основан на отражении около 90%.

1 голос
/ 17 января 2010

Чтобы добавить в ответ 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;
    }
...