//+------------------------------------------------------------------+ //| Interpreter.mqh | //| 2019-2020, dimitri pecheritsa | //| 792112@gmail.com | //+------------------------------------------------------------------+ //| interpreter — behavioral design pattern | //+------------------------------------------------------------------+ // design patterns: elements of reusable object-oriented software // gof > erich gamma, richard helm, ralph johnson, john vlissides // published — 1994 //+------------------------------------------------------------------+ //| intent | //+------------------------------------------------------------------+ // given a language, define a represention for its grammar // along with an interpreter that uses the representation // to interpret sentences in the language //+------------------------------------------------------------------+ //| benefits | //+------------------------------------------------------------------+ // aspect that may vary > grammar and interpretation of a language //+------------------------------------------------------------------+ //| applicability | //+------------------------------------------------------------------+ // there is a language to interpret // statements can be abstract syntax trees // simple grammar // parser generators // for complex grammar // don't build abstract syntax trees // efficiency is not a critical concern // interpreters translate parse trees first (state machine) //+------------------------------------------------------------------+ //| structure | //+------------------------------------------------------------------+ // // +----->|Context| // | // |Client|-------+ // | // +----->|AbstractExpression|*<----------------+ // |------------------| | // |Interpret(Context)| | // ^ | // | | // +-----------+-------------+ | // | | | // |TerminalExpression| |NonterminalExpression|o--+ // |------------------| |---------------------| // |Interpret(Context)| |Interpret(Context) | // #include <SRC\Patterns\PatternOrganizer.mqh> namespace Interpreter { //+------------------------------------------------------------------+ //| participants > abstract expression | //+------------------------------------------------------------------+ // declare abstract interpret method for all nodes class Context; class AbstractExpression { public: virtual void Interpret(Context&)=0; }; //+------------------------------------------------------------------+ //| participants > terminal expression | //+------------------------------------------------------------------+ // implement interpret method // associated with terminal symbols in the grammar // an instance is required for every terminal symbol in a sentence class TerminalExpression:public AbstractExpression { public: void Interpret(Context&); }; //+------------------------------------------------------------------+ //| participants > terminal expression > interpret | //+------------------------------------------------------------------+ void TerminalExpression::Interpret(Context& context) { context.m_result= StringSubstr(context.m_source,context.m_position,1)== CharToString(context.m_vocabulary); } //+------------------------------------------------------------------+ //| participants > nonterminal expression | //+------------------------------------------------------------------+ // required for every rule r = r1, r2, ..., rn in the grammar // maintains instances of abstract expression // for each of the symbols r1 through rn // implements interpret method for nonterminal symbols in the grammar // interpret method calls itself recursively on r1 through rn class NonterminalExpression:public AbstractExpression { protected: AbstractExpression* m_nonterminal_expression; AbstractExpression* m_terminal_expression; public: void Interpret(Context&); ~NonterminalExpression(void); }; //+------------------------------------------------------------------+ //| participants > nonterminal expression > destructor | //+------------------------------------------------------------------+ NonterminalExpression::~NonterminalExpression(void) { delete m_nonterminal_expression; delete m_terminal_expression; } //+------------------------------------------------------------------+ //| participants > nonterminal expression > interpret | //+------------------------------------------------------------------+ void NonterminalExpression::Interpret(Context& context) { if(context.m_position<StringLen(context.m_source)) { m_terminal_expression=new TerminalExpression; m_terminal_expression.Interpret(context); context.m_position++; if(context.m_result) { m_nonterminal_expression=new NonterminalExpression; m_nonterminal_expression.Interpret(context); } } } //+------------------------------------------------------------------+ //| participants > context | //+------------------------------------------------------------------+ // contains information that's global to the interpreter class Context { public: string m_source; char m_vocabulary; int m_position; bool m_result; //--- Context(char,string); void Result(void); }; //+------------------------------------------------------------------+ //| participants > context > constructor | //+------------------------------------------------------------------+ Context::Context(char vocabulary,string source): m_source(source), m_vocabulary(vocabulary), m_position(0), m_result(false) { } //+------------------------------------------------------------------+ //| participants > context > result | //+------------------------------------------------------------------+ void Context::Result(void) { printf("result is %s for m_source:'%s' with m_vocabulary:'%s'", (string)m_result,m_source,CharToString(m_vocabulary)); } //+------------------------------------------------------------------+ //| participants > client | //+------------------------------------------------------------------+ // builds (or is given) an abstract syntax tree // tree represents a sentence in the language // grammar defines language // tree is assembled from instances of the nonterminal expression and // terminal expression classes // call interpret method class Client:public ClientExample { public: string Output(void); void Run(void); }; string Client::Output(void) {return __FUNCTION__;} //+------------------------------------------------------------------+ //| collaborations | //+------------------------------------------------------------------+ // client // builds (or is given) the sentence // as an abstract syntax tree of nonterminal expression and // terminal expression // initializes the context and invokes the interpret operation // nonterminal expression // defines interpret method on each subexpression // terminal expression // interpret method defines the base case in the recursion // node // interpret method uses the context to store and access // the state of the interpreter void Client::Run(void) { //---language recognition grammar context (example) // V = {a}; L = V*; where V-m_vocabulary, L-language // correct chains: a, aa, aaa, ... // wrong chains: b, ab, aba, ... Context context_1('a',"aaa"); //chain ok Context context_2('a',"aba"); //wrong chain AbstractExpression* expression; //--- expression=new NonterminalExpression; expression.Interpret(context_1); context_1.Result(); //result ok delete expression; //--- expression=new NonterminalExpression; expression.Interpret(context_2); context_2.Result(); //bad result delete expression; } } //+------------------------------------------------------------------+ //| output | //+------------------------------------------------------------------+ // Interpreter::Client::Output // result is true for m_source:'aaa' with m_vocabulary:'a' // result is false for m_source:'aba' with m_vocabulary:'a' //+------------------------------------------------------------------+ //| consequences | //+------------------------------------------------------------------+ // easy to change and extend the grammar // inherit to change or extend the grammar // modify expressions incrementally // change old expressions to define new ones // easy to implement grammar // nodes // have similar implementations // easy to write // can be generated with a compiler/parser generator // complex grammars are hard to maintain // at least one class for every rule // hard to manage and maintain // parser or compiler generators are more appropriate // adding new ways to interpret expressions // easier to evaluate an expression // define a new operation on the expression // support pretty printing/type-checking // use visitor to avoid changing the grammar classes //+------------------------------------------------------------------+ //| implementation | //+------------------------------------------------------------------+ // creating the abstract syntax tree // doesn't address parsing // the tree can be created by // table-driven parser // hand-crafted (recursive) parser // client // defining the interpret operation // not in the expression classes // put interpret in a separate visitor object // grammar for a programming language operations // type-checking // optimization // code generation // terminal symbols with the flyweight pattern // grammars // whose sentences contain many occurrences // of a terminal symbol // might benefit from sharing a single copy of that symbol // for computer programs // each program variable will appear in many places // throughout the code // terminal nodes // generally don't store their tree m_position // parent nodes // pass them the context for interpretation // flyweight pattern applies // shared (intrinsic) state and passed-in (extrinsic) state // are distinct //+------------------------------------------------------------------+ //| related patterns | //+------------------------------------------------------------------+ // composite > the abstract syntax tree // flyweight > share terminal symbols within the abstract syntax tree // iterator > traverse the structure // visitor > maintain the behavior in each node // in the abstract syntax tree in one class //+------------------------------------------------------------------+
