Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Look-ahead table generator from non-empty deterministic grammar.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment