Shulou(Shulou.com)06/02 Report--

This article mainly explains "Scala how to combine parser combiner and case class to build calculator", the content of the article is simple and clear, easy to learn and understand, please follow Xiaobian's train of thought slowly in-depth, together to study and learn "Scala how to combine parser combiner and case class to build calculator" bar!

To be clear, our DSL is a little messy at the moment. We have an abstract grammar tree (Abstract Syntax Tree), which consists of a large number of case classes.

Listing 1. Backend (AST)

Package com.tedneward.calcdsl {/ /... Private [calcdsl] abstract class Expr private [calcdsl] case class Variable (name: String) extends Expr private [calcdsl] case class Number (value: Double) extends Expr private [calcdsl] case class UnaryOp (operator: String, arg: Expr) extends Expr private [calcdsl] case class BinaryOp (operator: String, left: Expr, right: Expr) extends Expr}

…… For this, we can provide behavior similar to that of an interpreter, which can simplify mathematical expressions to the maximum.

Listing 2. Backend (interpreter)

Package com.tedneward.calcdsl {/ /... Object Calc {def simplify (e: Expr): Expr = {/ / first simplify the subexpressions val simpSubs = e match {/ / Ask each side to simplify case BinaryOp (op, left, right) = > BinaryOp (op, simplify (left), simplify (right)) / / Ask the operand to simplify case UnaryOp (op, operand) = > UnaryOp (op Simplify (operand)) / / Anything else doesn't have complexity (no operands to simplify) case _ = > e} / / now simplify at the top, assuming the components are already simplified def simplifyTop (x: Expr) = x match {/ / Double negation returns the original value case UnaryOp ("-", UnaryOp ("-", x)) = > x / / Positive returns the original value case UnaryOp ("+") X) = > x / / Multiplying x by 1 returns the original value case BinaryOp ("*", x, Number (1)) = > x / / Multiplying 1 by x returns the original value case BinaryOp ("*", Number (1), x) = > x / / Multiplying x by 0 returns zero case BinaryOp ("*", x) Number (0) = > Number (0) / / Multiplying 0 by x returns zero case BinaryOp ("*", Number (0), x) = > Number (0) / / Dividing x by 1 returns the original value case BinaryOp ("/", x, Number (1)) = > x / / Dividing x by x returns 1 case BinaryOp ("/", x1) X2) if x1 = = x2 = > Number (1) / / Adding x to 0 returns the original value case BinaryOp ("+", x, Number (0)) = > x / / Adding 0 to x returns the original value case BinaryOp ("+", Number (0)) X) = > x / / Anything else cannot (yet) be simplified case e = > e} simplifyTop (simpSubs)} def evaluate (e: Expr): Double = {simplify (e) match {case Number (x) = > x case UnaryOp ("-", x) = >-(evaluate (x)) case BinaryOp ("+", x1) X2) = > (evaluate (x1) + evaluate (x2)) case BinaryOp ("-", x1, x2) = > (evaluate (x1)-evaluate (x2)) case BinaryOp ("*", x1, x2) = > (evaluate (x1) * evaluate (x2)) case BinaryOp ("/", x1, x2) = > (evaluate (x1) / evaluate (x2))}

…… We used a text parser built by the Scala parser combiner to parse simple mathematical expressions.

Listing 3. Front end

Package com.tedneward.calcdsl {/ /... Object Calc {object ArithParser extends JavaTokenParsers {def expr: Parser [Any] = term ~ rep ("+" ~ term | "-" ~ term) def term: Parser [Any] = factor ~ rep ("*" ~ factor | "/" ~ factor) def factor: Parser [Any] = floatingPointNumber | ("~ expr~") "def parse (text: String) = {parseAll (expr) Text)}} / /.}}

…… But when parsing, because the parser combiner is currently written to return the Parser [Any] type, it generates String and List collections, and you should actually have the parser return any type it needs (as we can see, this is a String and List collection).

For the DSL to succeed, the parser needs to return the objects in the AST so that the execution engine can capture the tree and evaluate () on it when the parsing is complete. For this front end, we need to change the parser combiner implementation to generate different objects during parsing.

Clean up syntax

The first change to the parser is to modify one of the syntax. In the original parser, expressions like "5 + 5 + 5" were accepted because rep () combinators were defined for expressions (expr) and terms (term) in the grammar. However, if you consider extension, this may cause some relevance and operator priority issues. Future operations may require the use of parentheses to explicitly give priority to avoid such problems. So the first change is to change the syntax to require the addition of "()" to all expressions.

In retrospect, this is something I should have done in the first place; in fact, relaxing restrictions is usually easier than adding restrictions later (if you don't need them in the end), but solving operator precedence and relevance issues is much more difficult. If you don't know the precedence and relevance of operators, let me outline how complex our environment will be. Considering the Java language itself and the various operators it supports (as shown in the Java language specification) or some related challenges (from the Java Puzzlers provided by Bloch and Gafter), you will find that the situation is not optimistic.

Therefore, we need to solve the problem step by step. The first is to test the syntax again:

Listing 4. Use parentheses

Package com.tedneward.calcdsl {/ /... Object Calc {/ /... Object OldAnyParser extends JavaTokenParsers {def expr: Parser [Any] = term ~ rep ("+" ~ term | "-" ~ term) def term: Parser [Any] = factor ~ rep ("*" ~ factor | "/" ~ factor) def factor: Parser [Any] = floatingPointNumber | "(" ~ expr~ ") def parse (text: String) = {parseAll (expr) Text)}} object AnyParser extends JavaTokenParsers {def expr: Parser [Any] = (term~ "+" ~ term) | (term~ "-" ~ term) | term def term: Parser [Any] = (factor~ "*" ~ factor) | (factor~ "/" ~ factor) | factor def factor: Parser [Any] = "(" ~ > expr and BinaryOp ("-", lhs) Rhs)} | term def term: Parser [Expr] = (factor ~ "*" ~ factor) ^ {case lhs~times~rhs = > BinaryOp ("*", lhs, rhs)} | (factor ~ "/" ~ factor) ^ {case lhs~div~rhs = > BinaryOp ("/", lhs) Rhs)} | factor def factor: Parser [Expr] = "(" ~ > expr Number (x.toFloat)} def parse (text: String) = parseAll (expr, text)} def parse (text: String) = ExprParser.parse (text). Get / /.} / /.}

The ^ ^ Combinator receives an anonymous function whose parsing result (for example, assuming that the input is 5 + 5, then the parsing result will be ((5 +) ~ 5)) will be passed separately and get an object-in this case, an appropriate type of BinaryObject. Notice once again the power of pattern matching; I bind the left part of the expression to the lhs instance, the + part to the (unused) plus instance, and the right side of the expression to rhs, and then I use lhs and rhs to populate the left and right side of the BinaryOp constructor, respectively.

Now run the code (remember to comment out the temporary tests), and the unit test set produces all the correct results again: the various expressions we tried won't fail again, because now the parser generates derived Expr objects. As I said earlier, it would be irresponsible not to test the parser further, so let's add more tests (including the informal tests I used earlier in the parser):

Listing 7. Test the parser (this time officially)

Package com.tedneward.calcdsl.test {class CalcTest {import org.junit._, Assert._ /... @ Test def parseAnExpr1 = assertEquals (Number (5), Calc.parse ("5")) @ Test def parseAnExpr2 = assertEquals (Number (5)) Calc.parse ("5)") @ Test def parseAnExpr3 = assertEquals (BinaryOp ("+", Number (5), Number (5)), Calc.parse ("5 + 5")) @ Test def parseAnExpr4 = assertEquals (BinaryOp ("+", Number (5), Number (5)) Calc.parse ("(5 + 5)") @ Test def parseAnExpr5 = assertEquals (BinaryOp ("+", BinaryOp ("+", Number (5), Number (5)), Number (5)), Calc.parse ("5 + 5) + 5") @ Test def parseAnExpr6 = assertEquals (BinaryOp ("+", BinaryOp ("+", Number (5)) Number (5)), BinaryOp ("+", Number (5), Number (5)), Calc.parse ("(5 + 5) + (5 + 5)") / / other tests elided for brevity}}

Readers can add a few more tests, because I may have missed some unusual situations (it's better to pair programming with others on Internet).

Complete the last step

Assuming that the parser is working the way we want it to work-that is, generating AST-all we need now is to refine the parser based on the evaluation of the AST object. It's simple, just add code to Calc, as shown in listing 8.

Listing 8. It's really done!

Package com.tedneward.calcdsl {/ /... Object Calc {/ /... Def evaluate (text: String): Double = evaluate (parse (text))}}

…… At the same time, add a simple test to make sure that evaluate ("1: 1") returns 2. 0.

Listing 9. Finally, let's see if 1 + 1 equals 2.

Package com.tedneward.calcdsl.test {class CalcTest {import org.junit._, Assert._ /... @ Test def add1 = assertEquals (Calc.evaluae ("1 + 1"), 2.0)}}

…… Then run it, everything is fine!

Extended DSL language

If you write the same calculator DSL entirely in Java code without the problems I encounter (recursively calculating each fragment without building a complete AST, etc.), it seems to be another language or tool that can solve the problem. But the power of building a language in this way is reflected in extensibility.

For example, we add a new operator to the language, the ^ operator, which performs exponentiation; that is, 2 ^ 2 equals 2 squared or 4. Adding this operator to the DSL language requires some simple steps.

First, you must consider whether you need to change the AST. In this case, the exponentiation operator is another form of binary operator, so you can use the existing BinaryOp case class. No changes are required to AST.

Second, you must modify the evaluate function to perform the correct operation using BinaryOp ("^", x, y); it's simple to add a nested function (because you don't have to see it externally) to actually calculate the index, and then add the necessary lines of code to the pattern match, as shown below:

Listing 10. Just a moment.

Package com.tedneward.calcdsl {/ /... Object Calc {/ /... Def evaluate (e: Expr): Double = {def exponentiate (base: Double, exponent: Double): Double = if (exponent = = 0) 1.0 else base * exponentiate (base, exponent-1) simplify (e) match {case Number (x) = > x case UnaryOp ("-", x) = >-(evaluate (x)) case BinaryOp ("+", x1) X2) = > (evaluate (x1) + evaluate (x2)) case BinaryOp ("-", x1, x2) = > (evaluate (x1)-evaluate (x2)) case BinaryOp ("*", x1, x2) = > (evaluate (x1) * evaluate (x2)) case BinaryOp ("/", x1, x2) = > (evaluate (x1) / evaluate (x2)) case BinaryOp ("^", x1, x2) = > exponentiate (evaluate (x1) Evaluate (x2)}}

Note that here we effectively add exponentiation to the system with only six lines of code without making any superficial changes to the Calc class. This is encapsulation!

When I was trying to create the simplest exponentiation, I deliberately created a version with a serious bug-- to focus on the language, not the implementation. In other words, see which reader can find bug. He can write unit tests that discover bug and then provide a bug-free version.

But before adding this exponentiation function to the parser, let's test the code to make sure that the exponentiation part works:

Listing 11. Find the square

Package com.tedneward.calcdsl.test {class CalcTest {/... @ Test def evaluateSimpleExp = {val expr = BinaryOp ("^", Number (4), Number (2)) val results = Calc.evaluate (expr) / / (4 ^ 2) = > 16 assertEquals Results)} @ Test def evaluateComplexExp = {val expr = BinaryOp ("^", BinaryOp ("*", Number (2), Number (2)), BinaryOp ("/", Number (4), Number (2)) val results = Calc.evaluate (expr) / / (2 * 2) ^ (4 / 2) = > (4 ^ 2) = > 16 assertEquals Results)}

Run this code to make sure you can exponentiate (ignore the bug I mentioned earlier), so you're half done.

The final change is to modify the syntax to accept the new exponentiation operator; because exponentiation has the same priority as multiplication and division, the easiest thing to do is to put it in the term combiner:

Listing 12. It's done, it's real this time!

Package com.tedneward.calcdsl {/ /... Object Calc {/ /... Object ExprParser extends JavaTokenParsers {def expr: Parser [Expr] = (term ~ "+" ~ term) ^ {case lhs~plus~rhs = > BinaryOp ("+", lhs, rhs)} | (term ~ "-" ~ term) ^ {case lhs~minus~rhs = > BinaryOp ("-", lhs, rhs)} | term def term: Parser [Expr] = (factor ~ "*" ~ factor) ^ {case lhs~times~rhs = > BinaryOp ("*", lhs) Rhs)} | (factor ~ "/" ~ factor) ^ {case lhs~div~rhs = > BinaryOp ("/", lhs, rhs)} | (factor ~ "^" ~ factor) ^ {case lhs~exp~rhs = > BinaryOp ("^", lhs, rhs)} | factor def factor: Parser [Expr] = "(" ~ > expr Number (x.toFloat)} def parse (text: String) = parseAll (expr) | Text)} / /.}}

Of course, we need to do some tests on this parser.

Listing 13. And then square.

Package com.tedneward.calcdsl.test {class CalcTest {/... @ Test def parseAnExpr17 = assertEquals (BinaryOp ("^", Number (2), Number (2)), Calc.parse ("2 ^ 2")) @ Test def parseAnExpr18 = assertEquals ("^", Number (2), Number (2)) Calc.parse ("(2 ^ 2)") @ Test def parseAnExpr19 = assertEquals (BinaryOp ("^", Number (2), BinaryOp ("+", Number (1), Number (1)), Calc.parse ("2 ^ (1 + 1)") @ Test def parseAnExpr20 = assertEquals (BinaryOp ("^", Number (2)) Number (2)), Calc.parse ("2 ^ (2)")}}

…… After running and passing, there is one last test to see if everything is working properly:

Listing 14. From String to square

Package com.tedneward.calcdsl.test {class CalcTest {/... @ Test def square1 = assertEquals (Calc.evaluate ("2 ^ 2"), 4.0)}}

It worked!

Thank you for reading, the above is the content of "Scala how to combine parser combiner and case class to build calculator". After the study of this article, I believe you have a deeper understanding of how Scala combines parser combiner and case class to build calculator, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.