Создание парсера рекурсивного спуска вручную. Это весело!
Сначала определите грамматику:
Expression -> SimpleExpression ExpressionTail
(Expression)
SimpleExpression -> Atom Inequality Atom
ExpressionTail -> && Expression |
|| Expression |
e
Atom -> Variable | Literal
Inequality -> == | != | > | >= | < | <=
(Эта грамматика не обрабатывает приоритет оператора, но легко написать грамматику, которая будет.)
Затем создайте лексический анализатор, который будет читать входную строку и создавать токены, чтобы строка «var1! = 4.0» была преобразована в список {Variable,! =, Literal}. Это может быть взломано вместе, или если вы хотите получить фантазию, вы можете использовать конечный автомат для анализа строки.
Теперь создайте анализатор рекурсивного спуска, чтобы проанализировать список токенов в дереве выражений.
public class Parser {
public Parser() {
}
public Expression parse( LexicalAnalyzer lex) {
lex.advance();
return expression( lex);
}
private Expression expression( LexicalAnalyzer lex) {
switch( lex.current().type() ) {
case Token.OpenParen:
lex.advance();
Expression expression = expression( lex);
lex.eat( Token.CloseParen);
return expression;
case Token.Literal:
case Token.Variable:
return expressionTail( lex, simpleExpression(lex));
default:
throw new Exception( "ParseError: Expecting (, variable, or literal at character " +
lex.character());
}
}
private SimpleExpression simpleExpression( LexicalAnalyzer lex) {
Atom atom = atom( lex);
switch( lex.current().type() ) {
case Token.Equal:
lex.advance();
return new Equal( atom, atom(lex));
case Token.NotEqual:
lex.advance();
return new NotEqual( atom, atom(lex));
...
default:
throw new Exception( "ParseError: Expecting ==, !=, <, <=, >, >= at" +
lex.character());
}
}
private Expression expressionTail( LexicalAnalyzer lex, SimpleExpression expression) {
switch( lex.current().type() ) {
case Token.LogicalOr:
lex.advance();
return new OrExpression( expression, expression(lex) );
case Token.LogicalAnd:
lex.advance();
return new AndExpression( expression, exptression(lex) );
default:
return expression;
}
}
private Atom atom( LexicalAnalyzer lex) {
switch( lex.current().type() ) {
case Token.Literal:
Literal literal = new Literal( lex.current() );
lex.advance();
return literal;
case Token.Variable:
Variable var = new Variable( lex.current() );
lex.advance();
return var;
default:
throw new Exception("ParseError: ...");
}
}
}
public interface Expression {
boolean evaluate( VariableValues values);
}
public interface SimpleExpression implements Expression {
}
public class Equal implements SimpleExpression {
private final Atom left, right;
public Equal( Atom left, Atom right) {
this.left = left;
this.right = right;
}
public boolean evaluate( VariableValues values) {
return left.evaluate(values) == right.evaluate(values);
}
}
public class NotEqual implements SimpleExpression {
private final Atom left, right;
public NotEqual( Atom left, Atom right) {
this.left = left;
this.right = right;
}
public boolean evaluate( VariableValues values) {
return left.evaluate(values) != right.evaluate(values);
}
}
public class OrExpression implements Expression {
private final Expression left, right;
public OrExpression( Expression left, Expression right) {
this.left = left;
this.right = right;
}
public boolean evaluate( VariableValues values) {
return left.evaluate(values) || right.evaluate(values);
}
}
public class AndExpression implements Expression {
private final Expression left, right;
public AndExpression( Expression left, Expression right) {
this.left = left;
this.right = right;
}
public boolean evaluate( VariableValues values) {
return left.evaluate(values) && right.evaluate(values);
}
}
public interface Atom {
double evaluate( VariableValues values);
}
public class Literal implements Atom {
private final double value;
public Literal( double value) {
this.value = value;
}
public double evaluate( VariableValues values) {
return value;
}
}
public class Variable implements Atom {
private final String name;
public Variable( String name) {
this.name = name;
}
public double evaluate( VariableValues values) {
return values.getValue( name);
}
}