racc_trie.rb

require 'racc'
require 'racc/grammarfileparser'
require 'set'

class Trie
  Entry = Struct.new(:keys, :value)

  def initialize
    @tokens = Set.new
    @sentences = []
  end

  def to_yacc
    tokens = @tokens.map { |t| "token #{t}" }.join("\n")
    rules = @sentences.map { |s| "main: #{s.keys.join(' ')} { result = #{s.value.inspect} }" }.join("\n")

    grammar = <<-RACC
class GeneratedGrammar
#{tokens}

rule
#{rules}
end

---- inner
def initialize
  @ary = @len = @i = nil
end

def parse(ary)
  @ary = ary
  @len = ary.length
  @i = 0
  do_parse
end

def next_token
  return if @i == @len
  token = @ary[@i].to_sym
  @i += 1
  [token, token]
end
    RACC

    # warn "############# GENERATED GRAMMAR"
    # warn grammar
    # warn "############# END GENERATED GRAMMAR"

    grammar
  end

  def to_parser
    parser     = Racc::GrammarFileParser.new
    result     = parser.parse(to_yacc)
    nfa        = Racc::States.new(result.grammar).nfa
    parsegen   = Racc::ParserFileGenerator.new(nfa.dfa, result.params)
    parser_src = parsegen.generate_parser

    # warn "############# PARSED GRAMMAR"
    # warn parser_src
    # warn "############# END PARSED GRAMMAR"

    Module.new { class_eval parser_src }.const_get('GeneratedGrammar')
  end

  def [](*keys)
    @parser ||= to_parser.new
    @parser.parse(keys)
  rescue Racc::ParseError
    nil
  end

  def []=(*keys)
    value = keys.pop
    keys.each { |k| @tokens << k }
    @sentences << Entry.new(keys, value)
  end
end

t = Trie.new
t['foo', 'bar'] = 'baz'
puts t['foo', 'bar']