Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit1f68339

Browse files
committed
Interpreter explanation
1 parent3b1f82a commit1f68339

File tree

2 files changed

+175
-18
lines changed

2 files changed

+175
-18
lines changed

‎interpreter/README.md

Lines changed: 148 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -10,22 +10,161 @@ tags:
1010
---
1111

1212
##Intent
13-
Given a language, define a representation for its grammar along
14-
with an interpreter that uses the representation to interpret sentences in the
15-
language.
13+
14+
Given a language, define a representation for its grammar along with an interpreter that uses the
15+
representation to interpret sentences in the language.
16+
17+
##Explanation
18+
19+
Real-world example
20+
21+
>The halfling kids are learning basic math at school. They start from the very basics "1 + 1",
22+
>"4 - 2", "5 + 5", and so forth.
23+
24+
In plain words
25+
26+
>Interpreter pattern interprets sentences in the desired language.
27+
28+
Wikipedia says
29+
30+
>In computer programming, the interpreter pattern is a design pattern that specifies how to
31+
>evaluate sentences in a language. The basic idea is to have a class for each symbol (terminal or
32+
>nonterminal) in a specialized computer language. The syntax tree of a sentence in the language
33+
>is an instance of the composite pattern and is used to evaluate (interpret) the sentence for
34+
>a client.
35+
36+
**Programmatic example**
37+
38+
To be able to interpret basic math, we need a hierarchy of expressions. The basic abstraction for
39+
it is the`Expression` class.
40+
41+
```java
42+
publicabstractclassExpression {
43+
44+
publicabstractintinterpret();
45+
46+
@Override
47+
publicabstractStringtoString();
48+
}
49+
```
50+
51+
The simplest of the expressions is the`NumberExpression` that contains only a single integer
52+
number.
53+
54+
```java
55+
publicclassNumberExpressionextendsExpression {
56+
57+
privatefinalint number;
58+
59+
publicNumberExpression(intnumber) {
60+
this.number= number;
61+
}
62+
63+
publicNumberExpression(Strings) {
64+
this.number=Integer.parseInt(s);
65+
}
66+
67+
@Override
68+
publicintinterpret() {
69+
return number;
70+
}
71+
72+
@Override
73+
publicStringtoString() {
74+
return"number";
75+
}
76+
}
77+
```
78+
79+
The more complex expressions are operations such as`PlusExpression`,`MinusExpression`, and
80+
`MultiplyExpression`. Here's the first of them, the others are similar.
81+
82+
```java
83+
publicclassPlusExpressionextendsExpression {
84+
85+
privatefinalExpression leftExpression;
86+
privatefinalExpression rightExpression;
87+
88+
publicPlusExpression(ExpressionleftExpression,ExpressionrightExpression) {
89+
this.leftExpression= leftExpression;
90+
this.rightExpression= rightExpression;
91+
}
92+
93+
@Override
94+
publicintinterpret() {
95+
return leftExpression.interpret()+ rightExpression.interpret();
96+
}
97+
98+
@Override
99+
publicStringtoString() {
100+
return"+";
101+
}
102+
}
103+
```
104+
105+
Now we are able to show the interpreter pattern in action parsing some simple math.
106+
107+
```java
108+
// the halfling kids are learning some basic math at school
109+
// define the math string we want to parse
110+
finalvar tokenString="4 3 2 - 1 + *";
111+
112+
// the stack holds the parsed expressions
113+
var stack=newStack<Expression>();
114+
115+
// tokenize the string and go through them one by one
116+
var tokenList= tokenString.split("");
117+
for (var s: tokenList) {
118+
if (isOperator(s)) {
119+
// when an operator is encountered we expect that the numbers can be popped from the top of
120+
// the stack
121+
var rightExpression= stack.pop();
122+
var leftExpression= stack.pop();
123+
LOGGER.info("popped from stack left: {} right: {}",
124+
leftExpression.interpret(), rightExpression.interpret());
125+
var operator= getOperatorInstance(s, leftExpression, rightExpression);
126+
LOGGER.info("operator: {}", operator);
127+
var result= operator.interpret();
128+
// the operation result is pushed on top of the stack
129+
var resultExpression=newNumberExpression(result);
130+
stack.push(resultExpression);
131+
LOGGER.info("push result to stack: {}", resultExpression.interpret());
132+
}else {
133+
// numbers are pushed on top of the stack
134+
var i=newNumberExpression(s);
135+
stack.push(i);
136+
LOGGER.info("push to stack: {}", i.interpret());
137+
}
138+
}
139+
// in the end, the final result lies on top of the stack
140+
LOGGER.info("result: {}", stack.pop().interpret());
141+
```
142+
143+
Executing the program produces the following console output.
144+
145+
```
146+
popped from stack left: 1 right: 1
147+
operator: +
148+
push result to stack: 2
149+
popped from stack left: 4 right: 2
150+
operator: *
151+
push result to stack: 8
152+
result: 8
153+
```
16154

17155
##Class diagram
156+
18157
![alt text](./etc/interpreter_1.png"Interpreter")
19158

