The expression evaluator and interpreter pattern

The authors of this book believe that any programmer worth his salt needs to learn the rudiments of compiler construction for implementing mini-languages or domain-specific language (DSL) in his work. A compiler treats expressions as data, and expressions are mostly hierarchical in nature. We use a data structure called AST for representing the nodes of an expression tree. To convert textual expressions into an AST, we need to write a parser to analyze the constituents of an expression. The subsystem which feeds data to the parser is a module called lexical analyzer, which breaks the input stream into a series of tokens.

The definition of a mini language, and writing an evaluator for it, is dealt with by the GoF catalog as interpreter pattern.

In software design, the interpreter pattern is a design pattern that specifies how to evaluate sentences in a (mini) language. The basic idea is to have a class for each symbol (terminal or non-terminal...