Interpreter design pattern and detailing in C

Published:

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

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.