Interpreter Design Pattern
Video Lecture
Overview
The Interpreter pattern helps to convert information from one language into another.
The language can be anything such as words in a sentence, numerical formulas or even software code.
The process is to convert the source information, into an Abstract Syntax Tree (AST) of Terminal and Non-Terminal expressions that all implement an interpret() method.
A Non-Terminal expression is a combination of other Non-Terminal and/or Terminal expressions.
Terminal means terminated, i.e., there is no further processing involved.
An AST root starts with a Non-Terminal expression and then resolves down each branch until all expressions terminate.
An example expression is A + B.
The A and B are Terminal expressions and the + is Non-Terminal because it depends on the two other Terminal expressions.
The Image below, is an AST for the expression 5 + 4 - 3 + 7 - 2
The official Interpreter pattern described in the original GoF Design Patterns book does not state how to construct an Abstract Syntax Tree. How your tree is constructed will depend on the grammatical constructs of your sentence that you want to interpret.
Abstract Syntax Trees can be created manually or dynamically from a custom parser script. In the first example code below, I construct the AST manually.
Once the AST is created, you can then choose the root node and then run the Interpret operation on that, and it should interpret the whole tree recursively.
Terminology
- Abstract Expression: Describe the method(s) that Terminal and Non-Terminal expressions should implement.
- Non-Terminal Expression: A composite of Terminal and/or Non-Terminal expressions.
- Terminal Expression: A leaf node Expression.
- Context: Context is state that can be passed through interpret operations if necessary.
- Client: Builds or is given an Abstract Syntax Tree to interpret.
Interpreter UML Diagram
Source Code
In this example, I interpret the string 5 + 4 - 3 + 7 - 2 and then calculate the result.
The grammar of the string follows a pattern of Number ⇾ Operator ⇾ Number ⇾ etc.
I convert the string into a list of tokens that I can refer to by index in the array.
I then construct the AST manually, by adding a
- Non-Terminal
Add row containing two Terminals for the 5 and 4,
- Non-Terminal
Subtract row containing the previous Non-Terminal row and the 3
- Non-Terminal
Add row containing the previous Non-Terminal row and the 7
- Non-Terminal
Subtract row containing the previous Non-Terminal row and the 2
The AST root becomes the final row that was added, and then I can run the interpret() method on that, which will interpret the full AST recursively because each AST row references the row above it.
./src/interpreter/interpreter-concept.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78 | // The Interpreter Pattern Concept
interface IAbstractExpression {
// All Terminal and Non-Terminal expressions will implement
// an `interpret` method
interpret(): number
}
class Numeral implements IAbstractExpression {
// Terminal Expression
value: number
constructor(value: string) {
this.value = parseInt(value)
}
interpret(): number {
return this.value
}
}
class Add implements IAbstractExpression {
// Non-Terminal Expression.
left: IAbstractExpression
right: IAbstractExpression
constructor(left: IAbstractExpression, right: IAbstractExpression) {
this.left = left
this.right = right
}
interpret() {
return this.left.interpret() + this.right.interpret()
}
}
class Subtract implements IAbstractExpression {
// Non-Terminal Expression.
left: IAbstractExpression
right: IAbstractExpression
constructor(left: IAbstractExpression, right: IAbstractExpression) {
this.left = left
this.right = right
}
interpret() {
return this.left.interpret() - this.right.interpret()
}
}
// The Client
// The sentence complies with a simple grammar of
// Number -> Operator -> Number -> etc,
const SENTENCE = '5 + 4 - 3 + 7 - 2'
console.log(SENTENCE)
// Split the sentence into individual expressions that will be added to
// an Abstract Syntax Tree(AST) as Terminal and Non - Terminal expressions
const TOKENS = SENTENCE.split(' ')
console.log(JSON.stringify(TOKENS))
// Manually Creating an Abstract Syntax Tree from the tokens
const AST: IAbstractExpression[] = [] // An array of AbstractExpressions
AST.push(new Add(new Numeral(TOKENS[0]), new Numeral(TOKENS[2]))) // 5 + 4
AST.push(new Subtract(AST[0], new Numeral(TOKENS[4]))) // ^ - 3
AST.push(new Add(AST[1], new Numeral(TOKENS[6]))) // ^ + 7
AST.push(new Subtract(AST[2], new Numeral(TOKENS[8]))) // ^ - 2
// Use the final AST row as the root node.
const AST_ROOT = AST.pop()
// Interpret recursively through the full AST starting from the root.
console.log((AST_ROOT as IAbstractExpression).interpret())
// Print out a representation of the AST_ROOT
console.dir(AST_ROOT, { depth: null })
|
Output
node ./dist/interpreter/interpreter-concept.js
5 + 4 - 3 + 7 - 2
["5","+","4","-","3","+","7","-","2"]
11
Subtract {
left: Add {
left: Subtract {
left: Add { left: Numeral { value: 5 }, right: Numeral { value: 4 } },
right: Numeral { value: 3 }
},
right: Numeral { value: 7 }
},
right: Numeral { value: 2 }
}
SBCODE Editor
Interpreter Use Case
The example use case will expand on the concept example by dynamically creating the AST and converting Roman numerals to integers as well as calculating the final result.
The Image below, is an AST for the expression 5 + IV - 3 + VII - 2
Example UML Diagram
Source Code
./src/interpreter/client.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | // The Interpreter Pattern Use Case Example
import IAbstractExpression from './iabstract-expression'
import Parser from './sentence-parser'
// The sentence complies with a simple grammar of
// Number -> Operator -> Number -> etc,
const SENTENCE = '5 + IV - 3 + VII - 2'
// const SENTENCE = "4 + II + XII + 1 + 2"
// const SENTENCE = "5 + 4 - 3 + 7 - 2"
// const SENTENCE = "V + IV - III + 7 - II"
// const SENTENCE= "CIX + V"
// const SENTENCE = "CIX + V - 3 + VII - 2"
// const SENTENCE = "MMMCMXCIX - CXIX + MCXXII - MMMCDXII - XVIII - CCXXXV"
console.log(SENTENCE)
const AST_ROOT = Parser.parse(SENTENCE)
// Interpret recursively through the full AST starting from the root.
console.log((AST_ROOT as IAbstractExpression).interpret())
// Print out a representation of the AST_ROOT
console.dir(AST_ROOT, { depth: null })
|
./src/interpreter/iabstract-expression.ts
| export default interface IAbstractExpression {
// All Terminal and Non-Terminal expressions will implement
// an `interpret` method
value?: number
left?: IAbstractExpression
right?: IAbstractExpression
interpret(): number
}
|
./src/interpreter/numeral.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | import IAbstractExpression from './iabstract-expression'
export default class Numeral implements IAbstractExpression {
// Terminal Expression
value: number
constructor(value: string | number) {
this.value = typeof value === 'string' ? parseInt(value) : value
}
interpret(): number {
return this.value
}
}
|
./src/interpreter/add.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | import IAbstractExpression from './iabstract-expression'
export default class Add implements IAbstractExpression {
// Non-Terminal Expression.
left: IAbstractExpression
right: IAbstractExpression
constructor(left: IAbstractExpression, right: IAbstractExpression) {
this.left = left
this.right = right
}
interpret(): number {
return this.left.interpret() + this.right.interpret()
}
}
|
./src/interpreter/subtract.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | import IAbstractExpression from './iabstract-expression'
export default class Subtract implements IAbstractExpression {
// Non-Terminal Expression.
left: IAbstractExpression
right: IAbstractExpression
constructor(left: IAbstractExpression, right: IAbstractExpression) {
this.left = left
this.right = right
}
interpret(): number {
return this.left.interpret() - this.right.interpret()
}
}
|
./src/interpreter/roman-numeral.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81 | // Roman Numeral Expression. This is a Non-Terminal Expression
import IAbstractExpression from './iabstract-expression'
import Numeral from './numeral'
export default class RomanNumeral implements IAbstractExpression {
// Non Terminal expression
romanNumeral: string
context: [string, number]
constructor(romanNumeral: string) {
this.romanNumeral = romanNumeral
this.context = [romanNumeral, 0]
}
interpret(): number {
RomanNumeral1000.interpret(this.context)
RomanNumeral100.interpret(this.context)
RomanNumeral10.interpret(this.context)
RomanNumeral1.interpret(this.context)
return new Numeral(this.context[1]).interpret()
}
}
class RomanNumeral1 extends RomanNumeral {
// Roman Numerals 1 - 9
static one = 'I'
static four = 'IV'
static five = 'V'
static nine = 'IX'
static multiplier = 1
static interpret(context: [string, number]) {
if (context[0].length === 0) {
return new Numeral(context[1]).interpret()
}
if (context[0].substring(0, 2) === this.nine) {
context[1] += 9 * this.multiplier
context[0] = context[0].substring(2)
} else if (context[0].substring(0, 1) === this.five) {
context[1] += 5 * this.multiplier
context[0] = context[0].substring(1)
} else if (context[0].substring(0, 2) === this.four) {
context[1] += +(4 * this.multiplier)
context[0] = context[0].substring(2)
}
while (context[0].length > 0 && context[0][0] === this.one) {
context[1] += 1 * this.multiplier
context[0] = context[0].substring(1)
}
return new Numeral(context[1]).interpret()
}
}
class RomanNumeral10 extends RomanNumeral1 {
// Roman Numerals 10 - 99
static one = 'X'
static four = 'XL'
static five = 'L'
static nine = 'XC'
static multiplier = 10
}
class RomanNumeral100 extends RomanNumeral1 {
// Roman Numerals 100 - 999
static one = 'C'
static four = 'CD'
static five = 'D'
static nine = 'CM'
static multiplier = 100
}
class RomanNumeral1000 extends RomanNumeral1 {
// Roman Numerals 1000 - 3999
static one = 'M'
static four = ''
static five = ''
static nine = ''
static multiplier = 1000
}
|
./src/interpreter/sentence-parser.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107 | // A Custom Parser for creating an Abstract Syntax Tree
import IAbstractExpression from './iabstract-expression'
import Add from './add'
import Numeral from './numeral'
import RomanNumeral from './roman-numeral'
import Subtract from './subtract'
export default class Parser {
// Dynamically create the Abstract Syntax Tree
static parse(sentence: string): IAbstractExpression | undefined {
// Create the AST from the sentence
const tokens = sentence.split(' ')
const tree: IAbstractExpression[] = [] // Abstract Syntax Tree
while (tokens.length > 1) {
const leftExpression = Parser.decideLeftExpression(
tree,
tokens
)
// get the operator, make the token list shorter
const operator = tokens.shift()
const right = tokens[0]
if (!Number(right)) {
tree.push(new RomanNumeral(right))
if (operator === '-') {
tree.push(
new Subtract(
leftExpression,
tree[tree.length - 1]
)
)
}
if (operator === '+') {
tree.push(
new Add(leftExpression, tree[tree.length - 1])
)
}
} else {
const rightExpression = new Numeral(right)
if (!tree.length) {
// Empty Data Structures return False by default
if (operator === '-') {
tree.push(
new Subtract(leftExpression, rightExpression)
)
}
if (operator === '+') {
tree.push(
new Add(leftExpression, rightExpression)
)
}
} else {
if (operator === '-') {
tree.push(
new Subtract(
tree[tree.length - 1],
rightExpression
)
)
}
if (operator === '+') {
tree.push(
new Add(
tree[tree.length - 1],
rightExpression
)
)
}
}
}
}
return tree.pop()
}
static decideLeftExpression(
tree: IAbstractExpression[],
tokens: string[]
): IAbstractExpression {
// On the First iteration, the left expression can be either a
// number or roman numeral.Every consecutive expression is
// reference to an existing AST row
const left = tokens.shift()
let leftExpression: IAbstractExpression
if (!tree.length) {
// only applicable if first round
if (!Number(left)) {
// if 1st token a roman numeral
tree = []
tree.push(new RomanNumeral(left as string))
leftExpression = tree[
tree.length - 1
] as IAbstractExpression
} else {
leftExpression = new Numeral(left as string)
}
return leftExpression
} else {
leftExpression = tree[tree.length - 1] as IAbstractExpression
return leftExpression
}
}
}
|
Output
node ./dist/interpreter/client.js
5 + IV - 3 + VII - 2
11
Subtract {
left: Add {
left: Subtract {
left: Add {
left: Numeral { value: 5 },
right: RomanNumeral { romanNumeral: 'IV', context: [ '', 4 ] }
},
right: Numeral { value: 3 }
},
right: RomanNumeral { romanNumeral: 'VII', context: [ '', 7 ] }
},
right: Numeral { value: 2 }
}
SBCODE Editor
Summary
-
ASTs are hard to create and are an enormous subject in themselves. My recommended approach is to create them manually first using a sample sentence to help understand all the steps individually, and then progress the conversion to be fully dynamic one step at a time ensuring that the grammatical constructs still work as you continue to progress.
-
The Interpreter pattern uses a class to represent each grammatical rule.
-
ASTs consist of multiple Non-Terminal and Terminal Expressions, that all implement an interpret() method.
-
Note that in the sample code above, the interpret() methods in the Non-Terminal expressions, all call further interpret() recursively. Only the Terminal expressions interpret() method returns an explicit value. See the Number class in the above code.
