/* 

  DCG interpreter in Picat.

  From Pereira & Shieber "Prolog and Natural-Language Analysis",  page 166ff

  This works which is nice. Note that Picat already supports DCGs so it's just
  a demonstration...

  One interesting - or perhaps annoying - feature of this is that parse/3 can
  identify which DCG(s) that matches a string. See go2/0, go6/0, and go7/0 for this.
  The reason for this is that the DCGs are "global" in constrast to DCG proper.

  What I know, Prolog's phrase/2-3 doesn't support this (since the first
  argument must be properly instantiated).

  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

main => go.

%
% Output: [aba,ab,aa,a,ba,b,a,[],[]]
%
go ?=>
  println(findall(X,parse(s,X,[]))), 
  nl.
go => true.

%
% Reversibility: what DCG matches the string "aaabbbaaa".
%
% This generates an infinity number of solutions.
% It finds both s and s2 as well as or_test and ab_call_a (which prints "hello, world!").
%
% Output:
% hello,world!
% hello,world!
% hello,world!
% hello,world!
% hello,world!
% hello,world!
% hello,world!
% hello,world!
% hello,world!
% nt = (s,s,s,s,s) = 2
% nt = (s,s,s,s,s2) = 2
% nt = (s,s,s,s,s2) = 2
% nt = (s,s,s,s,s2) = 2
% nt = (s,s,s,s,s2) = 2
% nt = (s,s,s,s,s2) = 2
% nt = (s,s,s,s,s2) = 2
% nt = (s,s,s,s,s2) = 2
% hello,world!
% nt = (s,s,s,s,ab_call_a) = 2
% hello,world!
% nt = (s,s,s,s,s,s) = 2
% nt = (s,s,s,s,s,s) = 2
% nt = (s,s,s,s,s,s2) = 2
% nt = (s,s,s,s,s,s2) = 2
% nt = (s,s,s,s,s,s2) = 2
% nt = (s,s,s,s,s,a) = 2
% nt = (s,s,s,s,s,b) = 2
% hello,world!
% nt = (s,s,s,s,s,ab_call_a) = 2
% nt = (s,s,s,s,s,or_test) = 2
% nt = (s,s,s,s,s,or_test) = 2
% nt = (s,s,s,s,s,s,s) = 2
% nt = (s,s,s,s,s,s,s) = 2
% nt = (s,s,s,s,s,s,s2) = 2
% nt = (s,s,s,s,s,s,s2) = 2
% nt = (s,s,s,s,s,s,s2) = 2
% nt = (s,s,s,s,s,s,a) = 2
% nt = (s,s,s,s,s,s,b) = 2
% ...
go2 ?=>
  parse(NT, "aaabbbaaa", []),
  Len = and_to_list(NT).len,
  bp.writeln(nt=NT=Len),
  % Restrict to a sample...
  (Len < 20 -> fail ; true),
  nl.
go2 => true.

%
% Minimal test of {}.
%
% Output:()
% hello,world!
% x = aba
% x = ab
% hello,world!
% x = aa
% x = a
% hello,world!
% x = ba
% x = b
% hello,world!
% x = a
% x = []
%
go3 ?=>
  parse(ab_call_a, X, []), 
  println(x=X),
  fail,
  nl.
go3 => true.

%
% Testing alternative (;)
% Output:
% x = abca
% x = abc
% x = aca
% x = ac
% x = acca
% x = acc
% x = bca
% x = bc
% x = ca
% x = c
% x = cca
% x = cc
% x = bbca
% x = bbc
% x = bca
% x = bc
% x = bcca
% x = bcc
% x = bca
% x = bc
% x = ca
% x = c
% x = cca
% x = cc
% 
go4 ?=>
  parse(or_test, X, []), 
  println(x=X),
  fail,

  nl.
go4 => true.

% 
% Generate possible spellings of kjellerstrand and mankell
% See mankell_v3.pi for more on this.
% Great! It finds all the 47 possible misspellings of "kjellerstrand" and
% the correct one:
%    kjellstad,kjellstand,kjellstrad,kjellstrand,kjellbad,kjellband,kjellbrad,kjellbrand,
%    kjellerstad,kjellerstand,kjellerstrad,
%        kjellerstrand
%    kjellerbad,kjellerband,kjellerbrad,kjellerbrand,kjellarstad,kjellarstand,kjellarstrad,
%    kjellarstrand,kjellarbad,kjellarband,kjellarbrad,kjellarbrand,källstad,källstand,
%    källstrad,källstrand,källbad,källband,källbrad,källbrand,källerstad,källerstand,
%    källerstrad,källerstrand,källerbad,källerband,källerbrad,källerbrand,källarstad,
%    källarstand,källarstrad,källarstrand,källarbad,källarband,källarbrad,källarbrand]
%
% And all the 1296 possible spellings of Henning Mankell.
% 
go5 ?=>
  Kjellerstrand = findall(X,parse(kjellerstrand, X, [])), 
  println(kjellerstrand=Kjellerstrand),
  println(len=Kjellerstrand.len),
  nl,
  
  Mankell = findall(X,parse(mankell, X, [])), 
  println(mankell=Mankell),
  println(len=Mankell.len),
  
  nl.
go5 => true.

%
% Reversibility: Which DCG matches "kjellerbad" (wrong spelling of my last name).
%
% Perhaps a little surpring it also matches the DCG s. But s (and a and b) accepts empty string
% so it's not that surprising.
% 
% Output
% dcg = kjellerstrand
% hello,world!
% dcg = (s,kjellerstrand)
% hello,world!
% dcg = (s,s,kjellerstrand)
% hello,world!
% dcg = (s,s,s,kjellerstrand)
% ...
%
% What I know, proper DCG's don't have this feature...
% 
go6 ?=>
  % Which dcg matches "kjellerbad"
  parse(DCG,"kjellerbad",[]),
  println(dcg=DCG),
  fail,
  nl.
go6 => true.

%
% Now let both the DCG name and the string be free.
% This generates all the possible DCG + strings that
% is possible given these DCGs.
%
% Here are some examples - again - of combining DCGs.
%
% ...
% (s,kjellerstrand) = abakällarstrand
% (s,kjellerstrand) = abakällarbad
% (s,kjellerstrand) = abakällarband
% (s,kjellerstrand) = abakällarbrad
% (s,kjellerstrand) = abakällarbrand
% (s,mankell1) = abaHenking
% (s,mankell1) = abaHenkell
% (s,mankell1) = abaHenkall
% (s,mankell1) = abaHening
% ...
% 
go7 ?=>
  parse(DCG,String,[]),
  println(DCG=String),
  fail,
  nl.
go7 => true.


parse(NT, P_0, P) :-
  % (NT ---> Body),  % We cannot define new operators in Picat.
  dcg(NT,Body), % so we use a plain predicate: dcg/2.
  parse(Body, P_0, P).

parse((Body1, Body2), P_0, P) :-
  parse(Body1, P_0, P_1),
  parse(Body2, P_1, P).

% hakank: added or
parse((Body1 ; Body2), P_0, P) :-
  parse(Body1, P_0, P) ;
  parse(Body2, P_0, P).

parse([], P, P).

parse([Word|Rest], P_0, P) :-
  connects(Word, P_0, P_1),
  parse(Rest, P_1, P).

parse({Goals}, P, P) :- call(Goals).

connects(Word, [Word|Rest], Rest). % Program 3.8 in section 3.4.2 (page 61)


%
% DCGs
%

dcg(s,(a,b,a)). % s --> a,b,a
dcg(s,[]).      % s --> []

dcg(s2,(a,s,a)).
dcg(s2,[]).

dcg(a,"a").
dcg(a,[]).

dcg(b,"b").
dcg(b,[]).

dcg(c,"c").
% dcg(c,[]).

%
% Test of {...} (Picat code):
%
dcg(ab_call_a,(a,b,{println("hello,world!")},a )).

%
% Testing ; (alternatives)
%
dcg(or_test, ((a;b) , (b;c) , (c,a))).

%
% See mankell_v3.pi for more on these two:
%
dcg(kjellerstrand, ("k", ("je" ; "ä"), "ll", ("" ; "er" ; "ar"), ("st" ; "b"), ("" ; "r"), "a", (""; "n"), "d")).

dcg(mankell1,(("H";"M"),("e";"a"),("nk";"n";"nn"),("ing";"ell";"all"))).
dcg(mankell, (mankell1," ", mankell1)).