Ruby: Racc を利用した Prolog ミニパーサ

はじめに

(※ 2015/01/18 追記)
本稿で作成したパーサの改修について、新しく投稿した記事に書きました。

• Ruby: ミニ Prolog パーサ (改)

(※追記 ここまで)

---

以下の記事で Prolog のサーバを利用するのにクライアントを Ruby で作成していました。
言語を連携して利用するのはいいアイデアで、面白い記事だと思いました。

• PrologなNoSQLサーバを立てる

記事のサンプルでは、Prolog 側の応答を Ruby 側で文字列として受け取っています。
Ruby 側で扱いやすくするために、Prolog の応答文字列を Ruby オブジェクトに変換するパーサを Racc を使って作成しました。

Prolog ミニパーサ

Ruby 上での Prolog の表現方法は以下のようにしています。

Prolog	Ruby	Prolog側の例	対応するRuby側の例
述語	Hash (*1)	pred(a,b,10)	{pred: [:a,:b,10]}
リスト	Array (*2)	[a,b,10]、[]	[:a,:b,10]、[]
リスト(文字列)	String	"abc"	"abc"
数値(整数)	Integer	1、-10	1、-10
数値(小数)	Float	1.1、-10.5	1.1、-10.5
アトム	Symbol (*3)	a、'ABC'	:a、:"'ABC'"
変数	Symbol	X、_abc、_	:X、:_abc、:_

• (*1) Hash のサイズは 1。形式は { アトム => 空でないリスト }
• (*2) (空リストでない場合) Array の要素は項として妥当なもの
• (*3) 「'」で囲まれたアトムは、「'」も含んだ文字列を to_sym する

prolog_parser.ry

class Prolog::Parser
rule
    response :
             | term

    term     : pred
             | list
             | number
             | atom
             | var

    terms    : term                     { result = [val[0]] }
             | terms ',' term           { result << val[2]  }

    pred     : atom '(' terms ')'       { result = { val[0] => val[2] } }

    list     : '[' ']'                  { result = []     }
             | '[' terms ']'            { result = val[1] }
             | string

    string   : DQWORD                   { result = val[0][1..-2] }

    number   : INTEGER                  { result = val[0].to_i }
             | FLOAT                    { result = val[0].to_f }

    atom     : LWORD                    { result = val[0].to_sym }
             | SQWORD                   { result = val[0].to_sym }

    var      : UWORD                    { result = val[0].to_sym }
             | USWORD                   { result = val[0].to_sym }
end

---- header
require 'pp'
require 'strscan'

---- inner
attr_accessor :yydebug
attr_accessor :verbose

def parse(str)
  s = StringScanner.new str
  @q = []

  until s.eos?
    s.scan(/[-+]?(0|[1-9]\d*)\.\d+/) ? (@q << [:FLOAT,      s.matched]) :
    s.scan(/[-+]?(0|[1-9]\d*)/)      ? (@q << [:INTEGER,    s.matched]) :
    s.scan(/[[:lower:]]\w*/)         ? (@q << [:LWORD,      s.matched]) :
    s.scan(/[[:upper:]]\w*/)         ? (@q << [:UWORD,      s.matched]) :
    s.scan(/'[^']+'/)                ? (@q << [:SQWORD,     s.matched]) :
    s.scan(/"[^"]+"/)                ? (@q << [:DQWORD,     s.matched]) :
    s.scan(/_\w*/)                   ? (@q << [:USWORD,     s.matched]) :
    s.scan(/./)                      ? (@q << [s.matched,   s.matched]) :
                                       (raise "scanner error")
  end

  pp @q if verbose

  do_parse
end

def next_token
  @q.shift
end

---- footer
if __FILE__ == $0
  require 'pp'
  require 'optparse'
  require 'ostruct'

  opt    = OpenStruct.new ARGV.getopts 'vd'
  str    = ARGV.shift or (raise "no arguments")
  parser = Prolog::Parser.new.tap {|p| p.yydebug = opt.d; p.verbose = opt.v }

  begin
    pp parser.parse str
  rescue Racc::ParseError => e
    $stderr.puts e
  end
end

コンパイル

$ racc -g -o prolog_parser.rb prolog_parser.ry

動かしてみる

Prolog 処理系は SWI-Prolog を使用しました。
Ubuntu Linux では以下のようにインストールします。

$ sudo apt-get install swi-prolog

Prolog プログラムは上記の記事のサンプルをほぼそのまま流用させていただきます。

server.pro

create_server(Port) :-
    tcp_socket(Socket),
    tcp_bind(Socket, Port),
    tcp_listen(Socket, 5),
    tcp_open_socket(Socket, AcceptFd, _),
    dispatch(AcceptFd).

dispatch(AcceptFd) :-
    tcp_accept(AcceptFd, Socket, Peer),
    thread_create(process_client(Socket, Peer), _,
        [ detached(true)
        ]),
    dispatch(AcceptFd).

process_client(Socket, _) :-
    setup_call_cleanup(tcp_open_socket(Socket, In, Out),
       handle_service(In, Out),
       close_connection(In, Out)).

close_connection(In, Out) :-
    close(In, [force(true)]),
    close(Out, [force(true)]).

handle_service(In, Out) :-
    read(In, Chars),
    findall(Chars, Chars, L),
    write(Out, L),
    writeln(L).

