Class: Lrama::States

Inherits:
Object
  • Object
show all
Extended by:
Forwardable
Includes:
Tracer::Duration
Defined in:
lib/lrama/states.rb

Overview

States is passed to a template file

"Efficient Computation of LALR(1) Look-Ahead Sets" https://dl.acm.org/doi/pdf/10.1145/69622.357187

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Tracer::Duration

enable, enabled?, #report_duration

Constructor Details

#initialize(grammar, tracer) ⇒ States

Returns a new instance of States.



47
48
49
50
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/lrama/states.rb', line 47

def initialize(grammar, tracer)
  @grammar = grammar
  @tracer = tracer

  @states = []

  # `DR(p, A) = {t ∈ T | p -(A)-> r -(t)-> }`
  #   where p is state, A is nterm, t is term.
  #
  # `@direct_read_sets` is a hash whose
  # key is goto,
  # value is bitmap of term.
  @direct_read_sets = {}

  # Reads relation on nonterminal transitions (pair of state and nterm)
  # `(p, A) reads (r, C) iff p -(A)-> r -(C)-> and C =>* ε`
  #   where p, r are state, A, C are nterm.
  #
  # `@reads_relation` is a hash whose
  # key is goto,
  # value is array of goto.
  @reads_relation = {}

  # `Read(p, A) =s DR(p, A) ∪ ∪{Read(r, C) | (p, A) reads (r, C)}`
  #
  # `@read_sets` is a hash whose
  # key is goto,
  # value is bitmap of term.
  @read_sets = {}

  # `(p, A) includes (p', B) iff B -> βAγ, γ =>* ε, p' -(β)-> p`
  #   where p, p' are state, A, B are nterm, β, γ is sequence of symbol.
  #
  # `@includes_relation` is a hash whose
  # key is goto,
  # value is array of goto.
  @includes_relation = {}

  # `(q, A -> ω) lookback (p, A) iff p -(ω)-> q`
  #   where p, q are state, A -> ω is rule, A is nterm, ω is sequence of symbol.
  #
  # `@lookback_relation` is a two-stage hash whose
  # first key is state_id,
  # second key is rule_id,
  # value is array of goto.
  @lookback_relation = {}

  # `Follow(p, A) =s Read(p, A) ∪ ∪{Follow(p', B) | (p, A) includes (p', B)}`
  #
  # `@follow_sets` is a hash whose
  # key is goto,
  # value is bitmap of term.
  @follow_sets = {}

  # `LA(q, A -> ω) = ∪{Follow(p, A) | (q, A -> ω) lookback (p, A)`
  #
  # `@la` is a two-stage hash whose
  # first key is state_id,
  # second key is rule_id,
  # value is bitmap of term.
  @la = {}
end

Instance Attribute Details

#includes_relation ⇒ Object (readonly)

: Hash[State::Action::Goto, Array[State::Action::Goto]]



43
44
45
 
# File 'lib/lrama/states.rb', line 43

def includes_relation
  @includes_relation
end

#lookback_relation ⇒ Object (readonly)

: Hash[state_id, Hash[rule_id, Array[State::Action::Goto]]]



44
45
46
 
# File 'lib/lrama/states.rb', line 44

def lookback_relation
  @lookback_relation
end

#reads_relation ⇒ Object (readonly)

: Hash[State::Action::Goto, Array[State::Action::Goto]]



42
43
44
 
# File 'lib/lrama/states.rb', line 42

def reads_relation
  @reads_relation
end

#states ⇒ Object (readonly)

: Array



41
42
43
 
# File 'lib/lrama/states.rb', line 41

def states
  @states
end

Instance Method Details

#compute ⇒ Object 



111
112
113
114
115
116
117
118
119
120
121
 
# File 'lib/lrama/states.rb', line 111

def compute
  report_duration(:compute_lr0_states) { compute_lr0_states }

  # Look Ahead Sets
  report_duration(:compute_look_ahead_sets) { compute_look_ahead_sets }

  # Conflicts
  report_duration(:compute_conflicts) { compute_conflicts(:lalr) }

  report_duration(:compute_default_reduction) { compute_default_reduction }
