Chapter 26. Embedded Interpretation

Embed interpreter actions into the grammar, so that executing the parser causes the text to be directly interpreted to produce the response.

There are many occasions where you may want to run a DSL script and get an immediate result, such as performing a calculation or running a query. Embedded Interpretation interprets the DSL script during parsing, so the result of the parse is the result of the script itself.

26.1 How It Works

Embedded Interpretation works by evaluating DSL expressions as soon as possible, collating results together, and returning the overall result. Embedded Interpretation does not use a Semantic Model; instead, the interpretation is done directly on the DSL input. As the parse recognizes each fragment of a DSL script, it interprets as much as it can.

26.2 When to Use It

I’m a big proponent of a Semantic Model, so I don’t usually favor Embedded Interpretation—it is useful when you have relatively small expressions that you just want to evaluate and run. Sometimes, building a Semantic Model just isn’t worth the overhead. But I find this is a rare case; even a relatively small DSL is usually simpler to deal with by creating a Semantic Model and interpreting that, rather than trying to do everything in the parser. Furthermore, a Semantic Model provides a stronger foundation if the language grows.

26.3 A Calculator (ANTLR and Java)

A calculator is perhaps the best example case for Embedded Interpretation. It’s easy to interpret each expression and compose the results together. It’s also a case where the syntax tree for arithmetic is a perfectly good Semantic Model, so there’s no gain in trying to create the usual Semantic Model that I prefer.

Doing a calculator in ANTLR is a bit awkward, because arithmetic expressions are Nested Operator Expressions while ANTLR is a top-down parser. So, the grammar gets a bit more involved.

I begin with a top-level rule. Since arithmetic expressions are recursive, ANTLR needs a top-level rule to know where to start the parse.

I call this top-level rule from a simple Java class that wraps the ANTLR grammar file.

With Nested Operator Expressions, I need to start from the lowest-precedence operators, which in this case are addition and subtraction.

This shows the basic pattern of the calculator. Each grammar rule recognizes one operator, and the embedded Java code executes the arithmetic based on that input. The rest of the grammar follows this pattern.

Indeed this calculator is so simple and fits the structure of a syntax tree so well that I don’t even need an Embedment Helper.

Arithmetic expressions are a common choice for illustrating how to use a parser; many articles and papers use some form of calculator example. But I don’t think this is very representative of what you have to deal with when working with a DSL. The big problem with using arithmetic expressions as examples is that they force you to deal with a rare problem (Nested Operator Expression) but avoid the common DSL-related problems that encourage the use of Semantic Model and Embedment Helper.