サーバを起動します。(TCPポート3333 を LISTEN します)

$ swipl -l server.pro -g 'create_server(3333).'        # 起動したままになる                                   

定番ネタ(?)「ソクラテスは死ぬ(三段論法)」をしてみたいと思います。
以下は、slog(S-Prolog) という処理系で「ソクラテスは死ぬ」を実行した様子です。

person(socrates).           %% ファクト
mortal(X) :- person(X).     %% ルール 

?- mortal(Who).             %% 問い合わせ
Who = socrates ->;
no

クライアント側スクリプトその1。(Prolog データベースにファクトとルールを追加する)

client1.rb

require 'pp'
require 'socket'

host, port = 'localhost', 3333

insert = -> clause {
  TCPSocket.open(host, port) do |s|
    s.puts "assert(#{clause})."
    s.gets
  end
}

pp insert.("person(socrates)")
pp insert.("mortal(X) :- person(X)")

スクリプトその1、実行。 (データベースにファクトとルールが追加された)

$ ruby client1.rb 
"[assert(person(socrates))]"
"[assert((mortal(_G61):-person(_G61)))]"

クライアント側スクリプトその 2 です。(問い合わせをします)
応答は作成した Prolog ミニパーサでパースしてみたいと思います。

client2.rb

require 'pp'
require 'socket'
require 'prolog_parser'

host, port = 'localhost', 3333

inquire = -> query {
  TCPSocket.open(host, port) do |s|
    s.puts "#{query}."
    s.gets
  end
}

res = inquire.("mortal(Who)")
pp Prolog::Parser.new.parse(res)

実行。

$ ruby client2.rb 
[{:mortal=>[:socrates]}]

応答も返って来てるし、想定通りパースできているようです。
OK です。

サーバ側の表示も確認しておきます。

[assert(person(socrates))]                  # クライアントその1 で表示
[assert((mortal(_G61):-person(_G61)))]      #    〃
[mortal(socrates)]                          # クライアントその2 で表示

今後の課題

本当はクライアントその1の応答もパースしたいのですが、Prolog ミニパーサは、

(mortal(_G61):-person(_G61))

が、まだ解析できません。（「:-」がネックになっています。。。）
今後の課題です。(。。。といって、実現できるかわかりませんが)

---

(※2015/01/13 追記) 今後の課題をまとめました。

• 記号列から成るアトムに対応していない(字句/構文解析の問題)
• 前置/中置/後置 の構文に対応していない(字句/構文解析の問題)
• [H|T] の構文に対応していない(字句/構文解析の問題、Rubyでの表現の問題)
• 項を囲む括弧「(」「)」に対応していない(字句/構文解析の問題、Rubyでの表現の問題)
• まだ、他にもあるかも。。。。

特に括弧の問題では、現在考えているRubyでの表現を見直す必要があるかもしれません。

その他 (※2015/01/13 追記)

Ruby のオブジェクトから Prolog 上の表現への変換

to_prolog = -> x, w='[]' {
  x.kind_of?(Hash)   ? "#{x.first[0]}#{to_prolog.(x.first[1],'()')}" :
  x.kind_of?(Array)  ? "#{w[0]}#{(x.map(&to_prolog) * ',')}#{w[-1]}" :
  x.kind_of?(String) ? %("#{x}") :
                       "#{x}"
}

puts to_prolog.(pred: [:a,:b,10])    # pred(a,b,10)
puts to_prolog.([:a,:b,10])          # [a,b,10]
puts to_prolog.([])                  # []
puts to_prolog.("abc")               # "abc"
puts to_prolog.(1)                   # 1
puts to_prolog.(-10)                 # -10
puts to_prolog.(1.1)                 # 1.1
puts to_prolog.(-10.5)               # -10.5
puts to_prolog.(:a)                  # a
puts to_prolog.(:"'ABC'")            # 'ABC'
puts to_prolog.(:X)                  # X
puts to_prolog.(:_abc)               # _abc
puts to_prolog.(:_)                  # _

リスト<->文字列変換

s_to_l = -> s { s.unpack("C*") }
l_to_s = -> l { l.pack("C*") }

p s_to_l.("abc")             #=> [97, 98, 99]
p l_to_s.([97, 98, 99])      #=> "abc"

アトム、変数判定

is_atom = -> x { !!(x.kind_of?(Symbol) && x.to_s =~ /\A[[:lower:]']/) }
is_var  = -> x { !!(x.kind_of?(Symbol) && x.to_s =~ /\A[[:upper:]_]/) }

p is_atom.(:a)         #=> true
p is_atom.(:"'ABC'")   #=> true
p is_var.(:X)          #=> true
p is_var.(:_abc)       #=> true
p is_var.(:_)          #=> true

puts "---"

p is_var.(:a)          #=> false
p is_var.(:"'ABC'")    #=> false
p is_atom.(:X)         #=> false
p is_atom.(:_abc)      #=> false
p is_atom.(:_)         #=> false

おわりに

本稿内容の動作確認は以下の環境で行っています。

• Ruby 2.1.5 p273
• SWI-Prolog version 6.6.4 for amd64
• Ubuntu Linux 14.04
• S-Prolog version 2.5

参考: (Racc についての拙稿です)

• Ruby: Racc