I am trying to understand how interpreter pattern can actually be implemented. 

[![enter image description here](https://i.stack.imgur.com/nPNP3.gif)](https://i.stack.imgur.com/nPNP3.gif)

As per the diagram; an expression has 2 nodes: terminal & non-terminal. Can it have multiple type of nodes as well? Because I believe it is drawn considering the math expression transformed in binary tree DS where leaf nodes are number and non-leaf nodes are operations: +,-,/ etc.

Somewhere I read that [java.util.Pattern](http://docs.oracle.com/javase/8/docs/api/java/util/regex/Pattern.html) is an example of interpreter pattern. 

```
Pattern pattern = Pattern.compile("^[abc](ab|c?d)?ef$");
Matcher matcher = pattern.matcher("some RE");
if(matcher.matches()){ .. }

```

So I was trying to relate if my implementation of RE engine: [BooleanSequence](https://github.com/NaturalIntelligence/BooleanSequence) is also an example of interpreter pattern.

```
BooleanSequence seq = new BooleanSequence("[abc](ab|c?d)?ef");
seq.compile();seq.minimize();
Matcher matcher = seq.getCoreMatcher();
matcher.match("some RE");

```

Implementation note:

Main class BooleanSequence(BS) takes RE (can be considered as **context**) and build some kind of in-memory DS, where each char of RE is a node. There are many types of node, like: normal, range, lazy, any etc. I believe it can be considered as **expression** as given in diagram.

Node class also has match(). BS gives a matcher or it can be created separately. It is completely isolated from BS class. And there are many types of matchers (currently 3). Matcher calls match() of all the nodes until whole expression is evaluated.