1. Approach
The class org.vishia.util.CalculatorExpr
was firstly created and used for a graphical user interface (Inspector)
to show values after calculation, for example with specific scaling.
For that only add/sub and multiplication was necessary (scaling, offset) and a simple solution was created.
But later, with the JZtxtcmd calculation using also Strings (contains etc.)
become necessary and the CalculatorExpr class was enhanced.
Of course CalculatorExpr uses the https://en.wikipedia.org/wiki/Reverse_Polish_notation for internal work.
Parsing expressions in a language should be resolve precedences of operators. For generating another language from parsing, or executing, also the RPN can be used. It is interesting that transformation of a parse result expression to RPN allows generating the same expression with other precedense rules for another language. The back converting of RPN to a normal expression with specific precedences is possible and not complicated.
2. RPN
The https://de.wikipedia.org/wiki/Umgekehrte_polnische_Notation (RPN) should be known. It is important that a 'normal' notation with precedence rules of operators and parentheses can be transformed unambiguously into the RPN by the parsing process, but also the back transformation into the 'normal' notation, which generates the necessary parentheses, is possible. Thus an expression can be used not only for execution, which can be realized quickly in RPN notation, but also for storing an expression for later code generation.
A storage in a tree of binary expressions as recognized by the parser (Xtext) assumes that the tree delivered by the parser also corresponds to the target language in the precedence rules of the operators. However, this is not always the case. In the RPN the precedence rules of the parsed source are already processed accordingly, the RPN has no precedence rules but only a processing order. The precedence rules can be set differently when generating a 'normal' expression from the RPN than in the syntax of the source parser. By 'normal' expression is meant the notation in the common programming languages.
2.1. Notation form
The classic notation form for RPN follows the rules to enter an RPN expression to a RPN calculator:
5 8 4 / +
or
5 ENTER 8 ENTER 4 ENTER / +
stands for
5 + 8 / 4
in normal writing style. The operator comes after the operand always.
For representation outside of the calculator’s key pressing it is better to do the following:
-
Always join the operand with the operator. Any operand has its operator.
-
Also an unary operation can be assembled with the operand.
-
The operand can be of course also a variable, not only a number.
-
The current stack level is designated as accumulator or accu, because it is used for the current calculation. Hence the mnemonically symbol
@is used for that. -
@as operand (left side) means "store in accu". -
@as operator (right side) means "use the accu as value". -
Multiple Storing to
@stores the current accu of course in the stack. Usage of the accu value for operation pops the next value from stack to the accu for next usage. The accu is the current presentation of stack level. All deeper stack levels are never used immediately. -
If functions are called, their operands comes from accu and stack in order of the arguments, as usual in RPN.
Regarding this, the writing style for RPN can be better defined in the form:
@ 5, @ 8, / 4, + @
-
The operator is left, the operand is right. An unary operator (not shown here) is left of the operand. The advantage is, seen for non-swapable operands, it is better seen with the eyes of knowledge non RPN formulas, which is left and right side. Here is is obviously that the
4is the divisor, not the divident. -
The
@presents the stack. Left side as operator it means "push" or "store" or "ENTRER". Right side as operand it means "pop" or use the last stack level, with pop as operand.
More complex example with parenthesis and unary operation:
In a Java source it is written:
w = a + b * -(c + f) / (a+b) - e + (d * g) / e;
Parsing this and transform to RPN using org.vishia.parseJava.JavaParser produces:
@ w; @ a; @ b; @ c; + f; @ a; + b; / @; * - @; + @; - e; @ d; * g; / e; + @; = @;
This expression can be used also as textual input for the operation setRpnExpr(expr, log) in
org.vishia.util.CalculatorExpr+setPrnExpr(…).
To present which result in stack is associated to which stack operand see:
+---------------------------------------->|
| +---------------------------->+ | +--------------->+
| | ++++++++----------->+ | | | |
@ w; @ a; @ b; @ c; + f; @ a; + b; / @; * - @; + @; - e; @ d; * g; / e; + @; = @;
++++++++--->++---->++-->+ ++++++++++++++-->+
2.2. Algorithm to produces RPN
In the org.vishia.util.CalculatorExpr
in operation setExpr(String) there is used a recursively approach:
-
Firstly an expression is parsed calling
parseAndExpr()for the operand and checks the||as operation. -
Recursively in
parseAndExpr()the&&is accepted as operator andparseCmpExpr()is called. -
In
parseCmpExpr()the possible operators are the comparison operators, andparseAddExpr()is called as operand. -
In
parseAddExpr()+and-are accepted andparseMultExpr()is called. -
In
parseMultExpr()*and/are accepted and nowparseArgument()is called as operand. -
In
parseArgument()also a whole expression in parenthesis is accepted, which is evaluated again withparseExpr()with this whole tree. -
Also the unary operator is accepted in
parseArgument(). -
Last not least this is a recursively call maybe with more recursions because nested parenthesis which produces a tree of expression parts with the correct precedence.
-
Storing the parts of the expressions is done in
parseArgument(). That produces the correct RPN order.
In org.vishia.parseJava.JavaSrc which is called in org.vishia.parseJava.JavaParser another algorithm is implemented:
-
The ZBNF parser itself stores an expression without precedence, in writing order. The ZBNF parser may be able to evaluate an expression exactly in the above shown form, firstly parse an OR-Expression then AND-Level etc. But this needs a longer time for the parsing because the parser should test all levels in recursion. Instead the parser does not test the precedense, a post preparation does it, in org.vishia.parseJava.JavaSrc
-
The precedence of the currently found operator for the next operationis determined by a table.
-
If the next operation has a higher precedence, then the current Operand is registered to store in stack, to perform the following operation.
-
If the next operation has not a higher precedence, means equal or lower, then the stack is checked whether it contains a lower or equal precedence. It is popped.
-
If the precedence in stack is lower then the precedence of the current operand, then firstly the current operand is added to the RPN expression.
-
If the precedence in stack is equal or higher of the current operand, then firstly that operands are added yet.
-
Further operands from stack with lower or equal precedences as the next one are added after them.
This sorts the operation. The advantage is: The precedence is only regarded by a defined table for pecedenses to the operators, and not by recursively called special evaluation operations.
-
If an nested expression is detected, then the operator and precedence, also an unary operator for the nested expression is stored in stack, which presents the result of the nested expression.
-
The nested expression is evaluated in line with all other operations, but with recursively call of this preparing operation.
2.3. Algorithm to produce a infix (normal) expression from RPN
This is done for example for the org.vishia.fpga.VhdlConv:
The RPN expression contains the operands in the given order as also for the infix expression. See simple example:
x = a + b * c; //infix @ x; @ a; @ b; * c; + @; = @; //RPN
Only the operators are in another order, using pushed and popped values.
Hence, the RPN can be evaluated from left to right to get the same operands. One continues expression term (consist of some parts) is also continues in RPN:
@ x; @ a; @ b; * c; + @; = @; //RPN
b * c
After that with + @ the "accu" will be added.
The accu is the last expression term itself, yet even calculated.
The continues expression now starts with the last calculated, which is here only the variable a in stack:
@ x; @ a;@ b; * c;+ @; = @; //RPN a + b * c
That will repeated, now the = @ will assign the accu (the current expression) to the next stack expression, means:
@ x;@ a; @ b; * c; + @;= @; //RPN x = a + b * c
But what about:
@ y; @ a; + b; * c; = @; //RPN
a + b * c //faulty!!
That will be faulty. Because: In RPN firstly a + b is calculated, then multiply with c.
If an expression is continued with a higher precedence operation, the part before must be set in parenthesis, to bind it.
@ y; @ a; + b; * c; = @; //RPN
(a + b) * c //correct
Example with two terms:
@ z; @ a; + b; @ c; + d; * @; = @; //RPN z, a + b, c + d
First three terms are built and stored in stack: z, a+b and c+d.
Then the accu should be multiplied, e.g. the last term. This results in
@ z; @ a; + b;@ c; + d;* @; = @; //RPN z, (a + b) * (c + d)
Same approach. But the terms, first the accu term must be set in parenthesis because the connection operator has a higher precedence. As shown above the now current left expression should also set in parenthesis because a higher precedence operator follows.
A specialism:
@ m; @ a; @ b; + c; + @; = @; //RPN
a, b + c
a + (b + c)
Why it is not notated as
@ m; @ a; + b; + c; = @; //RPN
Because it comes from an expression m = a + (b + c); in the Java original.
Why parenthesis around b+c? May be it is a special condition, prevent overflow fro integer arithmetic or such one.
It is the decision of the user. The user want to add (b+c) prior. Exact that is mapped to the RPN.
The back conversion from RPN to infix should set parenthesis also if the operator for the accu has an equal precedence. Only if all the operator in the right accu expression has higher precedences (or the lowest precedence of this expression is higher), then the parenthesis can be omitted. Because: The precedence ensures first calculation by itself.
That are the basic rules for back conversion from RPN to infix.
3. CalculatorExpr
This java class org.vishia.util.CalculatorExpr was firstly written in a simple form for scaling variable values to show in scaled and/or offset cleaned form in a GUI. That was a simple approach. It seems to be stupid to use a manual written calculator where the Java Runtime Environment can caculate expressions very more faster using the byte code of Java. That may be one point of view. But the other point is: If the expression is given only in runtime, or given as simple text without possible use of the Java compiler, and secondly the calculation time is not important (in ranges of some µs till ms in comparison to ns and µs), then an interpreted calculation is also sensible. It is similar to access to Java data via reflection (it is interpreting) instead compile a program.
The JZtxtcmd is one of interpretation tool working with Java data. In JZtxtcmd the user can mix hard compiled Java classes with textual given access. So a decision can be done, which parts are flexible changeable only in text without Java compiler, and which parts are compiled and not changeable for example by a user which can/should only deal with the scripts. So the CalculatorExpr class takes place in the JZtxtcmd also (as in the inspector GUI) for such flexible calculations.
3.1. Operation
The inner class CalculatorExpr.Operation has exact the described property of a RPN expression part, it contains the operator, an unary operator and the operand. Following the
/**All Operations which acts with the accumulator and the stack of values. * They will be executed one after another. All calculation rules of prior should be regarded * in this order of operations already. It will not be checked here. */ private final List<Operation> listOperations_ = new ArrayList<Operation>();
as only one field in CalculatorExpr contains the expression in working order, and this is Revers Polish Notation.
3.2. Operand
The inner class CalculatorExpr.Operand describes what can be an operand.
/**Operand for a part of the expression, refer from {@link Operation}.
*/
public static class Operand {
/**Index of the value contained in a given array on execution, -1 if not used.*/
public int ixValue;
/**Set if the value uses reflection. */
public final DataAccess dataAccess;
/**Set for constant data. */
public final Object dataConst;
/**The String literal or the given sDatapath. Last one is for debug/comment, not for using. */
public final String textOrVar;
/**If not null the operand is calculated with an expression itself. */
public final CalculatorExpr expr;
3.3. Operator
The inner class CalculatorExpr.Operator is only a base class as interface to given operators.
/**An operator for the current value (accu), the given second value maybe the operand from the {@link Operation},
* or for some additional values in stack.
* The operation are such as a set operation (set the arg to accu), add, subtract, negate, boolean operators etc or standard maths routines.
* Instances of this class are defined in the {@link CalculatorExpr}.
*/
public abstract static class Operator {
protected final String name;
protected Operator(String name){ this.name = name; }
/**Operates and returns the result type. This method is used only internally, it is private, only protected to show it in the documentation.
* Before invoking the operation, both arguments are converted in a proper format for the operation with the method
* {@link ExpressionType#checkArgument(Value, Value)} with respect to the current type of the expression
* starting with the {@link CalculatorExpr#startExpr}.
* @param Type The current type
* @param accu First operand, used cumulatively or the only one operand for unary operations.
* @param arg The second argument for binary operations.
* @return The result type after the operation.
* @throws Exception If the operation is not admissible.
*/
protected abstract void operate(Value accu, Value arg) throws Exception;
/**Returns true on an unary operation, false on a operation with both operands. */
protected abstract boolean isUnary();
/**Returns true if this is a bool check operation. */
protected abstract boolean isBoolCheck();
@Override public String toString(){ return name; }
}
The Operators itself are defined in CalculatorExpr.Operators
Any Operator class contain the required methods from Operator to execute the specific operation. The operations should be executed with the different given types:
-
All numeric types
-
boolean
-
Object types for instance check and also conversion to numeric
-
String types also for String operations.
Type conversion as preparation for the core operation is also a necessary part. For that the interface CalculatorExpr.ExprType is given:
/**Common interface to check and maybe change the type of expression.
* All instances of Expression type implements this interface to check and maybe change the arguments adequate to the given or higher type.
*/
protected interface ExpressionType {
char typeChar();
/**Checks the second argument whether it is matching to the current expression type
* which matches to the accu.
* If the val2 provides another type, either it is converted to the current expression type
* or another (higher) expression type is taken and the accumulator value is converted.
* @param accu The accumulator maybe changed..
* @param val2 the second operand is tested, may be changed.
* @return type of the expression. Often it is this, sometimes it is an higher type.
*/
ExpressionType checkArgument(Value accu, Value val2) throws Exception;
}
The expression types itself with the converting routines are defined in CalculatorExpr.ExprTypes
All operations see CalculatorExpr.Operators
3.4. Set the expression
The inner but public static class CalculatorExpr.SetExprBase.SetExpr is used to set an expression immediately from the ZBNFparser’s parse result which also can sort the expression parts and terms to the RPN order by the syntax definition. This is used to translate a JZtxtcmd Script.
Else this list is able to fill with some operations from any textual form:
/**Converts the given expression in a stack operable form (Reverse Polish Notation) to execute.
* @param spExpr given textual expression
* @param nameVariables An operand can be given as name of a variable from this index.
* Then for execution an array should be given as last argument of {@link #calcDataAccess(Map, Object...)}.
* It is the same approach as in {@link DataAccess#DataAccess(StringPartScan, Map, Class, char)}.
* @param reflData An operand can be given with access to this data via reflection.
* Then for execution data with this reflection class should be given as argument of {@link #calcDataAccess(Map, Object...)}
* @param bSpecialSyntax true then ">" is not accepted (as compare operator).
* It is for texts where the ">" has other meanings. The "gt" can be used to formulate "greater than" instead
* @return null if ok or an error description.
* @throws ParseException
*/
public String setExpr(StringPartScan spExpr, Map<String, DataAccess.IntegerIx> nameVariables
, Class<?> reflData, boolean bSpecialSyntax)
{ listOperations_.clear();
try{
parseExpr(spExpr, nameVariables, reflData, "!", bSpecialSyntax, 1);
} catch(ParseException exc){
return exc.getMessage();
}
return null;
}
/**All Operations which acts with the accumulator and the stack of values. * They will be executed one after another. All calculation rules of prior should be regarded * in this order of operations already. It will not be checked here. */ private final List<Operation> listOperations_ = new ArrayList<Operation>();
4. JavaParser
The class org.vishia.parseJava.JavaParser respectively the package contains a syntax definition in ZBNF format and also a RPN preparation:
The approach of this class is not a alternative to a JDK for byte code. No. It is to parse Java sources for converting to other languages. The first usage of that was a Java2C idea, which produces C language code from Java sources. The translator itself is no more used curently, but the translated sources are part of the emC concept.
Currently this parser is used to produce VHDL (for FPGA designs).
5. Tests
The test class org.vishia.parseJava.test.TestParseJava organize tests firstly for Java parsing
but secondly especially to test the RPN conversion.
For that the class org.vishia.parseJava.test.ParseExample contains some expressions which are parsed,
but also calculated in Java:
/**This operation is used to parse, and then execute the expression via {@link org.vishia.util.CalculatorExpr}
* inside {@link TestParseJava}. There also this operation is called to compare the self executed result
* after conversion to RPN with the result calculated from Java execution itself.
*/
@SuppressWarnings("unqualified-field-access") //because the fields are used for independent calculation is simple names too.
public void exmplOperation ( ) {
x = a + b * c; // u#; a#; b#; #+; c*; #=; d-;
y = (a + b) * c;
z = (a + b) * (c + d);
m = a + (b + c);
q6 = q1 || q2 && q4;
q7 = c < d || b >a && c >b;
u = (a + b) * c -d; // u#; a#; b#; #+; c*; #=; d-;
v = a * -(d+g) / e + (a+b); // v#; a#; d#; g+; #*; e/; a#; b+; #+; #=;
//this.x = (a ==0) ? c+d : d+e;
// w#; a#; b#; c#; f+; a#; b+; #/; #*; #+; e-; m#; d#; #=; g*; #+; #=; e/;
//w#; a#; b#; c#; f+; a#; b+; #/; #*; #+; e-; m#; d#; g*; #=; e/; #+; #=;
//[set "w" [22], set "a" [0], set "b" [1], set "c" [2], + "f" [5], set "a" [0], + "b" [1], / stack , * stack , + stack , - "e" [4], set "m" [12], set "d" [3], * "g" [6], / "e" [4], + stack ]
// w = a + b * (c + f) / (a+b) - e + (m = d * g) / e;
//@ w; @ a; @ b; @ c; + f; @ a; + b; / @; * - @; + @; - e; @ d; * g; / e; + @; = @;
//[set "w" [22], set "a" [0], set "b" [1], set "c" [2], + "f" [5], set "a" [0], + "b" [1], / stack , * stack , + stack , - "e" [4], set "d" [3], * "g" [6], / "e" [4], + stack ]
w = a + b * -(c + f) / (a+b) - e + (d * g) / e;
p = q1 || q2 && q4 ? a+b : e+c*d;
a = a;
return;
}
The parsing looks like:
this.parser = new ZbnfParser(this.console, 10);
this.parser.setSyntaxFromJar(JavaSrc.class, "JavaSyntax.zbnf");
.....
public JavaSrc parseJava(File fileIn) throws .....
bOk = this.parser.parseFile(fileIn);
....
JavaSrc_Zbnf result = new JavaSrc_Zbnf();
ZbnfParseResultItem resultItem = this.parser.getFirstParseResult();
try{ ZbnfJavaOutput.setOutputStrictNewFromType(result, resultItem, this.console); }
The parse result is after parsing stored in the given JavaSrc result class.
The syntax of an expression in the syntax.zbnf script is simple:
Expression::={<?*ExprPart> <simpleValue?value> ? <operator?>} [ \? <TrueFalseValue>].
operator::=[<?@operator> \|\| | && | & | \| | ^ | + | - | * | / | \>\> | \<\< | \<= | \>= | \< | \> | == | != | = | += | -= | *= | /= | &= | \|= | \<\<= | \>\>= ].
TrueFalseValue::=<Expression?trueExpression> : <Expression?falseExpression>.
As you can see the operators are not sorted by parsing, the result contains the given writing order.
After parsing each used expression is post-prepared for RPN presentation:
/**Tests some expressions which are given in the Java src file.
* @param testParent
* @throws IllegalCharsetNameException
* @throws UnsupportedCharsetException
* @throws FileNotFoundException
* @throws IOException
*/
void testExpression(TestOrg testParent) throws IllegalCharsetNameException, UnsupportedCharsetException, FileNotFoundException, IOException {
TestOrg test = new TestOrg("test Expressions in ParseExample", 7, testParent);
try {
String pathJavasrc = "D:/vishia/Java/cmpnJava_vishiaBase/src/test/java/org/vishia/parseJava/test/ParseExample.java";
File fileIn = new File(pathJavasrc);
JavaSrc res = parseJava(fileIn);
int ixTest = 0;
for(JavaSrc.ClassDefinition theClass: res.get_classDefinition()) {
for(JavaSrc.ClassDefinition iClass: theClass.get_classDefinition()) {
for(JavaSrc.MethodDefinition rOper: iClass.get_methodDefinition()) {
for(JavaSrc.Statement rStmnt: rOper.get_methodbody().get_statement()) {
JavaSrc.Expression rExpr = rStmnt.get_Expression(); // statement is an expression
if(rExpr !=null) {
JavaSrc.Expression exprRpn = rExpr.prep(log);
if(exprRpn !=null) {
rStmnt.set_AssignExpression(exprRpn);
if(ixTest ==3)
Debugutil.stop();
this.expr[ixTest] = exprRpn;
this.results[ixTest] = executeRpnExpr(exprRpn);
this.backExpr[ixTest] = convertToInfixExpr(exprRpn);
if(++ixTest >= this.results.length) { ixTest = this.results.length-1; } //limit it.
All found expressions are stored in the last three arrays, as
-
expr: The expression itself to view via.toString() -
results: As shown following the expression is executed withCalculatorExpr. Store the result. -
backExpr: The RPN expression is converted back to the infix form, which should be compared to the Java original.
After that the results are compared with the expected values.
The results are compared in calculated values with the original Java result, stored in :
float[] resultJavaCalcF = { this.parseExample.prc.x, this.parseExample.prc.y, this.parseExample.prc.z
, this.parseExample.prc.m
, Float.NaN, Float.NaN
, this.parseExample.prc.u, this.parseExample.prc.v, this.parseExample.prc.w, this.parseExample.prc.p
};
boolean[] resultJavaCalcB = { false, false, false, false
, this.parseExample.prc.q6, this.parseExample.prc.q7
};
This part of software should be adapted if the ParseExample.java is changed.
The value Float.NaN is used to mark that the result for boolean should be used.
The calculation from the RPN format is done with:
/**Executes the prepared expression in RPN with the {@link CalculatorExpr}.
* <ul>
* <li> First the given expr is converted in the necessary internal form
* using {@link CalculatorExpr#setRpnExpr(CharSequence, Map, Class)}.
* <li> second this expression is evaluated.
* <li> The result is returned and outside of this routine stored and compared as test result.
* </ul>
* @param expr
* @return result
* @throws ParseException
*/
CalculatorExpr.Value executeRpnExpr ( JavaSrc.Expression expr) throws ParseException {
String sExpr = expr.toString();
System.out.append("\n-----------------------------------------------------------\n");
System.out.append(sExpr); // prepare the RPN for the calculator
this.calculator.setRpnExpr(sExpr, this.nameVariables, null);
System.out.append("\n").append(this.calculator.toString()).append("\n");
CalculatorExpr.Value result = null;
try { // calculate the stored RPN
Object[] values = new Object[] { this.variable, this.variableBool};
result = this.calculator.calcDataAccess(null, values);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
return result;
}
The proper test result looks like:
Test JavaParser, RPN expressions test Expressions in ParseExample ok: result: 7.0 == 7.0 Expr: x = a + b * c : ok: result: 9.0 == 9.0 Expr: y = ( a + b ) * c : ok: result: 21.0 == 21.0 Expr: z = ( a + b ) * ( c + d ) : ok: result: 6.0 == 6.0 Expr: m = a + ( b + c ) : ok: result: true == true Expr: q6 = q1 || q2 && q4 : ok: result: true == true Expr: q7 = c < d || b > a && c > b : ok: result: 5.0 == 5.0 Expr: u = ( a + b ) * c - d : ok: result: 0.79999995 == 0.79999995 Expr: v = a * - ( d + g ) / e + ( a + b ) : ok: result: -4.4 == -4.4 Expr: w = a + b * - ( ( c + f ) / ( a + b ) ) - e + d * g / e : ok: RPN , "@ x; @ a; @ b; * c; + @; = @; " ok: back, " x = a + b * c " ok: RPN , "@ y; @ a; + b; * c; = @; " ok: back, " y = ( a + b ) * c " ok: RPN , "@ z; @ a; + b; @ c; + d; * @; = @; " ok: back, " z = ( a + b ) * ( c + d ) " ok: RPN , "@ m; @ a; @ b; + c; + @; = @; " ok: back, " m = a + ( b + c ) " ok: RPN , "@ q6; @ q1; @ q2; && q4; || @; = @; " ok: back, " q6 = q1 || q2 && q4 " ok: RPN , "@ q7; @ c; < d; @ b; > a; @ c; > b; && @; || @; = @; " ok: back, " q7 = c < d || b > a && c > b " ok: RPN , "@ u; @ a; + b; * c; - d; = @; " ok: back, " u = ( a + b ) * c - d " ok: RPN , "@ v; @ a; @ d; + g; * - @; / e; @ a; + b; + @; = @; " ok: back, " v = a * - ( d + g ) / e + ( a + b ) " ok: RPN , "@ w; @ a; @ b; @ c; + f; @ a; + b; / @; * - @; + @; - e; @ d; * g; / e; + @; = @; " ok: back, " w = a + b * - ( ( c + f ) / ( a + b ) ) - e + d * g / e "
Here some expressions are converted and tested..