yacc.rb

## Yacc is dead - Ruby edition (recognizer only)
# Pretty much a direct port of the recognizer from:
#   http://matt.might.net/articles/parsing-with-derivatives/code/dparse.rkt
# 
# Requires 1.9
# gem install lazy

require 'lazy'
include Lazy::Methods

class Parser
  module Common
    def |(other)
      Union.new(self, Parser.token(other))
    end
  end
  
  Eps = Object.new
  Empty = Object.new
  def Eps.inspect() "Eps" end
  def Empty.inspect() "Empty" end

  Eps.extend Common
  Empty.extend Common
  Union = Struct.new(:left, :right) { include Common }
  Concat = Struct.new(:left, :right) { include Common }
  
  String.send(:include, Common)
  Lazy::Promise.send(:include, Common)
  
  class << self
    def token(rule)
      case rule
      when Lazy::Promise
        rule
      when Proc
        promise { rule.call }
      when Symbol
        promise { const_get(rule) }
      else
        rule
      end
    end
    
    def rule(*rules)
      case rules.size
      when 0
        Eps
      when 1
        token(rules.first)
      else
        (car, *cdr) = rules
        Concat.new(token(car), rule(*cdr))
      end
    end
    
    def nullable?(rule, cache = {})
      id = rule.__id__
      return cache[id] if cache.has_key?(id)
      cache[id] = false
      cache[id] = case rule
      when Empty, String
        false
      when Eps
        true
      when Union
        l1 = demand(rule.left)
        l2 = demand(rule.right)
        nullable?(l1, cache) || nullable?(l2, cache)
      when Concat
        l1 = demand(rule.left)
        l2 = demand(rule.right)
        nullable?(l1, cache) && nullable?(l2, cache)
      else
        p rule.class
        raise "Oh no!"
      end
    end
    
    def derive(char, rule, cache = {})
      id = rule.__id__
      cache[id] ||= case rule
      when Empty, Eps
        Empty
      when String
        (char == rule) ? Eps : Empty
      when Union
        l1 = demand(rule.left)
        l2 = demand(rule.right)
        
        left = -> { derive(char, l1, cache) }
        right = -> { derive(char, l2, cache) }
        token(left) | token(right)
      when Concat
        l1 = demand(rule.left)
        l2 = demand(rule.right)
        base = rule(-> { derive(char, l1, cache) }, l2)
        
        if nullable?(l1)
          left = -> { derive(char, l2, cache) }
          right = base
          token(left) | token(right)
        else
          base
        end
      end
    end
    
    def recognize?(str, rule, cache = {})
      nullable?(str.split(//).inject(rule) do |r, c|
        derive(c, r, cache)
      end)
    end
  end
  
  S =
    rule(:A, :S, "d") |
    rule(:B, :S) |
    rule
  
  A = rule("a") | rule("c")
  B = rule("a") | rule("b")
  
  p recognize?("aaaaaaaaaaaa", S)
  p recognize?("d", S)
  
  # Grammar for: N+N+N+N+N
  T =
    rule(:T, "+", :T) |
    rule("N")
    
  p recognize?("N+N+N+N", T)
  p recognize?("N+N+N++N", T)
end