Class: Ibex::LALR::IELR::Annotator

Inherits:
Object
  • Object
show all
Defined in:
lib/ibex/lalr/ielr/annotator.rb,
sig/ibex/lalr/ielr/annotator.rbs

Overview

Finds grammar-relative inadequacies and traces their possible manifestations through predecessor states.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(grammar, states, transitions, items, goto_follows, resolver: nil) ⇒ Annotator

Returns a new instance of Annotator.

RBS:

  • (IR::Grammar grammar, Array[core_set] states, transitions transitions, Array[packed_items] items, GotoFollows goto_follows, ?resolver: ConflictResolver?) -> void

Parameters:



28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 28

def initialize(grammar, states, transitions, items, goto_follows, resolver: nil)
  @grammar = grammar
  @states = states
  @transitions = transitions
  @items = items
  @goto_follows = goto_follows
  @resolver = resolver || ConflictResolver.new(grammar)
  @kernel_cores = states.map { |state| kernel_items(state) }
  @item_lookaheads = ItemLookaheads.new(
    grammar, goto_follows, @kernel_cores, goto_follows.predecessors,
    start_states: (0...grammar.starts.length).to_a
  )
  @annotation_lists = Array.new(states.length) { [] }
  @keys = Array.new(states.length) { Set.new }
  @inadequacies = Array.new(states.length) { [] }
  @next_id = 0
  @split_stable_discarded = 0
end

Instance Attribute Details

#annotation_lists ⇒ Array[Array[Annotation]] (readonly)

Signature:

  • Array[Array[Annotation]]

Returns:



21
22
23
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 21

def annotation_lists
  @annotation_lists
end

#inadequacies ⇒ Array[Array[Inadequacy]] (readonly)

Signature:

  • Array[Array[Inadequacy]]

Returns:



22
23
24
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 22

def inadequacies
  @inadequacies
end

#item_lookaheads ⇒ ItemLookaheads (readonly)

Signature:

  • ItemLookaheads

Returns:



23
24
25
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 23

def item_lookaheads
  @item_lookaheads
end

#split_stable_discarded ⇒ Integer (readonly)

Signature:

  • Integer

Returns:

  • (Integer) 


24
25
26
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 24

def split_stable_discarded
  @split_stable_discarded
end

Instance Method Details

#always_via_lhs?(state_id, cores, row, token) ⇒ Boolean

RBS:

  • (Integer state_id, Array[item_core], Integer, Integer) -> bool

Parameters:

  • state_id (Integer)
  • (Array[item_core])
  • (Integer)
  • (Integer)

Returns:

  • (Boolean) 


127
128
129
130
131
132
133
134
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 127

def always_via_lhs?(state_id, cores, row, token)
  Bits.each_set_bit(row).any? do |index|
    production_id, dot = cores.fetch(index)
    next false unless dot == 1

    compute_lhs_contributions(state_id, lhs_for(production_id), token).nil?
  end
end

#annotate_manifestation(state_id, inadequacy) ⇒ Annotation

RBS:

  • (Integer state_id, Inadequacy inadequacy) -> Annotation

Parameters:

Returns:



99
100
101
102
103
104
105
106
107
108
109
110
111
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 99

def annotate_manifestation(state_id, inadequacy)
  matrix = inadequacy.contributions.map do |kind, production_id|
    next nil if kind == :shift

    rhs = rhs_for(production_id)
    if rhs.empty?
      compute_lhs_contributions(state_id, lhs_for(production_id), inadequacy.token)
    else
      completed_kernel_mask(state_id, production_id, rhs.length)
    end
  end
  Annotation.new(inadequacy: inadequacy, matrix: matrix)
end

#annotate_predecessor(state_id, successor_id, annotation) ⇒ Annotation

RBS:

  • (Integer state_id, Integer successor_id, Annotation annotation) -> Annotation

Parameters:

  • state_id (Integer)
  • successor_id (Integer)
  • annotation (Annotation)

Returns:



114
115
116
117
118
119
120
121
122
123
124
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 114

def annotate_predecessor(state_id, successor_id, annotation)
  token = annotation.inadequacy.token
  cores = @kernel_cores.fetch(successor_id)
  matrix = annotation.matrix.map do |row|
    next nil if row.nil?
    next nil if always_via_lhs?(state_id, cores, row, token)

    project_row(state_id, cores, row, token)
  end
  Annotation.new(inadequacy: annotation.inadequacy, matrix: matrix)
end

#build ⇒ Array[Array[Annotation]]

RBS:

  • () -> Array[Array[Annotation]]

Returns:



48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 48

def build
  @states.each_index do |state_id|
    @inadequacies[state_id] = build_inadequacies(state_id)
    @inadequacies.fetch(state_id).each do |inadequacy|
      register?(state_id, annotate_manifestation(state_id, inadequacy))
    end
  end
  worklist = @annotation_lists.each_with_index.flat_map do |annotations, state_id|
    annotations.map { |annotation| [state_id, annotation] }
  end
  cursor = 0
  while cursor < worklist.length
    state_id, annotation = worklist.fetch(cursor)
    cursor += 1
    @goto_follows.predecessors.fetch(state_id).each do |previous|
      derived = annotate_predecessor(previous, state_id, annotation)
      worklist << [previous, derived] if register?(previous, derived)
    end
  end
  @annotation_lists
end

#build_inadequacies(state_id) ⇒ Array[Inadequacy]

RBS:

  • (Integer state_id) -> Array[Inadequacy]

Parameters:

  • state_id (Integer)

Returns:



73
74
75
76
77
78
79
80
81
82
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 73

