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

[Peter Schachte]

> 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).

I think your own example answers your question.  To me, the DCG syntax
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
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------