Back Home Up Next


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;

       . . .

            <<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;

       . . .

            <<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;

       . . .

            <<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;

       . . .

            <<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;

       . . .

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

        . . .

end component RepetitionExpressions;



5  Remarks


An  alternative approach can be found in Language Processing.


Back Home Up Next

  Part 5: Design Patterns   Interpreter


Home | Highlights of Elisa | Integrating Different Paradigms | Getting Started with Elisa | Demo's  | What is Domain Orientation | Bibliography | Copyright | News | Contact | Contents

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:

Domain Modeling | Concepts | Domain Definitions | Domain Operations | Domain Implementations | Systems | Case study: an Order processing system | Case study: an Airport Support system | Domain Orientation versus Object Orientation

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 


click tracking


Send me your comments


This page was last modified on 27-11-2012 16:55:13   

free hit counter