Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 36 ยท Projects and Practice

Project: A Tokenizer and Calculator in D

Build a tokenizer, recursive-descent parser and evaluator for arithmetic in D, using ranges, algebraic enums and unit tests, with a runnable C version of the same design.

In this project you build the front end of a tiny language: a tokenizer that turns text like 2 + 3 * (4 - 1) into tokens, and a parser and evaluator that computes the value. It is a classic exercise because it touches strings, ranges, enums, recursion, error handling and tests: the things D does best. The design is shown in D (read-only); the complete working program runs in C below, and you can translate it function by function.

D code is read-only on this site. The runnable program is the same design written in C.

Plan

flowchart LR
    T["Text: 2 + 3 * (4 - 1)"] --> L["Tokenizer"]
    L --> K["Tokens: NUM 2, PLUS, NUM 3, STAR, LPAREN ..."]
    K --> P["Parser (precedence)"]
    P --> V["Value: 11"]

Text becomes tokens, tokens become a value.

The grammar, from loosest to tightest binding:

Text
expr   = term   { ("+" | "-") term }
term   = factor { ("*" | "/") factor }
factor = NUMBER | "(" expr ")" | "-" factor

Each rule becomes one function, and the nesting of rules encodes operator precedence: multiplication sits below addition, so 3 * 4 is grouped before +.

Step 1: tokens in D

D
import std.ascii : isDigit, isWhite;

enum Kind { number, plus, minus, star, slash, lparen, rparen, end }

struct Token
{
    Kind kind;
    double value;     // only for numbers
    size_t pos;       // where it started, for error messages
}

Token[] tokenize(string src)
{
    Token[] result;
    size_t i = 0;
    while (i < src.length)
    {
        char c = src[i];
        if (isWhite(c)) { i++; continue; }

        if (isDigit(c) || c == '.')
        {
            size_t start = i;
            while (i < src.length && (isDigit(src[i]) || src[i] == '.')) i++;
            result ~= Token(Kind.number, src[start .. i].to!double, start);
            continue;
        }

        switch (c)
        {
            case '+': result ~= Token(Kind.plus, 0, i); break;
            case '-': result ~= Token(Kind.minus, 0, i); break;
            case '*': result ~= Token(Kind.star, 0, i); break;
            case '/': result ~= Token(Kind.slash, 0, i); break;
            case '(': result ~= Token(Kind.lparen, 0, i); break;
            case ')': result ~= Token(Kind.rparen, 0, i); break;
            default: throw new Exception("unexpected '" ~ c ~ "' at " ~ i.to!string);
        }
        i++;
    }
    result ~= Token(Kind.end, 0, src.length);
    return result;
}

Note the slice src[start .. i]: no allocation, just a view into the input. An end token makes the parser simpler because it never has to check for running off the array.

Step 2: parser and evaluator in D

D
struct Parser
{
    Token[] tokens;
    size_t at;

    Token peek() { return tokens[at]; }
    Token take() { return tokens[at++]; }

    double expr()
    {
        double left = term();
        while (peek.kind == Kind.plus || peek.kind == Kind.minus)
        {
            auto op = take().kind;
            double right = term();
            left = (op == Kind.plus) ? left + right : left - right;
        }
        return left;
    }

    double term()
    {
        double left = factor();
        while (peek.kind == Kind.star || peek.kind == Kind.slash)
        {
            auto op = take().kind;
            double right = factor();
            if (op == Kind.slash && right == 0) throw new Exception("division by zero");
            left = (op == Kind.star) ? left * right : left / right;
        }
        return left;
    }

    double factor()
    {
        auto t = take();
        switch (t.kind)
        {
            case Kind.number: return t.value;
            case Kind.minus:  return -factor();
            case Kind.lparen:
                double v = expr();
                if (take().kind != Kind.rparen) throw new Exception("expected ')'");
                return v;
            default: throw new Exception("unexpected token at " ~ t.pos.to!string);
        }
    }
}

double evaluate(string src)
{
    auto p = Parser(tokenize(src));
    double v = p.expr();
    if (p.peek.kind != Kind.end) throw new Exception("trailing input");
    return v;
}

Step 3: tests

D
unittest
{
    assert(evaluate("1 + 2") == 3);
    assert(evaluate("2 + 3 * 4") == 14);
    assert(evaluate("(2 + 3) * 4") == 20);
    assert(evaluate("-3 + 5") == 2);
    assert(evaluate("10 / 4") == 2.5);

    import std.exception : assertThrown;
    assertThrown!Exception(evaluate("1 / 0"));
    assertThrown!Exception(evaluate("2 +"));
    assertThrown!Exception(evaluate("(1"));
}

The same program in C (runnable)

C Calculator: tokenizer, parser and evaluator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The tests mirror the unittest block: the first six succeed, the last four report errors.

Extensions

  1. Exponent: add ^ with right associativity, one level above factor.
  2. Variables: keep an associative array double[string] and tokenize identifiers.
  3. Functions: sqrt(9), max(1, 2): parse an identifier followed by a parenthesized argument list, then look the name up in a table of delegates.
  4. Better errors: carry pos into every message and print a caret under the faulty column.
  5. AST: build a tree (class Node, with subclasses for each operation) instead of evaluating immediately. See inheritance for that design. Then add a pretty-printer and a constant folder.
  6. Lazy tokens: make tokenize a range with empty, front and popFront, so no array is built.

Check your understanding

Quick check ยท 3 questions

of 3 answered You scored / 3 ยท perfect!

  1. 1. Why does term call factor, and expr call term?

    Rules that bind tighter are called by looser rules, so * groups before +.
  2. 2. What is the purpose of the end token?

    A sentinel simplifies lookahead.
  3. 3. How do you parse -3 + 5 correctly?

    Unary minus belongs to factor, binding tighter than binary operators.

Summary

  • A tokenizer plus a recursive-descent parser handles arithmetic in about a hundred lines.
  • One function per grammar rule; precedence comes from call nesting.
  • Test both good inputs and errors; sentinels and positions make errors friendly.
  • D's slices, enums and unittest fit the job; extend it with variables, functions and an AST.

Next: Project: A Bank Account Simulator