end

#compute_ielr ⇒ Object 



124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
 
# File 'lib/lrama/states.rb', line 124

def compute_ielr
  # Preparation
  report_duration(:clear_conflicts) { clear_conflicts }
  # Phase 1
  report_duration(:compute_predecessors) { compute_predecessors }
  report_duration(:compute_follow_kernel_items) { compute_follow_kernel_items }
  report_duration(:compute_always_follows) { compute_always_follows }
  report_duration(:compute_goto_follows) { compute_goto_follows }
  # Phase 2
  report_duration(:compute_inadequacy_annotations) { compute_inadequacy_annotations }
  # Phase 3
  report_duration(:split_states) { split_states }
  # Phase 4
  report_duration(:clear_look_ahead_sets) { clear_look_ahead_sets }
  report_duration(:compute_look_ahead_sets) { compute_look_ahead_sets }
  # Phase 5
  report_duration(:compute_conflicts) { compute_conflicts(:ielr) }
  report_duration(:compute_default_reduction) { compute_default_reduction }
end

#compute_la_sources_for_conflicted_states ⇒ Object 



194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
 
# File 'lib/lrama/states.rb', line 194

def compute_la_sources_for_conflicted_states
  reflexive = {}
  @states.each do |state|
    state.nterm_transitions.each do |goto|
      reflexive[goto] = [goto]
    end
  end

  # compute_read_sets
  read_sets = Digraph.new(nterm_transitions, @reads_relation, reflexive).compute
  # compute_follow_sets
  follow_sets = Digraph.new(nterm_transitions, @includes_relation, read_sets).compute

  @states.select(&:has_conflicts?).each do |state|
    lookback_relation_on_state = @lookback_relation[state.id]
    next unless lookback_relation_on_state
    rules.each do |rule|
      ary = lookback_relation_on_state[rule.id]
      next unless ary

      sources = {}

      ary.each do |goto|
        source = follow_sets[goto]

        next unless source

        source.each do |goto2|
          tokens = direct_read_sets[goto2]
          tokens.each do |token|
            sources[token] ||= []
            sources[token] |= [goto2]
          end
        end
      end

      state.set_look_ahead_sources(rule, sources)
    end
  end
end

#direct_read_sets ⇒ Object 



150
151
152
153
154
 
# File 'lib/lrama/states.rb', line 150

def direct_read_sets
  @_direct_read_sets ||= @direct_read_sets.transform_values do |v|
    bitmap_to_terms(v)
  end
end

#follow_sets ⇒ Object 



164
165
166
167
168
 
# File 'lib/lrama/states.rb', line 164

def follow_sets
  @_follow_sets ||= @follow_sets.transform_values do |v|
    bitmap_to_terms(v)
  end
end

#la ⇒ Object 



171
172
173
174
175
176
177
 
# File 'lib/lrama/states.rb', line 171

def la
  @_la ||= @la.transform_values do |second_hash|
    second_hash.transform_values do |v|
      bitmap_to_terms(v)
    end
  end
end

#read_sets ⇒ Object 



157
158
159
160
161
 
# File 'lib/lrama/states.rb', line 157

def read_sets
  @_read_sets ||= @read_sets.transform_values do |v|
    bitmap_to_terms(v)
  end
end

#rr_conflicts_count ⇒ Object 



185
186
187
 
# File 'lib/lrama/states.rb', line 185

def rr_conflicts_count
  @rr_conflicts_count ||= @states.flat_map(&:rr_conflicts).count
end

#sr_conflicts_count ⇒ Object 



180
181
182
 
# File 'lib/lrama/states.rb', line 180

def sr_conflicts_count
  @sr_conflicts_count ||= @states.flat_map(&:sr_conflicts).count
end

#states_count ⇒ Object 



145
146
147
 
# File 'lib/lrama/states.rb', line 145

def states_count
  @states.count
end

#validate!(logger) ⇒ Object 



190
191
192
 
# File 'lib/lrama/states.rb', line 190

def validate!(logger)
  validate_conflicts_within_threshold!(logger)
end