1/*
    2Probabilistic context-free grammar. The grammar is left-recursive, MCINTYRE
    3is necessary to ensure termination.
    4Grammar:
    50.4:S->SS
    60.3:S->a
    70.3:S->b
    8From
    9 Taisuke Sato and Keiichi Kubota. Viterbi training in PRISM. 
   10Theory and Practice of Logic Programming,  doi:10.1017/S1471068413000677. 
   11*/
   12:- use_module(library(mcintyre)).   13
   14:- if(current_predicate(use_rendering/1)).   15:- use_rendering(c3).   16:- endif.   17
   18:- mc.   19
   20:- begin_lpad.   21% pcfg(LT): LT is string of terminals accepted by the grammar
   22% pcfg(L,LT,LT0) L is a string of terminals and not terminals that derives
   23% the list of terminals in LT-LT0
   24
   25pcfg(L):- pcfg(['S'],[],_Der,L,[]).
   26% L is accepted if it can be derived from the start symbol S and an empty
   27% string of previous terminals
   28
   29pcfg([A|R],Der0,Der,L0,L2):-
   30  rule(A,Der0,RHS),
   31  pcfg(RHS,[rule(A,RHS)|Der0],Der1,L0,L1),
   32  pcfg(R,Der1,Der,L1,L2).
   33% if there is a rule for A (i.e. it is a non-terminal), expand A using the rule
   34% and continue with the rest of the list
   35
   36pcfg([A|R],Der0,Der,[A|L1],L2):-
   37  \+ rule(A,_,_),
   38  pcfg(R,Der0,Der,L1,L2).
   39% if A is a terminal, move it to the output string
   40
   41pcfg([],Der,Der,L,L).
   42% there are no more symbols to expand
   43
   44rule('S',Der,['S','S']):0.4; rule('S',Der,[a]):0.3; 
   45  rule('S',Der,[b]):0.3.
   46
   47% encodes the three rules of the grammar
   48
   49:- end_lpad.