# 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 */

## Kommentare