# How to write an Executable Grammar (Part II)
#
# Copyright (c) 2008, Adrian Kuhn akuhn()iam.unibe.ch
#
# http://www.iam.unibe.ch/~akuhn/blog/2008/04/executable-grammar-parser/ 
# http://www.iam.unibe.ch/~akuhn/blog/2008/04/executable-grammar-dsl/ 
# 

require 'strscan'
require 'test/unit'

# --- source code of part 1 ---

class Expression
  def initialize(regexp)
    @regexp = regexp
  end
  def match(input)
    save = input.pos
    input.skip_whitespace
    match = self.private_match(input)
    input.pos = save if match.nil?
    return match    
  end
  def private_match(input)
    input.scan @regexp
  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

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

class TestParser1 < 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

# --- source code of part 1 ---

class Expression
  attr_writer :omit
  def omit?
    @omit or false
  end
end

class Terminal < Expression
  def self.from_string(term) 
    self.new Regexp.new("^#{Regexp.escape(term)}")
  end
  def omit?
    @omit or true
  end
end

class Expression
  def to_expr
    self
  end
end

class String
  def to_expr
    Terminal.from_string(self)
  end
  def & expr
    self.to_expr & expr
  end
  def | expr
    self.to_expr | expr
  end
end 

class SequenceExpression
  def & expr
    @children << expr.to_expr; self
  end
end

class OrderedChoiceExpression
  def | expr
    @children << expr.to_expr; self
  end
end

class Parser < Expression
  attr_accessor :name, :expression, :semantics
  def initialize(name=nil, expression=nil)
    @name = name
    @expression = expression
    @semantics = lambda { |args| args }
  end
  def match(input)
    match = @expression.match(input)
    return if match.nil?
    @semantics.call(*match)
  end
end

class TestParser2 < Test::Unit::TestCase

  def test_add_source_codish
    number = Parser.new
    number.expression = Expression.new /(-)?\d+/
    number.semantics = lambda { |str| str.to_i }
    add = Parser.new
    add.expression = number & "+" & number
    add.semantics = lambda { |a, b| a + b }
    input = StringScanner.new "3 + 4"
    assert_equal 7, add.match(input)
  end

end

module Grammar
  def const_missing(symb)
    const_set symb, Parser.new(symb) 
  end
end

module Grammar
  def eos
    eos = Terminal.new nil
    def eos.private_match(input)
      input.eos? ? true : nil
    end
    eos
  end
  def number
    number = Parser.new
    number.expression = Expression.new /^\d+/
    number.semantics = lambda { |string| string.to_i }
    number
  end
end

class Parser
  def <= expr
    self.expression = expr
  end
  def do &lambda
    self.semantics = lambda
  end
end

module Grammar
  def =~ input
    self::Root.match StringScanner.new(input)
  end
end


class TestParser2 < Test::Unit::TestCase

  module Addition
    extend Grammar
    Root <= number & "+" & number
    Root.do { |a, b| a + b }
  end

  def test_add_source_codish
    assert_equal 7, Addition =~ "3 + 4"
  end
  
end

class SequenceExpression < Expression
  def private_match(input)
    matches = []
    @children.each { |expr| 
      match = expr.match input
      return if match.nil?
      matches << match unless expr.omit? 
    }
    matches
  end
end

class TestParser2 < Test::Unit::TestCase

  module Calculator
    extend Grammar
  
    Root    <= Sum & eos
    Sum     <= Add | Sub | Prod
    Add     <= Prod & '+' & Sum
    Sub     <= Prod & '-' & Sum
    Prod    <= Mult | Div | Atom
    Mult    <= Atom & '*' & Prod
    Div     <= Atom & '/' & Prod
    Atom    <= number | '(' & Sum & ')'
 
    Add.do    { |a, b| a + b }
    Sub.do    { |a, b| a - b }
    Mult.do   { |a, b| a * b }
    Div.do    { |a, b| a / b }
  
  end

  def test_calculator
    assert_equal 55, Calculator =~ "14 + 15 * 3 + 2 * (5 - 7)"   
  end
  
end