Mini Prolog Parser (for Ruby with Racc)

example.txt

:
: 実行例 (コマンドライン引数に渡す文字列には最後の「.」は含めません)
:

$ ruby prolog_parser.rb "abc"
:abc

$ ruby prolog_parser.rb "a(abc)"
{:a=>[:abc]}

$ ruby prolog_parser.rb "[1,2,3]"
[1, 2, 3]

$ ruby prolog_parser.rb "a(X) :- b(X),!"
{:":-"=>[{:a=>[{nil=>:X}]}, {:","=>[{:b=>[{nil=>:X}]}, :!]}]}

$ ruby prolog_parser.rb ",(,,,),,(,,,,,)"
{:","=>[{:","=>[:",", :","]}, {:","=>[:",", :",", :","]}]}

$ ruby prolog_parser.rb -v "a(abc)"
[:FUNCTOR, "a"]
[:ATOM, "abc"]
[")", ")"]
[".", "."]
nil
{:a=>[:abc]}

Makefile

RACC        := racc
RACCFLAGS   := -g

SOURCES := prolog_parser.ry
TARGETS := ${patsubst %.ry, %.rb, ${SOURCES}}


.SUFFIXES : .rb .ry

%.rb : %.ry
    ${RACC} ${RACCFLAGS} -o $@ $<

.PHONY: all

all : ${TARGETS}
~                     

prolog_parser.ry

class Prolog::MiniParser
prechigh
  right FX____1
  right XFY_200
  right XFX_200
  right FY__200
  left  YFX_250
  left  YFX_400
  left  YFX_500
  right XFY_600
  right XFX_700 OP
  right FY__900
  right XFX_990
  right ','
  right XFY1000
  right XFY1050
  right XFY1100
  right FX_1150
  right XFX1200 ':-'
  right FX_1200
preclow

rule
  program  :
           | program term '.'  { @commit << (result = val[1]) }

  term     : primary
           | op2
           | term XFY_200 term { result = {val[1].to_sym => [val[0], val[2]]} }
           | term XFX_200 term { result = {val[1].to_sym => [val[0], val[2]]} }
           | term YFX_250 term { result = {val[1].to_sym => [val[0], val[2]]} }
           | term YFX_400 term { result = {val[1].to_sym => [val[0], val[2]]} }
           | term YFX_500 term { result = {val[1].to_sym => [val[0], val[2]]} }
           | term XFY_600 term { result = {val[1].to_sym => [val[0], val[2]]} }
           | term XFX_700 term { result = {val[1].to_sym => [val[0], val[2]]} }
           | term OP      term { result = {val[1].to_sym => [val[0], val[2]]} }
           | term XFX_990 term { result = {val[1].to_sym => [val[0], val[2]]} }
           | term ','     term { result = {val[1].to_sym => [val[0], val[2]]} }
           | term XFY1000 term { result = {val[1].to_sym => [val[0], val[2]]} }
           | term XFY1050 term { result = {val[1].to_sym => [val[0], val[2]]} }
           | term XFY1100 term { result = {val[1].to_sym => [val[0], val[2]]} }
           | term XFX1200 term { result = {val[1].to_sym => [val[0], val[2]]} }
           | term ':-' term    { result = {val[1].to_sym => [val[0], val[2]]} }
           | FX____1 term      { result = {val[0].to_sym => [val[1]]} }
           | FY__200 term      { result = {val[0].to_sym => [val[1]]} }
           | FY__900 term      { result = {val[0].to_sym => [val[1]]} }
           | FX_1150 term      { result = {val[0].to_sym => [val[1]]} }
           | FX_1200 term      { result = {val[0].to_sym => [val[1]]} }
           | ':-' term         { result = {val[0].to_sym => [val[1]]} }

  primary  : number
           | var
           | atom
           | pred
           | list
           | '(' term ')'           { result = val[1] }
           | '{' term '}'           { result = { true => val[1] } }

  pred     : functor args ')'       { result = { val[0]        => val[1] } }
           | ',' '(' args ')'       { result = { val[0].to_sym => val[2] } }

  functor  : FUNCTOR                { result = val[0].to_sym }

  args     : arg                    { result = [val[0]] }
           | args ',' arg           { result << val[2]  }

  arg      : primary
           | primary op2 primary    { result = {val[1].to_sym => [val[0], val[2]]} }
           | op                     { result = val[0].to_sym }
           | ':-'                   { result = val[0].to_sym }

  list     : '[' ']'                { result = [] }
           | '[' args ']'           { result = val[1] }
           | '[' args '|' arg ']'   { result = { val[1] => [val[3]] } }
           | string

  string   : STRING

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

  var      : VAR                    { result = { nil => val[0].to_sym } }

  atom     : ATOM                   { result = val[0].to_sym }
           | ','                    { result = val[0].to_sym }
           | '.'                    { result = val[0].to_sym }

  op       : op2
           | op1

  op2      : OP
           | XFY_200
           | XFX_200
           | YFX_250
           | YFX_400
           | YFX_500
           | XFY_600
           | XFX_700
           | XFX_990
           | XFY1050
           | XFY1100
           | XFX1200

   op1     : FX____1
           | FY__200
           | FY__900
           | FX_1150
           | FX_1200
