1/*
    2Prefix parser for probabilistic context free grammars.
    3The program computes the probability that a string is 
    4a prefix of a string generated by the grammar. 
    5From 
    6T. Sato, P. Meyer, Tabling for infinite probability computation, in: 
    7Intnational Confence on Logic Programming, Vol. 17 of LIPIcs, 2012, 
    8pp.  348-358.
    9T. Sato, P. Meyer, Infinite probability computation by cyclic explanation
   10graphs, Theory and Practice of Logic Programming 14 (2014) 909-937.
   11doi:10.1017/S1471068413000562.
   12*/
   13
   14:- use_module(library(mcintyre)).   15
   16:- if(current_predicate(use_rendering/1)).   17:- use_rendering(c3).   18:- endif.   19
   20:- mc.   21
   22:- begin_lpad.   23% grammar
   24% 0.4:S->SS
   25% 0.3:S->a
   26% 0.3:S->b
   27pre_pcfg(L):- pre_pcfg(['S'],[],_Der,L,[]).
   28
   29pre_pcfg([A|_R],Der0,Der,L0,[]):-
   30  rule(A,Der0,RHS),      % A is a nontminal
   31  pre_pcfg(RHS,[rule(A,RHS)|Der0],Der,L0,[]). % pseudo success, R is discarded
   32
   33pre_pcfg([A|R],Der0,Der,L0,L2):-
   34  rule(A,Der0,RHS),      % rule A->RHS is selected
   35  pre_pcfg(RHS,[rule(A,RHS)|Der0],Der1,L0,L1), % recursion
   36  pre_pcfg(R,Der1,Der,L1,L2).   % recursion
   37
   38pre_pcfg([A|R],Der0,Der,[A|L1],L2):-
   39  \+ rule(A,_,_),     % A is a tminal, consume A
   40  pre_pcfg(R,Der0,Der,L1,L2).
   41
   42pre_pcfg([],Der,Der,L,L).      % termination
   43
   44rule('S',Der,['S','S']):0.4; rule('S',Der,[a]):0.3; 
   45  rule('S',Der,[b]):0.3.
   46
   47
   48
   49:- end_lpad.