%
% Simple grammar example
% taken from: David S. Warren: 
% Programming in tabled Prolog, Ch 4 Grammars
% 
% illustrates efficient recognition and parsing
% using tabled logic programming
%
% Author: Brigitte Pientka
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Define token stream
%

tok:type.

% tokens 
'c': tok.
'a': tok.
'd': tok.
'b': tok.

% list of tokens
tokens : type.
nil: tokens.
; : tok -> tokens -> tokens.  %infix right 10 ;.

%{
DCG : for Prolog 

s --> b, [c].
s --> g, [d].
b --> b, b.
b --> [a].
g --> g, [a].
g --> [a].
}%

recogS : tokens -> tokens -> type.
recogB : tokens -> tokens -> type.
recogG : tokens -> tokens -> type.
%tabled recogS.
%tabled recogB.
%tabled recogG.

sb: recogS L R 
   <- recogB L ('c' ; R).

sg: recogS L R 
   <- recogG L ('d' ; R).

b1 : recogB L R 
      <- recogB L R1
      <- recogB R1 R.

b2 : recogB ('a' ; L) L.

g1 : recogG ('a' ; L) R <- recogG L R.
g2 : recogG ('a' ; L) L.


%%%%%%%%%%%%%%%%%%%%%%%%%
% parse simple grammar
%{ 

if we add an extra argument to the recognizer,
then our parser will have exponential complexity. 

Note: there are exponentially many parses 
   and we want to produce all of them!
   it will take exponential time to produce them all,
   however, it do not want to take exponential time 
   to report failure.
}%


% Parser : referring to recognizer

pterm: type.
s : pterm -> pterm -> pterm.
b : pterm -> pterm -> pterm.
g : pterm -> pterm.
a: pterm.
d: pterm.
c: pterm.

parseB : pterm -> tokens -> tokens -> type.
parseS : pterm -> tokens -> tokens -> type.
parseG : pterm -> tokens -> tokens -> type.

ps1: parseS (s P c) L R 
      <- recogB L ('c' ; R) 
      <- parseB P L ('c' ; R).

ps2: parseS (s P d) L R
   <- recogG L ('d' ; R)
   <- parseB P L ('d' ; R).

pb1: parseB (b P1 P2) L R
  <- recogB L L1
  <- recogB L1 R 
  <- parseB P1 L L1 
  <- parseB P2 L1 R.

pb2: parseB a ('a' ; L) L.

pg1: parseG (g P) L R
   <- recogG L ('a' ; R) 
   <- parseG P L ('a' ; R).

pg2: parseG a ('a' ; L) L.

% some simple queries 

%querytabled * *
 recogG ('a' ; 'a' ; 'a' ; nil) L.

%querytabled * *
 recogS ('a' ; 'a' ; 'a' ; 'c' ; nil) nil.

%querytabled * *
 recogS ('a' ; 'a' ; 'a' ; 'b' ; nil) nil.

%querytabled * *
 D : recogS ('a' ; 'a' ; 'a' ; 'c' ; nil) nil.

%querytabled * *
 D : recogS ('a' ; 'a' ; 'a' ; 'b' ; nil) nil.

%querytabled * *
parseS P ('a' ; 'a' ; 'a' ; 'd' ; nil) nil.

%querytabled * *
parseS P ('a' ; 'a' ; 'a' ; 'b' ; nil) nil.