Class: Lrama::States

Inherits:
Object
  • Object
show all
Extended by:
Forwardable
Includes:
Report::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

Defined Under Namespace

Classes: Item

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Report::Duration

enable, enabled?, #report_duration

Constructor Details

#initialize(grammar, warning, trace_state: false) ⇒ States

Returns a new instance of States.



279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
 
# File 'lib/lrama/states.rb', line 279

def initialize(grammar, warning, trace_state: false)
  @grammar = grammar
  @warning = warning
  @trace_state = trace_state

  @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 [state.id, nterm.token_id],
  # 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 [state.id, nterm.token_id],
  # value is array of [state.id, nterm.token_id].
  @reads_relation = {}

  # `@read_sets` is a hash whose
  # key is [state.id, nterm.token_id],
  # 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 [state.id, nterm.token_id],
  # value is array of [state.id, nterm.token_id].
  @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 hash whose
  # key is [state.id, rule.id],
  # value is array of [state.id, nterm.token_id].
  @lookback_relation = {}

  # `@follow_sets` is a hash whose
  # key is [state.id, rule.id],
  # value is bitmap of term.
  @follow_sets = {}

  # `LA(q, A -> ω) = ∪{Follow(p, A) | (q, A -> ω) lookback (p, A)`
  #
  # `@la` is a hash whose
  # key is [state.id, rule.id],
  # value is bitmap of term.
  @la = {}
end

Instance Attribute Details

#includes_relation ⇒ Object (readonly)

Returns the value of attribute includes_relation.



277
278
279
 
# File 'lib/lrama/states.rb', line 277

def includes_relation
  @includes_relation
end

#lookback_relation ⇒ Object (readonly)

Returns the value of attribute lookback_relation.



277
278
279
 
# File 'lib/lrama/states.rb', line 277

def lookback_relation
  @lookback_relation
end

#reads_relation ⇒ Object (readonly)

Returns the value of attribute reads_relation.



277
278
279
 
# File 'lib/lrama/states.rb', line 277

def reads_relation
  @reads_relation
end

#states ⇒ Object (readonly)

Returns the value of attribute states.



277
278
279
 
# File 'lib/lrama/states.rb', line 277

def states
  @states
end

Instance Method Details

#compute ⇒ Object 



337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
 
# File 'lib/lrama/states.rb', line 337

def compute
  # Look Ahead Sets
  report_duration(:compute_lr0_states) { compute_lr0_states }
  report_duration(:compute_direct_read_sets) { compute_direct_read_sets }
  report_duration(:compute_reads_relation) { compute_reads_relation }
  report_duration(:compute_read_sets) { compute_read_sets }
  report_duration(:compute_includes_relation) { compute_includes_relation }
  report_duration(:compute_lookback_relation) { compute_lookback_relation }
  report_duration(:compute_follow_sets) { compute_follow_sets }
  report_duration(:compute_look_ahead_sets) { compute_look_ahead_sets }

  # Conflicts
  report_duration(:compute_conflicts) { compute_conflicts }

  report_duration(:compute_default_reduction) { compute_default_reduction }

  check_conflicts
end

#direct_read_sets ⇒ Object 



364
365
366
367
368
369
370
371
372
 
# File 'lib/lrama/states.rb', line 364

def direct_read_sets
  h = {}

  @direct_read_sets.each do |k, v|
    h[k] = bitmap_to_terms(v)
  end

  return h
end

#follow_sets ⇒ Object 



384
385
386
387
388
389
390
391
392
 
# File 'lib/lrama/states.rb', line 384

def follow_sets
  h = {}

  @follow_sets.each do |k, v|
    h[k] = bitmap_to_terms(v)
  end

  return h
end

#la ⇒ Object 



394
395
396
397
398
399
400
401
402
 
# File 'lib/lrama/states.rb', line 394

def la
  h = {}

  @la.each do |k, v|
    h[k] = bitmap_to_terms(v)
  end

  return h
end

#read_sets ⇒ Object 



374
375
376
377
378
379
380
381
382
 
# File 'lib/lrama/states.rb', line 374

def read_sets
  h = {}

  @read_sets.each do |k, v|
    h[k] = bitmap_to_terms(v)
  end

  return h
end

#reporter ⇒ Object 



356
357
358
 
# File 'lib/lrama/states.rb', line 356

def reporter
  StatesReporter.new(self)
end

#states_count ⇒ Object 



360
361
362
 
# File 'lib/lrama/states.rb', line 360

def states_count
  @states.count
end