24. Interpreter

Interpreter Pattern: Define the grammar of a language and create an interpreter to interpret sentences in that language, where "language" refers to code that uses prescribed formats and grammars. The Interpreter pattern is a kind of behavioral pattern.

The Interpreter pattern consists of the following roles:

Abstract Expression: An Abstract Interpretation operation is declared in an abstract expression, which is the common parent of all terminator and non-terminator expressions.
TerminalExpression: TerminalExpressions are subclasses of abstract expressions that implement interpretations associated with grammatical terminators, and each terminator in a sentence is an instance of that class. Usually there are only a few terminator expression classes in an interpreter pattern, and their instances can form more complex sentences through non-terminator expressions.
Non-terminal expression: Non-terminal expression is also a subclass of abstract expression. It implements the interpretation of non-terminal in grammar. Since non-terminal expression can contain terminal expression or continue to contain non-terminal expression, its interpretation is usually done recursively.
Context: The environment class, also known as the context class, is used to store global information outside the interpreter, usually temporarily storing statements that need to be interpreted.

1. Main Advantages

(1) It is easy to change and expand grammar. Since classes are used to represent grammatical rules of language in interpreter mode, we can change or extend grammar through inheritance and other mechanisms.
(2) Each rule can be expressed as a class, so a simple language can be easily implemented.
(3) It is easier to realize grammar. In the abstract syntax tree, each expression node class is implemented in a similar way. The coding of these classes is not particularly complicated, and the node class code can be automatically generated by some tools.
(4) It is convenient to add new explanatory expressions. If users need to add new interpretative expressions, they only need to add a new terminator expression or non-terminator expression class. The original expression class code does not need to be modified, which conforms to the "open-close principle".

2. Main shortcomings

(1) It is difficult to maintain complex grammar. In interpreter mode, each rule needs to define at least one class, so if a language contains too many grammar rules, the number of classes will increase dramatically, which makes the system difficult to manage and maintain. At this time, we can consider using parser to replace interpreter mode.
(2) The execution efficiency is low. Because a large number of loops and recursive calls are used in interpreter mode, it is slow to interpret more complex sentences, and the debugging process of the code is more troublesome.

3. Applicable Scenario

(1) A sentence in a language that needs to be interpreted and executed can be represented as an abstract grammar tree.
(2) Some recurring problems can be expressed in a simple language.
(3) The grammar of a language is relatively simple.
(4) Implementation efficiency is not a key issue. [Note: Efficient interpreters are usually implemented not by directly interpreting abstract grammar trees, but by converting them into other forms. The implementation efficiency of interpreter mode is not high. ]

/**
 * 2018/12/6
 * Abstract expression
 *
 * @author machuanpeng
 */ 
public interface AbstractNode {
	public abstract String interpret();
}
/**
 * 2018/12/6
 * Termination expression
 *
 * @author machuanpeng
 */
public class ValueNode implements AbstractNode {
    private int value;
    
    public ValueNode(int value){
        this.value=value;
    }
        
    public int interpret(){
        return this.value;
    }
}
/**
 * 2018/12/6
 *  Non-terminal expression abstract class
 *
 * @author machuanpeng
 */
public abstract class SymbolNode implements AbstractNode {
    protected AbstractNode left;
    protected AbstractNode right;
    
    public SymbolNode(AbstractNode left,AbstractNode right) {
        this.left=left;
        this.right=right;
    }
}
/**
 * 2018/12/6
 * Multiplicative expression
 *
 * @author machuanpeng
 */
public class MulNode extends SymbolNode {
    public MulNode(AbstractNode left,AbstractNode right) {
        super(left,right);
    }
    
    public int interpret(){
        return left.interpret() * right.interpret();
    }
}
/**
 * 2018/12/6
 * Remainder expression
 *
 * @author machuanpeng
 */
public class ModNode extends SymbolNode {
    public ModNode(AbstractNode left,AbstractNode right) {
        super(left,right);
    }
    
    public int interpret(){
        return left.interpret() % right.interpret();
    }
}

/**
 * 2018/12/6
 * Division expression
 *
 * @author machuanpeng
 */
public class DivNode extends SymbolNode {
    public DivNode(AbstractNode left,AbstractNode right) {
        super(left,right);
    }
    
    public int interpret(){
        return left.interpret() / right.interpret();
    }
}

/**
 * 2018/12/6
 * Instruction processing
 *
 * @author machuanpeng
 */
public class InstructionHandler{
    
    private String statement;
    private AbstractNode node;
    
    public void build(String statement){
        
        AbstractNode left=null,
        AbstractNode right=null;
        Stack stack=new Stack();
        
        String[] statementArr=statement.split(" ");
        
        for(int i=0;i<statementArr.length;i++){    
            if(statementArr[i].equalsIgnoreCase("*")){
                left=(AbstractNode)stack.pop();
                int val=Integer.parseInt(statementArr[++i]);
                right=new ValueNode(val); 
                stack.push(new MulNode(left,right));
            }else if(statementArr[i].equalsIgnoreCase("/")){
                left=(AbstractNode)stack.pop();
                int val=Integer.parseInt(statementArr[++i]);
                right=new ValueNode(val); 
                stack.push(new DivNode(left,right));                
            }else if(statementArr[i].equalsIgnoreCase("%")){
                left=(AbstractNode)stack.pop();
                int val=Integer.parseInt(statementArr[++i]);
                right=new ValueNode(val); 
                stack.push(new ModNode(left,right));               
            }else{
                stack.push(new ValueNode(Integer.parseInt(statementArr[i])));
            }
        }
        this.node=(AbstractNode)stack.pop();
    }
    
    public int compute()
        return node.interpret();
    }
}

Test:

public class Client{
    public static void main(String args[]){
        
        String statement = "3 * 2 * 4 / 6 % 5";
        
        Calculator calculator = new Calculator();
        calculator.build(statement);
        int result = calculator.compute();
        System.out.println(statement + " = " + result);    
    }
}

Tags: Programming calculator

Posted on Thu, 10 Oct 2019 02:59:13 -0700 by gerry123