Trivial parsing and generating DCG


I’m using: SWI-Prolog version 8.0.2

I want the code to:
Achieve parsing and generation of words separated by spaces.

But what I’m getting is:
I can do both, but I want my check/0 to be semi-deterministic and at the same time having generate/1 be able to generate multiple solutions. My problem is that by re-ordering clauses and/or inserting !/0, I can achieve either a well-behaved semi-deterministic check/0 and an infinite loop generate/1, or a check/0 that leaves a choicepoint behind and a functioning generate/1.

More generally, I’d be interested in how to locate and eliminate residual choicepoints.

My code looks like this:

query --> term.
query --> term -> ([W], {char_type(W, white)}) -> query.
term --> [].
term --> ([C], {char_type(C, alnum)}) -> term.

check :- phrase(query, [a,s]).
generate(X) :- phrase(query, X).

See: Controlling backtracking in a DCG grammar?

That will not directly answer your question, but addresses the problem of having a DCG parse and generate while trying to keep to the original DCG for parsing as close as possible and yet still work for generating.

Also see this StackOverflow answer: Is it appropriate for a parser DCG to not be deterministic?


The StackOverflow link is actually a question by me. I was trying to understand this issue better.
Evidently I do not fully understand the answers that were posted there.

I read several times posts from people advising to make parsing and generating grammars separate. But I’m still exploring about how to do that right.

Essentially, it looks as something like:

check :- once(phrase(query, [a,s])).
generate(X) :- phrase(query, X).

would be an answer to my question, although I could make check/0 and generate/1 more distinct (codewise) if I wanted to optimize for speed?


Glad you came here. At StackOverflow we are limited to questions and answers but here can discuss this all we want.

Glad to here that.

Yes that is a good answer when first learning. I started that same way but then found out that I was spending more time trying to maintain two grammars. When I started using more complicated grammars realized that judicial use of guard statements or using conditionals at the right place, a single grammar could do all three.

Using once/1 is something I try to avoid, but for learning it is fine. Since using once/1 is something Daniel suggested at StackOverflow, and he also hangs out here, hopefully he will jump in on this. In other words my style and Daniels styles are a bit different (both work) and when learning it is better to have one master than many. Also DCGs can be very confusing at first, so mixing styles will not help you.

If you focus on speed up front you wont be concentrating on making the grammar correct. The first thing is to get the grammar working correctly, then work on speed. My rule of thumb is that if the code is so slow that I can stop for a coffee break then I need to work on speed enhancements. In the last several years I have only had code in development run that slow less that I can count it on one hand.

While I would like to spend more time on this, at present I have to do something else and may not be back here for a few days, but then again might have many hours, don’t know yet. :slightly_smiling_face:

I suspect that what you are asking is a topic with a lot of depth; it might be that you end up hearing people’s opinions, instead of a clear useful answer.

The problem is not specific to DCGs. A much simpler example would be between/3 (which I see is also used as an example in the answers to the question that @EricGT linked).

With between/3, you can check if a number is in a range, and you can generate numbers between a range. Sounds trivial but how do you implement it?

I hope I am not wrong about this, but in SWI-Prolog, it seems to be implemented in C; I think this is where you see the implementation:

You can see the two cases (the comments are on spot!): between(+,+,+) (check) and between(+,+,-) (generate). But this is in C; how about the same in Prolog?

In “The Craft of Prolog” by O’Keefe, on page 105, you can see a Prolog implementation of between/3. It says, in the book, that it is from library(between); someone older than me can say whether this was a Quintus library and how you can get your hands on the code. Anyway, it is in “3 Where Does The Space Go”, “3.14 Disjunction and If-Then-Else”, “3.14.3 Pushing a choice point”. I am too lazy to type in the whole thing, but it is very similar in spirit to the C implementation I linked above. Skipping error handling and such, re-indenting a bit:

between(Lower, Upper, Index) :-
    (   var(Index), integer(Lower), integer(Upper) % between(+,+,-)
    ->  Lower =< Upper,
        between1(Lower, Upper, Index)
    ;   integer(Index), integer(Lower), integer(Upper) % between(+,+,+)
        Lower =< Index,
        Index =< Upper
    ;  /* the arguments are strange */
    % error handling, skipping

between1(Lower, Upper, Index) :-
    (   Lower =:= Upper
    ->  Index = Lower
    ;   Index = Lower
    ;   Next is Lower + 1, % Lower < Upper
        between1(Next, Upper, Index)

Sorry for the terribly long intro. I struggle to bring my point across one way or another, either by hoping the other will guess all the things I am not saying, or by drowning the message in unnecessary detail.

This was just to argue that at the bottom of it, you need conditional code in some form. I’d say it is up to the implementation, the goals of the implementation, and the taste of the person implementing to decide where the plain old conditional code should live.

I hope someone better at writing can give you practical advice. I am honestly struggling to decide where to start and where I should be going, in order to give a proper answer to your insightful question.

I would suggest to study Michael’ pack dcg_util.
Note my comment in the page linked, today I would add that the whole pack has been obsoleted by library(dcg/high_order), except for the diligent learner…

1 Like