2.3.2022 |

Interpreter Pattern

The interpreter pattern allows to define the grammar of a given language such as programming languages, natural languages, DSLs or others. IDEs for example use it under the hood to give useful hints and insights when programming. It should be used when the grammar of the described languages is quite simple otherwise it will become hard to maintain.

image

Source: https://www.baeldung.com/java-interpreter-pattern

There are two main parts in this pattern. A context and expressions. With expressions you define the grammar and change the state of the interpreting context. They can be terminating, i.e. the last expression in a sentence or non-terminating, i.e. it must be followed by another expression in a sentence. The context is responsible for holding the global processing state and applying the expressed operation.

Example

I created a simple Equation Interpreter with Angular to demonstrate how this design pattern can be used. It can calculate basic mathematical operations in infix notation (operator stands between its operands) using the Shunting-Yard parsing algorithm.

The context class:

export class CalculationContext {

  private numberStack: number[];

  private operatorStack: Operator[];

  constructor() {
    this.numberStack = [];
    this.operatorStack = [];
  }

  execute(): number {
    const result = this.numberStack[0];
    this.reset();
    return result;
  }

  reset() {
    this.numberStack = [];
    this.operatorStack = [];
  }

  ...helperMethods
}

The expressions:

export abstract class Expression {
  abstract calculate(ctx: CalculationContext): number;
}

export class NumberExpression extends Expression {

  constructor(private num: number,
              private next: Expression) {
    super();
  }

  calculate(ctx: CalculationContext): number {
    ctx.addNumber(this.num);
    return this.next.calculate(ctx);
  }
}

export interface Operator {
  symbol: string;
  precedence: number;
  apply: (left: number, right: number) => number;
  name: string;
}

export class BinaryOperatorExpression extends Expression {

  constructor(private operator: Operator,
              private nextExpr: Expression) {
    super();
  }

  calculate(ctx: CalculationContext): number {
    if (this.operator.precedence > (ctx.peekOperator()?.precedence ?? -1)) {
      ctx.addOperator(this.operator);
      return this.nextExpr.calculate(ctx);
    }

    const operator = ctx.popOperator();
    if (!operator) {
      throw new Error(`Expected an operator to be on the context stack`);
    }

    const [right, left] = ctx.getLastTwoNumbers();
    if (left == null || right == null) {
      throw new Error(`Expected two numbers as ${operator?.name} input`);
    }

    const result = operator.apply(left, right);

    ctx.addNumber(result);
    ctx.addOperator(this.operator);

    return this.nextExpr.calculate(ctx);
  }
}

export class EqualExpression extends Expression {

  constructor() {
    super();
  }

  calculate(ctx: CalculationContext): number {
    let operator: Operator | undefined = ctx.popOperator();
    while (operator) {
      const [right, left] = ctx.getLastTwoNumbers();
      if (left == null || right == null) {
        throw new Error(`Expected two numbers as ${operator?.name} input`);
      }

      const result = operator.apply(left, right);
      ctx.addNumber(result);

      operator = ctx.popOperator();
    }
    return ctx.execute();
  }
}

The grammar of an equation is quite simple. Every number or operator must be followed by another expression until the EqualExpression is hit. This is the only terminating expression in this grammar which at the end applies all remaining operators on the stack.

Additional source code such as the parser or the Angular app itself can be found here.

Adding new operators and braces to the interpreter is now quite simple. But as mentioned before maintaining a large grammar will be quite hard eventually.

Sven Röttering
Zur Übersicht

Mehr vom DevSquad...

Lars Silberg

Spiele um CSS zu lernen

Sophia Brandt

CSS Debug Hack: JavaScript Bookmarklet zum Debuggen von CSS