Interpreter design pattern and detailing in C

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Introduction:

An interpreter normally means a computer program that executes, i.e. performs, instructions written in a programming language. An interpreter may be a program that either

1. executes the source code directly

2. translates source code into some efficient intermediate representation (code) and immediately executes this

3. explicitly executes stored precompiled code made by a compiler which is part of the interpreter system

Perl, Python, MATLAB, and Ruby are examples of type 2, while UCSD Pascal and Java are type 3: Source programs are compiled ahead of time and stored as machine independent code, which is then linked at run-time and executed by an interpreter and/or compiler (for JIT systems). Some systems, such as Smalltalk, BASIC and others, may also combine 2 and 3.

While interpreting and compiling are the two main means by which programming languages are implemented, these are not fully distinct categories, one of the reasons being that most interpreting systems also perform some translation work, just like compilers. The terms "interpreted language" or "compiled language" merely mean that the canonical implementation of that language is an interpreter or a compiler; a high level language is basically an abstraction which is (ideally) independent of particular implementations.

Interpreter Design Pattern

Intent

Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language.

Map a domain to a language, the language to a grammar, and the grammar to a hierarchical object-oriented design.

Problem

A class of problems occurs repeatedly in a well-defined and well-understood domain. If the domain were characterized with a "language", then problems could be easily solved with an interpretation "engine".

Discussion

The Interpreter pattern discusses: defining a domain language (i.e. problem characterization) as a simple language grammar, representing domain rules as language sentences, and interpreting these sentences to solve the problem. The pattern uses a class to represent each grammar rule. And since grammars are usually hierarchical in structure, an inheritance hierarchy of rule classes maps nicely.

An abstract base class specifies the method interpret(). Each concrete subclass implements interpret() by accepting (as an argument) the current state of the language stream, and adding its contribution to the problem solving process.

Structure

Interpreter suggests modeling the domain with a recursive grammar. Each rule in the grammar is either a 'composite' (a rule that references other rules) or a terminal (a leaf node in a tree structure). Interpreter relies on the recursive traversal of the Composite pattern to interpret the 'sentences' it is asked to process.

Example

The Intepreter pattern defines a grammatical representation for a language and an interpreter to interpret the grammar. Musicians are examples of Interpreters. The pitch of a sound and its duration can be represented in musical notation on a staff. This notation provides the language of music. Musicians playing the music from the score are able to reproduce the original pitch and duration of each sound represented.

Check list

Decide if a "little language" offers a justifiable return on investment.

Define a grammar for the language.

Map each production in the grammar to a class.

Organize the suite of classes into the structure of the Composite pattern.

Define an interpret(Context) method in the Composite hierarchy.

The Context object encapsulates the current state of the input and output as the former is parsed and the latter is accumulated. It is manipulated by each grammar class as the "interpreting" process transforms the input into the output.

Rules of thumb

Considered in its most general form (i.e. an operation distributed over a class hierarchy based on the Composite pattern), nearly every use of the Composite pattern will also contain the Interpreter pattern. But the Interpreter pattern should be reserved for those cases in which you want to think of this class hierarchy as defining a language.

Interpreter can use State to define parsing contexts.

The abstract syntax tree of Interpreter is a Composite (therefore Iterator and Visitor are also applicable).

Terminal symbols within Interpreter's abstract syntax tree can be shared with Flyweight.

The pattern doesn't address parsing. When the grammar is very complex, other techniques (such as a parser) are more appropriate.

Code Example:

#include <iostream.h>

#include <string.h>

class Thousand;

class Hundred;

class Ten;

class One;

class RNInterpreter

{

public:

RNInterpreter(); // ctor for client

RNInterpreter(int){}

// ctor for subclasses, avoids infinite loop

int interpret(char*); // interpret() for client

virtual void interpret(char *input, int &total)

{

// for internal use

int index;

index = 0;

if (!strncmp(input, nine(), 2))

{

total += 9 * multiplier();

index += 2;

}

else if (!strncmp(input, four(), 2))

{

total += 4 * multiplier();

index += 2;

}

else

{

if (input[0] == five())

{

total += 5 * multiplier();

index = 1;

}

else

index = 0;

for (int end = index + 3; index < end; index++)

if (input[index] == one())

total += 1 * multiplier();

else

break;

}

strcpy(input, &(input[index]));

} // remove leading chars processed

protected:

// cannot be pure virtual because client asks for instance

virtual char one(){}

virtual char *four(){}

virtual char five(){}

virtual char *nine(){}

virtual int multiplier(){}

private:

RNInterpreter *thousands;

RNInterpreter *hundreds;

RNInterpreter *tens;

RNInterpreter *ones;

};

class Thousand: public RNInterpreter

{

public:

// provide 1-arg ctor to avoid infinite loop in base class ctor

Thousand(int): RNInterpreter(1){}

protected:

char one()

{

return 'M';

}

char *four()

{

return "";

}

char five()

{

return '\0';

}

char *nine()

{

return "";

}

int multiplier()

{

return 1000;

}

};

class Hundred: public RNInterpreter

{

public:

Hundred(int): RNInterpreter(1){}

protected:

char one()

{

return 'C';

}

char *four()

{

return "CD";

}

char five()

{

return 'D';

}

char *nine()

{

return "CM";

}

int multiplier()

{

return 100;

}

};

class Ten: public RNInterpreter

{

public:

Ten(int): RNInterpreter(1){}

protected:

char one()

{

return 'X';

}

char *four()

{

return "XL";

}

char five()

{

return 'L';

}

char *nine()

{

return "XC";

}

int multiplier()

{

return 10;

}

};

class One: public RNInterpreter

{

public:

One(int): RNInterpreter(1){}

protected:

char one()

{

return 'I';

}

char *four()

{

return "IV";

}

char five()

{

return 'V';

}

char *nine()

{

return "IX";

}

int multiplier()

{

return 1;

}

};

RNInterpreter::RNInterpreter()

{

// use 1-arg ctor to avoid infinite loop

thousands = new Thousand(1);

hundreds = new Hundred(1);

tens = new Ten(1);

ones = new One(1);

}

int RNInterpreter::interpret(char *input)

{

int total;

total = 0;

thousands->interpret(input, total);

hundreds->interpret(input, total);

tens->interpret(input, total);

ones->interpret(input, total);

if (strcmp(input, ""))

// if input was invalid, return 0

return 0;

return total;

}

int main()

{

RNInterpreter interpreter;

char input[20];

cout << "Enter Roman Numeral: ";

while (cin >> input)

{

cout << " interpretation is " << interpreter.interpret(input) << endl;

cout << "Enter Roman Numeral: ";

}

}

OutPut:

Enter Roman Numeral: MCMXCVI

interpretation is 1996

Enter Roman Numeral: MMMCMXCIX

interpretation is 3999

Enter Roman Numeral: MMMM

interpretation is 0

Enter Roman Numeral: MDCLXVIIII

interpretation is 0

Enter Roman Numeral: CXCX

interpretation is 0

Enter Roman Numeral: MDCLXVI

interpretation is 1666

Enter Roman Numeral: DCCCLXXXVIII

interpretation is 888