=begin
Context-Free Grammar - Sentences Generator
=end

class ContextFreeGrammar
  attr_reader :nonterminal_list, :terminal_list, :conv_rule_map, :start_symbol

  def initialize
    @nonterminal_list = []
    @terminal_list = []
    @conv_rule_map = {}
    @start_symbol = nil
  end
    
  def add_nonterminal(symbol)
    @nonterminal_list << symbol
    
    self
  end
  
  def add_terminal(symbol)
    @terminal_list << symbol
    
    self
  end
  
  def add_conv_rule(conversion_rule)
    #@conv_rule_list << conversion_rule
    
    rule_list = @conv_rule_map[conversion_rule.lhs]
    
    if !rule_list
      rule_list = []
      rule_list << conversion_rule
      @conv_rule_map[conversion_rule.lhs] = rule_list
    else
      rule_list << conversion_rule
    end
    
    self
  end
  
  def add_conv_rule_directly(lhs, rhs)
    cfg_conv_rule = ConversionRule.new
    cfg_conv_rule.set_lhs(lhs).set_rhs(rhs)
    
    add_conv_rule(cfg_conv_rule)
    
    self
  end
  
  def set_start_symbol(symbol)
    return nil if !(@nonterminal_list.include?(symbol))
    
    @start_symbol = symbol
    
    self
  end
  
end

class ContextFreeGrammar
  class ConversionRule
    attr_reader :lhs, :rhs

    def initialize
      @lhs = nil
      @rhs = nil
    end

    def set_lhs(lhs_symbol)
      @lhs = lhs_symbol
      
      self
    end

    def set_rhs(rhs_string)
      @rhs = rhs_string
      
      self
    end
  end
end

class ContextFreeGrammar
  def print_all_sentences(cutoff_depth) #(count)
    puts "=> Printing 'All Sentences' using DFS & Depth-cutoff"
    print_all_sentences_using_dfs(@start_symbol, cutoff_depth)
    
    puts "=> Printing 'All Sentences' using BFS & Depth-cutoff"
    print_all_sentences_using_bfs(@start_symbol, cutoff_depth)
  end
  
  def print_all_sentences_using_bfs(sentential_form, cutoff_depth)
    queue = [[sentential_form, 0]]
    
    while queue.length > 0
      sentential_form, curr_depth = queue.shift
      
      next if cutoff_depth < curr_depth
      
      nonterminal_idx = find_first_nonterminal_index(sentential_form)

      if -1 == nonterminal_idx
        puts sentential_form
        next
      end
      
      ch = sentential_form[nonterminal_idx].chr

      rule_list = @conv_rule_map[ch.to_s]

      # error if @conv_rule_map is nil

      rule_list.each do |rule|
        new_sentential_form = sentential_form.clone

        new_sentential_form[nonterminal_idx] = rule.rhs

        queue << [new_sentential_form, curr_depth + 1]
      end
    end
    
  end

  def print_all_sentences_using_dfs(sentential_form, cutoff_depth)
    stack = [[sentential_form, 0]]
    
    while stack.length > 0
      sentential_form, curr_depth = stack.pop
      
      next if cutoff_depth < curr_depth
      
      nonterminal_idx = find_first_nonterminal_index(sentential_form)

      if -1 == nonterminal_idx
        puts sentential_form
        next
      end
      
      ch = sentential_form[nonterminal_idx].chr

      rule_list = @conv_rule_map[ch.to_s]

      # error if @conv_rule_map is nil

      rule_list.reverse_each do |rule|
        new_sentential_form = sentential_form.clone

        new_sentential_form[nonterminal_idx] = rule.rhs

        stack.push([new_sentential_form, curr_depth + 1])
      end
    end
    
  end
  
  def find_first_nonterminal_index(sentential_form)
    (0...sentential_form.length).each do |idx|
      ch = sentential_form[idx].chr
      
      @nonterminal_list.each do |nonterminal|
        return idx if nonterminal == ch
      end
    end
    
    -1
  end
end

def generate_cfg_ex1
=begin
  # ex 1
  G=({S, A}, {a, b, c, d}, P, S)

  P: S -> abA | a
     A -> cA | d
=end

  cfg_obj = ContextFreeGrammar.new
  cfg_obj.add_nonterminal('S').add_nonterminal('A')
  cfg_obj.add_terminal('a').add_terminal('b').add_terminal('c').add_terminal('d')
  cfg_obj.set_start_symbol('S')

  cfg_obj.add_conv_rule_directly('S', 'abA')
  cfg_obj.add_conv_rule_directly('S', 'a')
  cfg_obj.add_conv_rule_directly('A', 'cA')
  cfg_obj.add_conv_rule_directly('A', 'd')

  cfg_obj
end

def generate_cfg_ex2
=begin
  # ex 2
  G = ({S,A}, {a,b}, P, S)
  
  P: S -> aAS | a
     A -> SbA | ba | SS
=end
  
  cfg_obj = ContextFreeGrammar.new
  cfg_obj.add_nonterminal('S').add_nonterminal('A')
  cfg_obj.add_terminal('a').add_terminal('b')
  cfg_obj.set_start_symbol('S')
  cfg_obj.add_conv_rule_directly('S', 'aAS')
  cfg_obj.add_conv_rule_directly('S', 'a')
  cfg_obj.add_conv_rule_directly('A', 'SbA')
  cfg_obj.add_conv_rule_directly('A', 'ba')
  cfg_obj.add_conv_rule_directly('A', 'SS')
  
  cfg_obj
end

cfg_obj = generate_cfg_ex2
cfg_obj.print_all_sentences(5)

=> Printing 'All Sentences' using DFS & Depth-cutoff
aabbaa
abaabaa
abaa
aaaa
a
=> Printing 'All Sentences' using BFS & Depth-cutoff
a
abaa
aabbaa
abaabaa
aaaa