Look-ahead table generator from non-empty deterministic grammar.

look_ahead_lookup_table.rb

require 'pp'

class RuleOption
  attr_accessor :parts

  def initialize(*parts)
    @parts = parts
  end 
end

class Rule
  attr_accessor :options

  def initialize(*options)
    @options = options
  end
end

class LookupGroup
  attr_accessor :idx, :tokens

  def initialize(idx = -1, *tokens)
    @idx = idx
    @tokens = tokens
  end
end

class Lookup
  attr_accessor :rule, :groups

  def initialize(rule, *groups)
    @rule = rule
    @groups = groups
  end
end

def terminal?(token)
  /^T_/ =~ token
end

def discover(rule_name, idx, grammar, limit)
  parts = [[]]

  grammar[rule_name].options[idx].parts.each do |part|
    next if !parts.empty? && parts.all? { |_part| _part.count >= limit }

    if terminal?(part)
      parts.map! { |e| e.count >= limit ? e : e + [part] }
    else
      new_parts = []
      grammar[part].options.each_with_index do |option, _idx|
        min_seq_length = parts.empty? ? 0 : parts.min { |a, b| a.count <=> b.count }.count
        reachables = discover(part, _idx, grammar, limit - min_seq_length)
        new_parts += parts.flat_map do |_part|
          reachables.map { |reachable| (_part + reachable).slice(0, limit) }
        end
      end
      parts = new_parts.uniq
    end
  end

  parts
end

grammar = {
  'PROG' => Rule.new(
    RuleOption.new('STMT', 'T_EOP'),
  ),
  'STMT' => Rule.new(
    RuleOption.new('EXP'),
    RuleOption.new('FN'),
    RuleOption.new('CMD', 'CMD_END'),
  ),
  'CMD' => Rule.new(
    RuleOption.new('T_KWD'),
    RuleOption.new(),
  ),
  'CMD_END' => Rule.new(
    RuleOption.new('T_CMD_END'),
  ),
  'FN' => Rule.new(
    RuleOption.new('T_NAME', 'EXP')
  ),
  'EXP' => Rule.new(
    RuleOption.new('VAL', 'OP', 'EXP'),
    RuleOption.new('VAL'),
  ),
  'VAL' => Rule.new(
    RuleOption.new('T_NUM'),
    RuleOption.new('T_STR'),
  ),
  'OP' => Rule.new(
    RuleOption.new('T_SUB'),
    RuleOption.new('T_ADD'),
  ),
}

lookups = []

grammar.each do |rule_name, rule|
  lookup = Lookup.new(rule_name)

  rule.options.each_with_index do |option, idx|
    lookup_group = LookupGroup.new(idx)
    lookup_group.tokens = discover(rule_name, idx, grammar, 1)

    lookup.groups << lookup_group
  end

  lookups << lookup
end

pp lookups