LR parser on Prolog (cont'd - compile)

Prolog

前回LR parser on Prolog - 鯨飲馬食コードで書いたものを、Prologを用いてコンパイル（？）するようなもののメモ。少し前「Prologのファイル入出力は変態だ」という意見を聞いたんだけど、どうなんだろう。

先にコードを貼り付けておく。

rule_compile(In_File,Out_File):-
  open(Out_File,write,OutStream),
  compile(In_File),
  compile_rule(OutStream),
  compile_rule_goto(OutStream),
  write_const(OutStream),
  close(OutStream).

compile_rule(OutStream):-
  entry(S,W,Act),
  format("S=~w W=~w Act=~w~n",[S,W,Act]),
  write1(S,W,Act,OutStream),
  fail.
compile_rule(OutStream):-format(OutStream,"~n",[]).

write1(S,W,sh(Sn),OutStream):-
  format(OutStream,
"lr([~w|Ss0],[~w|Ws0],Os,Out):- lr([~w,~w|Ss0],Ws0,Os,Out).
",[S,W,Sn,S]
  ).
write1(S,W,re(R),OutStream):-
  rule(R,LHS,RHS),
  length(RHS,Len),
  format(OutStream,
"lr([~w|Ss0],[~w|Ws0],Os,Out):-
  pop(~w,[~w|Ss0],[S0|Ss2]),entry(S0,~w,go(Sg)),lr([Sg,S0|Ss2],[~w|Ws0],[~w|Os],Out).
",[S,W,Len,S,LHS,W,R]
  ).
write1(S,W,accept,OutStream):-
  format(OutStream,
"lr([~w|_],[~w|_],Out,Out).
",[S,W]
  ).

compile_rule_goto(OutStream):-
  entry(S,W,go(Sg)),
  format(OutStream,
"entry(~w,~w,~w).
",[S,W,go(Sg)]
),fail.
compile_rule_goto(OutStream):-format(OutStream,"~n",[]).

write_const(OutStream):-
  start_state(S0),
  format(OutStream,
"pop(0,S,S).
pop(N,[_|S],Xs):-
  M is N-1, pop(M,S,Xs).

lr(Ws):- lr([~w],Ws,[],_).
lr(Ws,Out):- lr([~w],Ws,[],Out).

",[S0,S0]
  ).

前回挙げた、導出規則とLR表を述語で書いた例をもう一度。

rule(1,s,[np,vp]).
rule(2,np,[np,pp]).
rule(3,np,[det,n]).
rule(4,np,[n]).
rule(5,np,[pron]).
rule(6,vp,[v,np]).
rule(7,vp,[vp,pp]).
rule(8,pp,[p,np]).

start_state(0).

entry(0,det,sh(1)).
entry(0,n,sh(5)).
entry(0,pron,sh(2)).
entry(0,np,go(4)).
entry(0,s,go(3)).
entry(1,n,sh(6)).
entry(2,p,re(5)).
entry(2,v,re(5)).
entry(2,$,re(5)).
entry(3,$,accept).
entry(4,p,sh(7)).
entry(4,v,sh(8)).
entry(4,pp,go(10)).
entry(4,vp,go(9)).
entry(5,p,re(4)).
entry(5,v,re(4)).
entry(5,$,re(4)).
entry(6,p,re(3)).
entry(6,v,re(3)).
entry(6,$,re(3)).
entry(7,det,sh(1)).
entry(7,n,sh(5)).
entry(7,pron,sh(2)).
entry(7,np,go(11)).
entry(8,det,sh(1)).
entry(8,n,sh(5)).
entry(8,pron,sh(2)).
entry(8,np,go(12)).
entry(9,p,sh(7)).
entry(9,$,re(1)).
entry(9,pp,go(13)).
entry(10,p,re(2)).
entry(10,v,re(2)).
entry(10,$,re(2)).
entry(11,p,sh(7)).
entry(11,p,re(8)).
entry(11,v,re(8)).
entry(11,$,re(8)).
entry(11,pp,go(10)).
entry(12,p,sh(7)).
entry(12,p,re(6)).
entry(12,$,re(6)).
entry(12,pp,go(10)).
entry(13,p,re(7)).
entry(13,$,re(7)).
entry(13,pp,go(10)).

これらのデータを入力に用いると、こんな出力が得られる。

lr([0|Ss0],[det|Ws0],Os,Out):- lr([1,0|Ss0],Ws0,Os,Out).
lr([0|Ss0],[n|Ws0],Os,Out):- lr([5,0|Ss0],Ws0,Os,Out).
lr([0|Ss0],[pron|Ws0],Os,Out):- lr([2,0|Ss0],Ws0,Os,Out).
lr([1|Ss0],[n|Ws0],Os,Out):- lr([6,1|Ss0],Ws0,Os,Out).
lr([2|Ss0],[p|Ws0],Os,Out):-
  pop(1,[2|Ss0],[S0|Ss2]),entry(S0,np,go(Sg)),lr([Sg,S0|Ss2],[p|Ws0],[5|Os],Out).
lr([2|Ss0],[v|Ws0],Os,Out):-
  pop(1,[2|Ss0],[S0|Ss2]),entry(S0,np,go(Sg)),lr([Sg,S0|Ss2],[v|Ws0],[5|Os],Out).
lr([2|Ss0],[$|Ws0],Os,Out):-
  pop(1,[2|Ss0],[S0|Ss2]),entry(S0,np,go(Sg)),lr([Sg,S0|Ss2],[$|Ws0],[5|Os],Out).
lr([3|_],[$|_],Out,Out).
lr([4|Ss0],[p|Ws0],Os,Out):- lr([7,4|Ss0],Ws0,Os,Out).
lr([4|Ss0],[v|Ws0],Os,Out):- lr([8,4|Ss0],Ws0,Os,Out).
lr([5|Ss0],[p|Ws0],Os,Out):-
  pop(1,[5|Ss0],[S0|Ss2]),entry(S0,np,go(Sg)),lr([Sg,S0|Ss2],[p|Ws0],[4|Os],Out).
lr([5|Ss0],[v|Ws0],Os,Out):-
  pop(1,[5|Ss0],[S0|Ss2]),entry(S0,np,go(Sg)),lr([Sg,S0|Ss2],[v|Ws0],[4|Os],Out).
lr([5|Ss0],[$|Ws0],Os,Out):-
  pop(1,[5|Ss0],[S0|Ss2]),entry(S0,np,go(Sg)),lr([Sg,S0|Ss2],[$|Ws0],[4|Os],Out).
lr([6|Ss0],[p|Ws0],Os,Out):-
  pop(2,[6|Ss0],[S0|Ss2]),entry(S0,np,go(Sg)),lr([Sg,S0|Ss2],[p|Ws0],[3|Os],Out).
lr([6|Ss0],[v|Ws0],Os,Out):-
  pop(2,[6|Ss0],[S0|Ss2]),entry(S0,np,go(Sg)),lr([Sg,S0|Ss2],[v|Ws0],[3|Os],Out).
lr([6|Ss0],[$|Ws0],Os,Out):-
  pop(2,[6|Ss0],[S0|Ss2]),entry(S0,np,go(Sg)),lr([Sg,S0|Ss2],[$|Ws0],[3|Os],Out).
lr([7|Ss0],[det|Ws0],Os,Out):- lr([1,7|Ss0],Ws0,Os,Out).
lr([7|Ss0],[n|Ws0],Os,Out):- lr([5,7|Ss0],Ws0,Os,Out).
lr([7|Ss0],[pron|Ws0],Os,Out):- lr([2,7|Ss0],Ws0,Os,Out).
lr([8|Ss0],[det|Ws0],Os,Out):- lr([1,8|Ss0],Ws0,Os,Out).
lr([8|Ss0],[n|Ws0],Os,Out):- lr([5,8|Ss0],Ws0,Os,Out).
lr([8|Ss0],[pron|Ws0],Os,Out):- lr([2,8|Ss0],Ws0,Os,Out).
lr([9|Ss0],[p|Ws0],Os,Out):- lr([7,9|Ss0],Ws0,Os,Out).
lr([9|Ss0],[$|Ws0],Os,Out):-
  pop(2,[9|Ss0],[S0|Ss2]),entry(S0,s,go(Sg)),lr([Sg,S0|Ss2],[$|Ws0],[1|Os],Out).
lr([10|Ss0],[p|Ws0],Os,Out):-
  pop(2,[10|Ss0],[S0|Ss2]),entry(S0,np,go(Sg)),lr([Sg,S0|Ss2],[p|Ws0],[2|Os],Out).
lr([10|Ss0],[v|Ws0],Os,Out):-
  pop(2,[10|Ss0],[S0|Ss2]),entry(S0,np,go(Sg)),lr([Sg,S0|Ss2],[v|Ws0],[2|Os],Out).
lr([10|Ss0],[$|Ws0],Os,Out):-
  pop(2,[10|Ss0],[S0|Ss2]),entry(S0,np,go(Sg)),lr([Sg,S0|Ss2],[$|Ws0],[2|Os],Out).
lr([11|Ss0],[p|Ws0],Os,Out):- lr([7,11|Ss0],Ws0,Os,Out).
lr([11|Ss0],[p|Ws0],Os,Out):-
  pop(2,[11|Ss0],[S0|Ss2]),entry(S0,pp,go(Sg)),lr([Sg,S0|Ss2],[p|Ws0],[8|Os],Out).
lr([11|Ss0],[v|Ws0],Os,Out):-
  pop(2,[11|Ss0],[S0|Ss2]),entry(S0,pp,go(Sg)),lr([Sg,S0|Ss2],[v|Ws0],[8|Os],Out).
lr([11|Ss0],[$|Ws0],Os,Out):-
  pop(2,[11|Ss0],[S0|Ss2]),entry(S0,pp,go(Sg)),lr([Sg,S0|Ss2],[$|Ws0],[8|Os],Out).
lr([12|Ss0],[p|Ws0],Os,Out):- lr([7,12|Ss0],Ws0,Os,Out).
lr([12|Ss0],[p|Ws0],Os,Out):-
  pop(2,[12|Ss0],[S0|Ss2]),entry(S0,vp,go(Sg)),lr([Sg,S0|Ss2],[p|Ws0],[6|Os],Out).
lr([12|Ss0],[$|Ws0],Os,Out):-
  pop(2,[12|Ss0],[S0|Ss2]),entry(S0,vp,go(Sg)),lr([Sg,S0|Ss2],[$|Ws0],[6|Os],Out).
lr([13|Ss0],[p|Ws0],Os,Out):-
  pop(2,[13|Ss0],[S0|Ss2]),entry(S0,vp,go(Sg)),lr([Sg,S0|Ss2],[p|Ws0],[7|Os],Out).
lr([13|Ss0],[$|Ws0],Os,Out):-
  pop(2,[13|Ss0],[S0|Ss2]),entry(S0,vp,go(Sg)),lr([Sg,S0|Ss2],[$|Ws0],[7|Os],Out).

entry(0,np,go(4)).
entry(0,s,go(3)).
entry(4,pp,go(10)).
entry(4,vp,go(9)).
entry(7,np,go(11)).
entry(8,np,go(12)).
entry(9,pp,go(13)).
entry(11,pp,go(10)).
entry(12,pp,go(10)).
entry(13,pp,go(10)).

pop(0,S,S).
pop(N,[_|S],Xs):-
  M is N-1, pop(M,S,Xs).

lr(Ws):- lr([0],Ws,[],_).
lr(Ws,Out):- lr([0],Ws,[],Out).

こんな風に前処理しておけば探索の手間を減らせるので、一般的には高速になるはず。とはいえ、前回も書いたように、このLR構文解析器は実用には耐えないのだけれど。