Подсказки по парсингу строкового выражения?
Я скучал в течение праздничного сезона в этом году и случайным образом решил записать простую библиотеку понимания/фильтрации списка для 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". Моя базовая структура Выражения довольно тверда и может легко обработать любой объем вложения, проблемой является просто парсинг выражения от строки.
Спасибо
Только для ударов, вот немного понимания относительно того, как структура выражения негласно может работать (очевидно, я, возможно, указал '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 ответа
в основном то, что вы хотите, это Рекурсивный падающий анализатор для выражений. Это тема, которая в значительной степени показана в теории компилятора, поэтому любая книга на компиляторах будет охватывать тему. В формальных условиях грамматики он будет выглядеть что-то подобное:
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");
как то, что делает дерево выражения в коде и должно быть легче реализовать.
Чтобы добавить к ответу 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;
}
Спасибо за все советы, ребята. Я решил, что большая часть этого было больше, чем мне было больше, поэтому я закончил перезвонить, черт возьми, чтобы получить вещи к управляемым группам, которые я мог легко разбирать в 20-30 строк кода.
IVE получил струнную работу интерфейса лямбдаэкспрессии почти , а также беглый интерфейс, только одна или две маленькие ошибки.
Я, вероятно, продолжаю разрабатывать его немного для развлечения, но это, очевидно, слишком неэффективно, чтобы действительно использовать, поскольку его около 90% на основе отражения.