end

---- header
require 'strscan'
require 'stringio'
require 'forwardable'
require 'drb'

---- inner
include DRb::DRbUndumped

attr_accessor :yydebug			# デバッグコード出力フラグ
attr_accessor :verbose			# トークンキューダンプ出力フラグ
attr_accessor :term, :line, :file, :io, :enum, :reader	# 入力ソース

#
# パースする。戻り値は解析結果を返す Enumerator
#
def parse(str=nil, term:nil, line:nil, file:nil, io:nil, enum:nil, reader:nil, &block)
  self.term   = str    if str
  self.term   = term   if term
  self.line   = line   if line
  self.file   = file   if file
  self.io     = io     if io
  self.enum   = enum   if enum
  self.reader = reader if reader
  self.reader = block  if block

  Enumerator.new {|y| @commit = y ; do_parse }.extend(DRb::DRbUndumped)
end

private
def next_token
  tokenizer.next.tap {|token| p token if verbose }
end

def source
  reader_gen = -> io { -> { io.read rescue nil } }

  (reader)                                               ||
  (enum && -> { enum.next rescue nil })                  ||
  (io   && reader_gen.(io))                              ||
  (file && reader_gen.(StringIO.new(open file, &:read))) ||
  (line && reader_gen.(StringIO.new(line)))              ||
  (term && reader_gen.(StringIO.new("#{term.sub(/%.*\z/){}.strip} .")))
end

