# How to write an Executable Grammer (Part I)
#
# Copyright (c) 2008, Adrian Kuhn <akuhn (at) iam (dot) unibe (dot) ch>
#
# http://www.iam.unibe.ch/~akuhn/blog/2008/04/executable-grammar-parser/ 
# 


class Expression
  def initialize(regexp)
    @regexp = regexp
  end
  def match(input)
    input.scan @regexp
  end
end

require 'strscan'

input = StringScanner.new "raining cats cats dogs cats"
grammar = Expression.new /raining/
p grammar.match(input)


class Expression
  alias :private_match :match
  def match(input)
    save = input.pos
    input.skip_whitespace
    match = self.private_match(input)
    input.pos = save if match.nil?
    return match    
  end
end

class StringScanner
  def skip_whitespace
    self.skip /\s+/
  end
end

class SequenceExpression < Expression
  def initialize
    @children = []
  end
  def & expr
    @children << expr; self
  end
  def private_match(input)
    @children.collect { |expr| 
      match = expr.match input
      return if match.nil?
      match 
    }
  end
end

class OrderedChoiceExpression < Expression
  def initialize
    @children = []
  end
  def | expr
    @children << expr; self
  end
  def private_match(input)
    @children.each { |expr| 
      match = expr.match input
      return match if not match.nil?
    }
    return nil
  end
end

class RepetitionExpression < Expression
  def initialize(expression)
    @child = expression
  end
  def private_match(input)
    matches = []
    while match = @child.match(input)
      matches << match 
    end
    return matches
  end
end

class Expression
  def & expr
    SequenceExpression.new & self & expr
  end
  def | expr
    OrderedChoiceExpression.new | self | expr
  end
  def star
    RepetitionExpression.new self
  end
end

input = StringScanner.new("raining cats cats dogs cats")
raining = Expression.new /raining/
cats = Expression.new /cats/
dogs = Expression.new /dogs/
grammar = raining & (dogs | cats).star
p grammar.match(input)

class OneOreMoreExpression < RepetitionExpression
  def private_match(input)
    match = super(input)
    return if match.empty?
    match
  end
end

class ZeroOrOneExpression < RepetitionExpression
  def private_match(input)
    match = @child.match(input)
    return true if match.nil?
    match
  end
end

class AndPredicate < RepetitionExpression
  def private_match(context)
    save = context.string
    match = @child.match(context)
    context.string = save
    return true if not match.nil?
    nil
  end
end

class NotPredicate < RepetitionExpression
  def private_match(context)
    save = context.string
    match = @child.match(context)
    context.string = save
    return true if match.nil?
    nil
  end
end

class Expression
  def plus
    OneOreMoreExpression.new self
  end
  def mark
    ZeroOrOneExpression.new self
  end
  def +@ 
    AndPredicate.new self
  end
  def -@
    NotPredicate.new self
  end
end

require 'test/unit'

class TestParser < Test::Unit::TestCase

  def test_sequence
    aaa = Expression.new /aaa/
    grammar = aaa & aaa
    input = StringScanner.new("aaa aaa aaa bbb")
    assert_equal ["aaa"] * 2, grammar.match(input)
    assert_equal 7, input.pos
    input = StringScanner.new("aaa bbb")
    assert_equal nil, grammar.match(input)
    assert_equal 0, input.pos
    input = StringScanner.new("bbb")
    assert_equal nil, grammar.match(input)
    assert_equal 0, input.pos
  end

  def test_choice
    aaa = Expression.new /aaa/
    bbb = Expression.new /bbb/
    grammar = aaa | bbb
    input = StringScanner.new("aaa aaa aaa bbb")
    assert_equal "aaa", grammar.match(input)
    assert_equal 3, input.pos
    input = StringScanner.new("aaa bbb")
    assert_equal "aaa", grammar.match(input)
    assert_equal 3, input.pos
    input = StringScanner.new("bbb")
    assert_equal "bbb", grammar.match(input)
    assert_equal 3, input.pos
  end

  def test_star
    aaa = Expression.new /aaa/
    grammar = aaa.star
    input = StringScanner.new("aaa aaa aaa bbb")
    assert_equal ["aaa"] * 3, grammar.match(input)
    assert_equal 11, input.pos
    input = StringScanner.new("aaa bbb")
    assert_equal ["aaa"] * 1, grammar.match(input)
    assert_equal 3, input.pos
    input = StringScanner.new("bbb")
    assert_equal [], grammar.match(input)
    assert_equal 0, input.pos
  end

  def test_plus
    aaa = Expression.new /aaa/
    grammar = aaa.plus
    input = StringScanner.new("aaa aaa aaa bbb")
    assert_equal ["aaa"] * 3, grammar.match(input)
    assert_equal 11, input.pos
    input = StringScanner.new("aaa bbb")
    assert_equal ["aaa"] * 1, grammar.match(input)
    assert_equal 3, input.pos
    input = StringScanner.new("bbb")
    assert_equal nil, grammar.match(input)
    assert_equal 0, input.pos
  end
  
  def test_mark
    aaa = Expression.new /aaa/
    grammar = aaa.mark
    input = StringScanner.new("aaa aaa aaa bbb")
    assert_equal "aaa", grammar.match(input)
    assert_equal 3, input.pos
    input = StringScanner.new("aaa bbb")
    assert_equal "aaa", grammar.match(input)
    assert_equal 3, input.pos
    input = StringScanner.new("bbb")
    assert_equal true, grammar.match(input)
    assert_equal 0, input.pos
  end

  def test_and
    aaa = Expression.new /aaa/
    grammar = +aaa
    input = StringScanner.new("aaa aaa aaa bbb")
    assert_equal true, grammar.match(input)
    assert_equal 0, input.pos
    input = StringScanner.new("aaa bbb")
    assert_equal true, grammar.match(input)
    assert_equal 0, input.pos
    input = StringScanner.new("bbb")
    assert_equal nil, grammar.match(input)
    assert_equal 0, input.pos
  end

  def test_not
    aaa = Expression.new /aaa/
    grammar = -aaa
    input = StringScanner.new("aaa aaa aaa bbb")
    assert_equal nil, grammar.match(input)
    assert_equal 0, input.pos
    input = StringScanner.new("aaa bbb")
    assert_equal nil, grammar.match(input)
    assert_equal 0, input.pos
    input = StringScanner.new("bbb")
    assert_equal true, grammar.match(input)
    assert_equal 0, input.pos
  end
  
end