Компилятор выражений

Недавно у меня возникла необходимость в вычислении выражений. Выражение представлено в виде строки и может содержать имена переменных, целые числа, строковые константы и любые операции над ними.

Пример:
   выражение: «x + 10 == 5 * y / (1 + z*2)»;
   требуется уметь вычислять это выражение для любых значений x, y и z.

И конечно при этом надо учитывать приоритеты операторов.

Для решения нужно сделать компилятор, который по строке строит объект «Вычислимое Выражение». У этого объекта будет метод «вычислить для данных значений переменных».

Решение на Java, но может быть легко переведено на другие языки.



Сначала о том, что мы получаем на выходе после компиляции строки. Это объект Expression (выражение) с методом execute(Map vars). Объект древовидный, в узлах операторы на листьях переменные или константы. По примеру, думаю все понятно:

«x + 1 < y / (1+2)» =>

[ "<" ]
    [ "+" ]
        [ x ]
        [ 1 ]
    [ "/" ]
        [ y ]
        [ "+" ]
            [ 1 ]
            [ 2 ]


Узлы этого дерева бывают:

• Бинарными — оператор и два операнда (+, -, == и т.д.)
• Унарными— оператор и один операнд (отрицание и унарный минус)
• Переменная — листовой узел с именем переменной
• Строка
• Число

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

Теперь самое интересное — компиляция.
Попробую рассказать понятно для хабралюдей незнакомых с конечными автоматами и грамматиками.
Для ясности разберем простейшие выражения, которые могут содержать только числа, знаки «+», «-» и скобки Например 10 — (3 + 2 — (10 — 5)).

Запишем формально:

Выражение: Слагаемое [+ / - Слагаемое] *
Слагаемое: число | (Выражение)


Произносится так:
Выражение есть Слагаемое, плюс-минус Слагаемое (вот это «плюс-минус Слагаемое» может повторяться от нуля до любого числа раз).
Слагаемое есть число или Выражение в скобках.

Алгоритм обработки глядя на формальную запись получается такой:

построитьВыражение:
    X1 = построитьСлагаемое()

    пока в потоке «+» или «-»
        X2 = построитьСлагаемое();
        X1 = БинарныйУзел ( «+» или «-», X1, X2)
    конец цикла
    вернуть X1
конец

построитьСлагаемое:
    если в потоке '('
        X = построитьВыражение()
        вернуть X
    иначе
        вернуть число
конец



В приведенном компиляторе используется более сложная грамматика:

S0 : S1 [ || S1] *
S1: S2 [ && S2] *
S2: S3 | ! S3
S3: S4 | S4 == S4 | S4 != S4 | S4 <= S4 | S4 < S4 | S4 >= S4 | S4 > S4
S4: S5 [«+» или «-» S5] *
S5: S6 [«*» или «.» S6] *
S6: 'string' | var | number | null | (S0) | - var | - number | - (S0)


И собственно код:

import java.util.Map;

/**
* Вычислимое Выражение
*/
public abstract class Expression {
  
  /** Вычислить выражение для даных значений переменных */
  public abstract Object execute(Map<String, Object> values) throws Exception;
  
  
  /** Узел дерева — «Число» */
  static class Num extends Expression {
    private final long value;
    
    public Num(long x) {
      value = x;
    }
    
    @Override
    public Object execute(Map<String, Object> values) {
      return value;
    }
  }
  
  /** Узел дерева — «Строка» */
  static class Str extends Expression {
    private final String value;
    
    public Str(String x) {
      value = x;
    }
    
    @Override
    public Object execute(Map<String, Object> values) {
      return value;
    }
  }  

  /** Узел дерева — «Переменная» */
  static class Var extends Expression {
    private final String name;
    
    public Var(String name) {
      this.name = name;
    }
    
    @Override
    public Object execute(Map<String, Object> values) {
      return values.get(name);
    }
  }
  
  
  /** Узел дерева — «Унарный оператор» */
  static class Unary extends Expression {
    private final Expression expr;
    private final boolean not;
    
    public Unary(Expression e, String oper) {
      expr = e;
      not = "!".equals(oper);
    }
    
    @Override
    public Object execute(Map<String, Object> values) throws Exception {
      Object o = expr.execute(values);
      if(not)
        return !(Boolean)o;
      else
        return -(Long)o;
    }
  }  
  
  

  /** Узел дерева — «Бинарный оператор» */
  static class Binary extends Expression {
    private final Expression x1;
    private final Expression x2;
    private final String op;
    
    public Binary(Expression x1, Expression x2, String op) {
      this.x1 = x1;
      this.x2 = x2;
      this.op = op;
    }

    @Override
    public Object execute(Map<String, Object> values) throws Exception {
      Object o1 = x1.execute(values);
      Object o2 = x2.execute(values);
      
      Class type = commonType(o1, o2);
      
      if(type == String.class)
        return execStr(o1 != null? o1.toString() : null, o2 != null ? o2.toString() : null);
      else if(type == Long.class)
        return execNum((Long)o1, (Long)o2);
      else
        return execBool((Boolean)o1, (Boolean)o2);
    }
    
    private Class commonType(Object o1, Object o2) {
      if(o1 == null || o2 == null || o1 instanceof String || o2 instanceof String)
        return String.class;
      if(o1 instanceof Long && o2 instanceof Long)
        return Long.class;
      return Boolean.class;
    }
    
    private Object execStr(String s1, String s2) throws Exception {
      if("==".equals(op))
        return (Boolean)(s1 == null ? s2 == null : s1.equals(s2));
      if("!=".equals(op))
        return (Boolean)(s1 == null ? s2 != null : !s1.equals(s2));
      if("+".equals(op))
        return (String)(s1 == null ? s2 : s1 + (s2 == null ? "" : s2));
      throw new Exception("Illegal String operator: " + op);
    }