def build_inadequacies(state_id)
  @grammar.terminals.filter_map do |terminal|
    contributions = contributions_for(state_id, terminal.id)
    next if contributions.length < 2

    inadequacy = Inadequacy.new(state: state_id, token: terminal.id, contributions: contributions, id: @next_id)
    @next_id += 1
    inadequacy
  end
end

#completed_kernel_mask(state_id, production_id, length) ⇒ Integer

RBS:

  • (Integer state_id, Integer production_id, Integer length) -> Integer

Parameters:

  • state_id (Integer)
  • production_id (Integer)
  • length (Integer)

Returns:

  • (Integer) 


153
154
155
156
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 153

def completed_kernel_mask(state_id, production_id, length)
  index = kernel_index_of(state_id, production_id, length)
  index ? (1 << index) : 0
end

#compute_lhs_contributions(state_id, lhs_id, token_id) ⇒ Integer?

RBS:

  • (Integer state_id, Integer lhs_id, Integer token_id) -> Integer?

Parameters:

  • state_id (Integer)
  • lhs_id (Integer)
  • token_id (Integer)

Returns:

  • (Integer, nil) 


159
160
161
162
163
164
165
166
167
168
169
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 159

def compute_lhs_contributions(state_id, lhs_id, token_id)
  goto_id = @goto_follows.goto_for(state_id, lhs_id)
  raise Ibex::Error, "missing goto for #{lhs_id} from #{state_id}" unless goto_id
  return nil if @goto_follows.always_follows.fetch(goto_id).anybits?(1 << token_id)

  mask = 0
  Bits.each_set_bit(@goto_follows.follow_kernel_items.fetch(goto_id)) do |index|
    mask |= 1 << index if @item_lookaheads.fetch(state_id, index).anybits?(1 << token_id)
  end
  mask
end

#contributions_for(state_id, token_id) ⇒ Array[[ Symbol, Integer? ]]

RBS:

  • (Integer state_id, Integer token_id) -> Array[[Symbol, Integer?]]

Parameters:

  • state_id (Integer)
  • token_id (Integer)

Returns:

  • (Array[[ Symbol, Integer? ]]) 


85
86
87
88
89
90
91
92
93
94
95
96
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 85

def contributions_for(state_id, token_id)
  reductions = @items.fetch(state_id).filter_map do |(production_id, dot), lookaheads|
    next unless dot == rhs_for(production_id).length && lookaheads.include?(token_id)

    production_id
  end.sort
  contributions = reductions.select(&:negative?).map { |production_id| [:accept, production_id] }
  symbol = @grammar.symbol_by_id(token_id)
  contributions << [:shift, nil] if symbol&.terminal? && @transitions.fetch(state_id).key?(token_id)
  contributions.concat(reductions.reject(&:negative?).map { |production_id| [:reduce, production_id] })
  contributions
end

#kernel_index_of(state_id, production_id, dot) ⇒ Integer?

RBS:

  • (Integer state_id, Integer production_id, Integer dot) -> Integer?

Parameters:

  • state_id (Integer)
  • production_id (Integer)
  • dot (Integer)

Returns:

  • (Integer, nil) 


205
206
207
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 205

def kernel_index_of(state_id, production_id, dot)
  @kernel_cores.fetch(state_id).index([production_id, dot])
end

#kernel_items(items) ⇒ Array[item_core]

RBS:

  • (core_set items) -> Array[item_core]

Parameters:

  • items (core_set)

Returns:

  • (Array[item_core]) 


200
201
202
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 200

def kernel_items(items)
  items.select { |production_id, dot| production_id.negative? || dot.positive? }.to_a.sort
end

#lhs_for(production_id) ⇒ Integer

RBS:

  • (Integer state_id, Integer production_id) -> Integer

Parameters:

  • state_id (Integer)
  • production_id (Integer)

Returns:

  • (Integer) 


186
187
188
189
190
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 186

def lhs_for(production_id)
  return @grammar.symbol(@grammar.starts.fetch(-production_id - 1)).id if production_id.negative?

  @grammar.productions.fetch(production_id).lhs
end

#project_row(state_id, cores, row, token) ⇒ Integer

RBS:

  • (Integer state_id, Array[item_core], Integer, Integer) -> Integer

Parameters:

  • state_id (Integer)
  • (Array[item_core])
  • (Integer)
  • (Integer)

Returns:

  • (Integer) 


137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 137

def project_row(state_id, cores, row, token)
  Bits.each_set_bit(row).reduce(0) do |mask, index|
    production_id, dot = cores.fetch(index)
    if dot > 1
      previous = kernel_index_of(state_id, production_id, dot - 1)
      next mask unless previous && item_lookaheads.fetch(state_id, previous).anybits?(1 << token)

      mask | (1 << previous)
    else
      lhs_mask = compute_lhs_contributions(state_id, lhs_for(production_id), token)
      mask | lhs_mask.to_i
    end
  end
end

#register?(state_id, annotation) ⇒ Boolean

RBS:

  • (Integer state_id, Annotation annotation) -> bool

Parameters:

Returns:

  • (Boolean) 


172
173
174
175
176
177
178
179
180
181
182
183
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 172

def register?(state_id, annotation)
  if SplitStability.split_stable?(annotation, @resolver)
    @split_stable_discarded += 1
    return false
  end

  key = annotation.key
  return false unless @keys.fetch(state_id).add?(key)

  @annotation_lists.fetch(state_id) << annotation
  true
end

#rhs_for(production_id) ⇒ Array[Integer]

RBS:

  • (Integer production_id) -> Array[Integer]

Parameters:

  • production_id (Integer)

Returns:

  • (Array[Integer]) 


193
194
195
196
197
 
# File 'lib/ibex/lalr/ielr/annotator.rb', line 193

def rhs_for(production_id)
  return [lhs_for(production_id)] if production_id.negative?

  @grammar.productions.fetch(production_id).rhs
end