Tutorial: Calculator¶

In this tutorial, we will write a calculator. It supports

Positive integers.
Negative integers.
Addition operator +.
Subtraction operator -.
Multiplication operator *.
Division operator /.
Parenthesis ().
Detect invalid zero division.

The calculator can take arbitrary valid string and yield a result.

Step 1: Create Grammar¶

Let’s create a new file “calc.h” and create the grammar using P4_LoadGrammar().

P4_Grammar*  P4_CreateCalcGrammar() {
    return P4_LoadGrammar(
        "statement = term eol;\n"

        "@nonterminal\n"
        "term = factor | term  (add / minus) factor;\n"

        "@nonterminal\n"
        "factor = unary | factor (mul / div) unary;\n"

        "@nonterminal\n"
        "unary = primary / (add / minus)? unary;\n"

        "@lifted\n"
        "primary = integer / \"(\" term \")\";\n"

        "@squashed @tight\n"
        "integer = [0-9]+;\n"

        "add = \"+\";\n"
        "minus = \"-\";\n"
        "mul = \"*\";\n"
        "div = \"/\";\n"

        "@spaced @lifted\n"
        "whitespace = \" \" / \"\\t\";\n"

        "eol = \"\\n\" / !.;\n"
    );
}

To extend a little bit,

Rule statement is the entry.
Rule term can parse inputs like a + b - c + d … or a.
Rule factor can parse inputs like a * b / c * d … or a.
Rule unary can parse inputs like +a, ++a, -a, a, etc.
Rule primary can parse inputs like (a), etc.
Rule integer are some squashed digits. It avoids creating nodes for each digit.
Rule whitespace allows arbitrary number of whitespace or tab in between expressions.

Step 2: Eval Ast¶

Next, let’s evaluate the tree. We traverse the AST and calculate the result.

P4_Error P4_CalcEval(P4_Node* node, long* result) {
    P4_Error err = P4_Ok;
    P4_Node* tmp = NULL;
    char sign   = '+';
    long val = 0;
    char* intstr = NULL;

    if (strcmp(node->rule_name, "statement") == 0) {
        return P4_CalcEval(node->head, result);
    } else if (strcmp(node->rule_name, "term") == 0) {
        if ((err = P4_CalcEval(node->head, &val)) != P4_Ok)
            return err;

        *result = val;

        if ((err = P4_CalcEval(node->tail, &val)) != P4_Ok)
            return err;

        if (strcmp(node->head->next->rule_name, "add") == 0) {
            *result += val;
        } else if (strcmp(node->head->next->rule_name, "minus") == 0) {
            *result -= val;
        } else {
            return P4_ValueError;
        }

        return P4_Ok;
    } else if (strcmp(node->rule_name, "factor") == 0) {
        if ((err = P4_CalcEval(node->head, &val)) != P4_Ok)
            return err;

        *result = val;

        if ((err = P4_CalcEval(node->tail, &val)) != P4_Ok)
            return err;

        if (strcmp(node->head->next->rule_name, "mul") == 0) {
            *result *= val;
        } else if (strcmp(node->head->next->rule_name, "div") == 0) {
            if (val == 0) {
                return P4_ValueError;
            }
            *result /= val;
        } else {
            return P4_ValueError;
        }

        return P4_Ok;
    } else if (strcmp(node->rule_name, "unary") == 0) {
        if (node->head == node->tail)
            return P4_CalcEval(node->head, result);
        else {
            long val = 0;
            if ((err = P4_CalcEval(node->tail, &val)) != P4_Ok)
                return err;
            if (strcmp(node->head->rule_name, "add") == 0)
                *result = val;
            else if (strcmp(node->head->rule_name, "minus") == 0)
                *result = -val;
            else
                return P4_ValueError;
            return P4_Ok;
        }
    } else if (strcmp(node->rule_name, "integer") == 0) {
        intstr = P4_CopyNodeString(node);
        *result = atol(intstr);
        free(intstr);
        return P4_Ok;
    } else {
        return P4_ValueError;

    }
}

Step 3: Parse¶

Let’s create a new file “calc.c” and parse inputs reading from stdin.

The main function does the below things:

Create the grammar.
Create the source.
Parse the source using the grammar.
Eval the source ast.
Print the evaluated result.

#include "calc.h"

int main() {
    P4_Grammar* grammar = P4_CreateCalcGrammar();
    P4_Source*  source  = NULL;
    P4_Error    error   = P4_Ok;
    long        result  = 0;
    char        line[256];

    printf("Type statement to continue. Type ^C to quit.\n");

    while (fgets(line, sizeof(line), stdin)) {
        source = P4_CreateSource(line, "statement");
        if ((error = P4_Parse(grammar, source)) != P4_Ok) {
            printf("error: parse: %s\n", P4_GetErrorMessage(source));
        } else if ((error = P4_CalcEval(P4_GetSourceAst(source), &result)) != P4_Ok){
            printf("error: eval: %d\n", error);
        } else {
            printf("[Out] %ld\n\n", result);
        }
        P4_DeleteSource(source);
    }

    P4_DeleteGrammar(grammar);
}

Run:

$ gcc -o calc calc.c peppa.c && ./calc
Type statement to continue. Type ^C to quit.

1+2*3
[Out] 7

-1 + 4/2*3 - 1
[Out] 4

5/0
error: eval: 6