derive.rb

class Parser
  def force; self end

  def |(other)
    DisjunctiveParser.new(self, other)
  end

  def >>(other)
    SequentialParser.new(self, other)
  end

  def recognize?(str)
    str.each_char.inject(self) do |parser, char|
      parser.derive(char).tap { |x| p x.size }
    end.nullable?
  end

  def size; 1 end
end

Eps = Parser.new
def Eps.nullable?; true end
def Eps.inspect(*); 'Eps' end
def Eps.derive(char); Empty end

Empty = Parser.new
def Empty.nullable?; false end
def Empty.inspect(*); 'Empty' end
def Empty.derive(char); Empty end

class CompoundParser < Parser
  def initialize(a, b)
    @a = a
    @b = b
    @derive = {}
    @nullable = nil
    @size = nil
  end

  def a; @a.force end
  def b; @b.force end

  def nullable?
    return @nullable unless @nullable.nil?
    @nullable = false
    @nullable = inner_nullable?
  end

  def derive(char)
    @derive[char] ||= inner_derive(char)
  end

  def size
    return @size unless @size.nil?
    @size = 0
    @size = a.size + b.size
  end
end

class SequentialParser < CompoundParser
  def inner_derive(char)
    base = lazy { a.derive(char) >> b }

    if a == Empty || b == Empty
      Empty
    elsif a.nullable?
      base | b.derive(char)
    else
      base
    end
  end

  def inner_nullable?
    a.nullable? && b.nullable?
  end
end

class DisjunctiveParser < CompoundParser
  def inner_derive(char)
    da = lazy { a.derive(char) }
    db = lazy { b.derive(char) }

    if a == Empty
      db
    elsif b == Empty
      da
    else
      da | db
    end
  end

  def inner_nullable?
    a.nullable? || b.nullable?
  end
end

class LiteralParser < Parser
  def initialize(str)
    @str = str
  end

  def nullable?; false end

  def derive(input)
    input == @str ? Eps : Empty
  end
end

def lit(s)
  LiteralParser.new(s)
end

class LazyParser < Parser
  def initialize(&blk) @blk = blk end

  def force; @parser ||= @blk.call end

  def recognize?(str) force.recognize?(str) end
  def derive(char) force.derive(char) end
  def nullable?; force.nullable? end
end

def lazy(&blk)
  LazyParser.new(&blk)
end

if $0 == __FILE__
  require 'minitest/autorun'

  class GLLTest < MiniTest::Unit::TestCase
    def test_literal
      a = lit("a")

      assert a.recognize?("a")
      refute a.recognize?("b")
    end

    def test_seq
      a = lit("a")
      b = lit("b")
      s = a >> b

      assert s.recognize?("ab")
    end

    def test_alt
      a = lit("a")
      b = lit("b")
      c = lit("c")
      s = a | b | c

      assert s.recognize?("a")
      assert s.recognize?("b")
      refute s.recognize?("d")
    end

    def test_seq_alt
      a = lit("a")
      b = lit("b")
      c = lit("c")
      s = a >> (b | c)
      
      assert s.recognize?("ab")
      assert s.recognize?("ac")
      refute s.recognize?("bc")
    end

    def test_parens
      s = lazy { lit("(") >> s >> lit(")") | lit("a") }
      assert s.recognize?("a")
      assert s.recognize?("(a)")
      assert s.recognize?("((a))")
      refute s.recognize?("(a))")
    end

    def test_big
      s = lazy { (s >> lit("+") >> s) | lit("1") }
      assert s.recognize?("1+1")
      refute s.recognize?("1++1")
      assert s.recognize?("1+" * 99 + "1")
      refute s.recognize?("1+" * 99 + "+1")
    end
  end

end