20159
##Applicability
21-
Use the Interpreter pattern when there is a language to
22-
interpret, and you can represent statements in the language as abstract syntax
23-
trees. The Interpreter pattern works best when
24160

25-
* the grammar is simple. For complex grammars, the class hierarchy for the grammar becomes large and unmanageable. Tools such as parser generators are a better alternative in such cases. They can interpret expressions without building abstract syntax trees, which can save space and possibly time
26-
* efficiency is not a critical concern. The most efficient interpreters are usually not implemented by interpreting parse trees directly but by first translating them into another form. For example, regular expressions are often transformed into state machines. But even then, the translator can be implemented by the Interpreter pattern, so the pattern is still applicable
161+
Use the Interpreter pattern when there is a language to interpret, and you can represent statements
162+
in the language as abstract syntax trees. The Interpreter pattern works best when
163+
164+
* The grammar is simple. For complex grammars, the class hierarchy for the grammar becomes large and unmanageable. Tools such as parser generators are a better alternative in such cases. They can interpret expressions without building abstract syntax trees, which can save space and possibly time
165+
* Efficiency is not a critical concern. The most efficient interpreters are usually not implemented by interpreting parse trees directly but by first translating them into another form. For example, regular expressions are often transformed into state machines. But even then, the translator can be implemented by the Interpreter pattern, so the pattern is still applicable
27166

28-
##Real world examples
167+
##Known uses
29168

30169
*[java.util.Pattern](http://docs.oracle.com/javase/8/docs/api/java/util/regex/Pattern.html)
31170
*[java.text.Normalizer](http://docs.oracle.com/javase/8/docs/api/java/text/Normalizer.html)

‎interpreter/src/main/java/com/iluwatar/interpreter/App.java

Lines changed: 27 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -34,59 +34,77 @@
3434
*
3535
* <p>In this example we use the Interpreter pattern to break sentences into expressions ({@link
3636
* Expression}) that can be evaluated and as a whole form the result.
37+
*
38+
* <p>Expressions can be evaluated using prefix, infix or postfix notations This sample uses
39+
* postfix, where operator comes after the operands.
40+
*
3741
*/
3842
@Slf4j
3943
publicclassApp {
4044

4145
/**
4246
* Program entry point.
43-
*
44-
* <p>Expressions can be evaluated using prefix, infix or postfix notations This sample uses
45-
* postfix, where operator comes after the operands.
46-
*
47-
* @param args command line args
47+
* @param args program arguments
4848
*/
4949
publicstaticvoidmain(String[]args) {
50-
vartokenString ="4 3 2 - 1 + *";
50+
51+
// the halfling kids are learning some basic math at school
52+
// define the math string we want to parse
53+
finalvartokenString ="4 3 2 - 1 + *";
54+
55+
// the stack holds the parsed expressions
5156
varstack =newStack<Expression>();
5257

58+
// tokenize the string and go through them one by one
5359
vartokenList =tokenString.split(" ");
5460
for (vars :tokenList) {
5561
if (isOperator(s)) {
62+
// when an operator is encountered we expect that the numbers can be popped from the top of
63+
// the stack
5664
varrightExpression =stack.pop();
5765
varleftExpression =stack.pop();
5866
LOGGER.info("popped from stack left: {} right: {}",
5967
leftExpression.interpret(),rightExpression.interpret());
6068
varoperator =getOperatorInstance(s,leftExpression,rightExpression);
6169
LOGGER.info("operator: {}",operator);
6270
varresult =operator.interpret();
71+
// the operation result is pushed on top of the stack
6372
varresultExpression =newNumberExpression(result);
6473
stack.push(resultExpression);
6574
LOGGER.info("push result to stack: {}",resultExpression.interpret());
6675
}else {
76+
// numbers are pushed on top of the stack
6777
vari =newNumberExpression(s);
6878
stack.push(i);
6979
LOGGER.info("push to stack: {}",i.interpret());
7080
}
7181
}
82+
// in the end, the final result lies on top of the stack
7283
LOGGER.info("result: {}",stack.pop().interpret());
7384
}
7485

86+
/**
87+
* Checks whether the input parameter is an operator.
88+
* @param s input string
89+
* @return true if the input parameter is an operator
90+
*/
7591
publicstaticbooleanisOperator(Strings) {
7692
returns.equals("+") ||s.equals("-") ||s.equals("*");
7793
}
7894

7995
/**
80-
* Get expression for string.
96+
* Returns correct expression based on the parameters.
97+
* @param s input string
98+
* @param left expression
99+
* @param right expression
100+
* @return expression
81101
*/
82102
publicstaticExpressiongetOperatorInstance(Strings,Expressionleft,Expressionright) {
83103
switch (s) {
84104
case"+":
85105
returnnewPlusExpression(left,right);
86106
case"-":
87107
returnnewMinusExpression(left,right);
88-
case"*":
89-
returnnewMultiplyExpression(left,right);
90108
default:
91109
returnnewMultiplyExpression(left,right);
92110
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp