Interpreter Pattern

The interpreter literally means a translator, someone who can convert from one form of speech to a another. The interpreter pattern converts a language's sentences into its grammar and interprets them.

Understanding the interpreter pattern requires background knowledge in automata and theory of computation. We'll briefly go over some of the concepts required to understand the pattern.

Every human language has an associated grammar that defines what constructs are legal or illegal. Similarly, computer languages are defined by grammar too. Given a snippet of code, the language defined by the grammar would determine if the code is syntactically correct or not. There are four types of grammar known as the Chomsky's hierarchy.

• Regular
• Context Free
• Context Sensitive
• Recursively Enumerable

We'll be interested in context free grammar for the purposes of this lesson. Most programming languages use context free grammars to specify the syntax of a language. A syntactically correct program however may or may not compile.

A CFG consists of four components:

• start symbol

• a set of terminal symbols

• a set of non-terminal symbols

• a set of productions (rules)

Let's immediately see an example to understand what is meant by each of the above terms. Consider the below productions or rules for an arithematic expression

1. <expression> --> number
2. <expression> --> <expression> + <expression>
3. <expression> --> <expression> - <expression>
4. <expression> --> <expression> * <expression>
5. <expression> --> <expression> / <expression>

The above rules say that the left hand side expression, which is a ...