Legal use (\ +) // 1

Question

In grammar rules ( dcg ), there are several predefined constructs: (',')//2 value of concatenation, ('|')//2 means alternation, etc. One design supported by several, but not all Prolog systems, (\+)//1 .

Personally, I used it only for the sake of using it. I have never seen it in code written by others.

So, are there legal uses of (\+)//1 ?

Edit: Also, are there legitimate uses of (\+)//1 in the phrase(nt, L) query with L uninstalled variable.

Answer 1

\ + can be used to create less ambiguous grammars. The advantage of using \ + over! for example, declarative \ + is certain, so that, for example, DCG-derived rules can be reordered.

Let's make an example, consider the following grammar:

 s([X|Y]) --> t(X), s(Y). % 1 s([]) --> []. % 2 t(2) --> [a,a]. % 3 t(1) --> [a]. % 4 

The above grammar is very ambiguous, for example, I get some analyzes of the following input:

 ?- phrase(s(A),[a,a,a,a,a]). A = [2,2,1] ; A = [2,1,2] ; A = [2,1,1,1] ; etc.. 

Now suppose I want to prefer a long parsing of t over a short parsing of t. I can do this with a cut as follows:

 t(2) --> [a,a], !. % 5 t(1) --> [a]. % 6 ?- phrase(s(A),[a,a,a,a,a]). A = [2,2,1] ; No 

Sorry, I can’t change the order. Since the following is not given the desired result. Although s (A) now gives the results in a different order, we will return to the square, since the grammar is again ambiguous:

 t(1) --> [a]. % 7 t(2) --> [a,a], !. % 8 ?- phrase(s(A),[a,a,a,a,a]). A = [1,1,1,1,1] ; A = [1,1,1,2] ; A = [1,1,2,1] ; etc... 

Now try the same with \ +. We can replace the cut with the following negation:

 t(2) --> [a,a]. % 9 t(1) --> [a], \+ [a]. % 10 ?- phrase(s(A),[a,a,a,a,a]). A = [2,2,1] ; No 

Now let's try changing the order. We reorder the grammar rules of t // 1:

 t(1) --> [a], \+ [a]. % 11 t(2) --> [a,a]. % 12 ?- phrase(s(A),[a,a,a,a,a]). A = [2,2,1] ; No 

Declarative is very useful. This means, for example, that we can use \ + in the parser of a chart from right to left to select grammar rules in an arbitrary order. declaratively ensures that the bottom straight chain of the chart analyzer gives the same result regardless of the order in which DCG rules are entered.

You can then apply the DCG technique in large natural language (NL), and it scales well. NL grammars can be empirically tuned for determinism. The more deterministic grammar the more effective its analysis. Comprehensive NL grammars that otherwise unsolvable become possible.

Bye

Answer 2

When L is not created, the grammar is used to generate text. then you don’t need grammar at all \ +. Since there is no longer the problem of ambiguity from some text.

Let's make an example, consider the following grammar:

 s([X|Y]) --> t(X), s(Y). % 1 s([]) --> []. % 2 t(2) --> [a,a]. % 3 t(1) --> [a]. % 4 

Each different parsing has a different parsing tree. And there is no ambiguity in using the phrase / 2 to generate text. The following queries give exactly one answer:

 ?- phrase(s([2,1]),L). L = [a,a,a] ?- phrase(s([1,2]),L). L = [a,a,a] ?- phrase(s([1,1,1]),L). L = [a,a,a] 

But there is a slight problem of reuse. Suppose I have an NL grammar with \ + for parsing. Then I can not use it for parsing. Since the pattern of creating an instance of the target \ + will be different, and therefore the semantics of the design change.

The way out is probably just using two grammars. One for parsing and one for unparsing. I think that parsing and legibility are two different cognitive abilities. Remember that the school had exercises for reading and exercises for exercises. the same thing happens in computer science.

I think that in some cases it is possible to use one grammar, and view \ + as annotation to eliminate the ambiguity, which is discarded during impermeability or processed differently. Such a mechanism can be built. But the problems with unparsing versus parsing are deeper: bi-directionality of auxiliary conditions ({} / 1), left recursion during unparsing, etc.

Bye