LR parser on Prolog (cont'd - tree)

LR parser on Prolog - 鯨飲馬食コードで書いたLR parserの出力は導出規則の番号の列になっていた。前回も挙げた例だとこんな感じ。

| ?- lr([pron,v,det,n,p,det,n,$],Out).
Out = [1,6,2,8,3,3,5] ? ;
Out = [1,7,8,3,6,3,5] ? ;
no

このリストはスタックとして利用しているので、左側がスタックトップに相当する。そしてスタックは上から導出規則の番号に対応する。LR parserは右端導出（Rightmost derivation）なので、積み重ねていったのとは逆の順番で（つまりスタックトップから）導出規則を開始記号に適応していけば、構文解析した文字列になるというわけだ。上の例だとこんな感じ。

s ->(1) np vp
  ->(6) np v np
  ->(2) np v np pp
  ->(8) np v np p np
  ->(3) np v np p det n
  ->(3) np v det n p det n
  ->(5) pron v det n p det n

s ->(1) np vp
  ->(7) np vp pp
  ->(8) np vp p np
  ->(3) np vp p det n
  ->(6) np v np p det n
  ->(3) np v det n p det n
  ->(5) pron v det n p det n

文字列の右側非終端記号に導出規則を適用しているのが分かるはず。ということで、導出規則の列から構文解析木を表示するものをPrologで書いてみた。以下コード。

ex_out([],[]).
ex_out([O1|Rest],[[LHS,RHS]|T0]):-
  rule(O1,LHS,RHS),
  ex_out(Rest,T0).

ex_tree_lr(Out,T):-
  ex_out(Out,Rule),
  rev(Rule,RevR),
  ex_tree_lr1(RevR,[T]).

ex_tree_lr1(R,T):-
  ex_tree_lr2(R,T0),
  ( T0=[_],T=T0
  ; ex_tree_lr1(T0,T)
  ).

ex_tree_lr2([R],[R]).
ex_tree_lr2([R1,R2|Rest],[R3|Rest]):-
  ex_tree_lr3(R1,R2,R3).
ex_tree_lr2([R1,R2|Rest],[R1|T0]):-
  ex_tree_lr2([R2|Rest],T0).

ex_tree_lr3(R1,[LHS2,RHS2],[LHS2,RHS3]):-
  rev(RHS2,RRHS2),
  ex_tree_lr4(R1,RRHS2,RRHS3),
  rev(RRHS3,RHS3).

ex_tree_lr4(_,[],_):-fail.
ex_tree_lr4([LHS1,RHS1],[LHS1|Rest],[[LHS1,RHS1]|Rest]).
ex_tree_lr4(R1,[LR2|Rest],[LR2|R4]):-
  ex_tree_lr4(R1,Rest,R4).

rev(L,R):-rev(L,[],R).
rev([],R,R).
rev([X|L],Y,R):-rev(L,[X|Y],R).

ごちゃごちゃしているけど、一応は動くはず。以下動作例。

| ?- lr([pron,v,det,n,p,det,n,$],Out).
Out = [1,6,2,8,3,3,5] ? ;
Out = [1,7,8,3,6,3,5] ?
yes
| ?- ex_tree_lr([1,6,2,8,3,3,5],Tree).
Tree = [s,[[np,[pron]],[vp,[v,[np,[[np,[det,n]],[pp,[p,[np,[det|...]]]]]]]]]] ?
yes
| ?- ex_tree_lr([1,7,8,3,6,3,5],Tree).
Tree = [s,[[np,[pron]],[vp,[[vp,[v,[np,[det,n]]]],[pp,[p,[np,[det,n]]]]]]]] ?
yes