An Alpha Interpreter

Alpha is a simple expression-oriented language with LISP-like syntax.

Here's an EBNF for Alpha:

<Expression> ::= <Literal> | <FunCall>
<FunCall> ::= ( <Operator> <Expression>+ )
<Operator> ::= + | *
<Literal> ::= -?<Digit>*(.<Digit>+)?
<Digit> ::= 0 .. 9

Here's a sample session with the Alpha interpreter:

-> -3.1416
value = -3.1416
-> ( + 2 3 )
value = 5.0
-> ( + ( * 2 3 ) ( * 4 ( + 5 3.1416 ) ) )
value = 38.5664
-> quit
bye

Design Model

The design of Alpha uses the Interpreter pattern:

Notes:

1. We don't need a context in this simple language because the only symbols are + and *.

2. Values are doubles.

3. Each node knows how to parse itself.

4. Each node knows how to evaluate itself.

Adding Visitors

We can combine the Interpreter pattern and the Visitor pattern:

Implementation

The implementation is contained in the following files:

Expression.java

Literal.java

FunCall.java

Interpreter.java

Visitors

The visitors are defined in the following files:

ExpVisitor.java

TreePrintVisitor.java

TreeSearchVisitor.java

Project

Beta extends Alpha by adding symbols and definitions:

<Phrase> ::= <Expression> | <Definition>
<Expression> ::= <Literal> | <Symbol> | <FunCall>
<Definition> ::= [ define <Symbol> <Expression> ]
<Symbol> ::= <Char>(<Char> | <Digit>)*
<Char> ::= a..z | A..Z

Here's a sample session:

-> [ define pi 3.14 ]
done
-> ( + 2 pi )
value = 5.14
->

Design and write an interpreter for Beta.

Hint: eval now needs a symbol table parameter:

abstract class Phrase {
abstract double eval(Map<Symbol, Double> context);
// etc.
}

The context will be initialized by the interpreter and passed to the eval method of each phrase. Definitions will add new rows to the context.