Exploring Context Sensitive LSystem rules in ruby / ruby-processing

Warning the following code depends on ruby 1.9, where string index returns a char rather than an ascii value (ruby 1.8) see following post for how this tripped me up at first when exploring a proper ruby-processing example. (Update 5 March 2011)


######################################
# cs_grammar.rb a context sensitive
# 1-L lsystem grammar for
# ruby/ruby-processing
# by Martin Prout (1 March 2011)
######################################

#######################
# A helper class stores
# cs rules idx, and cchar
# methods extract cs data
#######################
class CSRule
  
  attr_accessor :pre, :crule
  
  def initialize pre, crule
    @pre, @crule = pre, crule
  end
  
  def idx
    x = 0
    if (pre[1] == "<")
      x -= 2
    end
    return x
  end
  
  def cchar
    return pre[0]
  end

end

##################################
# The grammar class stores rules
# in two Hashes, one for cs rules,
# one for context free rules. Rules
# are filtered on input, and context
# is checked using get_rule in production
##################################

class CSGrammar

  attr_reader :axiom, :context, :no_context, :idx
  def initialize(axiom)
    @axiom = axiom
    @no_context = Hash.new
    @context = Hash.new
  end
  
  def add_rule(pre, rule)
    case pre.length
      when 3
        @context.store(pre[2], CSRule.new(pre, rule)) # index, context, rule
      when 1
        @no_context.store pre, rule
      else print "unrecognized grammar '#{pre}'"  
    end
  end
  
  def generate(repeat = 0) # repeat iteration grammar rules
    prod = axiom
    repeat.times do
      prod = new_production(prod)
    end
    return prod
  end 
  
  
  def new_production prod  # single iteration grammar rules
    @idx = 0
    prod.gsub!(/./) do |ch|
      get_rule(prod, ch)
    end
  end
  
  def get_rule prod, ch
    rule = ch # default is return original character as rule (no change)
    @idx += 1 # increment the index of axiom/production as a side effect
    if (context.has_key?(ch)) && (prod[context[ch].idx + idx] == context[ch].cchar)
      rule = context[ch].crule  # use context sensitive rule
    else
      rule = no_context[ch] if no_context.has_key?(ch) # context free rule if it exists
    end
    return rule
  end
end

# Test data taken from ABOP

7.times do |i|
   grammar = CSGrammar.new("baaaaaa")
   grammar.add_rule("b<a", "b")  # context sensitive rule replace a when preceded by b
   grammar.add_rule("b", "a")
   result = grammar.generate(i)
   print result << "\n"
end

Test Output:

baaaaaa
abaaaaa
aabaaaa
aaabaaa
aaaabaa
aaaaaba
aaaaaab

Note the way b 'travels' from left to right through the production string in the test output.

Reference:

The Algorithmic Beauty of Plants

Przemyslaw Prusinkiewicz
Aristid Lindenmayer