Create a DCG Parser in PROLOG

Question

I have to implement an a context-free parser in PROLOG that uses a grammar that can generate:

I saw a tutorial.
I went in a library.
In library a tutorial I saw. 

(I know it's not correct grammatically, but I need to see how to match the pattern)

I receive an input as a query - let's suppose it it the first sentence - and I have to print the number of applications of rules for a successful parsing, false otherwise.

In order to achieve this, I found these grammars:

---

s(X,Z):- vp(Y,Z), np(X,Y).
np(X,Z):- det(X,Y), n(Y,Z).
np(X,Z):- det(X,Y), n(Y,Z), np(X,Z).
vp(X,Z):- det(X,Y), v(Y,Z).

det([i|W],W).
det([a|W],W).
det([in|W],W).

n([tutorial|W],W).
n([library|W],W).

v([went|W],W).
v([saw|W],W).

---

It works for the first 2 sentences, but I don't know how to make it work for the last one and I don't know how to print the number of applications of rules for a successful parsing.

Thank you!

Answer 1

This will help with the number of applications of rules for a successful parsing. However, as you can see, it will always be the same number as the quantity of words in the sentence. What I did was to implement a 'counter' in the parameters of each rule and each time a 'base rule' succeed it increase the value of the 'counter'.

det([i|W], W, A, R) :- R is A + 1.
det([a|W], W, A, R) :- R is A + 1.
det([in|W], W, A, R) :- R is A + 1.

n([tutorial|W], W, A, R) :- R is A + 1.
n([library|W], W, A, R) :- R is A + 1.

v([went|W], W, A, R):- R is A + 1.
v([saw|W], W, A, R):- R is A + 1.

np([], R, R).
np(X, A, R2):- det(X, Y, A, R), np(Y, R, R2).
np(X, A, R3):- det(X, Y, A, R), n(Y, Z, R, R2), np(Z, R2, R3).
vp(X, Z, R2):- det(X, Y, 0, R), v(Y, Z, R, R2).

s(X, R2):- atomic_list_concat(L,' ', X), vp(L, Z, R), np(Z, R, R2), !.

Here are the results. Results.

As you can see the last sentence still failing, that is because if you follow the flow of the algorithm or calls of it you can see that the rule 's' calls the rule 'vp' which only admits a 'det' follow by a 'v', so if you see the first word of third sentence which is 'In', 'det' in 'vp' will work, but the next word that is 'library' will not success on 'v', because 'library' is not a verb, so that' s why it fail. To conclude, if you want the third sentence to succeed you will have to do some changes to your grammars. By the way there is better way, probably a lit bit more complex to achieve, but once you understand how to use it, will be faster to work and easier to create a complex grammar this by using Prolog DCG https://www.swi-prolog.org/pldoc/man?section=DCG. I mentioned in case you did not know about this.