    private Object execBool(boolean q1, boolean q2) throws Exception {    
      if("&&".equals(op))
        return q1 && q2;
      if("||".equals(op))
        return q1 || q2;
      if("==".equals(op))
        return q1 == q2;
      if("!=".equals(op))
        return q1 != q2;
      throw new Exception("Illegal Boolean operator: " + op);
    }

    private Object execNum(long n1, long n2) throws Exception {    
      if("==".equals(op))
        return (Boolean)(n1 == n2);
      if("!=".equals(op))
        return (Boolean)(n1 != n2);
      if("<".equals(op))
        return (Boolean)(n1 < n2);
      if("<=".equals(op))
        return (Boolean)(n1 <= n2);
      if(">".equals(op))
        return (Boolean)(n1 > n2);
      if(">=".equals(op))
        return (Boolean)(n1 >= n2);
      if("+".equals(op))
        return (Long)(n1 + n2);
      if("-".equals(op))
        return (Long)(n1 - n2);
      if("*".equals(op))
        return (Long)(n1 * n2);
      if("/".equals(op))
        return (Long)(n1 / n2);
      
      throw new Exception("Illegal Long operator: " + op);
    }
  }
}

* This source code was highlighted with Source Code Highlighter.

И сам компилятор:

import java.util.HashMap;
import java.util.Map;

import org.junit.Test;
import static org.junit.Assert.assertTrue;

/** Компилятор выражений */
public class ExpressionBuilder {
  
  private String expression; // Строка с исходным выражением
  private int p = 0; // текущая позиция
  
  public static Expression build(String expression) {
    ExpressionBuilder builder = new ExpressionBuilder(expression);
    builder.skip(" ");
    Expression expr = builder.build(0);
    return expr;
  }
  
  private ExpressionBuilder(String expression) {
    this.expression = expression;
  }
  
  
  /** Построить узел выражения */
  Expression build(int state) {
    if(lastState(state)) {
      Expression ex = null;
      boolean isMinus = startWith("-");
      if(isMinus)
        skip("-");

      if(startWith("(")) {
        skip("(");
        ex = build(0);
        skip(")");
      }
      else
        ex = readSingle();
      if(isMinus)
        ex = new Expression.Unary(ex, "-");
      return ex;
    }
    
    boolean unarNot = state == 2 && startWith("!");
    if(unarNot)
      skip("!");
    
    /* Строим первый операнд */
    Expression a1 = build(state+1);
    if(unarNot)
      a1 = new Expression.Unary(a1, "!");
    
    // строим последущие операнды
    String op = null;
    while((op = readStateOperator(state)) != null) {
      Expression a2 = build(state + 1);
      a1 = new Expression.Binary(a1, a2, op);
      
    }
    return a1;
  }
  
  private static String [][] states = new String[][] {
    {"||"},
    {"&&"},
    {"!"},
    { "<=", ">=", "==", "!=", "<", ">"},
    {"+", "-"},
    {"*", "/"},
    null
  };
  
  private boolean lastState(int s) {
    return s+1 >= states.length;
  }
  
  private boolean startWith(String s) {
    return expression.startsWith(s, p);
  }
  
  private void skip(String s) {
    if(startWith(s))
      p+= s.length();
    while(p < expression.length() && expression.charAt(p) == ' ')
      p++;
  }
  
  
  private String readStateOperator(int state) {
    String[] ops = states[state];
    for(String s : ops) {
      if(startWith(s)) {
        skip(s);
        return s;
      }
    }
    return null;
  }
  
  /**
   * считываем из потока "простое" значение (имя переменной, число или строку)
   * @return
   */
  private Expression readSingle() {
    int p0 = p;
    // чиатем из потока строку
    if(startWith("'") || startWith("\"")) {
      boolean q2 = startWith("\"");
      p = expression.indexOf(q2 ? '"' : '\'', p+1);
      Expression ex = new Expression.Str(expression.substring(p0+1, p));
      skip(q2 ? "\"" : "'");
      return ex;
    }
    
    // в потоке не строка => число или переменная
    while(p < expression.length()) {
      if(!(Character.isLetterOrDigit(expression.charAt(p))))
        break;
      p++;
    }
    
    Expression ex = null;
    if(p > p0) {
      String s = expression.substring(p0, p);
      skip(" ");
      try{
        // из потока прочитали число
        long x = Long.parseLong(s);
        return new Expression.Num(x);
      }
      catch(Exception e){}
      
      if("null".equals(s))
        return new Expression.Str(null);
      
      // не строка, не число и не null — значит переменная
      return new Expression.Var(s);
      
    }
    return null;
  }
  
  
  
  
  
  // для юнит-тестов
  public ExpressionBuilder(){}
  
  @Test
  public void testBuilder() throws Exception {
    String str = "qwerty";
    long n1 = 10;
    long n2 = 5;
    
    Map<String, Object> map = new HashMap<String, Object>();
    map.put("str", "str");
    map.put("n1", n1);
    map.put("n2", n2);
    
    Expression e = ExpressionBuilder.build("str != 'qwerty' && n1 / n2 >= 3 * (n2 + 10 / n1 * (2+3))");
    Boolean a = (Boolean) e.execute(map);
    Boolean b = !"qwerty".equals(str) && n1 / n2 >= 3 * (n2 + 10 / n1 * (2+3));
    assertTrue(a == b);
  }
}


* This source code was highlighted with Source Code Highlighter.

Спасибо за внимание!