Change DCG to be deterministic

Question

how to change this gramma to be deterministic

e --> [].
e --> "*".
e --> s_e.
e --> e, s_e.
s_e --> ("a",e);("b",e).

I just dont know where to put cut to avoid backtracking.

Answer 1

You can rewrite the last rule as follows:

s_e --> "a", e.
s_e --> "b", e.

Now it makes probably sense to place the following cuts:

s_e --> "a", !, e.
s_e --> "b", !, e.

You can also place the cuts in the original compact form with (;)/2, but I find the above more transparent. The above is valid if s_e is not invoked multiple times with the same input list.

But your grammar has a flaw, e is left recursive, and s_e will be called multiple times with the same input list. Means your grammar will for example loop for negative sentences, i.e. it will not be able to reject them, and your grammar will loop after redo for a positive sentences, i.e. when the input has be accepted.

So you need additionally to eliminate the left recursion since normal Prolog depth fist search cannot deal with it. The easiest is to replace it by right recursion with a new non-terminal. Namely you can write the productions for e as follows:

 e --> s_e, rest_e.
 e --> "*", rest_e.
 e --> [].

 rest_e --> s_e, rest_e.
 rest_e --> "*", rest_e.
 rest_e --> [].

And we can place cuts as well:

 e --> s_e, !, rest_e.
 e --> "*", !, rest_e.
 e --> [].

 rest_e --> s_e, !, rest_e.
 rest_e --> "*", !, rest_e.
 rest_e --> [].

Also the above grammar is slightly modified in the sense that multiple empty e productions don't go anymore into e itself via s_e. It is also more greedy, in that sub e productions are always fully parsed. So for example the sentence:

 aaa

Is only parsed as:

 a(a(a))

And not as:

 a(a)a

Or:

 aa(a)

Or:

 aaa

But otherwise it should accept the same sentences as if the DCG would be executed bottom up and would not have problems with left recursion.

Best Regards