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.
?-
mc_prob(pre_pcfg([a]),P)
. % expected result ~ 0.5.?-
mc_prob(pre_pcfg([a,b]),P)
. % expected result ~ 0.09692857142857143.?-
mc_prob(pre_pcfg([b]),P)
. % expected result ~ 0.49946153846153846.?-
mc_prob(pre_pcfg([a,b,a]),P)
. % expected result ~ 0.0302.?-
mc_prob(pre_pcfg([b,a]),P)
. % expected result ~ 0.1014.?-
mc_prob(pre_pcfg([b,a]),P)
,bar(P,C)
. % expected result ~ 0.1014.?-
mc_sample(pre_pcfg([b,a]),1000,P,[successes(T),failures(F)])
. % expected result ~ 0.1014.?-
mc_sample(pre_pcfg([b,a]),1000,P)
,bar(P,C)
. % expected result ~ 0.1014.*/