Data Structures   3.  Sorts of Domain Definitions 4.  Manipulations of Domain Definitions 5.  Translating Domain Definitions 6.  Dialogue Sessions 7.  Example of Concentric Circles 8.  Example of Domain Substitution applied to Concentric Circles 9.  Example of an Order Processing Application 10.Example of an Airport Information System 11.Example of a Rental Boat Business 12.Benefits of Domain Definitions

##### INTERPRETER

1 Purpose

2 Problem Description

3 Domain Definitions

4 Elisa Components

5 Remarks

1  Purpose

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

2  Problem Description

If a particular kind of problem occurs often enough, then it might be worthwhile to express instances of the problem as sentences in a simple language. Then you can build an interpreter that solves the problem by interpreting these sentences.

For example, searching for strings that match a pattern is a common problem. Regular expressions are a standard language for specifying patterns of strings. Rather than building custom algorithms to match each pattern against strings, search algorithms could interpret a regular expression that specifies a set of strings to match.

The Interpreter pattern describes how to define a grammar for simple languages, represent sentences in the language, and interpret these sentences. In this example, the pattern describes how to define a grammar for regular expressions, represent a particular regular expression, and how to interpret that regular expression.

Suppose the following grammar defines the regular expressions:

```    expression ::= literal | alternation | sequence | repetition |
'(' expression ')'
alternation ::= expression  '|' expression
sequence ::= expression '&' expression
repetition ::= expression '*'
literal ::= 'a' | 'b' | 'c' | ... { 'a' | 'b' | 'c' | ... }*
```

The symbol `expression` is the start symbol, and `literal` is a terminal symbol defining simple words.

The Interpreter pattern uses a class to represent each grammar rule. Symbols on the right-hand side of the rule are instance variables of these classes. The grammar above is represented by five classes: an abstract class RegularExpression and its four subclasses LiteralExpression, AlternationExpression, SequenceExpression, and RepetitionExpression. The last three classes define variables that hold subexpressions.

Every regular expression defined by this grammar is represented by an abstract syntax tree made up of instances of these classes. For example, the abstract syntax tree

represents the regular expression

```    raining & (dogs | cats) *
```

We can create an interpreter for these regular expressions by defining the Interpret operation on each subclass of RegularExpression. Interpret takes as an argument the context in which to interpret the expression. The context contains the input string and information on how much of it has been matched so far. Each subclass of RegularExpression implements Interpret to match the next part of the input string based on the current context. For example,

• LiteralExpression will check if the input matches the literal it defines,
• AlternationExpression will check if the input matches any of its alternatives,
• RepetitionExpression will check if the input has multiple copies of expression it repeats,

and so on.

## 3  Domain Definitions

We will transform the top-level relations into a set of corresponding domain definitions:

RegularExpression = LiteralExpression | AlternationExpression |SequenceExpression |RepetitionExpression

The next step is to translate the domain definitions into a number of Elisa components. In addition, we will use skeletons of definitions as shown in the preceding domain relationships.

## 4  Elisa components

Based on the domain definitions a set of related components are derived. The first component implements  a skeleton of the  RegularExpression domain.

component RegularExpressions;
type RegularExpression = category (LiteralExpression, AlternationExpression, SequenceExpression, RepetitionExpression);

Interpret(RegularExpression) -> nothing;

. . .
begin

<<implementations of >>

Interpret(LiteralExpression: literalExpression) = Interpret(literalExpression);

Interpret(AlternationExpression: alternationExpression) = Interpret(alternationExpression);

Interpret(SequenceExpression: sequenceExpression) = Interpret(sequenceExpression);

Interpret(RepetitionExpression: repetitionExpression) = Interpret(repetitionExpression);

. . .

end component RegularExpressions;

The following component is a skeleton example of a LiteralExpression

component LiteralExpressions;
type LiteralExpression;

CreateLiteralExpression( )  -> LiteralExpression;
Interpret(LiteralExpression) -> nothing;

. . .
begin

<<implementations of >>
CreateLiteralExpression() = LiteralExpression:[ ... ];
Interpret(LiteralExpression) = ...;

. . .

end component LiteralExpressions;

The following component is a skeleton example of a AlternationExpression

component AlternationExpressions;
type AlternationExpression;

CreateAlternationExpression( )  -> AlternationExpression;
Interpret(AlternationExpression) -> nothing;

. . .
begin

<<implementations of >>
CreateAlternationExpression() = AlternationExpression:[ ... ];
Interpret(AlternationExpression) = ...;

. . .

end component AlternationExpressions;

The following component is a skeleton example of a SequenceExpression

component SequenceExpressions;
type SequenceExpression;

CreateSequenceExpression( )  -> SequenceExpression;
Interpret(SequenceExpression) -> nothing;

. . .
begin

<<implementations of >>
CreateSequenceExpression() = SequenceExpression:[ ... ];
Interpret(SequenceExpression) = ...;

. . .

end component SequenceExpressions;

The following component is a skeleton example of a RepetitionExpression

component RepetitionExpressions;
type RepetitionExpression;

CreateRepetitionExpression( )  -> RepetitionExpression;
Interpret(RepetitionExpression) -> nothing;

. . .
begin

<<implementations of >>
CreateRepetitionExpression() = RepetitionExpression:[ ... ];
Interpret(RepetitionExpression) = ...;

. . .

end component RepetitionExpressions;

## 5  Remarks

An  alternative approach can be found in Language Processing.

 Part 5: Design Patterns Interpreter

 Introduction: Home | Highlights of Elisa | Integrating Different Paradigms | Getting Started with Elisa | Demo's  | What is Domain Orientation | Bibliography | Copyright | News | Contact Language Description: Lexical Elements | Basic Data Types and Expressions | Definitions | Streams | Backtracking | Statements and Special Expressions | Arrays | Lists | Descriptors | Components | Collections | Generic Components | Terms | Categories | Types | Built-in Definitions | Higher-order Definitions | External Interfaces | Index Data Structures: Sequences | Examples involving Lists | Trees | Graphs | Searching State Spaces | Language Processing | Knowledge Representations Domain Modeling: Design Patterns: Introduction | Abstract Factory | Builder | Factory Method | Prototype | Singleton | Adapter | Bridge | Composite | Decorator | Facade | Flyweight | Proxy | Chain of Responsibility | Command | Interpreter | Iterator | Mediator | Memento | Observer | State | Strategy | Template Method | Visitor