LR parser on Prolog

Prolog

PrologでLR構文解析器を書いたので、自分のためのメモ代わりに。手続き的であまり論理型言語っぽくない書き方だけど。

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

lr(Ss,Ws,Os,Out):-
  Ss=[S|_], Ws=[W|Ws0],
  entry(S,W,Op),
  ( Op=sh(Sn), lr([Sn|Ss],Ws0,Os,Out)
  ; Op=re(R), reduce(R,Ss,Ss1), lr(Ss1,Ws,[R|Os],Out)
  ; Op==accept, Out=Os
  ).

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

reduce(R,Ss,[S1|Ss0]):-
  rule(R,LHS,RHS),
  length(RHS,Len),
  pop(Len,Ss,Ss0),
  Ss0=[S0|_],
  entry(S0,LHS,go(S1)).

導出規則とLR表の例。

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


  |det| n |   p   |pron| v | $ | np| pp| s | vp|
 0|sh1|sh5|       | sh2|   |   |  4|   |  3|   |
 1|   |sh6|       |    |   |   |   |   |   |   |
 2|   |   |  re5  |    |re5|re5|   |   |   |   |
 3|   |   |       |    |   |acc|   |   |   |   |
 4|   |   |  sh7  |    |sh8|   |   | 10|   |  9|
 5|   |   |  re4  |    |re4|re4|   |   |   |   |
 6|   |   |  re3  |    |re3|re3|   |   |   |   |
 7|sh1|sh5|       | sh2|   |   | 11|   |   |   |
 8|sh1|sh5|       | sh2|   |   | 12|   |   |   |
 9|   |   |  sh7  |    |   |re1|   | 13|   |   |
10|   |   |  re2  |    |   |re2|   |   |   |   |
11|   |   |sh7/re8|    |   |re8|   | 10|   |   |
12|   |   |sh7/re6|    |   |re6|   | 10|   |   |
13|   |   |  re7  |    |   |re7|   | 10|   |   |

述語で書き下すとこうなる。

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([pron,v,det,n,p,det,n,$]).
yes
| ?- 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

文長の長さのリストを用いるので実際には使い物にならないはず。一応Prologのバックトラックでgeneralized LR parserっぽくなってるけど、非効率だし。Prolog上で効率的にGLRを扱いたいのであれば、SGLR : 逐次型一般化LRパーザのPrologによる実現(pdf)を読んだ方がいい。ちなみに上の導出規則とLR表もこちらから。

最初のやつを少し簡潔に書くとこんな感じ。

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

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

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