Class: Antelope::Generation::Tableizer

Inherits:
Object
  • Object
show all
Defined in:
lib/antelope/generation/tableizer.rb

Overview

Constructs the table required for the parser.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(grammar) ⇒ Tableizer

Initialize.

Parameters:



29
30
31
 
# File 'lib/antelope/generation/tableizer.rb', line 29

def initialize(grammar)
  @grammar = grammar
end

Instance Attribute Details

#conflicts ⇒ Object (readonly)

Returns the value of attribute conflicts.



24
25
26
 
# File 'lib/antelope/generation/tableizer.rb', line 24

def conflicts
  @conflicts
end

#grammar ⇒ Grammar

The grammar that the table is based off of.

Returns:



12
13
14
 
# File 'lib/antelope/generation/tableizer.rb', line 12

def grammar
  @grammar
end

#rules ⇒ Hash<(Numeric, Recognizer::Rule)>

All rules in the grammar.

Returns:



22
23
24
 
# File 'lib/antelope/generation/tableizer.rb', line 22

def rules
  @rules
end

#table ⇒ Array<Hash<(Symbol, Array<(Symbol, Numeric)>)>>

The table itself.

Returns:

  • (Array<Hash<(Symbol, Array<(Symbol, Numeric)>)>>) 


17
18
19
 
# File 'lib/antelope/generation/tableizer.rb', line 17

def table
  @table
end

Instance Method Details

#call ⇒ void

This method returns an undefined value.

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

See Also:



38
39
40
41
42
 
# File 'lib/antelope/generation/tableizer.rb', line 38

def call
  tablize
  conflictize
  defaultize
end

#conflictize ⇒ void

This method returns an undefined value.

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.

Raises:



88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
 
# 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 ⇒ void

This method returns an undefined value.

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.



159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
 
# 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 ⇒ void

This method returns an undefined value.

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).



51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
# 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