Geekly Articles each Day

式コンパイラ

最近、式を評価する必要がありました。 式は文字列として表示され、変数名、整数、文字列定数、およびそれらに対する操作を含めることができます。

例：
式：「x + 10 == 5 * y /（1 + z * 2）」;
任意のx、y、およびz値に対してこの式を計算できる必要があります。

そしてもちろん、オペレーターの優先順位を考慮する必要があります。

これを解決するには、1行にComputable Expressionオブジェクトを作成するコンパイラーを作成する必要があります。 このオブジェクトには、「特定の変数値の計算」メソッドがあります。

ソリューションはJavaにありますが、他の言語に簡単に翻訳できます。



まず、文字列をコンパイルした後の出力で得られるものについて。 これは、execute（Map vars）メソッドを持つExpressionオブジェクト（式）です。 オブジェクトはツリーに似ており、ノードでは葉の演算子は変数または定数です。 たとえば、私はすべてが明確だと思う：

「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 .


ご清聴ありがとうございました！

Source: https://habr.com/ru/post/J50139/

More articles:


All Articles