def tokenizer(input=source)
  token = method(:tokenize)
  @tokenizer ||= Enumerator.new do |y|
    StringScanner.new(input.() || '').instance_eval do
      until eos?
        scan(/%.*$/)                           ? (nil) : # comment
        scan(/\s+/)                            ? (nil) : # white space
        scan(/[-+]?(0|[1-9]\d*)\.\d+/)         ? (y << [:FLOAT,   matched]) :
        scan(/[-+]?(0|[1-9]\d*)/)              ? (y << [:INTEGER, matched]) :
        scan(/"(.*?)"/)                        ? (y << [:STRING,  self[1]]) :
        scan(/[_[:upper:]]\w*/)                ? (y << [:VAR,     matched]) :

        scan(/([[:lower:]]\w*)\(/)             ? (y << [:FUNCTOR, self[1]]) :
        scan(/'(.+?)'\(/)                      ? (y << [:FUNCTOR, self[1]]) :
        scan(/([\#$&*+\-.\/:;<=>?@\\^`~]+)\(/) ? (y << [:FUNCTOR, self[1]]) :
        scan(/(!)\(/)                          ? (y << [:FUNCTOR, self[1]]) :

        scan(/[[:lower:]]\w*/)                 ? (y << token.(matched)) :
        scan(/'(.+?)'/)                        ? (y << token.(self[1])) :
        scan(/[\#$&*+\-.\/:;<=>?@\\^`~]+/)     ? (y << token.(matched)) :

        scan(/!/)                              ? (y << [:ATOM,    matched]) :
        scan(/[^\x00-\x7f]+/)                  ? (y << [:ATOM,    matched]) :
        scan(/./)                              ? (y << [matched,  matched]) :
                                                 (raise "scanner error")
        concat(input.() || '')

        # 「!」は単独で現れる場合のみ FUNCTOR, ATOM と解釈する
        # ASCII(0x00-0x7f)以外の文字並びは ATOM と解釈する
      end
    end
    y << nil
  end.lazy
end

def tokenize(s)
  # 組み込み演算子は SWI-Prolog version 6.6.4 を参考にした
  operator = -> sym do
    {
      "$"                     => :FX____1,
      ###","                     => :XFY1000,
      ###"|"                     => :XFY1105,
      "*"                     => :YFX_400,
      "**"                    => :XFX_200,
      "*->"                   => :XFY1050,
      ###"+"                     => [:YFX_500, :FY__200],
      ###"-"                     => [:YFX_500, :FY__200],
      "+"                     => :YFX_500,
      "-"                     => :YFX_500,
      "-->"                   => :XFX1200,
      "->"                    => :XFY1050,
      "/"                     => :YFX_400,
      "//"                    => :YFX_400,
      "/\\"                   => :YFX_500,
      ":"                     => :XFY_600,
      ###":-"                    => [:XFX1200, :FX_1200],
      ":="                    => :XFX_990,
      ";"                     => :XFY1100,
      "<"                     => :XFX_700,
      "<<"                    => :YFX_400,
      "="                     => :XFX_700,
      "=.."                   => :XFX_700,
      "=:="                   => :XFX_700,
      "=<"                    => :XFX_700,
      "=="                    => :XFX_700,
      "=@="                   => :XFX_700,
      "=\\="                  => :XFX_700,
      ">"                     => :XFX_700,
      ">="                    => :XFX_700,
      ">>"                    => :YFX_400,
      "?"                     => :YFX_250,
      "?-"                    => :FX_1200,
      "@"                     => :FY__200,
      "@<"                    => :XFX_700,
      "@=<"                   => :XFX_700,
      "@>"                    => :XFX_700,
      "@>="                   => :XFX_700,
      "\\"                    => :FY__200,
      "\\+"                   => :FY__900,
      "\\/"                   => :YFX_500,
      "\\="                   => :XFX_700,
      "\\=="                  => :XFX_700,
      "\\=@="                 => :XFX_700,
      "^"                     => :XFY_200,
      "as"                    => :XFX_700,
      "discontiguous"         => :FX_1150,
      "div"                   => :YFX_400,
      "dynamic"               => :FX_1150,
      "initialization"        => :FX_1150,
      "is"                    => :XFX_700,
      "meta_predicate"        => :FX_1150,
      "mod"                   => :YFX_400,
      "module_transparent"    => :FX_1150,
      "multifile"             => :FX_1150,
      "public"                => :FX_1150,
      "rdiv"                  => :YFX_400,
      "rem"                   => :YFX_400,
      "thread_initialization" => :FX_1150,
      "thread_local"          => :FX_1150,
      "volatile"              => :FX_1150,
      "xor"                   => :YFX_400,
    }[sym]
  end

  case s
    when '.',':-'                    ; [s, s]
    when operator                    ; [operator[s], s]
    when /[\#$&*+\-.\/:;<=>?@\\^`~]/ ; [:OP, s]
    else                             ; [:ATOM, s]
  end
  # 「.」「:-」の意味合いは字句解析では判定しない。パーサに委ねる
end

---- footer
module Prolog
  class Parser
    include DRb::DRbUndumped
    extend Forwardable 

    DRB_URI = 'druby://:53332'

    attr_accessor :yydebug			# デバッグコード出力フラグ
    attr_accessor :verbose			# トークンキューダンプ出力フラグ
    attr_accessor :term, :line, :file, :io, :enum, :reader	# 入力ソース

    def parser
      Prolog::MiniParser.new.tap do |my|
	    my.yydebug = yydebug
	    my.verbose = verbose
        my.term    = term
        my.line    = line
        my.file    = file
        my.io      = io
        my.enum    = enum
        my.reader  = reader
      end
    end

    delegate %i(parse) => :parser

    #
    # パースする。戻り値は解析結果を格納した Array
    #
    def parse_to_a(*args, &block)
      parse(*args, &block).entries
    end
    
    #
    # パースする。戻り値は最初の解析結果
    #
    def parse_one(*args, &block)
      parse(*args, &block).first
    end

    alias to_ruby parse_one

    #
    # Ruby の表現形式(オブジェクト)を Prolog の表現形式(文字列)に変換する
    #
    def to_prolog(x, w='[]')
      case x
        when Hash
          key, val, = *x.first
      	  case key
      	    when Symbol; "#{to_prolog key}#{to_prolog val,'()'}"
      	    when Array ; "[#{to_prolog key,''}|#{to_prolog val,''}]"
      	    when true  ; "{#{to_prolog val}}"
      	    when nil   ; "#{val}"
      	  end
        when Array  ; "#{w[0]}#{(x.map(&method(:to_prolog)) * ',')}#{w[-1]}"
        when String ; %("#{x}")
        when Symbol ; x !~ /\A[[:lower:]]/ ? %('#{x}') : "#{x}"
        else        ; "#{x}"
      end
    end

    class << self
      extend Forwardable 

      delegate %i(to_prolog parse_to_a parse_one parse to_ruby) => :new

      def drb(uri=nil, *args)
        DRb.start_service (uri || DRB_URI), new(*args)
        DRb.thread.join
      end

      def daemon(*args)
        Process.daemon
        drb *args
      end
    end
  end

  class << self
    extend Forwardable 

    delegate %i(to_prolog parse_to_a parse_one parse to_ruby) => Parser
  end
end

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

  #
  # $ ruby prolog_parser.rb [options]
  #
  #   options are:
  #     -v        トークンキューをダンプ出力する
  #     -d        パーサデバッグコードを出力する
  #     --drb     デフォルト URI で druby サーバとして起動する
  #
  #     (以下は、druby サーバとして起動する場合に有効)
  #     --uri URI 指定の URI で druby サーバを起動する
  #     --daemon  druby サーバをデーモンにする
  #
  opt = OpenStruct.new ARGV.getopts 'vd', 'drb', 'daemon', 'uri:'
  str = ARGV.shift
  parser = Prolog::Parser.new.tap {|p| p.yydebug = opt.d ; p.verbose = opt.v }

  #
  # パーサへの入力ソースの指定の仕方 (同時に指定した場合、下の方が優先)
  #
  # parse メソッドに指定する方法
  #
  #   parser.parse(str) .......... 項(文字列、パーサで最後のピリオド(.)付加)
  #   parser.parse(term: str) .... (上と同じ)
  #   parser.parse(line: str) .... 行(文字列、最後のピリオド(.)必要)
  #   parser.parse(file: path) ... ファイル名(文字列)
  #   parser.parse(io: io) ....... read により入力文字列を読み出せる IO
  #   parser.parse(enum: enum) ... next により入力文字列を読み出せる Enumerator
  #   parser.parse(reader: pr) ... call により入力文字列を取得できる Proc
  #   parser.parse(&pr) .......... (上と同じ)
  #
  # アクセサで指定する方法
  #
  #   parser.term = str
  #   parser.line = str
  #   parser.file = path
  #   parser.io = io
  #   parser.enum = enum
  #   parser.reader = reader
  #
  #   parser.parse
  #
  #
  # (*) パーサでは、入力ソースを rewind することはない。
  #
  # ----
  #
  # parse の戻り値は、解析結果を出力する Enumerator である
  #
  # (I) ワンショット(解析結果を1回のみ取り出す)
  #
  #     (例)
  #        pp result = parser.parse(line: str).first
  #
  # (II) イテレート(解析結果を繰り返し取り出す)
  #
  #     (例)
  #        parser.parse(io: f).each {|result| pp result }
  #
  #        pp results = parser.parse(io: f).entries
  #
  # parse_to_a は、parse と機能は同じだが、戻り値は解析結果を格納した Array
  # parse_one は、parse と機能は同じだが、戻り値は最初の解析結果
  #

  if opt.drb
    Prolog::Parser.send(opt.daemon ? :daemon : :drb, opt.uri)
  else
    begin
      if str
        pp parser.parse(term: str).first
      else
        parser.parse(io: ARGF).each {|parsed| pp parsed }
      end
    rescue Racc::ParseError => e
      $stderr.puts e
    end
  end
end

Rakefile

require 'rake/testtask'

task:default => [:test]

desc 'Run test_unit based test'
Rake::TestTask.new do |t|
  t.libs << "test"
  t.test_files = Dir["test/**/test_*.rb"]
  t.verbose = true
end

ruby_vs_prolog.md

Ruby 上での Prolog の表現

Prolog	Ruby	Prolog側の例	Ruby側の例
述語	Hash (形式: {Symbol=>Array})	pred(a,b,10)	{pred: [:a,:b,10]}
リスト	Array	[a,b,10]、[]	[:a,:b,10]、[]
リスト(「H|T」形式)	Hash (形式: {Array=>Array})	[a,b|T]	{[:a,:b]=>[{nil=>:T}]}
リスト(文字列)	String	"abc"	"abc"
数値(整数)	Integer	1、-10	1、-10
数値(小数)	Float	1.1、-10.5	1.1、-10.5
アトム	Symbol	a、'ABC'	:a、:"ABC"
変数	Hash (形式: {nil=>Symbol})	X、_abc、_	{nil=>:X}、{nil=>:_abc}、{nil=>:_}
「{}」で囲まれた項	Hash (形式: {true=>項の表現})	{a(b,c)}	{true=>{:a=>[:b,:c]}}

test_prolog_parser.rb

#
# test/test/test_prolog_parser.rb
#
require 'test/unit'
require 'prolog_parser'

class TestPrologParser < Test::Unit::TestCase
  sub_test_case '項の構文解析' do
    test '整数' do
      assert_equal   1,  Prolog::Parser.new.parse(term: " 1").first
      assert_equal  -1,  Prolog::Parser.new.parse(term: "-1").first
      assert_equal  +1,  Prolog::Parser.new.parse(term: "+1").first
    end
    test '小数' do
      assert_equal   1.2,  Prolog::Parser.new.parse(term: " 1.2").first
      assert_equal  -1.2,  Prolog::Parser.new.parse(term: "-1.2").first
      assert_equal  +1.2,  Prolog::Parser.new.parse(term: "+1.2").first
    end
    test 'アトム' do
      assert_equal :abc,     Prolog::Parser.new.parse(term: "abc").first
      assert_equal :'a b',   Prolog::Parser.new.parse(term: "'a b'").first
      assert_equal :'!',     Prolog::Parser.new.parse(term: "!").first
      assert_equal :',',     Prolog::Parser.new.parse(term: ",").first
      assert_equal :'.',     Prolog::Parser.new.parse(term: ".").first
    end
    test '変数' do
      assert_equal({nil=>:X},    Prolog::Parser.new.parse(term: "X").first)
      assert_equal({nil=>:_a},   Prolog::Parser.new.parse(term: "_a").first)
      assert_equal({nil=>:_},    Prolog::Parser.new.parse(term: "_").first)
    end
    test '文字列' do
      assert_equal "abc",  Prolog::Parser.new.parse(term: '"abc"').first
      assert_equal "",     Prolog::Parser.new.parse(term: '""').first
    end
    test 'リスト' do
      assert_equal [:a,:b,10],    Prolog::Parser.new.parse(term:'[a,b,10]').first
      assert_equal [:a,:b,10],    Prolog::Parser.new.parse(term:'[a, b, 10]').first
      assert_equal [],            Prolog::Parser.new.parse(term:'[]').first
      assert_equal [:a,["a",10]], Prolog::Parser.new.parse(term:'[a,["a",10]]').first
      assert_equal({[:a,:b]=>[{nil=>:X}]},
                                  Prolog::Parser.new.parse(term:'[a,b|X]').first)
    end
    test '述語' do
      assert_equal({:a=>[:b,:c]},      Prolog::Parser.new.parse(term:'a(b,c)').first)
      assert_equal({:a=>[:b,:c]},      Prolog::Parser.new.parse(term:'a(b, c)').first)
      assert_equal({:','=>[:b,:c]},    Prolog::Parser.new.parse(term:',(b,c)').first)
      assert_equal({:~=>[:',',:',']},  Prolog::Parser.new.parse(term:'~(,,,)').first)
      assert_equal({:','=>[:',',:',']},Prolog::Parser.new.parse(term:',(,,,)').first)
      assert_equal({:+=>[1,2]},        Prolog::Parser.new.parse(term:'+(1,2)').first)
      assert_equal({:'.'=>[:a,:b]},    Prolog::Parser.new.parse(term:'.(a,b)').first)
    end
    test '節' do
      assert_equal(
        {:':-' => [
          {:a => [{nil=>:X}]},
          {:b => [:c]}
        ]},
        Prolog::Parser.new.parse(line:"a(X) :- b(c).").first)

      assert_equal(
        {:':-' => [
          {:a => [{nil=>:X}]},
          {:',' => [ {:b => [:c,10]}, :! ]}
        ]},
        Prolog::Parser.new.parse(line:"a(X) :- b(c,10),!.").first)

      assert_equal(
        {:":-" => [
          :a,
          {:"," => [ 
            :b,
            {:"," => [
              {:c => [:d]},
              :!
            ]}
          ]}
         ]},
         Prolog::Parser.new.parse(line:"a :- b,c(d),!.").first)

      assert_equal(
        {:":-" => [
          :a,
          {:"," => [ 
            {:"," => [
              :b,
              {:c => [:d]}
            ]},
            :!
          ]}
         ]},
         Prolog::Parser.new.parse(line:"a :- (b,c(d)),!.").first)

      assert_equal(
        {:is => [
          {nil => :X},
          {:+ => [1, 2]}
        ]},
        Prolog::Parser.new.parse(line:"X is 1 + 2.").first)

      assert_equal(
        {:',' => [ 
          {:is => [
            {nil => :X},
            {:+ => [1, 2]}
          ]},
          :!
        ]},
        Prolog::Parser.new.parse(line:"(X is 1 + 2),!.").first)

      assert_equal(
        {:',' => [ 
          {:is => [
            {nil => :X},
            {:+ => [1, 2]}
          ]},
          :!
        ]},
        Prolog::Parser.new.parse(line:"X is 1 + 2, !.").first)

      assert_equal(
        {:':-' => [
          {:f => [{nil=>:X},{nil=>:Y}]},
          {:',' => [
            {:is => [
              {nil => :X},
              {:+ => [{nil=>:Y},1]}
            ]},
            :!
          ]}
        ]},
        Prolog::Parser.new.parse(line:"f(X,Y) :- X is Y + 1,!.").first)

      assert_equal(
        {:is=>[{nil=>:X}, {:'+'=>[1, {:'*'=>[2, 3]}]}]},
        Prolog::Parser.new.parse(line:'X is 1 + 2 * 3.').first)

      assert_equal(
        {:is=>[{nil=>:X}, {:'+'=>[{:'*'=>[1, 2]}, 3]}]},
        Prolog::Parser.new.parse(line:'X is 1 * 2 + 3.').first)
    end
  end
end