calc Test Program

Definite clause grammars (DCG) are an extension of context free grammars. DCGs allow arbitrary tree structures to be built in the course of parsing and they allow extra conditions dependent on auxiliary computations. DCGs can also be used for text generation.

In our test program we want to use a DCG to parse an arithmetic expression and to return the evaluation of that expression. A first attempt would lead to the following grammar rule to handle for example subtraction:

    expr(Z) --> expr(X), "-", term(Y), {Z is X-Y}.

Unfortunately the above rule is left-recursive and top down parsing via DCG would run into an infinite loop. Therefore we use a modified set of grammar rules that implements the syntax via tail recursion and the evaluation via additional accumulator variables. We have also put cuts as to make the parser greedy and deterministic.

One test iteration will parse and evaluate the following expressions:

    -12+34*56+78          /*  Evaluates to 1970 */
(-12+34)*(56+78)      /*  Evaluates to 2948 */