class Antelope::Generation::Tableizer

Constructs the table required for the parser.

Attributes

conflicts[R]
grammar[RW]

The grammar that the table is based off of.

@return [Grammar]

rules[RW]

All rules in the grammar.

@return [Hash<(Numeric, Recognizer::Rule)>]

table[RW]

The table itself.

@return [Array<Hash<(Symbol, Array<(Symbol, Numeric)>)>>]

Public Class Methods

new(grammar) click to toggle source

Initialize.

@param grammar [Grammar]

# File lib/antelope/generation/tableizer.rb, line 29
def initialize(grammar)
  @grammar = grammar
end

Public Instance Methods

call() click to toggle source

Construct the table, and then check the table for conflicts.

@return [void] @see tablize @see conflictize

# File lib/antelope/generation/tableizer.rb, line 38
def call
  tablize
  conflictize
  defaultize
end
conflictize() click to toggle source

Resolve any conflicts through precedence, if we can. If we can’t, let the user know. This makes sure that every value of the hashes is a single array.

@raise [UnresolvableConflictError] if a conflict could not be

resolved using precedence rules.

@return [void]

# File lib/antelope/generation/tableizer.rb, line 88
def conflictize
  states = grammar.states.to_a.sort_by(&:id)
  @conflicts = Hash.new { |h, k| h[k] = {} }
  @table.each_with_index do |v, state|
    v.each do |on, data|
      if data.size == 1
        @table[state][on] = data[0]
        next
      end

      terminal = if states[state].transitions.key?(on)
        states[state].rules.
          detect { |rule| rule.active.name == on }.precedence
      end
      rule_part, other_part = data.sort_by { |(t, _)| t }

      conflict = proc do |result|
        hash = { result: result,
                 terminal: terminal,
                 prec: @rules[rule_part[1]].prec,
                 data: data,
                 rules: [], transitions: [] }

        hash[:rules].concat(data.select { |part|
            part[0] == :reduce || part[0] == :accept
          }.map { |(_, id)|
            states[state].rules.select(&:final?).
              detect { |rule| rule.production.id == id }
          })
        hash[:transitions].concat(data.select { |part|
            part[0] == :state
          }.map { |_|
            states[state].rules.
              detect { |rule| rule.active.name == on }
          })

        conflicts[state][on] = hash
      end

      unless other_part[0] == :state
        conflict.call(0)
        $stderr.puts \
          "Could not determine move for #{on} in state " \
          "#{state} (reduce/reduce conflict)"
        next
      end

      result = @rules[rule_part[1]].prec <=> terminal
      conflict.call(result)

      case result
      when 0
        @table[state][on] = nil
        $stderr.puts \
          "Could not determine move for #{on} in state " \
          "#{state} (shift/reduce conflict)"
      when 1
        @table[state][on] = rule_part
      when -1
        @table[state][on] = other_part
      end
    end
  end
end
defaultize() click to toggle source

Reduce many transitions into a single ‘$default` transition. This only works if there is no `$empty` transition; if there is an `$empty` transition, then the `$default` transition is set to be the `$empty` transition.

@return [void]

# File lib/antelope/generation/tableizer.rb, line 159
def defaultize
  max = @table.map { |s| s.keys.size }.max
  @table.each_with_index do |state|
    common = state.group_by { |k, v| v }.values.
      sort_by(&:size).first

    if common.size > (max / 2)
      action = common[0][1]

      keys = common.map(&:first)
      state.delete_if { |k, _| keys.include?(k) }
      state[:$default] = action
    end
  end
end
tablize() click to toggle source

Construct a table based on the grammar. The table itself is an array whose elements are hashes; the index of the array corresponds to the state ID, and the keys of the hashes correspond to acceptable tokens. The values of the hashes should be an array of arrays (at this point).

@return [void]

# File lib/antelope/generation/tableizer.rb, line 51
def tablize
  @table = Array.new(grammar.states.size) do
    Hash.new { |h, k| h[k] = [] }
  end
  @rules = []

  grammar.states.each do |state|
    state.transitions.each do |on, to|
      table[state.id][on] << [:state, to.id]
    end

    state.rules.each do |rule|
      @rules[rule.production.id] = rule.production
      if rule.final?
        rule.lookahead.each do |look|
          table[state.id][look.name] <<
            [:reduce, rule.production.id]
        end

        if rule.production.id.zero?
          table[state.id][:$end] =
            [[:accept, rule.production.id]]
        end
      end
    end
  end

  table
end