# [mercury-users] Is DCG really appropriate, even for the things it does well?

Peter Schachte schachte at cs.mu.OZ.AU
Wed Apr 3 11:44:08 AEST 2002

```> Examples.
>
> BNF
> ---
> term ::= factor "*" term
> term ::= factor "/" term
> term ::= factor
>
> Mercury using DCG.
> ------------------
> :- pred term(list(char)::in, list(char)::out) is nondet.
> term --> factor, ['*'], term.
> term --> factor, ['/'], term.
> term --> factor.
>
> Mercury using concatenation
> ---------------------------
> :- pred term(list(char)) is semidet.
> term(Factor ++ ['*'] ++ Term) :-
> 	factor(Factor), term(Term).
> term(Factor ++ ['/'] ++ Term) :-
> 	factor(Factor), term(Term).
> term(Factor) :-
> 	factor(Factor).

is much clearer and easier to read than the concatenation-based
approach.  This would be doubly so if you were constructing a parse
tree.

You might argue that parsing isn't really common enough to warrant a
special syntax, but given that it's already there, it seems like the
right way to code a grammar.

You might also argue that DCGs are not implemented efficiently enough.
I wouldn't disagree.  But I think some reasonably general compiler
optimization could help.  For example, in your code above, factoring
out the common initial goals in a disjunction would really help.
You ought to get code like:

term(S0, S) :-
factor(S0, S1),
(   S1 = [C|S2],
(	C = '*',
term(S2, S)
;	C = '/',
term(S2, S)
)
;   S = S1
).

which looks pretty efficient to me.

Your append-based approach would need accumulator introduction, and
then would need the same optimization.  Forget trying to do it without
accumulator introduction.

--
Peter Schachte              Predestination was doomed from the start.
schachte at cs.mu.OZ.AU
www.cs.mu.oz.au/~schachte/
Phone: +61 3 8344 9166
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au