Design patterns: Interpreter
I am just as I promised after two weeks and as I promised I will be describing the interpreter design pattern, as you can guess it interprets some content on the content we want, ie it is used in translators and compilers, etc. more precisely in the article.
Intent
- Interpretation of specific expressions, e.g. to a specific programming language.
- Defining the description of the grammar of the interpreted language.
Problem
The problem in which the interpreter can be used may relate to domains that relate to languages that we do not want to translate ourselves on each occasion, so we can create an interpreter for them that will translate their grammar itself.
Use when:
- You want to create your own compiler
- You create a project that has functionalities that need to be interpreted into a language that the user understands.
- Some tasks in the project are written in the interpreted language and there exists a grammar to it.
Discussion
Each abstract base class of the interpreter defines the interpret() method, and each concrete class inheriting from the base class implements the interpret() method, which translates the specific part of the language required at the moment.
As you can see, understanding the use of the interpreter pattern is easy, but its implementation is a little more difficult, the description of the implementation and the pattern structure further in the article.
Structure
As you can see in the UML diagram below, the interpreter consists of:
- The Context class that holds the data being interpreted.
- The AbstractExpression class, which interprets the commands.
- Specific classes that inherit from the AbstractExpression class, which interpret Context for individual cases.
The schema in the interpreter pattern code looks like this:
namespace InterpreterSchema
{
class Context
{
}
abstract class AbstractExpression
{
public abstract void Interpret(Context context);
}
class TerminalExpression : AbstractExpression
{
public override void Interpret(Context context)
{
Console.WriteLine("Called Terminal.Interpret()");
}
}
class NonterminalExpression : AbstractExpression
{
public override void Interpret(Context context)
{
Console.WriteLine("Called Nonterminal.Interpret()");
}
}
class MainApp
{
static void Main()
{
var context = new Context();
var list = new List<AbstractExpression>();
list.Add(new TerminalExpression());
list.Add(new NonterminalExpression());
list.Add(new TerminalExpression());
list.Add(new TerminalExpression());
foreach (AbstractExpression exp in list)
{
exp.Interpret(context);
}
}
}
}
The UML diagram of the interpreter pattern can also look like this:
The only difference is that there is no Context class, the code looks like this:
namespace Interpreter
{
interface Expression
{
void interpret(Stack<int> s);
}
class TerminalExpression_Number : Expression
{
private int number;
public TerminalExpression_Number(int number)
{
this.number = number;
}
public void interpret(Stack<int> s)
{
s.Push(number);
}
}
class TerminalExpression_Plus : Expression
{
public void interpret(Stack<int> s)
{
s.Push(s.Pop() + s.Pop());
}
}
class TerminalExpression_Minus : Expression
{
public void interpret(Stack<int> s)
{
s.Push(-s.Pop() + s.Pop());
}
}
class Parser
{
private List<Expression> parseTree = new List<Expression>();
public Parser(string s)
{
foreach (string token in s.Split(' '))
{
if (token.Equals("+"))
{
parseTree.Add(new TerminalExpression_Plus());
}
else if (token.Equals("-"))
{
parseTree.Add(new TerminalExpression_Minus());
}
else
{
parseTree.Add(new TerminalExpression_Number(Int32.Parse(token)));
}
}
}
public int evaluate()
{
Stack<int> context = new Stack<int>();
foreach (Expression e in parseTree)
{
e.interpret(context);
}
return context.Pop();
}
}
class Program
{
static void Main(string[] args)
{
string expression = "4 4 2 - +";
Parser p = new Parser(expression);
Console.WriteLine("'" + expression + "' equals " + p.evaluate());
Console.ReadKey();
}
}
}
In this example, we divide the characters, the numbers we put on the stack, when we want to add them or remove them, we subtract the numbers from the stack one by one, we get the result:
Real-life examples
An example of this is the musical keyboard, which interprets clicks on keys for specific tones and notes.
Roman numeral system
The real-life example that we will process in the code is based on the Roman numeral system, which we will interpret to the decimal system, that is, the numerical system that we use every day.
This is how it looks in the code:
namespace InterpreterRomanNumbers
{
class Context
{
private string _input;
private int _output;
public Context(string input)
{
_input = input;
}
public string Input
{
get { return _input; }
set { _input = value; }
}
public int Output
{
get { return _output; }
set { _output = value; }
}
}
abstract class Expression
{
public void Interpret(Context context)
{
if (context.Input.Length == 0)
return;
if (context.Input.StartsWith(Nine()))
{
context.Output += (9 * Multiplier());
context.Input = context.Input.Substring(2);
}
else if (context.Input.StartsWith(Four()))
{
context.Output += (4 * Multiplier());
context.Input = context.Input.Substring(2);
}
else if (context.Input.StartsWith(Five()))
{
context.Output += (5 * Multiplier());
context.Input = context.Input.Substring(1);
}
while (context.Input.StartsWith(One()))
{
context.Output += (1 * Multiplier());
context.Input = context.Input.Substring(1);
}
}
public abstract string One();
public abstract string Four();
public abstract string Five();
public abstract string Nine();
public abstract int Multiplier();
}
class HundredExpression : Expression
{
public override string One() { return "C"; }
public override string Four() { return "CD"; }
public override string Five() { return "D"; }
public override string Nine() { return "CM"; }
public override int Multiplier() { return 100; }
}
class OneExpression : Expression
{
public override string One() { return "I"; }
public override string Four() { return "IV"; }
public override string Five() { return "V"; }
public override string Nine() { return "IX"; }
public override int Multiplier() { return 1; }
}
class TenExpression : Expression
{
public override string One() { return "X"; }
public override string Four() { return "XL"; }
public override string Five() { return "L"; }
public override string Nine() { return "XC"; }
public override int Multiplier() { return 10; }
}
class ThousandExpression : Expression
{
public override string One() { return "M"; }
public override string Four() { return " "; }
public override string Five() { return " "; }
public override string Nine() { return " "; }
public override int Multiplier() { return 1000; }
}
class Program
{
static void Main()
{
string roman = null;
while (!string.IsNullOrEmpty(roman = Console.ReadLine()))
{
Context context = new Context(roman);
List<Expression> tree = new List<Expression>();
tree.Add(new ThousandExpression());
tree.Add(new HundredExpression());
tree.Add(new TenExpression());
tree.Add(new OneExpression());
foreach (Expression exp in tree)
{
exp.Interpret(context);
}
Console.WriteLine("{0} = {1}",
roman, context.Output);
}
Console.ReadKey();
}
}
}
It looks like in the previous examples, in the client we create and save specific classes to the list and interpret them in the foreach loop one by one. The main Interpret() method is in the Expression class, which interprets all Roman characters and calculates them into decimal values. Analyze this code thoroughly, you will not learn anything by looking at examples 😐
The results are:
Summary
That’s all philosophy about the interpreter pattern 🙂
Link to github with the whole code from this article: https://github.com/Slaw145/InterpreterTutorial
This content also you can find on my blog http://devman.pl/programtech/design-patterns-interpreter/
If you recognise it as useful, share it with others so that others can also use it.
Leave upvote and follow and wait for next articles :) .
I am aware that a lot of these patterns and it is difficult to understand all of them, but come back to them sometimes as you will have to solve a problem that can be solved with some pattern there is probably no one or there are very few people who remember all patterns 🙂
In the next article, we will talk about the Iterator pattern.
And NECESSERILY join the DevmanCommunity community on fb, part of the community is in one place 🙂
– site on fb: Devman.pl-Sławomir Kowalski
– group on fb: DevmanCommunity
Ask, comment underneath at the end of the post, share it, rate it, whatever you want🙂.