Class: Lrama::States

Inherits:
Object
  • Object
show all
Extended by:
Forwardable
Includes:
Report::Duration
Defined in:
lib/lrama/states.rb,
lib/lrama/states/item.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.



19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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
 
# File 'lib/lrama/states.rb', line 19

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.



17
18
19
 
# File 'lib/lrama/states.rb', line 17

def includes_relation
  @includes_relation
end

#lookback_relation ⇒ Object (readonly)

Returns the value of attribute lookback_relation.



17
18
19
 
# File 'lib/lrama/states.rb', line 17

def lookback_relation
  @lookback_relation
end

#reads_relation ⇒ Object (readonly)

Returns the value of attribute reads_relation.



17
18
19
 
# File 'lib/lrama/states.rb', line 17

def reads_relation
  @reads_relation
end

#states ⇒ Object (readonly)

Returns the value of attribute states.



17
18
19
 
# File 'lib/lrama/states.rb', line 17

def states
  @states
end

Instance Method Details

#compute ⇒ Object 



77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
 
# File 'lib/lrama/states.rb', line 77

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 



104
105
106
107
108
 
# File 'lib/lrama/states.rb', line 104

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

#follow_sets ⇒ Object 



116
117
118
119
120
 
# File 'lib/lrama/states.rb', line 116

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

#la ⇒ Object 



122
123
124
125
126
 
# File 'lib/lrama/states.rb', line 122

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

#read_sets ⇒ Object 



110
111
112
113
114
 
# File 'lib/lrama/states.rb', line 110

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

#reporter ⇒ Object 



96
97
98
 
# File 'lib/lrama/states.rb', line 96

def reporter
  StatesReporter.new(self)
end

#states_count ⇒ Object 



100
101
102
 
# File 'lib/lrama/states.rb', line 100

def states_count
  @states.count
end