######################################
# 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
No comments:
Post a Comment