Edited at

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

More than 3 years have passed since last update.


はじめに

(※ 2015/01/18 追記)

本稿で作成したパーサの改修について、新しく投稿した記事に書きました。

(※追記 ここまで)


以下の記事で Prolog のサーバを利用するのにクライアントを Ruby で作成していました。

言語を連携して利用するのはいいアイデアで、面白い記事だと思いました。

記事のサンプルでは、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 についての拙稿です)