<p>I don't think this is necessarily a good idea. I especially don't think it will be easier than using DCGs. You still need to write some sort of proper grammar that knows more about the input's structure than just &quot;combine certain sequences of words&quot;. That said, there is some work on parsing with CHR, see <a href="https://arxiv.org/abs/cs/0408027" rel="nofollow noreferrer">CHR Grammars</a> for example.</p>
<p>Your first problem is that CHR constraints are unordered. When you try to match <code>w(L), w(on), w(R)</code>, you have no guarantee that <code>L</code> is actually to the left of <code>R</code> in the input. This information is not recorded for you.</p>
<p>So what you can do is to record it yourself. You can replace each <code>w(X)</code> with a <code>w(X, Start, End)</code> constraint where <code>Start</code> and <code>End</code> are some sort of input position markers. For example, simply numbering tokens from left to right:</p>
<pre><code>:- use_module(library(chr)).

:- chr_constraint w/3.

parse(Tokens) :-
    parse(Tokens, 0).

parse([], _Position).
parse([Token | Tokens], Position) :-
    NextPosition is Position + 1,
    w(Token, Position, NextPosition),
    parse(Tokens, NextPosition).
</code></pre>
<p>You can use this as follows:</p>
<pre><code>?- parse([the, box, is, on, the, table]).
w(table, 5, 6),
w(the, 4, 5),
w(on, 3, 4),
w(is, 2, 3),
w(box, 1, 2),
w(the, 0, 1).
</code></pre>
<p>Given this format, you can enhance your matching rules to only combine adjacent inputs (where each component's end marker is the same as the &quot;next&quot; component's start marker):</p>
<pre><code>w(the, S, M), w(X, M, E) &lt;=&gt; w([the,X], S, E).
w(L, S, M1), w(on, M1, M2), w(R, M2, E) &lt;=&gt; w(on(L,R), S, E).
w(L, S, M1), w(is, M1, M2), w(R, M2, E) &lt;=&gt; w(is_(L,R), S, E).
</code></pre>
<p>(I use <code>is_</code> instead of <code>is</code> because <code>is</code> is a built-in operator, and <code>is(X, Y)</code> facts would be printed as <code>X is Y</code>, which is confusing in what follows.)</p>
<p>This allows you to make some progress:</p>
<pre><code>?- parse([the, box, is, on, the, table]).
w([the, table], 4, 6),
w(is_([the, box], on), 0, 4).
</code></pre>
<p>We see that <code>the</code> and <code>table</code> at positions 4 to 5 and 5 to 6 were merged together into a phrase <code>the, table</code> at position 4 to 6. Also the words <code>the</code>, <code>box</code>, <code>is</code>, <code>on</code>, were merged together into one object covering positions 0 to 4. But this is not correct: &quot;the box is on&quot; is not a valid phrase. The phrase to the right of &quot;is&quot; must be a location or other situation. You need more information about the kinds of sub-phrases in a phrase. You need proper grammar information, the kind that you would encode in a DCG by defining rules with different names.</p>
<p>Here is an expanded version:</p>
<pre><code>:- chr_constraint noun_phrase/3, situation/3, sentence/3.

w(the, S, M), w(X, M, E) &lt;=&gt;
    noun_phrase([the,X], S, E).
w(on, S, M), noun_phrase(R, M, E) &lt;=&gt;
    situation(on(R), S, E).
noun_phrase(L, S, M1), w(is, M1, M2), situation(R, M2, E) &lt;=&gt;
    sentence(is_(L,R), S, E).
</code></pre>
<p>And this works:</p>
<pre><code>?- parse([the, box, is, on, the, table]).
sentence(is_([the, box], on([the, table])), 0, 6).
</code></pre>
<p>But at this point you are writing a DCG in ugly syntax and with lots of extra information you must track by hand. Why not write the DCG instead?</p>
<pre><code>noun_phrase([the, X]) --&gt;
    [the],
    [X].

situation(on(Place)) --&gt;
    [on],
    noun_phrase(Place).

sentence(is_(Thing, Where)) --&gt;
    noun_phrase(Thing),
    [is],
    situation(Where).
</code></pre>
<p>This works just as nicely:</p>
<pre><code>?- phrase(sentence(Sentence), [the, box, is, on, the, table]).
Sentence = is_([the, box], on([the, table])).
</code></pre>
<p>If you want to get this information into a CHR constraint, you can do that by calling that constraint. For example, with the DCG above:</p>
<pre><code>:- chr_constraint sentence/1.

parse(Tokens) :-
    phrase(sentence(Sentence), Tokens),
    sentence(Sentence).
</code></pre>
<p>This gets the same CHR result as above, but without the position markers which are no longer needed:</p>
<pre><code>?- parse([the, box, is, on, the, table]).
sentence(is_([the, box], on([the, table]))).
</code></pre>
parsing with CHR (Constraint handling rules)
<p>Trying to do sort of parsing with CHR (Constraint handling rules)
I come up with this (still learning)</p>
<pre><code>w(the),w(X) &lt;=&gt; w([the,X]).
w(L),w(on),w(R) &lt;=&gt; w(on(L,R)).
w(L),w(is),w(R) &lt;=&gt; w(is(L,R)).
</code></pre>
<p>here is what i got :</p>
<pre><code>?- w(the),w(box),w(is),w(on),w(the),w(table).
w(table),
w([the, on(is, [the, box])]).
</code></pre>
<p>should be instead  :</p>
<pre><code>is([the,box],on([the,table]))
</code></pre>
<p>to make it work I have to figure how to do sort of late-binding on &quot;on&quot; and later &quot;is&quot;, so the the the-X has been already &quot;collected&quot;</p>
<p>Second question is how to write CHR rules so that they parse a list, instead of making w(..) goals.</p>
<p>PS&gt; also any info on mixing DCG with CHR would be welcome. Cant find anything !!</p>